设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?
$ W* j' r P0 G4 h: D, R# i' B; W
3 Q! g+ S; g q# u7 v
: L7 c4 ]1 W- Z$ T$ p+ i初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
, n0 E p8 m% N! I( ~第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]9 s' f1 f; H% Q
第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]/ s8 S7 m/ z7 F/ @ l1 x6 l C
第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
m3 W% ?0 Q0 ?: F/ w/ R查找成功。- Q% y% l- v! J8 g( ?4 E
2
4 ^/ P3 v7 p8 ]2 a已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
7 g8 J8 {# I$ ]9 Z1 \$ A9 Z: O5 e; d1 }5 h0 ^
4 O. Q4 N* x3 \5 R
第1趟:72,73,71,23, 94, 16,05,6
' x9 u8 h3 S+ P$ ~第2趟: 71,72,73,23,94, 16,05,68
O, |' p" G9 M3 ^& o; [: V第3趟: 23,71,72,73, 94, 16,05, 68: m( l: F) E* M2 z+ _9 p( l: S' }
第4趟: 23,71,72,73,94 16,05,681 C/ H7 @) z, f, S, h
第5趟: 16,23,71,72,73,94,05,68
0 ]# }4 U8 O5 M& A" U. ^第6趟: 05,16,23,71,72,73,94,68
6 e' U$ G2 T' A; h9 M6 @7 ]第7趟; 05,16,23,68,71,72,73,94
! i2 }# F# m V. D. w# a1 O |