设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?
, J% r6 x" P& S$ G) C% O" h% l- x$ V# p9 m7 N* a* i
' @% j$ {( N0 `5 n1 @7 y初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
' Z5 y; ?8 X$ k. E; W5 _3 ~第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]; w4 O/ C" N/ b' h% i
第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
" h7 n4 h3 U$ J& _$ N3 e7 f( s. k4 r& z第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
+ B' h' D/ @+ U" w查找成功。
% g" w6 t) d' Z0 k" O2
( l+ T% E+ D. Z+ P# j, S6 Z7 E已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
3 G; P$ n' E- R! z
8 O1 z# c" ]) F _" a! Y* I) a2 x8 R
! K! \2 A* C# Q( y5 y$ o7 X5 w第1趟:72,73,71,23, 94, 16,05,6
$ u1 t B( x2 S0 T第2趟: 71,72,73,23,94, 16,05,681 O' @, F8 d! q; c( a$ R
第3趟: 23,71,72,73, 94, 16,05, 68+ F, h. h8 s& f# n8 i3 i
第4趟: 23,71,72,73,94 16,05,68
5 ] k' d& Y. x0 x3 B& C第5趟: 16,23,71,72,73,94,05,68
0 j, u* ~% s u第6趟: 05,16,23,71,72,73,94,68 G+ l6 ?* w& ^' ^5 D2 _/ R
第7趟; 05,16,23,68,71,72,73,94/ R9 O1 w% Y# F
|