设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?& m& a+ ^ r+ A/ c# A8 c3 O
1 s6 k9 w3 y' c0 c: v
& A4 t- M" x( m5 J# ?6 y2 j初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]5 ?, w+ ]/ z/ \" v. j' ^0 @/ W% P
第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]* l4 ?* k$ E2 {( U5 {
第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
- Q# U- T4 H% j% S3 E& @/ m第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
" g1 @3 a4 J# Y查找成功。 _" G+ X' u0 K/ c" B0 b1 m
2. D! D, C$ [: N3 J; N
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。/ |1 I9 H, @$ O8 p/ K; J" ? p# m
% Y5 L, n7 K5 i) J' {% E
& `- n, E1 B: c9 H3 p# u X第1趟:72,73,71,23, 94, 16,05,6
* m( [ ]8 O( Y1 z第2趟: 71,72,73,23,94, 16,05,68
8 o8 @/ f* x. Q$ d6 `& C第3趟: 23,71,72,73, 94, 16,05, 68
% \5 X C# J0 j2 Z! V第4趟: 23,71,72,73,94 16,05,68
B. H4 y. h* T第5趟: 16,23,71,72,73,94,05,68" j& C& [) [" Y5 ?/ P8 N
第6趟: 05,16,23,71,72,73,94,68
5 ]* ]4 M( x: ]- q第7趟; 05,16,23,68,71,72,73,943 L7 w" }3 ~1 _1 r7 d
|