分法查找，则复杂性为 ；若用分块法查找(假定总块数和每块长度均接近 )，则时间复杂性为 。 37. 对长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找程 为 。
38. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找32，则所需的比较次数为 。
三、判断题
1. 用向量表示的有序表可以使用折半查找。 2. 用单链表表示的有序表可以使用折半查找。 3. 顺序查找的平均查找长度ASL与数据的排列有关。
( )( )( )
4. 在任意非空的二叉排序树中，删除某个结点之后，再将该结点插入在二叉排序树中，则所得到的二叉排序树与原二叉排序树相同。 ( )
5. 哈希表的装载因子越小则发生冲突的可能性越大。 ( ) 6. 二叉排序树中，关键字最小的结点必然无右孩子，关键字最大的结点必然无左孩子。
( )
7. 在分块查找、折半查找和顺序查找中，分块查找平均查找长度最大、折半查找平均查找长度最小。 ( )
8. 顺序查找的方法适合于顺序存储结构而不适合于链接存储结构。 ( ) 9. 前序遍历一棵二叉排序树的结点 , 就可以得到排好序的结点序列。 ( ) 10. AVL树是一棵二叉树，该树上的任意一个结点的平衡因子的绝对值均不大于1。 （ ） 11. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素的个数有关。 ( ) 12. 对一个堆按层次遍历，不一定能得到一个有序序列。 （ ）
四、综合题
l. 用 C 语言写出顺序查找算法。 2. 用 C 语言写出折半查找算法。 3. 用 C 语言写出分块查找算法。
4. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有n个结点的二叉排序树算法。
5. 简述平衡二叉树调整平衡的具体方法。
6. 关键字序列A=(36,27,68,33,97,40,81,24,23,90,32,14)共12个数据，哈希表长为13，采用的哈希函数为：h (key) = key % 13。如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其平均查找长度。
7. 写出折半查找的递归算法。
8. 编写算法，用折半查找算法在一个有序的顺序表中插入 x 结点，并保持结点的有序性。
9. 编写判定给定的二叉树是否是二叉排序树的算法。
10. 设哈希函数为 h (key)=key % 19，编写一个用链接表解决冲突的哈希表插入函数。 11. 设哈希函数为h (key)=key ，解决冲突的方法是链地址方法，编写一个从哈希表中删除关键字为 key 的一个记录的算法。
33
习题九
一、选择题
1．在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。 A．冒泡排序 B．希尔排序
C．直接选择排序 D．直接插人排序
2．从未排序序列中依次取出元素与已经排好序的序列中的元素作比较，将其放入已排序序列的正确位置上，此方法称为（）。
A．插人排序 B．选择排序
C．交换排序 D．归并排序
3．从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为（）。 A．插入排序 B．交换排序
C．选择排序 D．归并排序
4．依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。 A．插人排序 B．交换排序
C．选择排序 D．归并排序
5．当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。 A．插人排序 B．交换排序
C．选择排序 D．归并排序
6．每次把待排序的区间划分为左、右两个子区间，其中左区间中的记录的关键字均 小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种 排序称为（）。
A 插人排序 B．快速排序
C．堆排序 D．归并排序
7．在正常情况下，直接插人排序的时间复杂度为（）。 A．O(log2n) B．O(n)
C．O(n log2n) D．O(n2) 8．在正常情况下，冒泡排序的时间复杂度为（）。
A．O(log2n) B．O(n)
C．O(nlog2n) D．O(n2)
9．在归并排序中，归并趟数的数量级为（）。 A．O(log2n） B．O(n)
C．O(nlog2n) D．O(n2)
10．在归并排序中，每趟需要进行的记录比较和移动次数的数量级为（）。 A．O(log2n） B．O(n)
C．O(nlog2n) D．O(n2)
11．归并排序算法时间复杂度为（）。
A．O(log2n） B．O(n)
C．O(nlog2n) D．O(n2)
12．平均情况下，快速排序的时间复杂度为（）。
A．O(log2n） B．O(n)
C．O(nlog2n) D．O(n2)
13．最坏情况下，快速排序的时间复杂度为（）。
A．O（log2n） B．O(n)
34
C．O(nlog2n) D．O(n2)
14．堆排序中，在每次筛运算中，记录比较和移动次数的数量级为（）。 A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
15．堆排序算法时间复杂度为（）。
A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
16．设有 800条记录，希望用最快的方法挑选出其中前10个最大的元素，最好选用（）。 A．插人排序 B．快速排序 C．堆排序 D．归并排序
17 在待排序元素基本有序的情况下，效率最高的排序方法是（）。 A．插入排序 B．快速排序 C．堆排序 D．归并排序 18．下面几种排序方法中，要求内存量最大的是（）。 A 插人排序 B．交换排序 C．选择排序 D．归并排序
19．在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）方法。 A．希尔排序 B．冒泡排序 C．插人排序 D．选择排序
20．快速排序方法在（）情况下最不利于发挥其长处。
A．要排序的数据量大大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数
21．下述几种排序方法中，平均情况下占用内存量最大的是（）方法。 A．插人排序 B．选择排序 C．快速排序 D．归并排序
22．若构造一棵具有n个结点的二又树排序，在最坏的情况下，其深度不会超过（）。 A．n/2 B．n
C．（n＋l）/2 D．n＋l
二、填空题
1．假设对记录的次关键字进行排序，记录之中有两条记录Ri和Rj，它们的关键字Ki
和 Kj相等，在排序之前记录 Ri在 Rj之前，若排序之后记录 Ri仍在Rj之前，则称排序方法是___________; 相反，若经过某种排序之后 Ri在Rj之后，则称所用的排序方法是____________。
2．根据所排序过程中所用存储器的不同，可以将排序方法分为__________和__________。
3．如果按排序过程中所需要的工作量来分，又可以分为__________、__________ 和__________，其中__________的时间复杂度为 O(n2),__________的时间复杂度为O(nlogn)，__________时间复杂度为O（d·n）。
4．__________的基本思想是：每一趟将一个待排序的记录按其关键字的大小，插入到已经排好序的部分记录之中，使之构成一个新的有序序列，直到所有记录全部插入完成，所有待排记录的关键字都成为一个有序序列。 5．直接插人排序是一种__________．（填是否稳定）的排序算法。
6．希尔排序（Shell’s Sort）又称__________，它是由 D．L．Shell于 1959年提出来的一种改进的插入排序方法。希尔排序属于__________的一种，但比普通的插人排序效率要
35
高。
7．希尔排序是一种__________（填是否稳定）的排序算法.
8．__________是通过两两比较待排序记录的关键字，若发现两个记录关键字的大小次序相反，即进行交换，直到所有记录关键字全部满足排序要求为止。 这种排序方法可以包括有__________和__________两种交换排序方法。
9．__________是通过无序区中相邻记录关键字之间相互比较和交换位置，使之关键字 较小的记录在关键字较大的记录之上，从下标较大的单元逐步向下标较小的位置移动。 10．冒泡排序是一种__________（填是否稳定）的排序算法。
11．快速排序（Quick Soft）又称___________是由霍尔 (Hoare) 提出的的一种对冒泡 排序改进的交换排序。 因其排序速度快，故而称为快速排序。 12．快速排序是一种__________（填是否稳定）的排序算法。
13．__________的基本思想是：每一趟排序在待排序的记录中选关键字最小的记录，依次放在已经排序记录序列的最后，直至全部记录的关键字成为一个有序序列为止。 这种排序方法又可以分为：__________和__________。
14．堆排序的关键是构造堆。R．W．FIOyd提出了一个__________算法来建堆。
15．归并就是将两或两个或两个以上的有序数据序列合并成一个有序数据序列的过程。归并排序有__________和__________，可以用于__________，也可以用于__________，但一般情况下说归并排序都是指__________．它是最简单也是最基础的一种归并排序方法。 16．归并排序是一种__________（填是否稳定）的排序算法。
17.是利用关键字本身的结构，借助于多关键字排序的思想，通过“分配”和“收集”的方法实现排序。
18．基数排序是一种__________（填是否稳定）的排序方法。
19．对于多关键字排序，可以有两种方法。一种称为__________法，简称__________法，另一种方法称为__________法。
20．当排序的记录数量很多，可能出现正序或逆序情况的时候，并且要求排序方法稳定的时候，则要选择__________。
21．直接选择排序算法在最好情况下所作的交换元素的次数为__________。 22．简单选择排序方法所执行的元素交换次数最多为__________。
23．简单选择排序方法在最好的情况下所做的交换元素的次数为__________。 24．冒泡排序方法在最好情况下的元素交换次数为__________。
25．有n个求队参加的足球联赛按主、客场进行比赛，共需进行__________场比赛。 26．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序若干趟后，当需要把第7个记录60插入到有序表时，为寻找60的插入位置需比较__________次。 27．分别采用选择排序、堆排序、快速排序和归并排序方法对初始状态为递增序列按递增顺序排序，最省时间的是__________排序，最浪费时间的是__________排序。
三、判断题
1．快速排序在所有排序方法中最快，而且所需要的附加空间也最少。 （ ） 2．外部排序是把外存文件调入内存，可利用内部排序方法进行排序，冈此排序所花 费的时间取决于内部排序的时间。 （ ）
3．一般来说，外排序所需要的时问取决于内部排序时间、外存信息读写时间和内部 归井所需要的时间。 （ ）
4．外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的时间
（ ）
5．快速排序方法在任何情况下均可以得到最快的排序效果。 （ ）
36
6．基数排序的设计思想是依照对单个关键字值的比较来实施的。 （ ）
7．用希尔（Shell）排序方法进行排序的时候，关键字越是有序效率越高，关键字越是杂乱则排序效率越低。 （ ）
8．减少初始归并数量，可以使外部排序的时间缩短。 （ ） 9．直接插入排序是一种稳定的排序算法。 （ ） 10．希尔排序是一种稳定的排序算法。 （ ） 11．冒泡排序是一种稳定的排序算法。 （ ） 12．冒泡排序算法的时间复杂度最佳情况下为O(n2)。 （ ） 13．快速排序是一种稳定的排序算法。 （ ） 14．直接选择排序是一种稳定的排序算法。 （ ） 15．堆排序是一种稳定的排序算法。 （ ） 16．快速排序、堆排序和归并排序平均时间复杂度为O(nlog2n)。 （ ） 17．归并排序是一种稳定的排序算法。 （ ） 18．基数排序是一种稳定的排序算法。 （ ） 19．目前归并排序在内部排序和外部排序中都广为使用。 （ ） 20．当排序的记录数量很多，可能出现正序或逆序情况的时候，可以选择堆排序，如果进一步要求排序方法稳定的时候，则要选择归并排序。 （ ）
21．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 （ ）
22．二路归并排序的核心操作是将两个有序序列归并为一个有序序列。 （ ） 四、综合题
1．已知一组记录的关键字序列为{41，60，39，72，25，44，90，31}，请写出直接插入排序的每一趟过程。
2．已知一组记录的关键字序列为{36，55，31，28，79，66，12，07，89}，请写出进行冒泡排序的每一趟过程。
3．已知一组记录的关键字序列为{35，27，60，72，50，40，17，81，29，69，30}，请写出以第一个记录为基准记录，一趟快速排序时记录的移动情况。
4．已知一组记录的关键字序列为{76，98，23，65，40，39，52，65，87，11}，请写出直接选择排序的每一趟过程。
5．已知一组记录的关键字序列为{22，96，15，37，10，68，44，85，70，20，11}，请写出用归并排序进行排序的每一趟过程。
6．设计一个函数，实现冒泡排序的双向排序，即每一趟通过每两个相邻的关键字进行比较，产生最小和最大的关键字值的元素。
7．用递归的方法实现一趟归并排序，并写出完整的归并算法。
8．有一种算法称为奇偶转换排序，它的思路是：第一趟对所有的奇数i将a[i]和a[i+l]进行比较，第二趟对所有的偶数的i将a[i]和a[i+l]进行比较，每次比较时，若a[i]＞a［i＋l］，则将二者进行交换，直至所有记录关键字有序。试写出此算法。
37