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

1、-第三次作业下列说法中正确的是二叉树的线索化就是对二叉链表中的 n个空链域进行线索化; 二叉树一定是度为 2的树； 一个度为2的树一定为二叉树；树和图1、A.海交通大学网络教育学院-数据结构B.C.D. 任何一棵树都可以按照孩子兄弟法转化为一棵二叉树，而且这个二叉树的根结点的右孩 子一定不存在。# 2、四组编码中，哪一组是前缀码A. 0,1,00,11B. 0,10,110,111 閉C. 00,01,001,0001D. 0,01,10,113、对于图1示的二叉树，先根序列和后根序列分别为:B. ABCC. ABCD. ACBCBA第BCABCA 4、n个结点的线索二叉树中的线索数目为:A.

2、 (n-1)个B. ( n+1)个 #C. (n+2 )个D. n个 5、哈夫曼树的带权路径长度是指: 选择一项：A. 所有结点的权值之和B. 除根结点之外所有结点权值之和C. 所有叶子结点带权路径长度之和#D. 带权结点的值6、图2示的二叉树的带权路径长度为:25B. 46C. 48图2A. 36D. 47 7、具有4个顶点的无向完全图有（）条边。A. 16B. 6 #C. 12D. 20 8、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 选择一项：A. 1/2B. 1 #C. 4D. 2 9、一个深度为4的完全二叉树，至少有多少个结点:A. 15B. 7C. 8 #D

3、. 1410、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A. n-1 #B. n+1C. n/2D. n11、有n个结点的二叉树的二叉链表存储结构中有（）个空链域。A. 2nB. n-1C. nD. n+1 #12、已知图6所示的图，若从顶点 A出发按深度优先搜索法进行遍历，则可能得到的遍历 序列为：图6A. A,E,D,F,C,B #B. A,C,F,E,B,DC. A,B,E,C,D,FD. A,E,B,C,F,D13、已知如图3示的哈夫曼树，那么电文 CDAA的编码是:A. 11111100B. 010110111C. 11011100#D. 11010014、一个有

4、n个顶点的无向图最多有（）条边。 选择一项：A. n(n-1)B. n(n-1)/2#C. nD. 2n 15、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（） 选择一项：A. n-1B. n #C. n+1D. n+e16、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为：选择一项：A. 10 就B. 20C. 41D. 1117、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小（） 选择一项：A. n2 #B. （n-1）2C. n-1D. n,还可以利用（）。18

5、、判定一个有向图是否存在回路除了可以利用拓扑排序方法外 选择一项：A. 求关键路径的方法#B. 求最短路径的 Dijkstm方法C. 深度优先遍历算法D. 宽度优先遍历算法选择一项:A. 1 5 6 2 3 4B. 1 5 2 3 6 4C. 5 6 1 2 3 4D. 1 2 5 6 3 4）个结点的非空二叉树，采用任何一种遍历方式，其结点的访问序列均相同20、对含有（ 选择一项：A. 不存在这样的二叉树B. 0C. 2D. 1谱21、具有6个顶点的无向图至少有（）条边才可能是一个连通图。 选择一项：A. 5我B. 8C. 7D. 622、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（

6、）。选择一项：A.后序遍历B.C.D.先序遍历#按层遍历 中序遍历23、一棵深度为5的满二叉树，应该有多少个结点（）选择一项：A. 32B. 31 耆C. 17D. 1624、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。 选择一项：按层遍历#先序遍历中序遍历后序遍历A.B.C.D.25、没有度为1的结点的二叉树，被称之为严格二叉树。下列不是严格二叉树的是: 选择一项：满二叉树哈夫曼树所有非终端结点都有非空的左右子树的二叉树完全二叉树#A.B.C.D.26、对于一个具有 n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的结 点总数是（）选择一项：A. e/2B. n+eC.

7、 eD. 2e *n，那么二叉树27、一个所有非终端结点都有非空的左右子树的二叉树，叶子结点的个数为 上的结点总数为（）选择一项：A. 2n-1B. 2n+1C. 2nD. 2n-2）组中选取。应当从（A. B. C. D. (1，(3，(4，(1，4），4），5），2），(3，(3，(1，(2，4），（ 3，5），（ 4，3），（ 3，3），（ 3，5),( 2, 4) /5),( 1 , 4) 5) 5) 在一个有向图中 选择一项：29、，所有顶点的度数之和等于所有边数的（）倍。28、用Prim算法求下列连通的带权图（图 4）的最小代价生成树，在算法执行的某刻，已 选取的顶点集合 U= 1 , 2, 3，边的集合