综合题
1.设散列表为 T［0..12］，散列函数为 H（key）= key，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。 解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。
键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突
用线性探查法处理冲突构造的散列表见表8-1所示。
表8-1 用线性探查法处理冲突构造的散列表
下标 T［0..12］ 查找成功探查次数 查找失败探查次数
0 1 9
1 3 8
2 1 7
3 2 6
4 2 5
5 1 4
6 1 3
7 9 2
8 1
9 1
10 11 12 36 1 2
1
38 1 10
39 12 28 15 42 44 06 25
在等概率的情况下，查找成功的平均查找长度 ASL=（1×6+2×2+3×1+9×1）/10=2.2
设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、?、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，?，12进行分析可得查找失败的平均查找长度。
ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突
用拉链法处理冲突构造的散列表见图8-2所示。
26
图8-2 拉链法处理冲突构造的散列表
在等概率的情况下查找成功的平均查找长度： ASL=（1×7+2×2+3×1）/10=1.4
设待查键值 k不在散列表中，若 k% 13= d。则需在 d链表中查找键值为 k的结点，直到表尾，若不存在则查找失败，设 d链表中有 i个结点，则 k需与表中键值比较 i次，查找失败的平均长度为：
ASL=（1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.77
2.线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，7}，共有 13 个元素，已知散列函数为：H(k) = k % 13 ，采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。 解：依题意，得到：
H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11
27
H(47)=47 % 13=8
采用拉链法处理冲突的链接表如图8-3 所示。成功查找的平均查找长度： ASL=(1×10+2×3)/13=16/13=1
313 0 1 27 ^ 2 132 ^ 3 68 ^ 4 95 ^ 5 70 187 ^ 6 123 ^ 7 8 08 47 ^ 9 87 ^ 10
11 63 310 ^ 12
25 ^ 图8.3 处理冲突的链接表
28
第9章 排序
单项选择题
1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
2.设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用 。
A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序
3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序
4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 。 A. 79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38
5.在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A．堆排序 B．冒泡排序 C．插入排序 D.快速排序
6.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。
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.一组记录的排序码为(48，16， 79，35，82，23，36，72)，按归并排序的方法对该序列进行一趟归并后的结果为 。
A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82
8.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
9.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。
A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序
1-5 DCABC
29
6-9 CACD 填空题
1.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 8 个记录 45 插入到有序表时，为寻找插入位置需比较 次。
2.对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始。
3.对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 4.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序则选用 。 插入排序 选择排序
5.对 n 个元素的序列进行起泡排序时，最少的比较次数是 。 6. 排序不需要进行记录关键字间的比较。 1. 5 2. 60 3. n(n-1)/2 4. ① ② 5. n-1 6. 基数
综合题
1.已知序列49．38，65，97，76，13，27，请给出采用起泡排序对该序列作升序排列的每一趟的结果。
2.已知序列{503，87，512，61，908，170，897，275，653，462}，采用快速排序法对该序列作升序排序时的每一趟的结果。
3.已知序列{265，301，751，129，937，863，742，694，076，438}，采用基数排序法对该序列作升序排序时的每一趟的结果。
4.已知序列{503，17，512，908，170，897，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。 5.已知序列{35，89，61，135，78，29，50}，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。
6.已知序列{11，18，4，3，6，15，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。
1.解：根据起泡排序法的基本思想，比较无序区中相邻关键字。按照大小关系调整其位置，本题的解法是，通过比较已知序列中相邻关键字，并根据需要调整其位置、重复此过程直到没有关键字的位置交换为止，结果正好是关键字的升序排列。
30