设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?4 v5 P/ e o9 [
: E1 ]5 @4 O) A& L! {
# J, ?+ U: A) E' `# `( o# M初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
: F O1 G4 ?" I8 E第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
4 o, v: | \+ B( a第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
, K0 Y+ x- ^/ O! I第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]% y3 P& F1 N. Z* [" Y( Z; n: m
查找成功。* k% b- {/ s, f" ^1 @# ]& j$ p
24 {! G9 i& P( f( z; v; U7 X6 j$ U
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
! I- Z! Z( |- z( K, B
8 g. z9 z5 U# b% o* m7 f3 Y4 q" _ l( x- a' V7 v
第1趟:72,73,71,23, 94, 16,05,6* Y5 P* z% n* l' c/ N
第2趟: 71,72,73,23,94, 16,05,68
) ^" H; s0 M6 z4 F5 l( n. H第3趟: 23,71,72,73, 94, 16,05, 68
; p& B. ^# o+ W! S第4趟: 23,71,72,73,94 16,05,68) w+ L# ^% A; l& v. _0 y, f
第5趟: 16,23,71,72,73,94,05,68
2 j X' _6 u$ H第6趟: 05,16,23,71,72,73,94,683 C( e( ^' A) h, m
第7趟; 05,16,23,68,71,72,73,94 m0 x# h, w% S S
|