数据结构习题6~12(含答桉)

1数据结构练习题第六章练习选择题1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．82.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）A．m-nB．m-n-1C．n+1D．条件不足，无法确定3．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9B．11C．15D．不确定4．具有10个叶结点的二叉树中有（B）个度为2的结点，A．8B．9C．10D．ll5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A．250B．500C．254D．505E．以上答案都不对6.有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-17.一棵具有n个结点的完全二叉树的树高度（深度）是（A）A．logn+1B．logn+1C．lognD．logn-18．深度为h的满m叉树的第k层有（A）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-19．在一棵高度为k的满二叉树中，结点总数为（C）A．2k-1B．2kC．2k-1D．log2k+110．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历11．树的后根遍历序列等同于该树对应的二叉树的(B).A.先序序列B.中序序列C.后序序列12．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（D）。A．acbedB．decabC．deabcD．cedba13．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：CA、EB、FC、GD、H14．对于前序遍历与中序遍历结果相同的二叉树为（F）;对于前序遍历和后序遍历结果相同的二叉树为（B）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树15．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树16.引入二叉线索树的目的是（A）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除2C．为了能方便的找到双亲D．使二叉树的遍历结果唯一17．n个结点的线索二叉树上含有的线索数为（C）A．2nB．n－lC．n＋lD．n18．（C）的遍历仍需要栈的支持.A．前序线索树B．中序线索树C．后序线索树19．二叉树在线索后，仍不能有效求解的问题是（D）。A．前（先）序线索二叉树中求前（先）序后继B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继20．由3个结点可以构造出多少种不同的二叉树？（D）A．2B．3C．4D．521．下述编码中哪一个不是前缀码（B）。A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）22．从下列有关树的叙述中,选出5条正确的叙述(共5分)（CDFHI）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．用树的前序周游和中序周游可以导出树的后序周游。D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E．将一棵树转换成二叉树后,根结点没有左子树。F．一棵含有N个结点的完全二叉树,它的高度是LOG2N+1。G．在二叉树中插入结点,该二叉树便不再是二叉树。H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J．用一维数组存储二叉树时,总是以前序周游存储结点。判断题1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√2.二叉树只能用二叉链表表示。×3．在二叉树的第i层上至少有2i-1个结点(i=1)×4．度为二的树就是二叉树。×5.在中序线索二叉树中，每一非空的线索均指向其祖先结点。√填空题：1．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。2．具有256个结点的完全二叉树的深度为__9____。3．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。4．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=__N2_+1___5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是__99____。6．一个有2001个结点的完全二叉树的高度为__11____。7．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__n1-1_个结点，右子树中有_n2+n3__个结点。作业题1、给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，3（1）试画出用Huffman算法建造的Huffman树；（2）求平均编码长度（）考虑概率解：（1）（2）（7×（2＋3）＋6×5＋5×7＋4×（17＋66＋13）＋3×（31＋37＋41＋29＋19＋23））/2382、．设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。解：（1）(2)后序遍历为：FDBGHECAABCDEGHF2381439565783431171710755233741534224291923111343．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。intdepth(bitreebt)/*bt为根结点的指针*/{inthl,hr;if(bt==NULL)return((1)_0__);hl=depth(bt-lchild);hr=depth(bt-rchild);if((2)hlhr___)(3)_hr=hl_____；return(hr+1);}4．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。/*pre是同tree类型相同的指针，初值是null*/thread_inorder(tree){if(tree!=null){thread_inorder((1)tree-lchild____);if(tree-lchild==(2)__NULL______){tree-ltag=1;tree-lchild=pre;}if((3)tree-rchild____==null){(4)tree-rtag=1__;(5)tree-rchild=tree_______;}pre=p;thread-inorder((6)_tree-rchild__);}}5、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？（请给出具体的推理过程）解：166、一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。kknn1)1(07.假设一个二叉树的两种遍历如下：ABCDEGHF5前序：ABFGCHDEIJLK中序：FGBHCDILJKEA画出这棵二叉树以及它的中序线索树；解：第七章练习选择题1．设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n22．一个n个顶点的连通无向图，其边的个数至少为（A）。A．n-1B．nC．n+1D．nlogn；3．一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。A．0B．1C．n-1D．n4．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A．1/2B．2C．1D．45．下列哪一种图的邻接矩阵是对称矩阵？（B）A．有向图B．无向图C．AOV网D．AOE网6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（B）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（D）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b8．下面哪一方法可以判断出一个有向图是否有环（回路）：（B）ABFCLJHGDIEKABFCLJHGDIEK6A．深度优先遍历B.拓扑排序C.求最短路径D.广度优先遍历9.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为(B)。A.O(n)B.O(n+e)C.O(n2)D.O(n3)10.求解最短路径的Floyd算法的时间复杂度为(D)。A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）11．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V712．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（A）。A．存在B．不存在13．一个有向无环图的拓扑排序序列（B）是唯一的。A．一定B．不一定14.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径15.在用邻接表表示图时，拓扑排序算法时间复杂度为(B)。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)16.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路17．下列关于AOE网的叙述中，不正确的是（B）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成判断题1.有e条边的无向图，在邻接表中有e个结点。（×）2.有向图的邻接矩阵是对称的。（×）3．任何无向图都存在生成树。（×）4.不同的求最小生成树的方法最后得到的生成树是相同的.（×）5.有环图也能进行拓扑排序。（×）6.关键路径是AOE网中从源点到终点的最长路径。（√）填空题1．具有10个顶点的无向图，边的总数最多为__45_____。2.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要___n___条弧。3．n个顶点的连通无向图，其边的条数至少为