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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  下列排序方法中，稳定的排序方法为
A. 希尔排序
8 [/ v$ N" e4 w! g' I! Z( v; N" mB. 直接插入排序
C.
D.
      满分：5  分
- y( }4 Z+ G5 ]5 p1 n2.  已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A. DEBAFC
B. DEFBCA
C.
D.
      满分：5  分
' M1 V- A3 p1 x" I% X3.  在分块索引查找的索引表中查找，算法中采用的技术是
A. 穷举法
B. 贪心法
6 i& g: w% u) ]5 V* S4 v- RC. 分治法
+ H( }" ]$ ?1 l/ Q. w( sD. 回溯法
; i5 x% G7 M; \      满分：5  分
/ k( H) r$ k- j+ O+ ^: v" q9 m4.  对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为
1 z) r/ @: B/ \. r5 hA. 123,145,298,314,486,000
B. 508,314,123,145,486,000
! u: F2 {  x& iC.
D.
      满分：5  分
5.  下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是
A. 堆排序
B. 直接插入排序
C.
% f6 X$ V- Y2 k& ?5 \D.
      满分：5  分
5 c9 U! a0 S8 _  K) }) V# [$ h+ e6.  下列编码中属于前缀编码的是
A. {1,01,000,001}
B. {1,01,011,010}
C.
D.
/ d2 n- g2 p* E) D& v      满分：5  分
: j# W, P" c" z. x* a! A. z  y7.  稠密索引是在索引表中
A. 为每个记录建立一个索引项
B. 为每个页块建立一个索引项
( \5 d* f% p6 U2 H7 K5 n, W2 [0 LC.
" W3 V$ b! \4 m+ l0 qD.
      满分：5  分
' I5 o" m) z) Y9 d8.  在VSAM文件的控制区间中，记录的存储方式为
A. 无序顺序
( P; _9 T2 i  Q7 d1 t/ qB. 有序顺序
+ {& \$ a' \3 U. L7 p1 d& A; mC.
" k  `. u$ |* b% p- FD.
+ r+ e4 a; ]1 R7 t% u  J& K# Q  k      满分：5  分
- B& u# \6 y, l2 i' p3 H0 d/ q9.  采用ISAM或VSAM组织的文件是
A. 索引非顺序文件
4 A$ U: L1 i: P/ _0 m* ]# jB. 索引顺序文件
C.
) j' n! W, o! G' \  N8 h0 tD.
      满分：5  分
10.  已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
+ T! J( J* O0 H- ~! c% J' MA. T[2]
B. T[8]
; I5 D- e" L- @( ]% OC.
$ m  c& ^- Q, R. r  Z+ U. P* SD.
7 p7 L/ _* h5 h" L3 `% N; R" z      满分：5  分
8 c4 _- J* m- Q3 u" L7 x11.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
( Y5 L" P8 z) Z+ m+ e" n; |C.
5 w7 e4 S- Z" fD.
5 G9 R5 w' Y6 S5 A      满分：5  分
12.  在下列各种文件中，不能进行顺序查找的文件是
A. 顺序文件
  |+ _# g$ y( |' t1 D: t1 Q5 \B. 散列文件
% ?/ z' C, W5 _# c; J% LC.
D.
1 x* Z! U$ P) J5 ]" M) k      满分：5  分
) i$ ~+ O; X) E13.  下列关于AOE网的叙述中，不正确的是
; T( V; |4 x) V% J1 v& FA. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C.
D.
      满分：5  分
$ H) @7 z7 h: |6 K# H1 X3 D9 p14.  根据数据元素的关键字直接计算出该元素存储地址的存储方法是
A. 顺序存储方法
B. 散列存储方法
C.
  z) T( C2 ~4 bD.
/ u+ c" w" g! \; h, K      满分：5  分
3 I9 ]& \% i8 a. ^) [* D0 Y5 r15.  ISAM文件和VSAM文件的区别之一是
# F4 m. Z/ Q3 }, N( s- l2 o. oA. 前者是索引顺序文件，后者是索引非顺序文件
" N: n$ |& N: U' g" cB. 前者建立静态索引结构，后者建立动态索引结构
0 i3 P4 a" e) U/ c& q2 kC.
" N$ R4 i; F: O# O) QD.
      满分：5  分
5 X; n" v9 z2 O8 C" K16.  可有效提高次关键字查找效率的文件是
A. 顺序文件
B. 倒排文件
C.
/ C+ [7 w5 R4 \- `" h, K- nD.
$ ~7 v4 p: M& t1 k5 Y      满分：5  分
! H2 }9 e$ A6 X; Q" x  @5 n8 Z  J17.  设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
* Y2 ?) _- V9 G2 K: K$ r6 GA. 8
8 V" u$ X# S) q+ |1 r1 l% L1 ^' kB. 3
C.
D.
      满分：5  分
4 V9 b# ]  h* n( q. h3 |18.  在分块索引的在顺序表中查找，算法中采用的技术是
4 N2 X' P' y# |6 K* Q* lA. 穷举法
: X% A" V' W; F" n1 \4 A- h5 S6 U* nB. 贪心法
C.
, u& ]0 e) D' a- bD.
2 K; r6 S2 j! k7 \2 j      满分：5  分
19.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
% s1 ^) ^* o2 [1 |5 JA. 快速排序
* E& ~# P, w4 j# M7 w1 L# bB. 归并排序
/ U  ^1 H9 i3 c3 C) w0 f/ _: _C.
$ v! |/ h( W  Q3 DD.
/ i/ Q4 s- O: R      满分：5  分
' \. f& z6 Y- W$ Y+ Z$ ]3 _20.  对于哈希函数H(key)=key%13,被称为同义词的关键字是
3 i! c9 G2 L6 l; t) A' O2 U; bA. 35和41
B. 25和51
C.
. y# H9 u; _5 K( jD.
      满分：5  分

需要满分标准资料请直接加QQ :1306998094