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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  无向图中一个顶点的度是指图中
4 @9 Z" p1 P& ~8 LA. 通过该顶点的简单路径数
6 {; O  `; d% F; S+ }. x( p: v5 {B. 与该顶点相邻接的顶点数
# H, }$ A3 J) p3 d  L% ~+ cC. 通过该顶点的回路数
D. 与该顶点连通的顶点数
      满分：5  分
& W0 i0 ^  t: D7 A2.  n个顶点的有向完全图中含有向边的数目最多为
1 j; e) ^' l: C% x3 S1 H  S  u% k7 CA. n-1
+ X5 p) l5 M! b+ N' D% y! ZB. n
" v( d5 z. y( }# f. I. EC. n(n-1)/2
D. n(n-1)
      满分：5  分
: V2 P7 z% @' c8 u$ Q1 W+ ]3.  一棵树高为K的完全二叉树至少的结点是
A. 2k –1
B. 2k-1 –1
C. 2k-1
D. 2k
      满分：5  分
4.  在VSAM文件的控制区间中，记录的存储方式为
A. 无序顺序
B. 有序顺序
0 C, [+ I; g% ^0 ZC.
% A+ o( ~, W, GD.
1 C2 c# @) v: l! v; n- i      满分：5  分
5.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
6 \5 w; m/ n$ l' C* i% {# }A. 5
. Y9 @% g0 @2 a8 E. zB. 6
C. 16
D. 17
  ?/ W  S: J4 J) D- g, M      满分：5  分
6 c- }# F& p$ I5 r; @6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
" y' a' [( f) H5 N$ vA. A，B，C，D
( M2 a3 j; U; X' _- U; C, c. gB. D，C，B，A
( a( j+ X6 D$ u7 ~+ yC. A，C，D，B
0 [2 H0 w( H; a" v3 E' i# o3 N' f) gD. D，A，B，C
3 f5 M# a  ~2 I. q4 k      满分：5  分
; I. v% p. i( u  y% l7.  某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
' U! T! ~$ Q! Q7 j/ D5 bA. 空或只有一个结点
0 G% i3 ?/ L; ~! UB. 高度等于其结点数
9 g3 T/ T9 \( hC.
D.
      满分：5  分
8.  索引非顺序文件的特点是
A. 主文件无序，索引表有序
  @6 |! C6 V$ e: AB. 主文件有序，索引表无序
: w1 f, n* c" F& Z6 p/ @, P& W+ lC.
# k' G( I: V4 v% QD.
& X  ]5 J" ^, {, ^: R7 {# _# K      满分：5  分
5 d$ [) ^" h. o& w( @* v$ _9.  在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为
$ u$ y# C4 S: F( w- G& q2 X0 d! sA. Dout
  v( k* G$ J/ G3 qB. Dout-1
: }5 D8 h- h3 V& e3 t1 S: AC.
D.
      满分：5  分
* v( d; b2 z3 D2 F6 ?9 h* w10.  倒排文件的主要优点是
0 ^7 K% U; f5 J/ OA. 便于进行插入和删除运算
1 Y; p" w* Q) _5 }: w- U& uB. 便于进行多关键字查询
C.
D.
      满分：5  分
11.  ISAM文件和VSAM文件的区别之一是
: p9 P# W: R0 N1 J; C( cA. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者建立静态索引结构，后者建立动态索引结构
. L' G7 B1 `# ^/ E% H9 QC.
2 g1 m% Y4 r6 Z' ~1 Q: eD.
      满分：5  分
: p; n* x: z2 w: w% E* U12.  在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
9 J5 E" j: Z. C, LA. 1月2日
2 D3 P( E! j: Q. ~( i: RB. 2
C. 1
0 r1 a) `% o: c+ \( h" ZD. 4
      满分：5  分
13.  在分块索引的在顺序表中查找，算法中采用的技术是
A. 穷举法
B. 贪心法
1 K+ o% p3 ~1 a1 E/ i' jC.
D.
      满分：5  分
: y  i  `# W2 p* ^9 r! Q# I14.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
" j  k8 t5 A9 T; {A. O(n)
B. O(e)
3 Z% l, K9 P9 ]: M  XC.
+ E  P9 m$ ^0 E' y& kD.
      满分：5  分
15.  若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
# Z& E6 N$ N( w$ w. P! [A. 10
B. 11
C.
: a* u7 ]7 w: q/ N  J0 eD.
      满分：5  分
& f* Z- M5 e* d3 F* F7 d/ L4 r1 r  P16.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
! A# @8 o( w% `3 W1 ~5 @A. 快速排序
B. 归并排序
8 T, m. k) {5 t$ ]C.
6 M' Y0 W! s  h3 y5 eD.
" p8 ^4 c+ Y1 D8 B# _) e      满分：5  分
) H6 V# v2 e7 h5 O5 J17.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
9 _5 g" x0 Q+ f. h) {( c8 iB. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
D.
! N6 J* M  y+ I* p5 e      满分：5  分
18.  高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
$ }$ s! Z) R0 F3 [. }! z. l; AC.
D.
( w8 F& G7 V  q# ^: U      满分：5  分
19.  判定“带头结点的链队列为空”的条件是
A. Q.front==NULL
  K6 W# B  M' @; ?' V: l$ t) d# SB. Q.rear==NULL
3 B7 d% e4 p3 @C. Q.front==Q.rear
D. Q.front!=Q.rear
      满分：5  分
) i* D& d, P, G" r( B& G! H$ o20.  二叉树中第5层上的结点个数最多为
2 k/ o7 _; J' i/ i, U! cA. 8
B. 16
: x2 s$ l/ W( F/ x2 t2 i/ V# fC.
D.
4 d% u& u' v' E6 U' [6 {      满分：5  分