设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?4 U6 x9 `- z0 s8 r% ?( _* k) s; q P
/ T" I6 m* }3 Q6 n" w4 ~
& n9 i C* h" x3 A" J7 b O8 o G初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
* f, ^* n- N4 U( T" M$ r& G( K0 Z第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
8 |* y) G, ]9 {! T: z. [7 @: D C第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
0 G: L4 Z. r7 d- E第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]3 T! W" Q! y) }
查找成功。) q* j6 q7 k$ t" N8 M
2
" y! Y+ P( j& c% k4 b7 S& t8 l8 B( b6 p% d已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
3 X5 w, A8 G/ V$ {9 a5 ?) J3 U& l
3 Z5 A. y7 _8 |1 {第1趟:72,73,71,23, 94, 16,05,6
1 l5 ^9 L2 K1 l; C" B7 H8 i" Z第2趟: 71,72,73,23,94, 16,05,68
. f3 C2 `& r! s$ ^- c* b* I0 Y! x第3趟: 23,71,72,73, 94, 16,05, 68
3 p2 \1 p- o7 ?! ~+ O6 I4 t7 \& z第4趟: 23,71,72,73,94 16,05,68
1 x! |! B7 @+ y' @; Y2 F k第5趟: 16,23,71,72,73,94,05,680 M% A, H# v7 e! ^0 \
第6趟: 05,16,23,71,72,73,94,68
, q7 U1 q3 b9 ^: P/ ~第7趟; 05,16,23,68,71,72,73,94( I: [8 Q; t8 N0 K
|