5-8章习题答案2015

一、名词解释1、二叉树：2、哈夫曼树：3、小根堆：4、最小生成树5、拓扑排序6、二叉搜索树7、出度：8、权二、填空1、二叉树的度为：2，当深度h=4时，其满二叉树的结点树为：15。2、在定义各种数据结构的存储实现时，为增强其数据类型的通用性，应将其定义为通用数据（ElemType）类型。如果是定义树的链接存储结构，除了定义数据类型，还应定义链接孩子结点的左指针域(left)和右指针域(right)。3.一棵二叉树的广义表表示是A（B（C,D）），则对其的中序遍历结果是CBDA。4．对一棵完全二叉树的各结点从1开始编号，并按此编号把它顺序存储到一维数组a中，即将根结点编号为1并存储到a[1]中，其余类推，则a[i]元素的左孩子（如果有的话）元素为a[2*i]，右孩子（如果有的话）元素为a[2*i+1]，双亲元素（如果有的话）为a[i/2]。5.一个大根堆中，值最大的结点是根结点。6、同一棵树中的数据元素必须是同质（或同类型）的。7、一个广义表形式的二叉树A（B,C（，D））此二叉树的深度为38、二叉搜索树是指树上所有右结点均大于根结点，同时左右子树又各是一棵排序二叉树。9、哈夫曼树是指此树的带权路径长度（WPL）最小。10、图由非空顶点集和边集所组成。无向图某个顶点的度是以该顶点为端点的边的数目。11．一个有n个顶点的连通图的最小生成树的边数为n-1。12、对有向图来说，出度是指某个顶点出边的数目。13、在计算机中若采用索引查找，索引表中的每个索引项应至少包含索引值域和子表开始位置域两个域。14、在散列查找中，多个关键字求出的散列地址相同时，若散列地址已被占用，这种现象被称之为冲突。15、在选择排序方法时，在最坏或平均情况下元素移动次数越多，则说明该方法的时间复杂性越大（越差）。三、选择题1、一棵三叉树的结点个数为10，则它的最小深度为？，最大深度为？，正确的是（B）。A．5和8B.3和10C.1和10D．2和72.一棵深度为h的二叉树最多有（D）个结点。A．2h+1B．2h-1C．2h+1D．2h-13.一棵二叉树的第i层最多有（D）个结点。A．2i+1B．2i-1C．2i+1D．2i-14、在计算机领域，磁盘上的目录结构就是一棵树，对于这种数据结构，在查找时采用哪种方法较好？（B）A．顺序查找B.二分查找C.索引查找D.散列查找A．1B.2C.3D.45、如果有一棵完全二叉树上的结点数是9，那么这棵二叉树的最大深度是（C）A．2B．3C．4D．56、下列算法是二叉树的（A）。voidPreorder(structBTreeNode*BT){if(BT!=NULL){printf(%c,BT-data);Preorder(BT-left);Preorder(BT-right);}}A．前序遍历算法B．中序遍历算法C．后序遍历算法D．按层遍历算法7、二叉搜索树的特点是（B）。A．后序遍历有序B．按层遍历有序C．前序遍历有序D．中序遍历有序8、哈夫曼编码是（B）A．等长编码B．无前缀编码C．有前缀编码D．最短编码9、根据大根堆排序，其排序结果为（B）。A．无序B．升序C．降序D．逆序10．一个图的边集形如：E(G)={(0,1),(0,2),(1,4),…},这是一个（A）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图11．一个图的边集形如：E(G)={0,1,0,2,1,4,…},这是一个（B）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图12．一个图的边集形如：E(G)={0,12,0,23,1,45,…},这是一个（D）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图13．一个图的边集形如：E(G)={(0,1)2,(0,2)3,(1,4)5,…},这是一个（C）。A．无向无权图B．有向无权图C．无向带权图D．有向带权图14.一个无向带权图的邻接矩阵是一个（B）。A．对角矩阵B．对称矩阵C．非对称矩阵D．行、列数不等的矩阵15．对一个有向图作拓扑排序，结果总有若干顶点不能进入序列，这说明（D）。A．图中一定没有回路B．图中可能有回路C．图中顶点顺序不对D．图中一定有回路16.以下查找算法是（A）算法。intSeqsch(structElemTypeA[],intn,KeyTypeK){inti;A[n].key=K;for(i=0;;i++)if(A[i].key==K)break;if(in)returni;elsereturn-1;}A．顺序查找B．索引查找C．二分查找D．散列查找17.以上Seqsch()算法中returni;的含义是（C）。A．查到的数据B．查到的数据的地址C．查到的数据的下标D．查到的数据的位置18．如果采用h(K)=K%13计算散列地址，则元素64的初始散列地址为（B）。A．8B．12C．13D．1419．对有序表进行二分查找，算法的时间复杂度为（B）。A．O（1）B．O(log2n)C．O（n）D．O（n2）20．以下排序算法是（D）算法。voidBubbleSort(structElemTypeA[],intn){structElemTypex;inti,j,flag;for(i=1;i=n-1;i++){flag=0;for(j=n-1;j=i;j--)if(A[j].stnA[j-1].stn){x=A[j];A[j]=A[j-1];A[j-1]=x;flag=1;}if(flag==0)return;}}A．直接插入排序B．直接选择排序C．快速排序D．气泡排序四、有一棵树，以广义表表示：A（B（D（，G））,C（E（H），F（I）））。要求：1、以图形表示法如下：ABCFGEHID2、此树的深度是：4。3、写出前序遍历的结果：ABDGCEHFI、中序遍历的结果：DGBAHECIF、后序遍历的结果：GDBHEIFCA。4、画出链接存储方式。5、如果以D结点为根（不考虑其他结点），开始代入求深度的算法，写出递归过程。五、用数组A[8]={12,4,7,3,5,34,11,22}要求1：建立二叉搜索树；要求2：并再次插入28结点；要求3：之后删除12结点；要求4：之后删除34结点。画出对应二叉树图形。要求1：12124127412374123745123437451234374511要求2：12343742251112343742251128要求3：113437422528要求4：1122374528六、要求1利用已有完全二叉树建初始堆（大根堆）：4791243653307516169124365330751636249153753047答1：4791243653307516169124365330751636479153753024479124365330751616912436533075163647915330752447912436533075169191243653307516364716533075244791243653307516369124365330751691471653307524479124365330752447912436533075913616533075要求2：插入55之后调整堆。479124365330752447912436533075913616533075554791243653307524479124365330759155165330753647912436533075245591243653307591471653307536要求3：删除堆顶元素。47912436533075245591243653307591471653307536479124365330752455912436533075364716533075914791243653307524559124365330757547165330369147912436533075245591243653307575471636305391七、有6个权值分别为3,4,6,8,9,12的结点，试：要求1：按左小右大规则画出哈夫曼树的图形。1791213783462542要求2：求该哈夫曼树的WPL。WPL=4*(3+4)+3*6+2*(8+9+12)=114。要求3：按左‘0’右‘1’的规则进行哈夫曼编码。1791213783410601101251420结点权值编码311104111161108009011210八、有一个带权无向图G如下021329467121611910745126要求1：写出顶点数组和邻接矩阵中缺失行。要求2：利用普里姆算法求出图的最小生成树（不要求编写算法），画出对应的图形。根据最小生成树填写边集数组CT的内容。答1：顶点数组：012345670213294671216119107458126邻接矩阵：0123456700927∞∞∞∞122∞04∞∞∞1034∞∞∞16012∞∞56∞∞∞11∞8097答2：(0)第0次U＝{0}02132946775TE={}LW={(0,1)9,(0,2)2,(0,3)7,(0,4)∞,(0,5)∞,(0,6)∞,(0,7)∞}(1)第1次0213294671045U＝{0,2}TE={(0,2)2}LW={(0,1)9,(2,3)4,(0,4)∞,(0,5)∞,(0,6)∞,(2,7)10}(2)第2次U＝{0,2，3}02132946716111045TE={(0,2)2,(2,3)4}LW={(0,1)9,(3,4)16,(0,5)∞,(3,6)11,(2,7)10}(3)第3次021329467121110456U＝{0,2，3,1}TE={(0,2)2,(2,3)4,(0,1)9}LW={(1,4)12,(2,5)6,(3,6)11,(2,7)10}(4)第4次02132946712104586U＝{0,4，1，3，2,5}TE={(0,2)2,(2,3)4,(0,1)9,(2,5)6}LW={(1,4)12,(5,6)8,(2,7)10}(5)第5次0213294671294586U＝{0,4，1，3，2,5,6}TE={(0,2)2,(2,3)4,(0,1)9,(2,5)6,(5,6)8}LW={(1,4)12,(6,7)9}(6)第6次0213294671294586U＝{0,4，1，3，2,5,6,7}TE={(0,2)2,(2,3)4,(0,1)9,(2,5)6,(5,6)8,(6,7)9}LW={(1,4)12}(7)第7次0213294671294586U＝{0,4，1，3，2,5,6,7,4}TE={(0,2)2,(2,3)4,(0,1)9,(2,5)6,(5,6)8,(6,7)9,(1,4)12}LW={}CT0123456fromvex0201561endvex2315674weight24968912九、有一个带权无向图G如下022811542165195243要求1：写出顶点数组和邻接矩阵中缺失行。要求2：利用普里姆算法求出图的最小生成树（不要求编写算法），画出对应的图形。根据最小生成树填写边集数组CT的内容。答1：顶点数组：012345邻接矩阵：0123450022∞∞8∞12205215∞2∞504∞∞3∞24019∞4815∞190165∞∞∞∞160答2：(0)第0次U＝{0}TE={}LW={(0,1)22,(0,2)∞,(0,3)∞,(0,4)8,(0,5)∞}022814523(1)第1次U＝{0,4}TE={（0,4）8}LW={(0,2)∞,(4,3)19,(4,1)15,(4,5)16}0811541619523(2)第2次U＝{0,4，1}TE={（0,4}8,(4,1)15}LW={（1,3)2,(1,2)5,(4,5)16}0811542165523(3)第3次U＝{0,4，1，3}TE={（0,4}8,(4,1)15，（1,3)2,}LW={(1,2)5，（（3，2）4）,(4,5