错误!未找到引用源。画表如下:
0 1 2 3 4 5 6 7 8 9 111111110 1 2 3 4 5 6 7 3164 241 33442 7 3 9 4 0 0 0 1 6 7 错误!未找到引用源。查找63,首先要与H(63)=63=15号单元内容比较,即63 vs 31 ,no;
然后顺移,与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.
022167241330455364678139101
H(22)=(3*22) % 11=0 H(41)=(3*41) % 11=2 H(53)=(3*53) % 11=5 H(46)=(3*46) % 11=6 H(30)=(3*30) % 11=2 冲突 H1=(2+(1×((7*30) % 10+1)))% 11=3
H(13)=(3*13) % 11=6 冲突 H1=(6+(1×((7*13)% 10+1)))% 11=8
H(1)=(3*1) % 11=3 冲突 H1=(3+(1×((7*1)% 10+1)))% 11=0 冲突
H2=(3+(2×((7*1) % 10+1)))% 11=8冲突H3=(3+(3×((7*1)% 10+1)))% 11=5冲突H4=(3+(4×((7*1) %
10+1)))% 11=2冲突H5=(3+(5×((7*1)% 10+1)))% 11=10
H(67)=(3*67) % 11=3 冲突 H1=(3+(1×((7*67)% 10+1)))% 11=2 冲突 H2=(3+(2×((7*67)% 10+1)))% 11=1
平均查找长度ASL=(1×4+2×2+3×1+6)/8=17/8
7. 建立2-3树后的状态 删除43后的2-3树状态: 删除 24后的2-3树状态: 34 62 34 34 62 18 13 18 51 75 18 51 75 13 51 24 62 75 43 13 24
三、算法题答案 typedef int KeyType; typedef struct{ KeyType key; char name[20]; }SElemType; typedef struct{
SElemType elem[MAXSIZE]; int length; }SSTable; (1)
int Search_Seq(SSTable ST, KeyType key) { ST.elem[0].key = key;
for ( int i = ST.length; (ST.elem[i].key != key); --i); return i;
}//Search_Seq (2)
int Search_Bin(SSTable ST, KeyType key) { int high,low,mid;
low = 1;high = ST.length; while(low <= high){ mid = (low + high)/2;
if (key == ST.elem[mid].key) return mid;
else if (key <= ST.elem[mid].key) high = mid - 1; else low = mid +1; }
return 0; }//Search_Bin
第十章 参考答案:
一.单选与填空
2
1.C 2. A 3.D 4.C 5. C 6.B 7.O(n) 8. 直接插入排序
二.解答题1. (1)希尔排序
初始3658 73 8324序列 7 5 6 6 9 4 1 6 63438527d=5 3 8 5 4 6 7 9 6 1 6 42537638d=3 3 8 6 1 6 4 6 5 7 9 23345678d=1 3 8 1 4 7 6 6 5 6 9
37,65(2)快速排序 ,56,8,76,3,89,34,21,46 i j j 21,65,56,8,76,3,89,34, □,46
i i j 21,□,56,8,76,3,89,34,65,46
i j j 21,34,56,8,76,3,89,□,65,46 过程
i i j 21,34,□,8,76,3,89,56,65,46
i j j 21,34, 3,8,76,□,89,56,65,46
i i j 21,34, 3,8,□,76,89,56,65,46
i j j (21,34, 3,8) 37 (76,89,56,65,46)
第一趟排序结果:
(3)堆排序
初始关键字的完全二叉树形式: 初始建堆的结果:
56,,658,76,38,89,34,21,46,56,,76,3,89,34,21,46 37,65,3737+6583437+568937+56893487637+566565+3*5637876+376+*389*3421462146
8462134214676+3*
89
第一次交换之后的结果: 第一次交换之后重建堆的结果:
4637+763482189+653*5637834218965+463*7637+5637
2.(1)直接插入排序
初始关键字:( 503 ) 087 512 061 908 170 897 275 653 426
i=2:( 087 503 ) 512 061 908 170 897
275 653 426
i=3:( 087 503 512 ) 061 908 170 897
275 653 426
i=4:( 061 087 503 512 ) 908 170 897
275 653 426
i=5:( 061 087 503 512 908 ) 170 897
275 653 426
i=6:( 061 087 170 503 512 908 ) 897
275 653 426
i=7:( 061 087 170 503 512 897 908 )
275 653 426