《数据结构》期末机考

川农在线

1
  E5 Y* _7 i$ C已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
( R  Y0 Y2 Q6 F5 H[68 05 71 23 16] 72 [94 73]
[16 05 23] 68 [71] 72 [94 73]
+ N8 y4 Z! r. z' R( W& S[05] 16 [23] 68 [71] 72 [94 73]
05 16 [23] 68 [71] 72 [94 73]
! \1 ]; R. ?* ?05 16 23 68 71 72 [94 73]
4 ]( i1 L7 K5 e& T/ j2 b8 ^; f6 f9 \05 16 23 68 71 72 [73] 94
" w/ \" \& b* Z05 16 23 68 71 72 73 94
6 X# t: s2 p  W/ ^8 }2
设有升序排列的线性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），用二分查找法进行查找。1）画出查找关键字27的过程；2）画出查找关键字11的过程；3）计算该表在等概率的情况下查找成功的平均查找次数为多少？
+ k- y& G+ ]1 P: T6 M初态: [2, 4, 7, 10, 12, 16，18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
! u+ o4 I1 k- S4 v4 C: ]# m0 [第1次:[2，4,7,10, 12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
5 H! I; D) W7 X, C第2次: [2, 4，7]，10,[12, 16, 18, 19], 20, [24, 27, 29, 30, 35, 36, 40, 41]
6 I: B* X5 Y" k6 u第3次: [2], 4, [7]，10, [12, 16, 18]，19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
5 O' |  C5 O9 N$ h1 G; K: e查找成功。.

" k! ~& K+ w0 m# f; o" `) [# V0 h% j