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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  无向图中一个顶点的度是指图中
* N# w- d5 {$ u9 q; E' xA. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
$ J1 b/ v# @5 z/ \8 RC. 通过该顶点的回路数
% M6 @8 _" a% P: l6 MD. 与该顶点连通的顶点数
      满分：5  分
2 f, X* [" K( f/ s2.  n个顶点的有向完全图中含有向边的数目最多为
6 [  p. Y- C: ?A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
7 D' o7 t, M! V0 m8 P0 ~      满分：5  分
" S8 I" U* |, Z3.  一棵树高为K的完全二叉树至少的结点是
. G4 B. f& \& |A. 2k –1
B. 2k-1 –1
C. 2k-1
8 B$ q& p. f, _0 }% |/ |2 i0 lD. 2k
0 G5 i& a# ?  M. M) i) B      满分：5  分
8 e5 |: n. n: C4 c4.  在VSAM文件的控制区间中，记录的存储方式为
) I* W; r' Q# z3 k( h6 i" ~A. 无序顺序
B. 有序顺序
* N& s* O; l/ J5 @& a/ |0 sC.
: k5 I' E  x4 g: n. Q( [D.
. S9 K8 z9 n* M2 i1 \      满分：5  分
5.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A. 5
B. 6
C. 16
2 n* Z3 M: Q- n5 w3 a7 G7 fD. 17
/ _# N! k$ \  j2 q* f      满分：5  分
# u6 n# F4 A3 e0 t$ {: M6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
8 ~7 f. z2 u& H: O0 A* ~A. A，B，C，D
B. D，C，B，A
C. A，C，D，B
D. D，A，B，C
      满分：5  分
$ W0 B$ `- f; c7 O6 r5 {7.  某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点
B. 高度等于其结点数
C.
D.
, e, Q, d1 e/ y) P% l( G      满分：5  分
6 C0 J1 J1 ?% u; c; R6 _1 r. D4 p8.  索引非顺序文件的特点是
A. 主文件无序，索引表有序
B. 主文件有序，索引表无序
! S0 Q# W, [# n8 G- pC.
D.
" u8 z. k- ]3 k% M      满分：5  分
9.  在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为
' M( X2 H7 d- H  W; u" e/ eA. Dout
8 @- `. r9 g8 p- D& q- [B. Dout-1
C.
D.
      满分：5  分
' J9 x$ P9 ~- Z$ G1 [& U: C10.  倒排文件的主要优点是
A. 便于进行插入和删除运算
4 T. j5 ?* a  U2 x% V8 v$ g+ d+ RB. 便于进行多关键字查询
C.
' z; s( M% g; m, L. |D.
" d6 g  m. F# w! T, @) @1 t      满分：5  分
11.  ISAM文件和VSAM文件的区别之一是
A. 前者是索引顺序文件，后者是索引非顺序文件
* P' S1 ?$ W* K; W  i  M3 _5 [B. 前者建立静态索引结构，后者建立动态索引结构
$ d" T  x8 j: k1 p, b4 CC.
1 T/ b7 `! {( _& C; Y1 N2 oD.
3 r; `' }. d6 f6 N2 y' E      满分：5  分
" P0 I/ P8 g6 {3 n4 V12.  在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
# }$ Q% ?0 g: F5 R) x+ CA. 1月2日
/ H, q  ~* L" P4 OB. 2
C. 1
: @0 A% L8 I' K8 {D. 4
      满分：5  分
' v6 V% s% l# r% r( X# k: H13.  在分块索引的在顺序表中查找，算法中采用的技术是
A. 穷举法
B. 贪心法
C.
D.
      满分：5  分
& d( A" z* T6 m1 f) v% ]14.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A. O(n)
1 R0 e0 v- [, l! D  U" y4 a, QB. O(e)
C.
1 S1 ?! K- M- @# K" M, G) C+ V7 CD.
3 C& n& M+ R- l9 I$ q6 m$ B9 B      满分：5  分
15.  若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
2 y: x, W. h3 T2 jA. 10
B. 11
C.
D.
) a) F( Z4 q3 T+ b' z& c; Z/ L8 l      满分：5  分
5 C6 v! `2 z( f1 E9 k16.  在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是
6 L% N2 W! E( n4 P$ SA. 快速排序
B. 归并排序
: k0 f; A& s; o  ]0 s7 S- H# ~C.
D.
      满分：5  分
3 x) S) k6 \! F- [; Y/ m3 P) l17.  当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
2 g* v! ^: t" D+ e/ dB. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
0 B( m9 a. F2 c9 mC.
" R2 A9 E9 X( k$ V  f; N$ d/ ED.
      满分：5  分
  m4 Y" v* W" K( ?3 d18.  高度为5的完全二叉树中含有的结点数至少为
; ^& g. g0 M- V( C2 E& bA. 16
B. 17
4 H/ m; T2 c# g; }5 Q0 CC.
% Y4 o6 I0 t# @6 {5 QD.
      满分：5  分
19.  判定“带头结点的链队列为空”的条件是
( s3 s0 G8 N7 MA. Q.front==NULL
' g) q* ^$ p7 l1 q+ |B. Q.rear==NULL
5 Y0 d: h% B6 Q) o, p3 QC. Q.front==Q.rear
D. Q.front!=Q.rear
      满分：5  分
/ U2 R8 I) @. Z. t( ~) L% @20.  二叉树中第5层上的结点个数最多为
* }1 Y' v( W% U. w- dA. 8
B. 16
1 I& t3 \  c/ C9 u6 z9 T" \: g8 FC.
1 z# v2 f9 O' P2 ~D.
      满分：5  分