数据结构第6,910章作业

1、二、单项选择题1.树最适合用来表示A)有序数据元素。无序数据元素B)D)C)元间具有分支层次关系的数据元间无联系的数据2.深度为 5 的二叉树至多有A)16C)31个结点。B)D)32103.在一棵具有 4 层的完全二叉树中，结点总数最多为。A)14B)15C)16D)174.在一棵具有 5 层的完全二叉树中，结点总数最少为。A)C)155B)16D)315.在完全二叉树中，如果一个结点是叶结点，则它没有。右子节点节点、右子节点和兄弟结点节点节点和右子节点A)C)B)D)6.如果结点A 有 3 个兄弟结点，而且 B 是A 的双亲结点，则 B 的度为。A)C)24B)3D)57.3 个结点可以构

2、造出种不同的二叉树。A)C)24B)3D)58.现有一棵度为 3 的树，它含有两个度为 3 的结点，一个度为 2 的结点和两个度为 1 的结点，由此可知度为 0 的结点数为。A)C)46B)5D)79.假定在一棵二叉树中，双分支结点数为 12 个，单分支结点数为 29 个，则叶子结点数为 。A)C)10.A)C)11.1214B)13D)41假定一棵二叉树的结点为 97，则它的最小高度为 。46用顺序女，则A2i 1Ai/2B)5D)7的方法将完全二叉树中的所有结点逐层存放在数组 A1,n中，结点 Ai若有女结点是。B)A2i + 1D)A2iA)C)12.A)C)13.一个满二叉树，共有n

3、个结点，其中 m 个为树叶，则 。n = m + 1n = 2m已知一棵二叉树结点的先根序列为为。ACFKBDGB)m = (n + 1)/2D)n = 2 * mABDGCFK，中根序列为 DGBAFCK，则结点的后根序列A)B)GDBFKCAD)ABCDFKGC)KCFAGDB以下两题基于下面的叙述：某二叉树结点的中序序列为A,B,C,D,E,F,G,后序序列为 B,D,C,A,F,G,E。14.A)C)15.A)16.该二叉树结点的前序序列为。E,G,F,A,C,D,BE,A,G,C,F,B,D该二叉树对应的森林包括棵树。B)D)E,A,C,B,D,G,FE,G,A,C,D,F,B1B)

4、2C)3D)4二叉树的前序遍历和中序遍历如下：前序遍历：E F H I G J K中序遍历：H F I E J K G该二叉树根中右的根是。A)17.A)C)18.E在下列B)F形式中，不是树的C)G形式。D)H双亲表示法孩子兄弟表示法B)孩子链表表示法D)顺序表示法设 A 是一个森林，B 是由 A 转换得到的二叉树，A 中有 n 个非终端结点，B 中在指针域为空的结点有个。A)C)19.n - 1n + 1B)nD)n + 2设森林 F 中有 3 棵树。第一、第二和第三棵树的结点个数分别是 m1,m2 和 m3，则与森林 F 对应的二叉树根结点的右m3 m1上的结点个数是。B)m2 + m3

5、D)m1 + m2A)C)20.A)C)21.该二叉树对应的森林结点的层次次序序列为。E,G,F,A,C,D,BE,A,G,C,F,B,DB)E,A,C,B,D,G,FD)E,G,A,C,D,F,B设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右的结点为 n，则二叉树 B中另一棵m-n+1 m-n-1的结点个数为。A)C)22.A)B)C)B) n+1D) m-n以下有关数据结构的叙述，正确的是 。线性表的线性结构优于链式结构二叉树的第 i 层上有 2i-1 个结点，深度为 k 的二叉树上有 2k-1 个结点二维数组是其数据元素为线性表的线性表栈的操作方式是先进先出D

6、)23.如果二叉树中任何一个结点的值都大于它的树上所有结点的值，且小于右上所有结点的值，要得到个结点值的递增序列，应按下列次序排列结点。先序后序B)中序D)层次序A)C)24.A)C)25.如果 T2 是由有序树T 转换而来的二叉树，那么 T 中结点的前序就是 T2 结点的。后序前序B)层次序D)中序对树中的一个结点 x，在先根序列中的序号为 pre(x)，在后根序列中的序号为t(x)，若树中结点 x 是结点y 的祖先，则下列 4 个序列中，是正确的。pre(x)pre(y)和 pre(x)pre(y)和D)pre(x)t(x)t(y)t(y)t(x)t(x) b总有 s = bA)C)11.

7、B)D)总有 s b对于关键码序列 K = 53,30,37,12,45,24,96 ，从空二叉树开始逐个每个关键码，建立与集合 K 对应的二叉排序树（又称二叉查找树）BST，若希望得到的 BST 高度最小，则应选择的输入序列是。A)37,24,12,30,53,45,96C)12,24,30,37,45,53,96B)30,24,12,37,45,96,53D)45,24,53,12,37,96,3012. 已知 8 个数据元素为(26,75,15,23,14,62,72,19)，按照依次结点的方法生成一棵二叉排序树，则该树的深度为。A)3C)5B)4D)613. 为了有效地利用散列查找技术

8、，需要解决 .找一个好的散列函数是。.设计有效的解决.用整数表示关键码值A)和C)，和以下两题基于下述描述的方法B) 和 D)和散列表的地址区间为 0-17，散列函数为 H(K)=K mod 17。采用线性探测法处理，并将关键字序列 (26,25,72,38,8,18,59)依次到散列表中。14. 元素 59 存放在散列表中的地址为 。A)8C)10B)9D)1115. 存放元素 59 需要搜索的次数是 。A)2C)4二、填空题16. 散列法三、计算题B)3D)5中处理碰撞的方法主要有两类：法和。第 10 章 排序 作业一、基础知识题二、单项选择题1.排序的重要目的打印输出查找以后对已排序的数

9、据元素进行。B)分类D)合并A)C)2.具有 12 个111的序列，采用冒泡排序，最少的比较次数是 。B)66D)144A)C)3.10 个数据元素为(54,28,16,34,73,62,95,60,26,43)的关键码序列，对该序列按从小到大排序，已知经过冒泡排序后的序列为。16,28,34,54,73,62,60,26,43,9528,16,34,54,62,73,60,26,43,9528,16,34,54,62,60,73,26,42,9516,28,34,54,62,60,73,26,42,95从未排序序列中挑选元素，并将其依次放入已排序序列初始时为空的一端，这种排序方法称为 。A)

10、B)C)D)4.排序选择排序在对一组B)归并排序D)快速排序(60,43,100,30,21,79,65,21,90)进行直接A)C)5.排序时，当把它的第七个65有序表时，为寻找13已知待排序的位置，需比较次。B)2D)4的关键字为50,34,65,76,97,27,13,37,49，采用直接A)C)6.排序方法将按关键字从小到大排序。当2437 时，需要比较的B)3D)5个数为 。A)C)7.排序方法对下面 4 个序列进行由小到大的排序，元素比较次数最少的是。用直接A)C)94,32,40,90,80,46,21,6921,32,46,40,80,69,90,94B)32,40,21,46

11、,69,94,90,80D)90,69,80,46,21,32,94,408.在设有关键码序列(16,9,4,25,15,2,13,18,17,5,8,24)，要按关键码值递增的次序排序，采用初始增量为 4 的排序法，一趟扫描后的结果为 。A)C)(15,2,4,18,16,5,8,24,17,9,13,25)(9,4,16,15,2,13,18,17,5,8,24,25)B)(2,9,4,25,15,16,13,18,17,5,8,24)D)(9,16,4,25,2,15,13,18,5,17,8,24)9.已知 12 个数据元素为(34,76,45,18,26,54,92,60,25,37

12、,03,78)，对该数列按从小到大排序。若采用排序方法排序，设第一趟排序的增量为 6，第二趟排序的增量为 3，则第二趟排序和的序列为。34,60,25,18,03,54,92,76,45,37,26,7818,25,03,26,34,37,54,60,45,76,78,9218,03,25,34,26,45,37,60,54,92,76,78以上都不正确A)B)C)D)10.一组的排序码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个为基准得到的一次划分结果为。(38,40,46,56,79,84)(40,38,46,56,79,84)A)C)11.A)C)12.A)C

13、)13.B)D)(40,38,46,79,56,84)(40,38,46,84,56,79)对下列关键字序列用快速排序法进行排序时，速度最快的排序方法是 。(5,9,17,21,23,25,30)(21,25,5,17,9,23,30)B)(21,9,17,30,25,23,5)D)(25,23,30,17,21,5,9)在文件局部有序或文件长度较小的情况下，最佳的排序方法是 。冒泡排序快速排序B)直接排序D)简单选择排序每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均不大于基准元素的排序码，右区间中元素的排序码均不小于基准元素的排序码，这种排序方法叫做。堆排序 起泡排序对

14、 n 个O(1)O(n)B)快速排序A)C)14.A)C)15.A)C)16.A)B)C)排序D)的文件进行快速排序，所需的辅助空间为。B)O(log2n)D)O(n2)下列排序方法中，稳定的排序方法是。快速排序排序B)二分法排序D)直接选择排序用快速排序法对下列关键字序列进行排序，速度最慢的是 。7,11,19,23,25,27,3227,25,32,19,23,7,1123,11,19,32,27,25,723,27,7,19,11,25,32下列关键码序列中， 是一个堆。D)17.A)C)18.A)C)19.A)C)20.A)C)21.A)(93,30,52,22,15,71)(15,3

15、0,22,93,52,71)B)D)(15,52,22,93,30,71)(15,71,30,22,93,52)堆的形状是一棵。二叉排序树完全二叉树满二叉树不是二叉树B)D)下列关键码序列不符合堆的定义。A,C,D,G,H,M,P,Q,R,XQ,D,P,R,C,Q,X,M,H,GB)A,C,M,D,H,P,X,G,O,RD)A,D,C,M,P,G,H,X,R,Q一组的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为。(79,46,56,38,40,84)(84,79,56,46,40,38)B)(84,79,56,38,40,46)D)(84,56,79,40,

16、38,46)对已建好的初始堆(84,79,56,38,36,40)进行排序，输出堆顶元素后，形成的堆为。79,56,38,46,40B)79,56,46,38,40D)79,46,56,38,40C)79,46,38,56,4022. 若关键码序列(k1,k2,kn)是一个堆，序列中元素的关系是。ki = k2i 且 ki = k2i 且 ki = k2i+1 k1 = K2 = = K2 = = knA)B)C)D)元素间没有任何限制23. 对 n 个情况下的执行时间为。B)O(n)D)O(n2)的文件进行堆排序，A)C)O(log2n)O(nlog2n)24. 一个序列中有若干个元素，若只

17、想得到其中 1 个元排序。前的部分排序，最好采用A)堆排序C)s排序排序B)D)快速排序25. 下列有关查找与排序的说法中正确的是。A)堆排序所需的时间与待排序的个数无关如果某种排序算法是不稳定的，则该方法没有实际应用价值任意一颗二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间中序遍历二叉树的结点就可以得到排好序的结点序列26. 一组的排序码为字母序列(Q,D,F,X,A,P,N,B,Y,M,C,W)，按归并排序方法对该序列进行一趟归并后的结果为 。A)(D,F,Q,X,A,B,M,W,Y)B)(D,F,Q,A,P,X,B,N,Y,C,M,W)D)(D,Q,F,X,

18、A,P,B,N,M,Y,C,W)C)(D,Q,F,X,A,P,N,B,Y,M,C,W)27. 一组序列的关键字为(25,48,16,79,82,23,40,36,72)，其中含有 5 个长度为 2 的有序表，按归并排序方法对该序列进行一趟归并后的结果为 。A)(16,25,35,48,23,40,79,82,36,72)B)(16,25,35,48,79,82,23,36,40,72)C)(16,25,48,35,79,82,23,36,40,72)D)(16,25,35,48,79,23,36,40,72,82)28. 若待排序序列已基本有序，要使它完全有序，则从关键码比较次数和移动次数考虑，应当使用的排序方法是。A)快速排序C)归并排序设待排序的是。20 16 13 14 1916 20 13 14 1913 16 20 14 1913 14 16 20 1913 14 16 19 20冒泡排序C)堆排序B)直接选择排序D)直接排序为(20,16,13,14,19)，并经过下列过程将这些排序，则所用的排序方法排序B)D)直接排序30. 用某种排序方法对线性表(D,I,C,G,A,E,H,F,B)进行关键码升序排列时，结点序列的变化情况如下：D,I,C,A,G,E,H,F,BA,B,C,D,F,E,G,H,I那么采用的排