四、应用题
2.数据元素之间的关系在计算机中有几种表示方法？
各有什么特点？
8．数据的逻辑结构有哪些基本类型？
12．数据的存储结构由哪四种基本的存储方法实现？
第2章线性表
一选择题
1．下述哪一条是顺序存储结构的优点？
（）
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？
（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
A．表元素B．字符C．数据元素D．数据项E．信息项
8.静态链表中指针表示的是（）.
A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址
9.链表不具有的特点是（）
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
10.下面的叙述不正确的是（）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
13.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1<=i<=n+1）。
A.O（0）B.O
（1）C.O（n）D.O（n2）
14.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O（n）O（n）B.O（n）O
（1）C.O
（1）O（n）D.O
（1）O
（1）
15．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）
A．O（i）B．O
（1）C．O（n）D．O（i-1）
二、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
3．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
5．在单链表中设置头结点的作用是________。
10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
12.对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。
15.带头结点的双循环链表L中只有一个元素结点的条件是：
________
16.在单链表L中，指针p所指结点有后继结点的条件是：
__
三应用题
1．线性表有两种存储结构：
一是顺序表，二是链表。
试问：
（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。
在此情况下，应选用哪种存储结构？
为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？
为什么？
3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？
为什么？
4．线性结构包括______、______、_______和_______。
线性表的存储结构分成______和______。
6.说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。
第三章栈和队列
一选择题
1.对于栈操作数据的原则是（）。
A.先进先出B.后进先出C.后进后出D.不分顺序
16.栈在（）中应用。
A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ
17.一个递归算法必须包括（）。
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分
22.用链接方式存储的队列，在进行删除运算时（）。
A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改
23.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（）。
A．仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
24.递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。
A．队列B．多维数组C．栈D.线性表
34.栈和队列都是（）
A．顺序存储的线性结构B.链式存储的非线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
应用题
1.名词解释：
栈、队列？
3.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
第4章数组和广义表
一、选择题
1.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
供选择的答案：
A.198B.195C.197
3.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n（n+1）/2]中，对上述任一元素aij（1≤i，j≤n，且i≤j）在B中的位置为（）。
A.i（i-l）/2+jB.j（j-l）/2+iC.j（j-l）/2+i-1D.i（i-l）/2+j-1
6.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.33
7.数组A[0..4,-1..-3,5..7]中含有元素的个数（）。
A.55B.45C.36D.16
8.广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（）。
Head（Tail（Head（Tail（Tail（A）））））
A.（g）B.（d）C.cD.d
9.已知广义表:
A=（a,b）,B=（A,A）,C=（a,（b,A）,B）,求下列运算的结果:
tail（head（tail（C）））=（）。
A.（a）B.AC.aD.（b）E.bF.（A）
10.广义表运算式Tail（（（a,b）,（c,d）））的操作结果是（）。
A.（c,d）B.c,dC.（（c,d））D.d
三、填空题
2.已知广义表A=（9,7,（8,10,（99））,12），试用求表头和表尾的操作Head（）和Tail（）将原子元素99从A中取出来。
4.广义表（a,（a,b）,d,e,（（i,j）,k））的长度是
（1），深度是
（2）_。
5.已知广义表LS=（a，（b，c，d），e）,运用head和tail函数取出LS中原子b的运算是______。
6.广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是:
__。
四应用题
1．数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。
求：
（1）存放该数组所需多少单元？
（2）存放数组第4列所有元素至少需多少单元？
（3）数组按行存放时，元素A[7,4]的起始地址是多少？
（4）数组按列存放时，元素A[4,7]的起始地址是多少？
4.什么是广义表？
请简述广义表和线性表的主要区别。
第五章树形结构
一、选择题
5.在下述结论中，正确的是（）
①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③B．②③④C．②④D．①④
6.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）
A．m-nB．m-n-1C．n+1D．条件不足，无法确定
7.树是结点的有限集合，它（
（1））根结点，记为T。
其余结点分成为m（m>0）个（
（2））的集合T1，T2，…，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
一个结点的子结点个数称为该结点的（（3））。
二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它（（4））根结点。
可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。
令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（（5））。
供选择的答案：
（1）（4）A.有0个或1个B.有0个或多个C.有且只有一个D.有1个或1个以上
（2）A.互不相交B.允许相交C.允许叶结点相交D.允许树枝结点相交
（3）A.权B.维数C.次数D.序
（5）A.丰满树B.查找树C.平衡树D.完全树
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9B．11C．15D．不确定
10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A．M1B．M1+M2C．M3D．M2+M3
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A．250B．500C．254D．505E．以上答案都不对
16.有关二叉树下列说法正确的是（）
A．二叉树的度为2B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2
17．二叉树的第I层上最多含有结点数为（）
A．2IB．2I-1-1C．2I-1D．2I-1
18.一个具有1025个结点的二叉树的高h为（）
A．11B．10C．11至1025之间D．10至1024之间
21.一棵具有n个结点的完全二叉树的树高度（深度）是（）
A．logn+1B．logn+1C．lognD．logn-1
22．深度为h的满m叉树的第k层有（）个结点。
（1=A．mk-1B．mk-1C．mh-1D．mh-1
23．在一棵高度为k的满二叉树中，结点总数为（）
A．2k-1B．2kC．2k-1D．log2k+1
24．高度为K的二叉树最大的结点数为（）。
A．2kB．2k-1C．2k-1D．2k-1-1
27.利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子C．空D．非空
28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
29．树的后根遍历序列等同于该树对应的二叉树的（）.
A.先序序列B.中序序列C.后序序列
31．在下列存储形式中，哪一个不是树的存储形式？
（）】
A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法
33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
A．CBEFDAB．FEDCBAC．CBEDFAD．不定
35.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：
A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对
37．二叉树的先序遍历和中序遍历如下：
先序遍历：
EFHIGJK；中序遍历:
HFIEJKG。
该二叉树根的右子树的根是：
A、EB、F C、G D、H
45．在完全二叉树中，若一个结点是叶结点，则它没（）。
A．左子结点B．右子结点 C．左子结点和右子结点D．左子结点，右子结点和兄弟结点
46．在下列情况中，可称为二叉树的是（）
A．每个结点至多有两棵子树的树B.哈夫曼树C．每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树E．以上答案都不对
三、填空题
1．二叉树由_
（1）__，__
（2）_，_（3）__三个基本单元组成。
6．具有256个结点的完全二叉树的深度为______。
9．深度为H的完全二叉树至少有_
（1）__个结点；至多有_
（2）__个结点；H和结点总数N之间的关系是（3）__。
13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。
14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______
17．高度为K的完全二叉树至少有______个叶子结点。
18．高度为8的完全二叉树至少有______个叶子结点。
19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。
30．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。
四、应用题
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
2．树和二叉树之间有什么样的区别与联系？
4．设某二叉树的前序遍历序列为:
ABCDEFGGI，中序遍历序列为:
BCAEDGHFI：
（1）试画出该二叉树；
（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
（4）已知一棵二叉树的前序遍历结果是：
ABCDEFGHIJ,中序遍历的结果是：
BCEDAGHJIF,试画出这棵二叉树。
五、编程题
1、求二叉树的叶子结点数。
（答案见课本第5.3.2节二叉树遍历与递归距离）
2、判断二叉树是否所有结点存放的都是数字字符。
（答案见课本第5.3.2节二叉树遍历与递归距离）
第六章图
一、选择题
2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1B．n（n-1）/2C．n（n+1）/2D．0E．n2
3．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1B．nC．n+1D．nlogn；
4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-lB．nC．n+lD．2n
5．n个结点的完全有向图含有边的数目（D ）。
A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）
6．一个有n个结点的图，最少有（B）个连通分量，最多有（）个连通分量。
A．0B．1C．n-1D．n
7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2B．2C．1D．4
11．下列哪一种图的邻接矩阵是对称矩阵？
（）
A．有向图B．无向图C．AOV网D．AOE网
13.下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：
深度遍历和广度遍历D．图的深度遍历是一个递归过程
14．无向图G=（V,E）,其中：
V={a,b,c,d,e,f},E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b
20．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（A）。
A．存在B．不存在
21．一个有向无环图的拓扑排序序列（）是唯一的。
A．一定B．不一定
22.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。
A．G中有弧B．G中有一条从Vi到Vj的路径
C．G中没有弧D．G中有一条从Vj到Vi的路径
24.关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长回路D．最短回路
25.下面关于求关键路径的说法不正确的是（）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
26．下列关于AOE网的叙述中，不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
1.判断一个无向图是一棵树的条件是_n个顶点，n-1条边的无向连通图_____。
2．有向图G的强连通分量是指___极大强连通子图___。
3．一个连通图的___生成树___是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为__45____。
5．若用n表示图中顶点数目，则有____n*（n-1）/2___条边的无向图成为完全图。
6.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1<=i<=n〉，则e=_（d1
+d2+……+dn）/2_____
7．G是一个非连通无向图，共有28条边，则该图至少有__9__个顶点。
12．如果含n个顶点的图形形成一个环，则它有____n__棵生成树。
15．有N个顶点的有向图，至少需要量____N__条弧才能保证是连通的。
16．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的___度___；对于有向图来说等于该顶点的_出度_____。
17.在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第I列非零元的个数_____。
19.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为__n____，邻接表的边结点个数为___2*e___。
20．构造连通网最小生成树的两个典型算法是_prim和kruskal算法_____。
21．求图的最小生成树有两种算法，_kruskal_____算法适合于求稀疏图的最小生成树。
22.Prim（普里姆）算法适用于求__稠密____的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求___稀疏___的网的最小生成树。
四、应用题
3题图
3．给出图G：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。
（2）深度：
12534768910广度：
12534678910
4．考虑右图：
（1）从顶点A出发，求它的深度优先生成树
（2）从顶点E出发，求它的广度优先生成树
（3）根据普利姆（Prim）算法，求它的最小生成树
（1）ABGFDEC
（2）EACFBDG
5．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
27题图
6．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。
第6图
7．设无向网G如上：
（1）．设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G的邻接表结构:
（2）．写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所的到的顶点序列：
按Prim算法求出网G的一棵最小生成树。
（2）深度：
abcdehf广度：
abfcdeh
升级会员 