然后顺移，与46,47,32,17,63相比，一共比较了6次！

③查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

④对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/11

（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

散列地址 0 关键字 14 比较次数 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

23

H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。

第8章 排序

1．选择题

CDBDCBCDBCBCCCA 2．应用题

（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

① 直接插入排序 ② 折半插入排序

③ 希尔排序（增量选取5，3，1） ④ 冒泡排序 ⑤ 快速排序 ⑥ 简单选择排序 ⑦ 堆排序

⑧ 二路归并排序

①直接插入排序

[2 12] 16 30 28 10 16* 20 6 18 [2 12 16] 30 28 10 16* 20 6 18 [2 12 16 30] 28 10 16* 20 6 18 [2 12 16 28 30] 10 16* 20 6 18 [2 10 12 16 28 30] 16* 20 6 18 [2 10 12 16 16* 28 30] 20 6 18

[2 10 12 16 16* 20 28 30] 6 18 [2 6 10 12 16 16* 20 28 30] 18 [2 6 10 12 16 16* 18 20 28 30] ② 折半插入排序 排序过程同① ③ 希尔排序（增量选取5，3，1）

10 2 16 6 18 12 16* 20 30 28 （增量选取5） 6 2 12 10 18 16 16* 20 30 28 （增量选取3） 2 6 10 12 16 16* 18 20 28 30 （增量选取1） ④ 冒泡排序

2 12 16 28 10 16* 20 6 18 [30] 2 12 16 10 16* 20 6 18 [28 30] 2 12 10 16 16* 6 18 [20 28 30] 2 10 12 16 6 16* [18 20 28 30] 2 10 12 6 16 [16* 18 20 28 30] 2 10 6 12 [16 16* 18 20 28 30] 2 6 10 [12 16 16* 18 20 28 30]

2 6 10 12 16 16* 18 20 28 30] ⑤ 快速排序

12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30 左子序列递归深度为1，右子序列递归深度为3 ⑥ 简单选择排序

2 [12 16 30 28 10 16* 20 6 18] 2 6 [16 30 28 10 16* 20 12 18] 2 6 10 [30 28 16 16* 20 12 18] 2 6 10 12 [28 16 16* 20 30 18] 2 6 10 12 16 [28 16* 20 30 18] 2 6 10 12 16 16* [28 20 30 18] 2 6 10 12 16 16* 18 [20 30 28] 2 6 10 12 16 16* 18 20 [28 30] 2 6 10 12 16 16* 18 20 28 [30] ⑧ 二路归并排序

2 12 16 30 10 28 16 * 20 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16* 20 28 30 6 18 2 6 10 12 16 16* 18 20 28 30 ⑦ 堆排序

第一步,形成初始大根堆（详细过程略），第二步做堆排序。

12 2 16 30 28 10 16* 20 6 18 初始排序 不是大根堆 12 28 16 20 18 10 16* 2 6 30 交换1与10对象 6 20 16 12 18 10 16* 2 28 30 交换1与9对象 2 18 16 12 6 10 16* 20 28 30 交换1与8对象 30 28 16 20 18 10 16* 2 6 12 形成初始大根堆

28 20 16 12 18 10 16* 2 6 30 从1到9重新形成堆

20 18 16 12 6 10 16* 2 28 30 从1到8重新形成堆

18 12 16 2 12 10 16* 20 28 30 从1到7重新形成堆

16* 12 16 2 6 10 18 20 28 30 交换1与7对象 10 12 16 2 6 16* 18 20 28 30 交换1与6对象 6 12 10 2 16 16* 18 20 28 30 交换1与5对象 12 6 10 12 16 16* 18 20 28 30 交换1与4对象 16* 12 16 2 6 10 18 20 28 30 从1到6重新形成堆

16 12 10 2 6 16* 18 20 28 30 从1到5重新形成堆

12 6 10 2 16 16* 18 20 28 30 从1到4重新形成堆

10 6 2 12 16 16* 18 20 28 30 从1到3重新形成堆

2 6 12 20 28 30 16 16* 10 18 20 12 28 30 2 16 6 10 16* 18

交换1与3对象 从1到2重新形成堆

2 6 12 20 28 30 16 16* 10 18 20 12 28 30 6 16 2 10 16* 18

交换1与2对象 得到结果

3．算法设计题

（1）试以单链表为存储结构，实现简单选择排序算法。 void LinkedListSelectSort(LinkedList head)

//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下

//当前结点和最小结点的前驱指针 p=head->next; while(p!=null)

{q=p->next; r=p; //设r是指向关键字最小的结点的指针 while (q!=null)

{if(q->datadata) r=q; q:=q->next; }

if(r!=p) r->data<-->p->data; p=p->next; }