数据结构第三次作业及答案

本文格式为Word版，下载可任意编辑——数据结构第三次作业及答案第三次作业树和图

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和CBAC.ABC和BCAD.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.46C.48D.47

7、具有4个顶点的无向完全图有（）条边。A.16

B.6C.12D.20

8、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。选择一项：A.1/2

B.1C.4D.2

9、一个深度为4的完全二叉树，至少有多少个结点：A.15B.7

C.8D.14

10、在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。

A.n-1B.n+1C.n/2D.n

11、有n个结点的二叉树的二叉链表存储结构中有()个空链域。A.2nB.n-1C.nD.n+1

12、已知图6所示的图，若从顶点A出发按深度优先探寻法进行遍历，则可能得到的遍历序列为：

A.A,E,D,F,C,BB.A,C,F,E,B,DC.A,B,E,C,D,FD.A,E,B,C,F,D

13、已知如图3示的哈夫曼树，那么电文CDAA的编码是：

A.11111100B.010110111

C.11011100D.110100

14、一个有n个顶点的无向图最多有（）条边。选择一项：A.n(n-1)

B.n(n-1)/2C.nD.2n

15、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（）选择一项：A.n-1

B.nC.n+1D.n+e

16、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为：选择一项：

A.10B.20C.41D.11

17、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（）选择一项：

A.n2B.(n-1)2C.n-1D.n

18、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）。选择一项：

A.求关键路径的方法

B.求最短路径的Dijkstm方法C.深度优先遍历算法D.宽度优先遍历算法

19、以下序列不是图5的拓扑有序序列的是：

选择一项：A.156234B.152364C.561234

D.125634

20、对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点的访问序列均一致选择一项：

A.不存在这样的二叉树B.0C.2