第三次作业------------------树和图
1、下列说法中正确的是
A. 二叉树的线索化就是对二叉链表中的n个空链域进行线索化； B. 二叉树一定是度为2的树； C. 一个度为2的树一定为二叉树；
D. 任何一棵树都可以按照孩子兄弟法转化为一棵二叉树，而且这个二叉树的根结点的右孩子一定不存在。
2、四组编码中，哪一组是前缀码 A. {0,1,00,11}
B. {0,10,110,111} C. {00,01,001,0001} D. {0,01,10,11}
3、对于图1示的二叉树，先根序列和后根序列分别为：
A. ACB和CBA
B. ABC和CBA C. ABC和BCA D. ACB和 BCA
4、n个结点的线索二叉树中的线索数目为： A. (n-1)个
B. （n+1）个 C. （n+2）个 D. n个
5、哈夫曼树的带权路径长度是指： 选择一项：
A. 所有结点的权值之和
B. 除根结点之外所有结点权值之和 C. 所有叶子结点带权路径长度之和
D. 带权结点的值
6、图2示的二叉树的带权路径长度为：
A. 36
B. 46 C. 48 D. 47
7、具有4个顶点的无向完全图有（）条边。 A. 16
B. 6 C. 12 D. 20
8、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。 选择一项： A. 1/2
B. 1 C. 4 D. 2
9、一个深度为4的完全二叉树，至少有多少个结点： A. 15 B. 7
C. 8 D. 14
10、在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。
A. n-1 B. n+1 C. n/2 D. n
11、有n个结点的二叉树的二叉链表存储结构中有( )个空链域。 A. 2n B. n-1 C. n D. n+1
12、已知图6所示的图，若从顶点A出发按深度优先搜索法进行遍历，则可能得到的遍历序列为：
A. A,E,D,F,C,B B. A,C,F,E,B,D C. A,B,E,C,D,F D. A,E,B,C,F,D
13、已知如图3示的哈夫曼树，那么电文CDAA的编码是：
A. 11111100 B. 010110111
C. 11011100 D. 110100
14、一个有n个顶点的无向图最多有（）条边。 选择一项： A. n(n-1)
B. n(n-1)/2 C. n D. 2n
15、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（） 选择一项： A. n-1
B. n C. n+1 D. n+e
16、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为： 选择一项：
A. 10 B. 20 C. 41 D. 11
17、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（） 选择一项：
A. n2 B. (n-1)2 C. n-1 D. n
18、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）。 选择一项：
A. 求关键路径的方法
B. 求最短路径的Dijkstm方法 C. 深度优先遍历算法 D. 宽度优先遍历算法
19、下列序列不是图5的拓扑有序序列的是：
选择一项： A. 1 5 6 2 3 4 B. 1 5 2 3 6 4 C. 5 6 1 2 3 4
D. 1 2 5 6 3 4
20、对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点的访问序列均相同 选择一项：
A. 不存在这样的二叉树 B. 0 C. 2
D. 1
21、具有6个顶点的无向图至少有（）条边才可能是一个连通图。 选择一项： A. 5 B. 8 C. 7 D. 6
数据结构第三次作业及答案--树和图
