A．mk-1 B．mk-1 C．mh-1 D．mh-114. 利用二叉链表存储树，则根结点的右指针是（ C ）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
15．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。
A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
16．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）。
A． 250 B． 500 C．254 D．505 E．以上答案都不对
17．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）。
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
18．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
19．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。
A．acbed B．decab C．deabc D．cedba 20. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( B )编号的。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序
21．对于前序遍历与中序遍历结果相同的二叉树为（ B ）。
A．一般二叉树 B．所有结点只有右子树的二叉树 C．根结点无左孩子的二叉树
D．所有结点只有左子数的二叉树
22. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：A．不确定 B. 0 C. 1 D. 2 23. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( B )。
A. 0 B. 1 C. 2 D. 不确定 24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) 。
A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 25. 引入二叉线索树的目的是（ A ）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中
。( D )
方便的进行插入与删除
C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 26．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ C ）。
A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树
27．n个结点的线索二叉树上含有的线索数为（ C ）。
A．2n B．n－l C．n＋l D．n 28．由3 个结点可以构造出多少种不同的二叉树？（ D ）。
A．2 B．3 C．4 D．5 29．下述编码中哪一个不是前缀编码（ B ）。
A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）
30．下面几个符号串编码集合中，不是前缀编码的是（ B ）。
A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 二、判断题
1. 完全二叉树一定存在度为1的结点。（ W ） 2. 对于有n个结点的二叉树，其高度为log2n。（ W ） 3．深度为K的二叉树中结点总数≤2k-1。（ A ）
4. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。（ W ）
5．用树的前序遍历和中序遍历可以导出树的后序遍历。（ W ） 6．由一棵二叉树的前序序列和后序序列可以唯一确定它。（ W ） 7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ A ） 8. 二叉树只能用二叉链表表示。（ W ）
9. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+110. 给定一棵树，可以找到唯一的一棵二叉树与之对应。（ A ）Chap7
一、选择题
1．设无向图的顶点个数为n，则该图最多有（ B ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
2．一个n个顶点的连通无向图，其边的个数至少为（ A ）。
A．n-1 B．n C．n+1 D．nlogn；
3．要连通具有n个顶点的有向图，至少需要（ B ）条边。
A．n-l B．n C．n+l D．2n 4．n个结点的完全有向图含有边的数目（ D ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
5．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）
个连通分量。
A．0 B．1 C．n-1 D．n
6．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。
A．1/2 B．2 C．1 D．4 7．下列哪一种图的邻接矩阵是对称矩阵？（ B ）。
A．有向图 B．无向图 C．AOV网 D．AOE网
8．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
9. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ C ），下面步骤重复n-1次: a：（ A ）；b：（ B ）；最后：（ A ）。
（1）．A．VT，ET为空 B．VT为所有顶点，ET为空
C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边
（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大
（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET
C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET
（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树
C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解
10．一个有向无环图的拓扑排序序列（ B ）是唯一的。
A．一定 B．不一定
11. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。
A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径12. 关键路径是事件结点网络中（ A ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路
径
C．最长回路 D．最短回路 13. 下面关于求关键路径的说法不正确的是（ C ）。 A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D．关键活动一定位于关键路径上
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（ A ） 2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ W ）
3. 有e条边的无向图，在邻接表中有e个结点。（ W ） 4．强连通图的各顶点间均可达。（ A ）
5．强连通分量是无向图的极大强连通子图。（ W ） 6．连通分量指的是有向图中的极大连通子图。（ W ） 7. 无向图的邻接矩阵可用一维数组存储。（ A ）
8．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ W ）
9．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接
矩阵中非零元素之和的一半。（ A ） 10. 有向图的邻接矩阵是对称的。（ W ）
11．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ W ）
12. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ W ） 13. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（ A ） 14．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ W ）
15．需要借助于一个队列来实现DFS算法。（ W ） 16. 广度遍历生成树描述了从起点到各顶点的最短路径。（ W ） 17．任何无向图都存在生成树。（ W ）
18. 不同的求最小生成树的方法最后得到的生成树是相同的.（ W ）
19．带权无向图的最小生成树必是唯一的。（ W ）
20. 最小生成树问题是构造连通网的最小代价生成树。（ A ） 21．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（ W ） 22．拓扑排序算法仅能适用于有向无环图。（ W ） 23. 无环有向图才能进行拓扑排序。（ W ） 24．AOV网的含义是以边表示活动的网。（ W ）
25．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。( W )
26. 关键路径是AOE网中从源点到终点的最长路径。（ A ） 27. 在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（ W ）
28．在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（ A ）
