数据结构(c语言版)课后习题答案完整版资料 下载本文

然后顺移,与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; }