搜索
第三单元课后练习题（参考答案）知识点范围：第6章树与二叉树、第7章图一、选择题（每小题1分，共25分）1．树最适合用来表示C。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据2．深度为5的二叉树至多有C个结点。A．16B．32C．31C．103．对一个满二叉树，m个叶子，n个结点，深度为h，则D。A．n=h+mB．h+m=2nC．m=h-1D．n=2h-14．任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序A。A．不发生改变B．发生改变C．不能确定D．以上都不对5．设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为：AA．10B．11C．12D．不确定6．在下述论述中，正确的是D。①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④7．设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，森林F中第一棵树的结点的个数是A。A．m-nB．m-n-1C．n+1D．不能确定8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是B。A．9B．11C．15D．不能确定9．具有10个叶子结点的二叉树中有B个度为2的结点。A．8B．9C．10D．1110．在一个无向图中，所有顶点的度数之和等于所有边数的C倍。A．1/2B．1C．2D．411.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（B）。A．2i+1B．2iC．i/2D．2i-112．某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：CA．3B．2C．4D．513．已知一算术表达式的中缀形式为A＋B*C–D/E，后缀形式为ABC*+DE/–，其前缀形式为D。A．–A+B*C/DEB．–A+B*CD/EC–+*ABC/DED．–+A*BC/DE14．有8个顶点的无向图最少有C条边。A．5B．6C．7D．615．有8个顶点的无向图最多有B条边。A．14B．28C．56D．11216．具有n个结点的连通图至少有A条边。A．n-1B．nC．n(n-1)/2D．2n17．无向图顶点V的度是依附于该顶点B的数目。A．顶点B．边C．序号D．下标18．任何一个无向连通图的最小生成树B。A．只有一棵B．一棵或多棵C．一定有多棵D．可有不存在19．设某棵二叉树中有2000个结点，则该二叉树的最小高度为C。A．9B．10C．11D．1220．如图所示的4棵二叉树中，不是完全二叉树的是C。A.B.C.D.21．有8个结点的无向图最多有B条边。A．14B.28C.56D.11222.设某二叉树中度数为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.n(n-1)B.n(n-1)/2C.n*n/2D.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．0B．1C．2D．n/230.完全二叉树中第5层上最少有1个结点，最多有（D）个结点。A．13B．14C．15D．1631.若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为（C）。A．60B．50C．69D．5932.一棵有n个叶子结点的哈夫曼树共有（C）个结点。A．n-1B．n+1C．2n-1D．2n+133.设无向图G中有n个顶点，则该无向图的最小生成树上有（B）条边。A．nB．n-1C．2nD．2n-134.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。A．9B．10C．11D．1235.已知一算术表达式的中缀形式为A＋B*C–D/E，后缀形式为ABC*+DE/–，其前缀形式为（D）。A．–A+B*C/DEB．–A+B*CD/EC–+*ABC/DED．–+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．设一棵二叉树的前序序列为ABC，则有5种不同的二叉树可以得到这种序列。9．完全二叉树中第5层上最少有1个结点，最多有16个结点。10．具有10个顶点的无向图，边的总数最多为45。11.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA12.设一棵完全二叉树有128个结点，则该完全二叉树的深度为8，有64个叶子结点。13.下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild，*rchild;}Btree;voidcreatebitree(Btreebt){scanf(“%c”,&ch);if(ch=='#')bt=0（或bt=NULL）;else{bt=(bitree*)malloc(sizeof(bitree));bt-data=ch;createbitree(bt-lchild;createbitree(bt-rchild);}}14．Prim算法生成一个最小生成树每一步选择都要满足：边的总数不超过n-1，当前选择的边的权值是候选边中最小的，选中的边加入树中不产生回路三项原则。15．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是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，右孩子结点的编号为___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．二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。（√）5．用一维数组存储二叉树时，总是以先序遍历顺序存储结点。（×）6．若已知一棵二叉树的先序遍历序列和后序遍历序列，则可以恢复该二叉树。（×）7．在哈夫曼树中，权值最小的结点离根结点最近。(×)8．.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（×）9．.具有12个结点的完全二叉树有5个度为2的结点。（√）10．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（√）11．完全二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（√）12．二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×）13．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（√）14．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（×）15．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（√）三、计算题(每题5分，共20分)1.已知二叉树的先序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树。答案：2、下图所示的森林：(1)将此森林转换为相应的二叉树；求树（a）的先根序列和后根序列；(2)写出转换后的二叉树的先序、中序和后序遍历序列；ABCDEFGHIJK(a)(b)答案：(1)此森林转换为相应的二叉树如下：AGBCDEFHIJK(2)转换后二叉树的先序遍历序列为：ABCDEFGHIJK;中序遍历序列为：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）用克鲁斯卡尔算法构造得到最小生成树，画出最小生成树构造步骤示意图。答案：5.假设在树中，如果结点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),(a,c)｝,请用树形结构画出此树，并回答下面的问题。(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?(8)结点b和n的层次各是多少？(9)树的深度是多少？(10)以结点c为根的子树的深度是多少？(11)树的度数是多少？答案：树的结构如下图所示：12345673581061542025101218123456731234567341234567345123456734581234567345810123456734581020(1)带权图(2)最小生成树构造步骤a(2)构造步骤b(2)构造步骤c(2)构造步骤d(2)构造步骤e(2)构造步骤f(1)a是根结点(2)m,n,d,f,l,j,k是叶结点(3)c是g的双亲(4)a