《数据结构》期末机考

川农在线

1
7 K" @2 ^" N' T3 X. [6 a* [$ l) U5 {已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
/ Q; I' r! u) Z$ f& T[68 05 71 23 16] 72 [94 73]
- E8 d. a& K7 P8 o, ?! ^$ U[16 05 23] 68 [71] 72 [94 73]
# H# Q3 t4 A" h; f$ F- S/ f# n! d9 m[05] 16 [23] 68 [71] 72 [94 73]
4 S* E' O4 y# X6 r05 16 [23] 68 [71] 72 [94 73]
8 w2 L' {# y# k4 S! F05 16 23 68 71 72 [94 73]
; G: u4 r/ d7 f+ y( B' R, b, |05 16 23 68 71 72 [73] 94
8 ~) _$ i7 Y' N3 q4 B. }% B9 R7 z05 16 23 68 71 72 73 94
* ]/ s0 ?( L# k+ g" ?2
设有升序排列的线性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），用二分查找法进行查找。1）画出查找关键字27的过程；2）画出查找关键字11的过程；3）计算该表在等概率的情况下查找成功的平均查找次数为多少？
初态: [2, 4, 7, 10, 12, 16，18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
$ Y  W4 i5 X! [6 E: L第1次:[2，4,7,10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
第2次: [2, 4，7]，10,[12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
第3次: [2], 4, [7]，10, [12, 16, 18]，19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
/ b  F/ f; W( P查找成功。.

' B2 X; w( Y  y