设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?" _! W# l$ ~( c- P# T
& E) b @9 P6 _% m$ g: k Y) W1 Y0 }. x. s' g8 A. q* |0 a T; |; k
初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]5 o* d- E* l! J/ r1 _( C: O
第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
s& c7 o! w) A第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]+ m+ {. k" y a. P9 m2 i/ y
第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]' u( A3 L6 }* M) s9 y* H5 P# z7 j
查找成功。6 L0 b2 z `5 f( f. e: @0 ^# ]) ~
2
n) U v4 x, L$ I2 n; l% A已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
. r1 Q! e O5 U7 A3 P4 Q7 N) D
/ d2 N% x. \6 u: l
! Y# E- `' D, o6 Y- \第1趟:72,73,71,23, 94, 16,05,6# `- V1 } W8 R- _3 _( K
第2趟: 71,72,73,23,94, 16,05,68
! }' x2 N- @0 U# _5 N第3趟: 23,71,72,73, 94, 16,05, 68
2 N- ~8 x# n$ U1 M+ {第4趟: 23,71,72,73,94 16,05,689 C4 G0 S9 b1 L( Q! C" W, {
第5趟: 16,23,71,72,73,94,05,681 P0 X3 y8 n0 \" y3 _# L8 \
第6趟: 05,16,23,71,72,73,94,68
! p9 |, s- ?7 p9 G! q第7趟; 05,16,23,68,71,72,73,94% H( G6 v/ B& @. V* _
|