设有升序排列的线性表(2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41),用二分查找法进行查找。1)画出查找关键字27的过程;2)画出查找关键字11的过程;3)计算该表在等概率的情况下查找成功的平均查找次数为多少?( K$ I/ `9 [4 k, n
) R! h4 O1 ]5 Z! _5 I# c9 f
3 W# L% ]* {7 j5 C# v8 X- p% u初态:[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]8 R1 P# z3 t7 ?. ?. ?
第1次:[2, 4, 7, 10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
' r3 B( S, ?% {- ?5 N- l第2次:[2, 4, 7], 10, [12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
$ V9 ^+ W; g$ J6 C6 g2 {第3次:[2], 4, [7], 10, [12, 16, 18], 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]0 X" w. B4 b2 K
查找成功。
4 I f0 T: I( Y2" @) T% [- _; [. `
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
}5 W" J8 k( v% G" E+ ^) V
- Q9 A, C* Y( o/ V4 c9 e( [" [3 u
/ \1 s0 U9 j) O4 D( H- L7 E W第1趟:72,73,71,23, 94, 16,05,6
! k* P4 t2 |! q4 P Z第2趟: 71,72,73,23,94, 16,05,68
# U1 l: @& Q% n* Z; i第3趟: 23,71,72,73, 94, 16,05, 686 ?, z3 M; q, W# g0 T; C
第4趟: 23,71,72,73,94 16,05,68
+ D8 v( l9 z. X4 L# f% r" _& p第5趟: 16,23,71,72,73,94,05,68, d% U7 P" |$ f/ T
第6趟: 05,16,23,71,72,73,94,68
. ~; S" j0 b. r第7趟; 05,16,23,68,71,72,73,948 j$ t/ g. i# ]: p! o8 h, \0 ^
|