设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?
" M7 m$ o+ q* s8 Q: B- }" X2 E7 F# V$ x
6 ?" M" [9 h5 J& b1 }3 H7 [+ U7 a; k3 y! w" j: W& v6 s6 l. n
初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]' _, ] q u4 c _+ U
第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
- w% ]4 f" u( Z第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
9 T1 J* E# C+ a7 X9 Q# _第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
0 T I/ D1 J6 e5 E, t% `查找成功。
6 o( X8 i) Q5 j) o0 t5 }4 M2& O! W! ~; S' }1 x8 k
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。: T8 k4 p% L/ L$ r9 r
, f/ r4 e1 f r9 m7 p& b7 O6 F9 W" M: n) i: i7 W9 n) N* ?
第1趟:72,73,71,23, 94, 16,05,6
6 |& D5 r D4 {8 e" Y; u第2趟: 71,72,73,23,94, 16,05,680 @7 e! r; y- z2 V, i8 M; z. P7 {
第3趟: 23,71,72,73, 94, 16,05, 684 O8 A' r6 E4 ~: a3 {5 z6 q6 j; ]: Z9 \
第4趟: 23,71,72,73,94 16,05,68- Y# s3 D# A. b; D& Q+ R/ j
第5趟: 16,23,71,72,73,94,05,68
1 H- G, R' \2 y第6趟: 05,16,23,71,72,73,94,68/ V( [5 w9 e' B/ e8 h. `7 A
第7趟; 05,16,23,68,71,72,73,94
& v+ I+ R$ F3 _; c |