设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?
' ?8 m% o2 f9 s3 b, _8 @4 [4 A b
2 `! ] `" q% L% d, e$ A0 I( E& [
初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
Z! A$ A1 r+ J9 O9 R+ l8 M u第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]8 R$ |2 j' ?, h; S! ~# Z3 l* e
第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]+ s- M- r$ I2 g9 t( @
第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
" p) G- ^. Z, c* }查找成功。. Y$ u) C1 P: z
2; a" q2 {8 `$ F# }
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
* R& [6 ~: Z8 U4 ?/ h
# X4 | g* f) w' z8 ] K D2 g( |7 m; C
第1趟:72,73,71,23, 94, 16,05,6
- ?3 c6 a9 f' `; ]0 M* ~第2趟: 71,72,73,23,94, 16,05,687 y! C9 s0 w$ |
第3趟: 23,71,72,73, 94, 16,05, 68
4 A2 l9 ^" {0 s) R* j" j第4趟: 23,71,72,73,94 16,05,68
* ]5 P" l: g$ P( d3 r: c9 m第5趟: 16,23,71,72,73,94,05,68
0 I# m( ?/ K3 _( b/ e2 [第6趟: 05,16,23,71,72,73,94,68
7 d* S' I0 c, D/ `3 g' n: k第7趟; 05,16,23,68,71,72,73,94' x2 m: t/ D2 j9 i" U! m! M* a
|