东大11春学期《数据结构Ⅱ》在线作业二

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  无向图中一个顶点的度是指图中
6 C' i: @* z1 l. J: S, PA. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
      满分：5  分
& T0 u# k. W* m# Z2.  n个顶点的有向完全图中含有向边的数目最多为
A. n-1
B. n
C. n(n-1)/2
5 ^( X1 _' D) T: ?& b" |$ _+ PD. n(n-1)
9 B. E' p+ t# T' o  h      满分：5  分
3.  一棵树高为K的完全二叉树至少的结点是
A. 2k –1
0 i* y/ w' Z' [) FB. 2k-1 –1
C. 2k-1
+ X7 q; |/ y+ r$ @D. 2k
9 ]) x4 {2 M% E: G. M2 C$ G, f2 ~" e      满分：5  分
4.  在VSAM文件的控制区间中，记录的存储方式为
A. 无序顺序
4 f( F; J! H/ u, {1 W4 w. AB. 有序顺序
C.
D.
      满分：5  分
5.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
& w' u- }: X4 H8 \( T; }A. 5
8 h, A3 A: x3 r1 {& [7 GB. 6
C. 16
D. 17
      满分：5  分
( |7 r5 h% d' g/ a6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A. A，B，C，D
3 [2 p' u% }' _/ gB. D，C，B，A
C. A，C，D，B
D. D，A，B，C
      满分：5  分
7.  某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点
B. 高度等于其结点数
C.
, \& r5 x& r7 gD.
      满分：5  分
, d3 a2 A( f. i' j* d" U8.  索引非顺序文件的特点是
A. 主文件无序，索引表有序
B. 主文件有序，索引表无序
) c2 c& e" S" {* xC.
1 g0 A; `" r* |8 y+ ED.
      满分：5  分
2 C0 [! B  H3 K+ T, Y( v9.  在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为
  Q4 [3 k1 O9 A' r7 P1 ZA. Dout
B. Dout-1
' N* J1 f7 {, b; C! O  X  z3 fC.
D.
      满分：5  分
: a/ g& P1 V/ Q) ~5 B: D  l- Y10.  倒排文件的主要优点是
A. 便于进行插入和删除运算
3 `2 V0 V6 n" }- Z, U" WB. 便于进行多关键字查询
C.
' K4 l5 n. R$ k/ a, n' }) J, qD.
* k# d5 l! T$ L7 L+ w      满分：5  分
6 O3 e0 e' B: v# T) m1 ]11.  ISAM文件和VSAM文件的区别之一是
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者建立静态索引结构，后者建立动态索引结构
. d4 p+ `4 p6 P+ U, n, m. iC.
D.
, \8 I( E4 G3 g% i% @6 a* x      满分：5  分
12.  在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
A. 1月2日
. c7 Q8 G: J2 w( G9 o6 AB. 2
' L2 }6 j9 d# LC. 1
0 J. U4 h0 e& D. t5 R1 CD. 4
- a3 K4 t) E3 V' c. a0 E      满分：5  分
7 _( b# f7 o9 V" L- w13.  在分块索引的在顺序表中查找，算法中采用的技术是
A. 穷举法
: j6 ]1 p! ?0 k6 eB. 贪心法
1 r' ^2 e5 `4 b! x( A/ n; }C.
8 v  ?+ |# |/ HD.
2 ~( Q* F$ ]  R' n      满分：5  分
" ?' T' C1 Z2 ~/ k6 M, h3 O& c14.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
0 C* T5 o) h& |, w. |A. O(n)
/ m: l, K8 a8 {" l+ W6 J( a/ aB. O(e)
C.
3 l0 c* }1 H. B) `/ XD.
      满分：5  分
15.  若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
+ C* Z. T3 S- s1 o8 ?& XA. 10
5 O2 q' b- G. W* x7 lB. 11
C.
3 j# f) p5 h" M: |# _5 ZD.
$ _! Q8 d1 d# l. S; s" r      满分：5  分
6 K: @) t/ F9 U7 l16.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
A. 快速排序
B. 归并排序
3 Z7 \& q; j* e( E" I6 fC.
D.
      满分：5  分
, p' U& _9 D. l6 A+ O17.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
  V- C4 Y1 q$ H/ ]* S7 @8 OD.
      满分：5  分
2 e# V# M0 s: C0 Q4 k. N0 }% `18.  高度为5的完全二叉树中含有的结点数至少为
: ?1 K- R( l) z3 ^& eA. 16
  `9 k& {/ h* sB. 17
C.
# p! L  C$ @, f3 d/ }0 o( m2 mD.
6 C% m2 z. ~" S, p" N, G      满分：5  分
19.  判定“带头结点的链队列为空”的条件是
A. Q.front==NULL
B. Q.rear==NULL
C. Q.front==Q.rear
& B  H! l5 g5 r& p5 T- CD. Q.front!=Q.rear
      满分：5  分
20.  二叉树中第5层上的结点个数最多为
A. 8
B. 16
4 T. _2 }4 X$ p. v+ [2 F* _, X3 mC.
D.
      满分：5  分