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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数
. z! E+ k$ j, k8 S& EB. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
3 v  }/ v6 o3 J$ z5 w" [      满分：5  分
2.  n个顶点的有向完全图中含有向边的数目最多为
A. n-1
- p. F* p6 K$ s0 hB. n
  p$ f& s& a# _3 y$ a% oC. n(n-1)/2
D. n(n-1)
      满分：5  分
4 {3 M9 I0 w8 H4 J& ^3 g- |2 y! ^3.  一棵树高为K的完全二叉树至少的结点是
A. 2k –1
B. 2k-1 –1
C. 2k-1
D. 2k
      满分：5  分
4.  在VSAM文件的控制区间中，记录的存储方式为
/ u" l4 C- ^7 e# w, S  vA. 无序顺序
B. 有序顺序
/ w8 V) j9 f( O, z+ CC.
D.
' `7 z, M2 J/ S" K' |      满分：5  分
5.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
0 m% P" t  F; R' XA. 5
9 [; h. p' _" M% g) C# \B. 6
1 K7 ?- c( S! L3 S4 hC. 16
" a2 {  ^+ W, N0 B# d6 m; U, {5 SD. 17
4 J. e4 N! f6 F8 a* l- x7 \      满分：5  分
6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
8 [, C5 J! v$ m2 `/ D0 KA. A，B，C，D
: p2 E" I; S2 w. S- m6 c6 HB. D，C，B，A
C. A，C，D，B
D. D，A，B，C
  R4 v$ I) _- H8 w* g      满分：5  分
7.  某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
! `* K1 [1 y! R# PA. 空或只有一个结点
B. 高度等于其结点数
C.
D.
0 f% s* [- Y2 g4 y      满分：5  分
8.  索引非顺序文件的特点是
; o& z9 d# ~" H, y# ^A. 主文件无序，索引表有序
" `9 E+ N/ o/ h7 C9 I, F' R) WB. 主文件有序，索引表无序
C.
/ S* s! F: F8 U, [) e6 C$ L# \D.
      满分：5  分
9.  在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为
! V7 Y  {, W+ k; t0 zA. Dout
B. Dout-1
C.
2 C5 N5 _2 x0 Z# U1 o" \% v6 hD.
      满分：5  分
5 r, K$ A/ B3 V& i10.  倒排文件的主要优点是
A. 便于进行插入和删除运算
4 B+ g  W' Q( C% v" X7 l" k) f2 O0 eB. 便于进行多关键字查询
C.
D.
& \9 g5 s+ Y! w2 g9 H; r* Q      满分：5  分
11.  ISAM文件和VSAM文件的区别之一是
6 D) E/ G6 _! Z- B6 w1 u) w3 y6 gA. 前者是索引顺序文件，后者是索引非顺序文件
9 h2 ^9 B8 E! Q( H) uB. 前者建立静态索引结构，后者建立动态索引结构
C.
D.
8 u) v2 y; H1 A- @: }      满分：5  分
12.  在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
/ U3 R" E+ a& `A. 1月2日
! i( ~5 H' {! Z$ k* N8 OB. 2
C. 1
) {: H# ~% D4 L+ F9 ?1 \+ pD. 4
      满分：5  分
4 }; x7 z  O0 T1 e4 H: Y& F* ~13.  在分块索引的在顺序表中查找，算法中采用的技术是
3 i) v! p; J1 r# w8 [6 f8 r! uA. 穷举法
B. 贪心法
C.
D.
      满分：5  分
5 y# J% ]/ N" y  C5 ~, ?14.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
7 N( i5 J) F  g# f! r) }" [A. O(n)
$ e- W; d1 @) Q7 R* h" @. v! ZB. O(e)
C.
: d  F3 q  ~  f" ^- @* |, \D.
0 v  k2 ^4 ~. p  r      满分：5  分
15.  若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
A. 10
B. 11
/ g- g9 e6 N: S& U  ?6 kC.
D.
& F& L2 i4 L* ?( j      满分：5  分
16.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
A. 快速排序
6 x+ O1 D% O1 ]* v- g4 Q3 j  ?$ V6 FB. 归并排序
. g- `( j  H: M6 ~C.
D.
7 q/ _& N5 I9 S, f      满分：5  分
17.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
$ a% G) f& N* O0 w, JB. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
! }0 a7 J4 h; \+ U& T, ~! ~- G6 Q. aD.
6 V% ]7 g0 @/ a8 `8 r      满分：5  分
18.  高度为5的完全二叉树中含有的结点数至少为
8 Y0 f6 |4 I) ~( uA. 16
B. 17
1 G: V+ d1 w2 a3 w( pC.
' n) B) K. n/ ?( @0 FD.
      满分：5  分
19.  判定“带头结点的链队列为空”的条件是
A. Q.front==NULL
B. Q.rear==NULL
  L: x1 Y+ _4 [! @! ~# ~C. Q.front==Q.rear
D. Q.front!=Q.rear
      满分：5  分
20.  二叉树中第5层上的结点个数最多为
A. 8
, m6 T. Q) W7 r9 T4 C6 MB. 16
C.
D.
# D) d1 r) z2 Z- d9 |      满分：5  分