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

交通大学网络教育学院----数据结构------第三次作业------------------树和图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. 29、一个深度为 4 的完全二叉树，至少有多少个结点：A. 15 B. 7 C. 8 D. 1410、在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要（）条边。A. n-1 B. n+1 C. n/2 D. n11、有 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. 1117、...