A． 2.9 B. 3 C. 4.5 D. 5.0 5、设哈希表长m=14,哈希函数H(key)=key%k11,表中已有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空
如果采用二次探测再散列处理冲突，关键字为49的结点的地址是（ D ）。
A. 8 B. 3 C. 5 D. 9
二、设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，
612，677，765，897，908。试画出对其进行折半查找时做性能分析用的判定树，并计算等概率条件下查找成功时的平均查找长度和查找不成功时的平均查找长度。 解：
1 14
2 3 4 5 6 7 8 9 10 11 12 13
017 094 154 170 275 503 509 512 553 612 677 765 897 908 判定树:
ASL成功=(1*1+2*2+3*4+4*7)/14=45/14 ASL不成功=(1*1+4*14)/15=57/15
三、已知待散列存储的线性表为（25，48，32，50，68），散列用的一维地址空间为[0..6],假定选用散列函数为h(k)=k%7,若发生冲突则菜用线性探测再散列的开放定地法解决，试计算出每一元素（即关键字）的存储地址，并计算出等概率条件下的平均查找长度。
2 4 8 6 10 12 14 7 3 9 1 5 11 13 三、解：
h(25)=25%7=4 h(48)=48%7=6 h(32)=32%7=4 h1=(4+1)%7=5 h(50)=50%7=1 h(68)=68%7=5 h1=(5+1)%7=6
36
h2=(5+2)%7=0 68 50 25 ASL=(1*3+2*1+3*1)/5=1.6
32 48 第十章 排序
一、选择题
1、在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是（ D ）。 A.希尔排序 B.起泡排序 C.插入排序 D.选择排序
2、在待排序的元素基本有序的前提下，效率最高的排序方法是（ A ）。 A.插入排序 B.选择排序 C.快速排序 D.归并排序
3、一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序的方法建立的初始堆为（ B ）。
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
4、下述几种排序方法中，平均查找长度最小的是（ C ）。 A.插入排序 B.选择排序 C.快速排序 D. 归并排序 5、下列算法中（ D ）中算法占用的辅助空间最多。
A．堆排序 B. SHELL排序 C. 快速排序 D. 归并排序
6、若数据表中每个元素已距其最终位置不远时，则采用（ D ）算法进行排序最省时间。
A．堆排序 B. 选择排序 C. 快速排序 D. 插入排序 7、下列排序算法中，稳定的是（ B ）。
A．直接选择排序 B. 直接插入排序 C. 快速排序 D.堆排序 二、已知待排序记录的关键字序列如下：（19，7，25，14，33，18）。请写出用快速排序时 每一趟的排序结果。 解：
（1） [18 7 14] 19 [33 25] （2） [14 7] 18 19 [33 25] （3） 7 14 18 19 [33 25] （4） 7 14 18 19 25 33
三、给出一组关键字序列：12，8，9，15，7，16，13，4，10，20，11，14，请给出用快速排序、堆排序、希尔排序（渐减增量序列d=6,3,2,1）各自的第一趟、第二趟排序结果。
解：1）快速排序
[11 8 9 10 7 4] 12 [13 16 20 15 14] [4 8 9 10 7] 11 12 [13 16 20 15 14] 2）堆排序（大根堆）
（1）16 15 14 12 11 9 13 4 10 7 8 20 （2）15 12 14 10 11 9 13 4 8 7 16 20
3）希尔排序
（1）12 4 9 15 7 14 13 8 10 20 11 16 （2）12 4 9 13 7 10 15 8 14 20 11 16
37