数据结构书面作业练习题6-9

1习题六树和二叉树6.1单项选择题1.如图8.7所示的4棵二叉树，_C___不是完全二叉树。2.如图8.8所示的4棵二叉树，__B_是平衡二叉树。3.在线索化二叉树中，t所指结点没有左子树的充要条件是B__。A.t—＞left=NULLB.t—＞ltag=1C.t—＞ltag=1且t—＞left=NULLD.以上都不对4.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B__。A.正确B.错误（A）（B）（C）（D）图8.74棵二叉树（A）（B）（C）（D）图8.84棵二叉树25.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。A.正确B.错误6.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。A.正确B.错误7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。A.2hB.2h-1C.2h+1D.h+1a8.如图8.9所示二叉树的中序遍历序列___B_。A.abcdgefB.dfebagcC.dbaefcgD.defbagc9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。A.acbedB.decabC.deabcD.cedba10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是B。A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙图8.9一棵二叉树efabcgd311.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。BA．15B．16C．17D．4712.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是D____。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca13.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__B__。A.正确B.错误14.按照二叉树的定义，具有3个结点的二叉树有__C__种。A.3B.4C.5D.615.一棵二叉树如图8.10所示，其中序遍历的序列为__B__。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh16.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论___A_是正确的。图8.10一棵二叉树ghabcedf4A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对17.深度为5的二叉树至多有___C_个结点。A.16B.32C.31D.1018.在一非空二叉树的中序遍历序列中，根结点的右边_A___。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点19.树最适合用来表示__C__。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据20.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A___。A.不发生改变B.发生改变C.不能确定D.以上都不对21.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用__C__存储结构。A.二叉链表B.广义表存储结构C.三叉链表D.顺序存储结构22.对一个满二叉树，m个树叶，n个结点，深度为h，则__D__。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-123.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_C___。A.uwvtsB.vwutsC.wuvtsD.wutsv24.具有五层结点的二叉平衡树至少有___B_个结点。F(n)=F(n-1)+F(n-2)+1,1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量A.10B.12C.15D.1725.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__C__。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙6.2填空题（将正确的答案填在相应的空中）51.有一棵树如图8.12所示，回答下面的问题：⑴这棵树的根结点是___K1_；⑵这棵树的叶子结点是___K2,K5,K7,K4_；⑶结点k3的度是_2___；⑷这棵树的度是___3_；⑸这棵树的深度是_4___；⑹结点k3的子女是__K5,K6__；⑺结点k3的父结点是__K1__；2.指出树和二叉树的三个主要差别_树的结点个数至少为1，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分。3.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_利用二叉树的已有算法解决树的有关问题___。4.一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图8.13所示，则该二叉树的链接表示形式为____。图8.12一棵树k5k1k2k4k7k6k3123456789101112131415161718192021eafgcjlhb图8.13一棵二叉树的顺序存储数组t65.深度为k的完全二叉树至少有__2k-1__个结点。至多有__2k-1__个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_2k-2+1___。6.在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0=_n2+1___。7.一棵二叉树的第i（i≥1）层最多有_2i-1___个结点；一棵有n（n0）个结点的满二叉树共有__2[log2n+1]-1__个叶子和___2[log2n+1]-1_个非终端结点。8.结点最少的树为__只有一个结点的树__，结点最少的二叉树为_空二叉树___。9.现有按中序遍历二叉树的结果为abc，问有__5__种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。10.根据二叉树的定义，具有三个结点的二叉树有___5_种不同的形态，它们分别是__参照楼上__。11.由如图8.17所示的二叉树，回答以下问题：⑴其中序遍历序列为_dgbaechif__；⑵其前序遍历序列为___abdgcefhi_；⑶其后序遍历序列为_gdbeihfca___；⑷该二叉树的中序线索二叉树为____；7⑸该二叉树的后序线索二叉树为____；⑹该二叉树对应的森林是____。12.已知一棵树如图8.20所示，转化为一棵二叉树，表示为____。图8.20一棵树gcedfab图8.17一棵二叉树ghabcedfi813.以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为____，其带权路径长度为__165__。6.3算法设计题:1．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。2.一棵度为2的树与一棵二叉树有何区别?3.一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?4.证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系:n0=(k-1)n1+15.请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。ADGGCEFHB96.画出和下列已知序列对应的树T：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBFG。7.假设用于通讯的电文仅有八个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。8.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。9.编写按层次顺序（同一层自左至右）遍历二叉树的算法。习题七图7.1单项选择题1.在一个图中，所有顶点的度数之和等于所有边数的_A___倍。A.1/2B.1C.2D.42.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。A.1/2B.1C.2D.43.一个有n个顶点的无向图最多有__C__条边。A.nB.n(n-1)C.n(n-1)/2D.2n4.具有4个顶点的无向完全图有__A__条边。A.6B.12C.16D.205.具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图。A.5B.6C.7D.86.在一个具有n个顶点的无向图中，要连通全部顶点至少需要___C_条边。A.nB.n+1C.n-1D.n/27.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是__D__。A.nB.(n-1)2C.n-1D.n28.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_10①A___；所有邻接表中的接点总数是_②C___。①A.nB.n+1C.n-1D.n+e②A.e/2B.eC.2eD.n+e9.已知一个图如图9.5所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__D①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。①A.a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b10.已知一有向图的邻接表存储结构如图9.6所示。⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是__C__。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是__B__。A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v211.采用邻接表存储的图的深度优先遍历算法类似于二叉树的__A__。A.先序遍历B.中序遍历C.后序遍历D.按层遍历图9.5一个无向图abcedf12^34^5324524图9.6一个有向图的邻接表存储结构^1112.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_D___。A.先序遍历B.中序遍历C.后序遍历D.按层遍历13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用___D_。A.求关键路径的方法B.求最短路径的Dijkstra方法C.宽度优先遍历算法D.深度优先遍历算法7.2填空题（将正确的答案填在相应饿空中）1.n个顶点的连通图至少_n-1___条边。2.在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于__1__，否则等于___0_。3.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于__1__。4.已知图G的邻接表如图9.7所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。图9.7图G的邻接表5.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。6.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。7.31．已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接距阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。V1v2v3v4^v5v6^V2V5V4^v3V5^V4V6V3^V6^516H224H3122．请用克鲁斯卡尔普里姆两种算法分别构造最小生成树：（1）1611151