第三单元树+图答案

1、第三单元课后练习题（参考答案）知识点范围：第6章树与二叉树、第7章图一、选择题（每小题1分，共25分）1树最适合用来表示 C 。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据2深度为5的二叉树至多有 C 个结点。A16 B 32 C 31 C 103对一个满二叉树，m个叶子，n个结点，深度为h，则 D 。An = h+m B h+m = 2n C m = h-1 D n = 2h-14任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A 。A不发生改变 B发生改变 C不能确定 D以上都不对5设一棵二叉树中，度为2的结点数为9，则该二叉树的叶

2、结点的数目为：AA10 B11 C12 D不确定6在下述论述中，正确的是 D 。只有一个结点的二叉树的度为0；二叉树的度为2；二叉树的左右子树可任意交换；深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。A B C D7设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是 A 。Am-n Bm-n-1 Cn+1 D不能确定8若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B 。A9 B11 C15 D不能确定9具有10个叶子结点的二叉树中有 B 个度为2的结点。A8 B9 C10 D1110在一个无

3、向图中，所有顶点的度数之和等于所有边数的 C 倍。A1/2 B1 C 2 D 411.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。A 2i+1B 2iC i/2D 2i-112某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为： C A3 B2 C4 D513已知一算术表达式的中缀形式为AB *CD/E，后缀形式为ABC *+DE/，其前缀形式为 D 。AA+B*C/DE BA+B*CD/E C +*ABC/DE D+A*BC/DE14有8个顶点的无向图最少有C条边。A5 B6 C7 D61

4、5有8个顶点的无向图最多有B条边。A14 B28 C56 D11216具有n 个结点的连通图至少有 A 条边。 A n-1 B n C n(n-1)/2 D 2n17无向图顶点V的度是依附于该顶点B的数目。A顶点 B 边 C 序号 D下标18任何一个无向连通图的最小生成树B。A只有一棵 B 一棵或多棵 C 一定有多棵 D 可有不存在19设某棵二叉树中有2000个结点，则该二叉树的最小高度为C。A 9B10C 11D 1220如图所示的4棵二叉树中，不是完全二叉树的是 C 。A. B. C. D. 21有8个结点的无向图最多有 B 条边。 A14 B. 28 C. 56 D. 11222.设某二

5、叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。A N0=N1+1B N0=Nl+N2C N0=N2+1D N0=2N1+l23设一组权值集合W=2，3，4，5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为D。A 20B 30C 40D 4524设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B ）个叶子结点。A 99B 100C 101D 10225设无向图G中有n个顶点，则该无向图的最小生成树上有（ B ）条边。A nB n-1C 2nD 2n-126. 有 n 个顶点的有向图有（ A ） 条边, 则此图为完全有向图 A

6、. n(n-1) B. n(n-1)/2 C. n*n/2 D. n27. 若有 n 个顶点的无向图有 （ B ）条边, 则此图为完全无向图。A. n(n-1)B. n(n-1)/2C. n*n/2D. n28. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为i/2，右孩子结点的编号为（ D ）。A nB n-iC i/2D 2i+129. 设哈夫曼树中共有n个结点，则该哈夫曼树中有（ A ）个度数为1的结点。A 0B1C 2D n/230. 完全二叉树中第5层上最少有1个结点，最多有（ D ）个结点。A 13B 14C 15D 1631.

7、 若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 （ C ）。A 60B 50C 69D 5932. 一棵有n个叶子结点的哈夫曼树共有（ C ）个结点。A n-1Bn+1C 2n-1D 2n+133. 设无向图G中有n个顶点，则该无向图的最小生成树上有（ B ）条边。A nB n-1C 2nD 2n-134. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。A 9B10C 11D 1235. 已知一算术表达式的中缀形式为AB *CD/E，后缀形式为ABC *+DE/，其前缀形式为 （ D ） 。 AA+B*C/DE BA+B*CD/E C +*

8、ABC/DE D+A*BC/DE二、填空题（每空1分，共30分）1在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0 n2+1 。2在有n个结点的二叉链表中，空链域的个数为 n+1 。3一棵有n个叶子结点的哈夫曼树共有_2n-1_个结点。4深度为5的二叉树至多有 31 个结点。5若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 69 。6设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_ n-1_。7某二叉树的前序遍历序列是abdgcefh，中序序列是dgbaechf，其后序序列为 gdbehfca 。8设一棵二叉树的前序序列为

9、ABC，则有5种不同的二叉树可以得到这种序列。9完全二叉树中第5层上最少有1个结点，最多有16个结点。10具有10个顶点的无向图，边的总数最多为45。11.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为 ABDECF ，中序遍历序列为 DBEAFC ，后序遍历序列为 DEBFCA12.设一棵完全二叉树有128个结点，则该完全二叉树的深度为 8 ，有 64 个叶子结点。13.下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild，*rchild;Btre

10、e;void createbitree(Btree bt)scanf(“%c”,&ch);if(ch=#) bt=0（或bt=NULL）;else bt=(bitree*)malloc(sizeof(bitree); bt-data=ch; createbitree(bt-lchild;createbitree(bt-rchild);14Prim 算法生成一个最小生成树每一步选择都要满足：边的总数不超过n-1， 当前选择的边的权值是候选边中最小的 ， 选中的边加入树中不产生回路 三项原则。15设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条

11、件是p-lchild=0&p-rchild=0(或p-lchild=NULL&p-rchild=NULL) 。16设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为CABD。17设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_ BDCA _。18.设哈夫曼树中共有n个结点，则该哈夫曼树中有_ 0 _个度数为1的结点。19.在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。20.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为 i/2 ，右孩子结点的编

12、号为_2i+1_。21.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为6。22.设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有0个结点只有非空右子树。三、判断题（每小题1分，共15分）1.二叉树中每个结点的两棵子树是有序的。 ( )2二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。（ ）3二叉树中每个结点有两棵非空子树或有两棵空子树。（ ）4二叉树的先序遍历序列中，任意一个结点均处在其

13、孩子结点的前面。（ ）5用一维数组存储二叉树时，总是以先序遍历顺序存储结点。（）6若已知一棵二叉树的先序遍历序列和后序遍历序列，则可以恢复该二叉树。（ ）7在哈夫曼树中，权值最小的结点离根结点最近。( )8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。（ ）9.具有12个结点的完全二叉树有5个度为2的结点。（ ）10若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（ ）11完全二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（ ）12二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（ ）13满二叉树一定是完

14、全二叉树，完全二叉树不一定是满二叉树。（ ）14设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）15设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）三、计算题(每题5分，共20分)1.已知二叉树的先序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树。答案： 2、下图所示的森林：(1) 将此森林转换为相应的二叉树；求树（a）的先根序列和后根序列； (2) 写出转换后的二叉树的先序、中序和后序遍历序列；答案：(1) 此森林转换为相应的二叉树如下：(2) 转换后二叉树的先序遍历序列为：ABCDEFGHIJK; 中序遍历序列

15、为：BDEFCAIJKHG后序遍历序列为：FEDCBKJIHGA3. 设无向图G（如下图所示），利用普里姆算法构造该图的最小生成树，写出最小生成树上边的集合并计算最小生成树各边上的权值之和。答案：边的集合为E=(1,5),(5,2),(5,3),(3,4)最小生成树各边上的权值之和W=104.已知一个无向图的顶点集V为：V=1,2,3,4,5,6,7; 边及边的权值集E为：E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; （1）画出带权图（2）用克鲁斯卡尔算法

16、构造得到最小生成树，画出最小生成树构造步骤示意图。答案：12345673581061542025101218123456731234567341234567345123456734581234567345810123456734581020(1) 带权图(2) 最小生成树构造步骤a(2)构造步骤b(2)构造步骤c(2)构造步骤d(2)构造步骤e(2)构造步骤f5.假设在树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合 为 (i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h)

17、,(a,c),请 用树形结构画出此树，并回答下面的问题。(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?(8)结点b和n的层次各是多少？(9)树的深度是多少？(10)以结点c为根的子树的深度是多少？(11)树的度数是多少？答案：树的结构如下图所示：(1)a是根结点(2)m,n,d,f,l,j,k是叶结点(3)c是g的双亲(4)a和c是g的祖先(5)j,k是g的孩子(6)i,m,n是e的子孙(7)d是e的兄弟(8)结点b是2,n的层次是5(9)树的度数是5(10)以结点c为根的子树的深度是3(11)树的度是36. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树7.假设用于通信的电文仅由8个字母ABCDEFGH组成，