东大10秋学期《数据结构Ⅱ》在线作业2

百分百晓林

东北大学
10秋学期《数据结构Ⅱ》在线作业二
. f) S' w3 x/ a$ |, q( e/ d单选题
1.n个顶点的有向完全图中含有向边的数目最多为
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
* p! J, m0 U9 B* A8 H资料：D
. A5 Z) W" Q. z! s0 f4 O2.若<vi, vj>是有向图的一条边，则称
A. vi邻接于vj
B. vj邻接于vi
C.
D.
0 M( l) G$ l# K$ f: g' P6 F资料：B
) V5 M1 c  p: x4 w6 |2 Z3.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
) ]* `! I7 B  g! _1 z% NA. n-1
/ ?5 y  u2 T& {# KB. n+l
% X* _$ j' R  E2 v: kC.
6 ?6 h& v4 r! B- ?6 i! v1 `% n6 OD.
资料：A
4.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是
9 L  {+ P- W. CA. (rear-front)%m= =1
B. front= =rear
: B2 H; q% j1 B  x" HC. (rear-front)%m= =m-1
# w0 ?" y4 k& K# s1 UD. front= =(rear+1)%m
1 F" `" ~7 ^; O1 O* L. Y资料：B
" a* V4 b4 M% x# x; Y1 I, u" z" B5.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A. 不一定相同
0 [8 o6 |- O2 D9 j: l' P0 yB. 都相同
/ ~/ I8 `/ ]; h# G4 H* tC.
D.
资料：B
6.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
% m: A( |0 v! x  n7 V/ O  lA. A，B，C，D
B. D，C，B，A
, g. j! |' `4 X" Q3 oC. A，C，D，B
D. D，A，B，C
资料：D
7.有关二叉树下列说法正确的是
  b5 o  p7 Z" g+ v1 S# X8 fA. 二叉树的度为2
6 r7 [0 @/ e5 I( ]. n# KB. 一棵二叉树的度可以小于2
6 A. D/ d% F  {  LC.
2 m9 i& Y& N, S( wD.
资料：B
8.一棵树高为K的完全二叉树至少的结点是
A. 2k –1
" l; n0 C) S  rB. 2k-1 –1
C. 2k-1
2 G6 O, K0 Z. q$ i9 @D. 2k
# x5 o0 E+ D" }' I资料：C
9.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
8 {% W. A9 X. WA. 1月2日
! p) H1 `$ i: _3 v4 lB. 2
C. 1
: e% G* D2 }$ W3 `- v5 cD. 4
资料：C
# \, Y6 f; B4 k# z4 B; [10.连通图是指图中任意两个顶点之间( )
4 p$ ?1 M0 `* i) vA. 都连通的无向图
B. 都不连通的无向图
C.
# L) d, [! r8 q/ u; ]1 v6 p8 @# MD.
资料：A
+ I- k+ Z9 v, b1 @* C- r. X. E) x* P11.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
7 P0 C0 `3 n0 Z* o, @# tA. 5
B. 6
C. 16
D. 17
6 i$ P/ U9 k  d资料：C
. q0 G0 _. A) Y' X$ K12.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
; F/ n* H' u4 R1 u7 x  GA. 空或只有一个结点
/ ^2 L3 ~( h6 i$ LB. 高度等于其结点数
C.
% v- X  X/ D) O: OD.
2 i( g3 n* w1 v  R9 t$ s  P' w3 w资料：B
$ S  J1 M/ V6 X13.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
: `8 d8 o) a2 MA. 先序
B. 中序
C. 后序
4 I; y2 \3 i; yD. 从根开始的层次遍历
资料：C
14.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
& V' E$ o- d! d7 J1 w; {; u  k" QA. ABCDEF
: J) X& u' I$ L" KB. ABCDFE
7 Z6 T* S# H: x* l, BC.
D.
4 W7 @% C+ R/ t2 c资料：B
15.对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为
; e" Q, d. p: X2 m* d8 g/ NA. 求一个顶点的邻接点
B. 求一个顶点的度
) h& b$ v: m& X/ Z1 b( @& a0 [* zC.
- s2 \" {* l; O7 ?9 {D.
6 \& ]4 t6 H5 S# E* R资料：B