设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?
+ ?- x! q) \( d! d9 _, ^2 F) @1 ?9 I: o% N( y
6 i* b/ M$ [5 H- s初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]8 B% q1 K+ K8 `- h
第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
* }/ O) z9 q3 u# l9 r( z' `$ o: `第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]6 D( ^, k; u/ }
第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
0 E6 d3 B8 J8 T, @% v3 w) ^1 u查找成功。/ f5 l( u1 r8 _* e+ @5 s
2
; y) }0 b) R% b已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
( x( H. b8 o3 R5 s; A }5 ?0 y1 {5 o* G3 v' Z ~
3 j8 M2 \& [, H$ F, Z% W4 E& e
第1趟:72,73,71,23, 94, 16,05,62 C2 v% H- s P6 u- n
第2趟: 71,72,73,23,94, 16,05,68- P% ]7 E! @% E8 o" c& N9 p
第3趟: 23,71,72,73, 94, 16,05, 68 I3 B. b0 N$ `- A2 m" ?# n
第4趟: 23,71,72,73,94 16,05,68
V4 r8 C( Z, t$ ^/ g第5趟: 16,23,71,72,73,94,05,68
( ?+ T6 X0 x/ `4 v3 D5 P第6趟: 05,16,23,71,72,73,94,68
s8 e. J+ w7 V第7趟; 05,16,23,68,71,72,73,94# A2 T- h1 |! d0 g
|