东北大学12春学期《数据结构Ⅱ》在线作业3

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
1 O: b2 m+ G& K# o* N1 m
5 Q! G$ L" Y0 \9 b' s一、单选题（共 20 道试题，共 100 分。）V 1.  下列排序方法中，稳定的排序方法为
A. 希尔排序
- H+ f4 O, C- o9 QB. 直接插入排序
/ n% E# F3 Z0 i8 r" k4 G4 F5 RC.
0 x* T2 h& D4 s5 dD.
8 L) j; O  _" a5 G      满分：5  分
% w/ n3 ^; D$ i2 V' X2.  采用ISAM或VSAM组织的文件是
# f+ o! c6 M! i* |" YA. 索引非顺序文件
0 O2 m3 ?3 J0 b1 e! y/ T! M7 [6 t1 U9 lB. 索引顺序文件
& E1 P' s& V, F* K" aC.
1 d* Q6 ?; Y/ Q2 @D.
      满分：5  分
! x5 `' m, M# ?  ~3.  已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
7 g; ]. A0 i' M5 a! u( JA. DEBAFC
) B; X6 Q/ [: _+ F$ e' [3 j  x( DB. DEFBCA
C.
D.
      满分：5  分
4.  下列编码中属于前缀编码的是
A. {1,01,000,001}
B. {1,01,011,010}
6 c) Z+ ?, U- c, @C.
3 H9 t' b. q! sD.
  e2 m1 \9 q3 U$ z; j9 b9 ?$ H4 g2 L      满分：5  分
5.  对于哈希函数H(key)=key%13,被称为同义词的关键字是
A. 35和41
B. 25和51
C.
+ E' E$ Y) Q0 c% [D.
      满分：5  分
& p$ B1 N$ \# c! |: I6.  在下列各种文件中，不能进行顺序查找的文件是
A. 顺序文件
B. 散列文件
C.
/ X- K5 {( U% b% x* `2 UD.
; g$ x% l" m+ Z4 c$ x: w- v      满分：5  分
7.  在分块索引查找的索引表中查找，算法中采用的技术是
A. 穷举法
" S5 r( m+ b. V) {1 O$ @2 F: A' kB. 贪心法
; d  ^3 m) ]; c0 v8 [& @C. 分治法
: W9 ~2 Y( o9 r2 i  u5 o& u4 ^$ P( dD. 回溯法
      满分：5  分
9 b3 O. {, R) F8 f) n8.  稠密索引是在索引表中
A. 为每个记录建立一个索引项
B. 为每个页块建立一个索引项
1 @6 Y+ ^$ b! w7 N2 [6 zC.
D.
: m& t* l* c. m4 Z  S: U  B      满分：5  分
1 V5 u2 Y$ I5 g3 [: i9.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
8 F# k, _# W; Z' bA. 快速排序
B. 归并排序
C.
D.
+ N4 S$ u2 K6 M      满分：5  分
10.  下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 分块查找
) R4 t, {9 P+ Q' x+ ?3 [B. 散列查找
: _- _2 Q1 `. ?C.
) J/ l/ }6 \2 Z- z' dD.
4 u. v8 r$ {' H$ K      满分：5  分
11.  下列关于AOE网的叙述中，不正确的是
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C.
D.
* c8 f; V" H5 w/ o/ A$ W      满分：5  分
12.  对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为
A. 123,145,298,314,486,000
B. 508,314,123,145,486,000
7 H3 n8 G0 r3 r% V) VC.
2 p0 V! o0 o1 n5 M) {+ P- @1 G% mD.
% V" d' |/ T" w7 ^6 p8 S      满分：5  分
3 A. H1 c) a7 A0 J7 d% u/ H0 l13.  下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是
, _- s  H$ z) e1 @; w: }5 B  q. b- LA. 堆排序
/ H7 G, m9 c) M8 @B. 直接插入排序
. u0 f" ?$ t" I( {7 bC.
D.
- s) {/ h, I3 Z0 d" `" i      满分：5  分
0 i; v" v4 K) x% y2 I14.  已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
% h9 S7 l6 g8 h" s' _3 r+ uA. T[2]
: H! X. b4 ?. h5 E) ?B. T[8]
C.
, G* E% ^# W* O9 d% xD.
      满分：5  分
5 W. l3 T8 c: y& F) Q( D4 k6 Q15.  ISAM文件和VSAM文件的区别之一是
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者建立静态索引结构，后者建立动态索引结构
. L! a" a$ X+ N& sC.
D.
      满分：5  分
16.  在VSAM文件的控制区间中，记录的存储方式为
A. 无序顺序
5 s2 h* w8 q8 W' EB. 有序顺序
% g1 s; `7 n3 E( BC.
D.
. F  g/ k" m% f0 x' @4 c, w& N7 w- d& l      满分：5  分
17.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
D.
9 t0 y; J' M' l  f      满分：5  分
& g5 q2 g' C9 A1 S18.  可有效提高次关键字查找效率的文件是
A. 顺序文件
B. 倒排文件
6 q( ^3 f% s. x) J& ?C.
D.
      满分：5  分
19.  根据数据元素的关键字直接计算出该元素存储地址的存储方法是
% S' U- C* P/ P- XA. 顺序存储方法
B. 散列存储方法
, y9 F( G, t: e5 j  F, ?9 [C.
* _# p( c/ c4 g& OD.
      满分：5  分
20.  求解最短路径的Floyd算法的时间复杂度为
* [: i; U# x1 R: aA. O（n）
B. O（n*n*n）
C.
D.
      满分：5  分
2 p/ ~1 ~! J. \% Q9 s
; Q- s2 i! ?8 R0 }谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。