2．假定对有序表(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树。 （2）若查找元素54，需依次与那些元素比较。 （2）若查找元素90，需依次与那些元素比较。 （3）求查找成功时的平均查找长度。

3、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，哈希函数为H（key）＝key％ 7，画出该哈希表，并计算查找成功的平均查找长度。

4．设有一组关键字{ 9，1，23，14，55，20，84，27 }．采用哈希函数：H(key)＝key％7。 采用开放地址法的二次探测再散列方法解决冲突

Hi?(H(key)?di)mod10(di?12,22,?)，试对该关键字序列构造哈希表，并计算查找

成功的平均查找长度。

5．输入一个正整数序列（17，31，13，11，20，35，25，8，4，11，24，40，27）画出该二叉排序树。依此二叉排序树，如何得到一个递增序列？

6．一棵二叉排序树结构如下图所示，各结点的值分别为1，2，3,...9,请在图中标出各结点的值。

第6第第

7．已知插入结点的序列为（17，31，13，11，20，35，25，8，4，11，24，40，27）,请画出该二叉排序树，并分别给出下列操作后的二叉排序树：

(1)插入数据9； （2）删除数据17； （3）再删除结点13；

8．按下列次序输入关键字：（E,F,P,K,M,L,B）,请画出AVL树的构造和调整过程。要求画出每插入一个关键字后查找树的形状及调整后的结果，并标明调整类型。

- 37 -

9.深度为6的平衡二叉树中最少应包含多少个结点，并画出这样一棵平衡二叉树。 10.从空树开始，依次输入结点20，30，50，52，60，68，70，画出建立3阶B-树的过程。并画出删除结点50和68后的B-树状态。

五、算法设计题

1．设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL。

2.试编写一个判别给定的二叉树是否为二叉排序树的算法。设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同.

3. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于X的关键字。

4.设二叉排序树的各元素均不相同，试分别采用递归和非递归算法按递减顺序打印所有左子．．树为空，右子树非空的结点的数据域的值。

5. 试编写一个算法，删除二叉排序树中所有关键字不小于x的结点，并释放该结点空间。 6. 试编写一个算法，将两棵二叉排序树合并为一棵二叉排序树。

7.写出从哈希表中删除关键字为k的一个记录的算法；设哈希函数为H,解决冲突的方法为链地址法。

- 38 -

第 10 章 内部排序

一、单选题

1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序 2．在待排序的元素序列基本有序的前提下，效率最高的排序方法是 (A)插入排序 (B)选择排序 (C)快速排序 (D)归并排序

3．设有5000个无序的元素，希望用最快的速度挑选出其中前l0个最大的元素，最好选 用

排序法。

。 。

(A)起泡排序 (B)快速排序 (C)堆排序 (D)基数排序

4．排序方法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为

。

(A)希尔排序 (B)起泡排序 (C)插入排序 (D)选择排序 5.下列排序算法中，稳定的是 。

(A)直接插入排序和快速排序 (B)折半插入排序和冒泡排序 (C)简单选择排序和四路归并排序 (D)树形选择排序和希尔排序 6．下述几种排序方法中，平均查找长度最小的是 。

(A)插入排序 (B)直接选择排序 (C)快速排序 (D)归并排序 7．下述几种排序方法中，要求内存量最大的是 。

(A)插入排序 (B)选择排序 (C)快速排序 (D)、归并排序 8．快速排序方法在 情况下最不利于发挥其长处。

(A)要排序的数据量太大 (B)要排序的数据中含有多个相同值 (C)要排序的数据已基本有序 (D)要排序的数据个数为奇数 9．下列排序方法中， 可能出现这种情况：在最后一趟开始之前，所有元素都不在

其最终应在的正确位置上。

(A)快速排序 (B)冒泡排序 (C)堆排序 (D)插入排序

10．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为 (A) n-1 (B)log2n (C) 1 (D)n2

- 39 -

11．快速排序在最坏的情况下的时间复杂度是 。

(A) O(log2n) (B)O(nlog2n) (C) O(n2) (D)O(n3) 12.在排序过程中，健值比较的次数与初始序列的排列顺序无关的是 (A)直接插入排序和快速排序 (B)直接插入排序和归并排序 (C)直接选择排序和归并排序 (D)快速排序和归并排序 13．下列排序方法中，哪一个是稳定的排序方法 。

。

(A)直接选择排序 (B)二分法插入排序 (C)希尔排序 (D)快速排序 14．在文件“有序”或文件长度较小的情况下，最佳内部排序的方法是 (A)直接插入排序 (B)选择排序 (C)冒泡排序 (D)快速排序

15．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用

方法。

。

(A)归并排序 (B)直接插入排序 (C)直接选择排序 (D)快速排序 16.下列排序算法中 排序在一趟结束后不一定能选出一个元素在其最终位置上。

(A) 选择排序 (B)冒泡排序 (C)归并排序 (D)堆排序

17.一组记录的关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为 (A)．15，25，35，50，20，40，80，85，36，70 (B)15，25，35，50，80，20，85，40，70，36 (C)15，25，50，35，80，85，20，36，40，70 (D)15，25，35，50，80，20，36，40，70，85

18. 一组记录的关键字为(56,34,23,38,40,69)，则利用直接插入排序的方法，经过 3趟排序之后，其关键字序列为 。

。

(A) 34,56,23,38,40,69 (B) 34,38,23,56,40,69 (C) 23,34,56,38,40,69 (D) 23,34,38,56,40,69

19. 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的 排序后的结果。

(A)选择排序 (B)冒泡排序 (C)插入排序 (D)堆排序

20. 一组记录的关键码为(46，79，56，38，40，84)，用堆排序的筛选方法建立的初始堆为 。

的两趟

(A) 79，46，56，38，40，80 (B) 84，79，56，38，40，46

- 40 -