发布时间 : 星期日 文章东软数据结构，树和二叉树复习题更新完毕开始阅读
8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行
先根遍历所得的遍历序列为。
9. 二叉树常用的存储结构是，树常用的存储结构是。
10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行遍历操作，并且对森
林的后根遍历序列与对森林所对应的二叉树的遍历序列相同。
习题七 参考答案
一、选择题
1．内部排序算法的稳定性是指( D )。
A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对
2．下面给出的四种排序算法中，( B )是不稳定的排序。 A．插入排序 B．堆排序 C．二路归并排序 D．冒泡排序
3. 在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。 A．直接插入排序B．冒泡排序 C．快速排序 D．直接选择排序
4．关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟
排序后的结果。
A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 5．下列排序方法中，( D )所需的辅助空间最大。 A．选择排序B．希尔排序C．快速排序 D．归并排序
6．一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（ C ）。
A．(38,40,46,56,79,84) B．(40,38,46,79,56,84) C．(40,38,46,56,79,84) D．(40,38,46,84,56,79)
7．在对一组关键字序列{70，55，100，15，33，65，50，40，95}，进行直接插入排序时，把65插入，需要比较( A )次。
A. 3 B. 4 C. 6 D. 8
8.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。
A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序 9．当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排序 D.直接插入排序 10．在待排序序列局部有序时，效率最高的排序算法是( B )。
A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序 二、填空题
1. 执行排序操作时，根据使用的存储器可将排序算法分为内排序和外排序。
2. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较 3 次。
3. 在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。 4. 在对一组记录序列{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为{50,70,60,95,80}。
5. n个记录的冒泡排序算法所需的最大移动次数为 3n(n-1)/2 ，最小移动次数为 0 。
6. 对n个结点进行快速排序，最大的比较次数是 n(n-1)/2 。 7. 对于堆排序和快速排序，若待排序记录基本有序，则选用堆排序。
8. 在归并排序中，若待排序记录的个数为20，则共需要进行 5 趟归并。 9. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比较和数据元素的移动。
10．在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是快速排序，需要内存容量最多的是基数排序。
习题八 参考答案
一、选择题
1．对线性表进行二分查找时，要求线性表必须( B )
A.以顺序方式存储 B.以顺序方式存储，且结点按关键字值有序排列 C.以链接方式存储 D.以链接方式存储，且结点按关键字值有序排列
2. 用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是( D ) A.O(n) B.O(nlog2n) C.O(n) D.O(log2n)
3. 对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24, 查找第二个记录的概率为1/6, 查找第三个记录的概率为2/3, 查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为( A )
A.23/8 B.20/8 C.17/8 D.14/8
4. 若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较( B )次。
A.9 B.7 C.5 D.3 5. 当采用分块查找时，数据的组织方式为( C ) A.数据必须有序 B.数据不必有序
C.数据分成若干块，每块内数据不必有序，但块间必须有序 D.数据分成若干块，每块内数据必须有序，但块间不必有序
6. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有( C )个结点。
A.2-1 B.2+1 C.2-1 D.2+1 7. 具有5层结点的平衡二叉树至少有( B )个结点。 A.10 B.12 C.15 D.17
8. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 9. 以下有关m阶B-树的叙述中，错误的是( B )。
A.根结点至多有m棵子树 B.每个结点至少有?m?棵子树
??2??k-1
k-1
k
k
2
C.所有叶子结点都在同一层上 D.每个结点至多有m-1个关键字
10．哈希表的地址区间为0～17，哈希函数为h(key)=K。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为( C )。
A.2 B.3 C.4 D.5 二、填空题
1．动态查找表和静态查找表的主要区别在于动态查找表有插入和删除操作 。
2．假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为 (n+1)/2 ；在查找失败情况下的平均查找长度为 n+1 。 3. 对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据有序。 4. 分块查找分为两个阶段，分别是确定待查元素所在的块和在块内查找待查的元素。 5．哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。 6. 一棵二叉排序树用中序遍历输出的信息是 递增序列。
7．深度为4的平衡二叉树中至少有 7 个结点，至多有 15 个结点。 8．引入B-树的根本原因是减少查找一个元素需要访问的外存的次数。 9．哈希法存储的基本思想是根据 关键字 来决定存储地址。
10．设计一个好的哈希函数，其函数值应该以 同等 概率取其值域的每个值。