上交大网络教育学院数据结构第三次作业.doc

上海交通大学网络教育学院-———数据结构—-——--第三次作业—-——--————-—-———--树和图
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
22、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。
选择一项：
A. 后序遍历
B。 先序遍历
C。 按层遍历
D。 中序遍历
23、一棵深度为5的满二叉树，应该有多少个结点（ ）
选择一项：
A。 32
B. 31
C。 17
D. 16
24、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（)。
选择一项：
A. 按层遍历
B. 先序遍历
C。 中序遍历
D. 后序遍历
25、没有度为1的结点的二叉树,被称之为严格二叉树.下列不是严格二叉树的是:
选择一项：
A。 满二叉树
B。 哈夫曼树
C。 所有非终端结点都有非空的左右子树的二叉树
D. 完全二叉树
26、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是( ）
选择一项:
A。 e/2
B. n+e
C。 e
D。 2e
27、一个所有非终端结点都有非空的左右子树的二叉树，叶子结点的个数为n,那么二叉树上的结点总数为（ ）
选择一项:
A. 2n-1
B. 2n+1
C. 2n
D. 2n—2
28、用Prim算法求下列连通的带权图（图4）的最小代价生成树,在算法执行的某刻，已选取的顶点集合U＝｛1，2，3｝，边的集合TE＝{（1，2）,（2，3）}，要选取下一条权值最小的边,应当从(　　）组中选取。

选择一项:
A. {（1,4)，（3，4),（3,5）,（2,4）}
B. ｛（3，4）,（3，5)，(4，5），（1,4)｝
C。 {（4，5），（1，3），(3，5)}
D。 ｛（1,2），（2,3),(3，5）｝
29、在一个有向图中，所有顶点的度数之和等于所有边数的(）倍。
选择一项:
A。 1
B。 2
C. 1/2
D。 4
30、在二叉树的第i层上至多有（ )个结点
选择一项：
A。 2i—1
B. i+2
C。 2i
D。 2i—2