东大10秋学期《数据结构Ⅱ》在线作业3

百分百晓林

东北大学
# _7 X+ R5 y6 B10秋学期《数据结构Ⅱ》在线作业三
单选题
1.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
/ r+ E, {* w2 @4 o/ @. Y! vA. 分块查找
B. 散列查找
C.
# |, i7 o! z3 G) QD.
% B/ m. \! X/ d: U2 S9 X; A8 [0 b资料：B
9 W, X) ^" g- r* z! m0 n2.根据数据元素的关键字直接计算出该元素存储地址的存储方法是
A. 顺序存储方法
B. 散列存储方法
C.
D.
- x" r0 f+ U7 n0 Q+ s) S: [. y资料：B
0 S5 K6 V) _  e- v3.求解最短路径的Floyd算法的时间复杂度为
A. O（n）
B. O（n*n*n）
C.
D.
资料：B
1 O5 z9 T$ H& Q. Q0 ]$ [4.ISAM文件和VSAM文件的区别之一是
' \7 a/ V( e0 c# b& O1 Y  |A. 前者是索引顺序文件，后者是索引非顺序文件
9 t$ d( Q# U: Y- \; C# `* T8 _B. 前者建立静态索引结构，后者建立动态索引结构
C.
3 q/ S( j3 N1 mD.
7 S. k! D: ?$ a' o; K7 ?资料：A
& Q# c9 E( o3 X3 F) i+ q( U5.下列排序方法中，稳定的排序方法为
A. 希尔排序
8 b6 Q& @4 K* UB. 直接插入排序
C.
+ s9 p. z+ q9 Q8 M9 AD.
资料：B
6.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
5 g1 Q, O  q  w6 [& OA. 21
B. 41
) ?& C& J" v- P( b; ~' V2 k, UC.
( j; I  ^% T9 W; t9 {  ]D.
) {0 E. X8 n5 {! \: s/ u# I. Y资料：B
7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是
A. 堆排序
B. 直接插入排序
C.
, G$ p  o- l8 T" n& c' }" O, FD.
4 _" i9 a* C  X资料：B
8.倒排文件的主要优点是
A. 便于进行插入和删除运算
7 H! w2 I% B. \% A/ ?5 K# ZB. 便于进行多关键字查询
C.
, U. o" A+ ^9 K9 r' DD.
8 m4 g- t7 A# u- w2 @# y资料：B
$ D$ s- H  Z' ~9.采用ISAM或VSAM组织的文件是
A. 索引非顺序文件
8 Y5 Q( `# ^3 UB. 索引顺序文件
+ b( q, s) y( \! l2 mC.
/ P& |# k5 z- d% n( C: Q) jD.
资料：A
& [. B* x: s( e$ u' k10.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
. b7 m9 C( p' _* ^( O2 nA. 8
/ A5 y; r# A6 u9 s! W% N0 hB. 3
7 ]3 x8 w8 }% ?, ^5 @, KC.
- e( w5 R/ f) D, bD.
( U3 C4 R# F' g5 c- |0 _资料：A
/ o. l: j4 k& p" t- c! k8 P11.对于哈希函数H(key)=key%13,被称为同义词的关键字是
A. 35和41
0 z; G) k' j2 v7 ZB. 25和51
  a, N( B8 L# H  B2 O" xC.
D.
资料：B
12.下列编码中属于前缀编码的是
4 {  e" {9 `% T; KA. {1,01,000,001}
. Q% l  }% f; H' [B. {1,01,011,010}
C.
D.
资料：A
: i/ {; m) x3 O. I9 e1 z# _0 v13.稠密索引是在索引表中
A. 为每个记录建立一个索引项
8 E; l/ H4 m9 NB. 为每个页块建立一个索引项
C.
D.
- c7 |' G: d1 f4 r( I资料：A