1、数据结构习题612含答桉数据结构习题612(含答桉)数据结构练习题 第六章练习 选择题 1. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为 A5B6 C7D8 2. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是 Am-n Bm-n-1Cn+1 D条件不足，无法确定 3若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 A9B11 C15D不确定 4具有10个叶结点的二叉树中有个度为2的结点， A8B9 C10 Dll 5一棵完全二叉树上有1001个结点，其中叶子结点的个
2、数是 A 250 B 500C254D505 E以上答案都不对6. 有n个叶子的哈夫曼树的结点总数为。 A不确定 B2n C2n+1 D2n-1 7. 一棵具有 n个结点的完全二叉树的树高度是 A?logn?+1Blogn+1C?logn? Dlogn-1 8深度为h的满m叉树的第k层有个结点。(1=Amk-1Bmk-1 Cmh-1 Dmh-1 9在一棵高度为k的满二叉树中，结点总数为 A2k-1B2k C2k-1D?log2k?+1 10对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的
3、遍历实现编号。 A先序B. 中序 C. 后序 D. 从根开始按层次遍历 11树的后根遍历序列等同于该树对应的二叉树的( B ). A. 先序序列B. 中序序列C. 后序序列 12已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是。 AacbedBdecabCdeabc Dcedba 13二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： C A、 E B、 F C、 GD、 H 14对于前序遍历与中序遍历结果相同的二叉树为; 对于前序遍历和后序遍历结果相同的二叉树为。 A一般二叉树B只有根结点
4、的二叉树C根结点无左孩子的二叉树 D根结点无右孩子的二叉树 E所有结点只有左子数的二叉树 F所有结点只有右子树的二叉树 15一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树 16. 引入二叉线索树的目的是 A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 1 C为了能方便的找到双亲 D使二叉树的遍历结果唯一 17n个结点的线索二叉树上含有的线索数为 A2n BnlCnl Dn 18的遍历仍需要栈的支持. A前序线索树B中序线索树 C后序线索树 19二叉树在线索后，仍
5、不能有效求解的问题是。 A前序线索二叉树中求前序后继 B中序线索二叉树中求中序后继 C中序线索二叉树中求中序前驱 D后序线索二叉树中求后序后继 203 个结点可以构造出多少种不同的二叉树？ A2B3 C4 D521下述编码中哪一个不是前缀码。 A B C D 22从下列有关树的叙述中,选出5条正确的叙述(共5分) A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B当K1时高度为K的二叉树至多有2k-1个结点。 C用树的前序周游和中序周游可以导出树的后序周游。 D线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E将一棵树转换成二叉树后,根结点没有左子树。 F一棵
6、含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G在二叉树中插入结点,该二叉树便不再是二叉树。 H采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J用一维数组存储二叉树时,总是以前序周游存储结点。 判断题 1完全二叉树中，若一个结点没有左孩子，则它必是树叶。 2. 二叉树只能用二叉链表表示。 3在二叉树的第i层上至少有2i-1个结点(i=1) 4度为二的树就是二叉树。 5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。 填空题： 1如某二叉树有20个叶子结点，有30个结点仅有一个
7、孩子，则该二叉树的总结点数为_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_
8、个结点。 作业题 1、给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41， 2 试画出用Huffman算法建造的Huffman树； 求平均编码长度考虑概率 解： 238 95 143 42 19 23 65 34 17 10 5 2 3 5 7 17 31 37 78 41 11 24 53 29 13 6557 43）/ 238 2、设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C 画出这棵二叉树。 画出这棵二叉树的后序线索树。 解： A B D F G E H C (2) 后
9、序遍历为：F D B G H E C A 3 A B D F G E H C3二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/ int hl,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则为
10、指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。 /* 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 _
11、); 5、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ 解： 16 6、一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 n(k?1)?1n0? k7. 假设一个二叉树的两种遍历如下： 4 前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA 画出这棵二叉树以及它的中序线索树； 解： A B F G H C D E I J L K F G B A C H D E I J L K 第七章练习 选择题 1设无向图的顶点个数为n，则该图最多有条边。 An-1Bn(n-1)/2C n(n+1)/2D0En2 2一个n个顶点的连通无向
12、图，其边的个数至少为。 An-1BnCn+1 Dnlogn； 3一个有n个结点的图，最少有个连通分量，最多有个连通分量。 A0 B1 Cn-1 Dn 4在一个无向图中，所有顶点的度数之和等于所有边数倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。 A1/2 B2 C1D4 5下列哪一种图的邻接矩阵是对称矩阵？ A有向图B无向图CAOV网 DAOE网 6当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是。 A?Ai,ji?1n B?A?i,j?j?1nCi?1?Aj,in Di?1?Ai,j?A?j,i?+ j?1nn 7无向图G=(V,E),其中：V=a,b,c,d,e,f
13、, E=(a,b),(a,e), (a,c), (b,e), (c,f), (f,d), (e,d)， 对该图进行深度优先遍历，得到的顶点序列正确的是。 Aa,b,e,c,d,fBa,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 8下面哪一方法可以判断出一个有向图是否有环： 5 A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历 9. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。 A. O(n) B. O(n+e)C. O(n2)D. O(n3) 10. 求解最短路径的Floyd算法的时间复杂度为(D )。 AOB.
14、 OC. OD. O 11已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7， E=,G的拓扑序列是。 AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7 CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7 12若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列。 A存在 B不存在 13一个有向无环图的拓扑排序序列是唯一的。 A一定 B不一定 14. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是。 AG中有弧 BG中有一条从Vi到Vj的路径CG中没
15、有弧DG中有一条从Vj到Vi的路径 15. 在用邻接表表示图时，拓扑排序算法时间复杂度为( B )。 A. O(n) B. O(ne)C. O(n*n) D. O(n*n*n) 16. 关键路径是事件结点网络中。 A从源点到汇点的最长路径B从源点到汇点的最短路径 C最长回路D最短回路 17下列关于AOE网的叙述中，不正确的是。 A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，那么整个工程将会提前完成 C所有的关键活动提前完成，那么整个工程将会提前完成 D某些关键活动提前完成，那么整个工程将会提前完成 判断题 1. 有e条边的无向图，在邻接表中有e个结点。 2. 有向
16、图的邻接矩阵是对称的。 3任何无向图都存在生成树。 4. 不同的求最小生成树的方法最后得到的生成树是相同的. 5. 有环图也能进行拓扑排序。 6. 关键路径是AOE网中从源点到终点的最长路径。 填空题 1具有10个顶点的无向图，边的总数最多为_45_。 2. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ n _条弧。 3n个顶点的连通无向图，其边的条数至少为_n-1_。 4N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_2(n-1)_个非零元素。 5构造连通网最小生成树的两个典型算法是_普里姆算法、克鲁斯卡尔算法_。 6. 有一个用于n个顶点连通带权无向图的算法描述如下：
17、 6 设集合T1与T2，初始均为空； 在连通图上任选一点加入T1； 以下步骤重复n-1次： a.在i属于T1，j不属于T1的边中选最小权的边； b.该边加入T2。 上述算法完成后，T2中共有_n-1_条边，该算法称_普里姆算法_算法，T2中的边构成图的_最小生成树_。 7AOV网中,结点表示_活动_,边表示_联系_。AOE网中,结点表示_事件_,边表示_活动_。 8. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 查邻接表中入度为_零_的顶点，并进栈； 若栈不空，则输出栈顶元素Vj，并退栈；查Vj的直接后继Vk，对Vk入度处理，处理方法是_ Vk 的入度减1，如为0则入栈_； 若栈
18、空时，输出顶点数小于图的顶点数，说明有_环路_，否则拓扑排序完成。 作业题 1n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：图的顶点号从 0开始计； indegree 是有n个分量的一维数组，放顶点的入度； 函数 crein 用于算顶点入度； 有三个函数push(data),pop( ),check( )其含义为数据 data进栈，退栈和测试栈是否空。 crein( array ,indegree,n) for (i=0;ifor(i=0,ifor (j=0;jtopsort (array,indegree,n) count= (4)_ 0_)for (i=
19、0;i vex=pop( ); printf(vex); count+; for (i=0;i k=array(6)_ vexi;_ if (7)_ k!=0_) indegreei-; if (8)_ indegreei=0_ ) push(i); if( count2设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。 234?1 5?1342 124? 31235? 4 524?7 解： 1 2 3 1 2 5 3 4 4 5 3下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出
20、所有可能的选择。 1621 215 111943 614 63356 18 16 16 解： 2 2 1 1 5 5 11 11 4 3 4 3 6 6 5 6 5 6 18 18 4、对下面的有向图，试利用DIJKSTRA算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。 8 10 v5 10 v6 15 v4 4 10 30 4 v2 2 20 v1 15 v39 第十章 选择题 1下面给出的四种排序法中( D )排序法是不稳定性排序法。 A. 插入B. 冒泡C. 二路归并D. 堆排序 2下列排序算法中，其中是稳定的。 A. 堆排序，冒泡排序B. 快速排序，堆排序 C
21、. 直接选择排序，归并排序D. 归并排序，冒泡排序 3下面的排序算法中，不稳定的是 A.起泡排序 B.折半插入排序 C.简单选择排序D.希尔排序E.基数排序 F.堆排序。 4对一组数据排序，数据的排列次序在排序的过程中的变化为 84 47 25 21 15 47 25 84 21 15 21 25 84 47 15 21 25 47 84 则采用的排序是 (A)。A. 选择B. 冒泡C. 快速D. 插入 5. 在下面的排序方法中，辅助空间为O的是( D ) 。 A希尔排序B. 堆排序 C. 选择排序D. 归并排序6. 下列排序算法中，占用辅助空间最多的是：(A) A. 归并排序 B. 快速排序
22、C. 希尔排序D. 堆排序 7用直接插入排序方法对下面四个序列进行排序，元素比较次数最少的是。 A 94,32,40,90,80,46,21,69 B 32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D 90,69,80,46,21,32,94,40 8直接插入排序在最好情况下的时间复杂度为 A O(logn)B O(n) C O(n*logn)D O(n2) 9对下列关键字序列用快速排序法进行排序时，速度最快的情形是。 A 21,25,5,17,9,23,30 B25,23,30,17,21,5,9 C 21,9,17,30,25,23,5
23、 5,9,17,21,23,25,30 10下列四个序列中，哪一个是堆。 A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,15 判断 1内排序要求数据一定要以顺序方式存储。 2排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 3直接选择排序算法在最好情况下的时间复杂度为O。 4在待排数据基本有序的情况下，快速排序效果最好。 5快速排序总比选择排序快。 填空 1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的
24、_比较_和记录的_移动_。 2关键码序列，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_ Q A C S Q D F X R H M Y _；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_ F H C D M 10 A Q S R Q Y X _。 作业题 1下面的排序算法的思想是：第一趟比较将最小的元素放在r1中，最大的元素放在rn中，第二趟比较将次小的放在r2中，将次大的放在rn-1中，?,依次下去，直到待排序列为递增序。代表两个变量的数据交换）。 void sort(SqList &r,int n) i=1; while(1)
25、 ifor (j=i+1;(2)_ jif(3)_ rj.keyrmax.key) max=j; if(4)_ min!=j_) rmin rj; if(max!=n-i+1)if (5)_ max=j _) rmin rn-i+1; else (6) rmaxrm-i+1_); i+; /sort 2快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？ 解：不是，已经有序情况下不适用，适用于基本无序的情况。 3、以上所列的排序方法，哪些是稳定的？哪些是不稳定的？对不稳定的方法举出反例。 4、设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取负
26、值关键字之前。 快速排序的一趟排序：把关键字改成跟零比较 5、以单链表为存储结构实现直接选择排序，写出它的算法。 6、判别以下序列是否为堆？若不是，则把它调整为堆 1）100，86，48，73，35，39，42，57，66，21 2）12，70，33，65，24，56，48，92，86，33 3）103，97，56，38，66，23，42，12，30，52，06，20 4）05，56，20，23，40，38，29，61，35，76，28，100 11 第九章 选择题 1、 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A ) A/2 B. N/2 C. N D. *N
27、 /2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( C )有关, 在 (C)时其查找效率最低(1): A. 高度 B. 结点的多少C. 树型D. 结点的位置(2): A. 结点太多B. 完全二叉树C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H=key MOD 17，则需 (A) 个链表。这些链的链首指针构成一个指针数组，数组的
28、下标范围为 (C) A17B. 13C. 16D. 任意 A0至17B. 1至17C. 0至16D. 1至16 判断题 1Hash表的平均查找长度与处理冲突的方法无关。 2. 若散列表的负载因子3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 填空题 1. 在顺序表中，用二分法查找关键码值20，需做的关键码比较次数为_4_. 作业题 1. 设有一组关键字9,01,23,14,55,20,84,27，采用哈希函数：H=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 解：14/8 012 345 6 789 1419 2384 27 55 20 11123312 2. 已知散列表的地址空间为A0.11，散列函数H=k mod 11，采用线性探测法处理冲突。请将下列数据25,16,38,47,79,82,51,39,89,151,231依次插入到散列表中，并计算出在等
