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

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
, A% ]  N0 w4 k4 k- L% L$ P6 y
7 H( T- L( i4 Q6 u6 l0 e一、单选题（共 20 道试题，共 100 分。）V 1.  除第一层外，满二叉树中每一层结点个数是上一层结点个数的
A. 1/2倍
B. 2倍
# g% s3 s0 m% cC.
D.
      满分：5  分
; J2 ?7 Z1 @& T5 t2 ?/ b2.  假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT中的结点有左孩子，则左孩子存放在
9 U/ o: v4 R% {2 @3 g+ o" HA. BT[i/2]
B. BT[2*i+1]
C.
( J9 a4 W  M4 R) @' C; l+ JD.
# U# E( Z# {6 v2 x; x6 ^+ Y      满分：5  分
. T, A- G5 h8 M* S  k7 m' n+ P3.  对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为
5 F( k# c3 Z1 b, Y+ [% a& j$ |A. 求一个顶点的邻接点
B. 求一个顶点的度
C.
, A, m. J/ t& J; s* K# ~0 J; AD.
0 ^0 U  y9 i. P. {3 @$ x      满分：5  分
3 ?1 D: N! d( c. F* d& q1 F4.  已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
- T" m& `2 P: CA. 5
. k0 Y) o/ s$ `" N0 Q# T4 aB. 11
! a5 O; J' i: N$ [, l) Q+ q/ {C.
3 N4 `; P; I$ s" m$ K; lD.
( d( U. K1 u/ F2 K: _  k4 n      满分：5  分
5.  在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
* r9 O, T8 f8 r7 rA. 不一定相同
B. 都相同
C.
4 K- ~' x  g2 y( OD.
+ Z& S$ Y; m4 C' ?$ n5 B. b- ]5 X      满分：5  分
5 N( ]" R1 P# a2 m6.  队列和栈的主要区别是
2 H/ m4 a6 ?9 _) k& I! }A. 逻辑结构不同
+ v5 Z. p1 C+ RB. 存储结构不同
C. 所包含的运算个数不同
9 x) w/ o1 w" A  D: q1 LD. 限定插入和删除的位置不同
0 b. W1 L, c0 H2 y6 \1 }      满分：5  分
7.  设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是
A. (rear-front)%m= =1
B. front= =rear
: E. k. R! B6 M$ P. _C. (rear-front)%m= =m-1
& R, i3 _9 o7 |' X2 y! R4 JD. front= =(rear+1)%m
      满分：5  分
) f/ B. {! N+ B( A4 d3 c. P8.  栈的两种常用存储结构分别为
/ u5 e: p& q+ q& d( y: [A. 顺序存储结构和链式存储结构
/ M# B' Y. N; v7 ^" ^B. 顺序存储结构和散列存储结构
C. 链式存储结构和索引存储结构
D. 链式存储结构和散列存储结构
. k+ Z; J, R" U$ z! M- m* Y      满分：5  分
9.  以下说法不正确的是
2 U' B( h% l& q9 w7 ?A. 无向图中的极大连通子图称为连通分量
+ p( [9 f% r! j7 JB. 有向图的遍历不可采用广度优先搜索
C.
D.
0 u! B* k; ^5 N: N! G. Z      满分：5  分
3 R. R3 F& H9 P- {/ P$ {: U10.  在一个有向图中，所有顶点的入度之和等于所有顶点出度之和倍数是
, {: _0 n) w9 W! ^A. 1月2日
B. 2
5 b, Q. {# y* h/ T: LC. 1
D. 4
$ |* ]% K6 \" V( X6 l3 X6 i, R      满分：5  分
11.  有关二叉树下列说法正确的是
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
+ w0 n- `7 p' b' T' k6 C8 iC.
) i6 R) b  u! I1 T. T9 kD.
      满分：5  分
) b9 a0 k( a7 ^12.  对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
A. 先序
3 a% j' }0 z: y5 h1 y! V) A- Q$ LB. 中序
C. 后序
D. 从根开始的层次遍历
5 T" E, g4 I) _) D3 z6 b      满分：5  分
" ?! K2 t1 i$ _$ Z) z13.  对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为
A. O（n）
+ l1 G4 u; z0 k$ D4 K/ V- JB. O(n2)
C.
D.
' [( n( q* z$ b: b) Z, y      满分：5  分
& q1 ^% o* [% S3 t" F14.  深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A. mk-1
B. mk-1
% i! q! s2 Q$ I6 s0 GC.
D.
* J  \- T* D* W% i      满分：5  分
15.  若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A. 层次遍历算法
2 a# z* P7 Y9 k6 }$ z1 {. t0 v1 qB. 中序遍历算法
+ R6 K/ p$ d! `8 C* h; TC.
D.
      满分：5  分
16.  已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
( k- A; x. s5 \( D. ]7 RA. ABCDEF
B. ABCDFE
% K2 v, F" t& @6 lC.
: {+ j( N) \, h* O" J8 {D.
) ^* E  u! y9 i      满分：5  分
17.  一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
/ H( N: m3 r( n0 |  m- ZA. O(n)
. \( s2 ^4 r. @# b: g& w; ?B. O(e)
C.
5 @' S1 x. v  ]6 y- z9 z" ]: CD.
) z4 ~0 V+ S, ~: k' W      满分：5  分
# }  M6 Y5 ^1 P18.  若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
A. 10
, x' ~3 f- A! C% dB. 11
8 s! U! r2 v! x! w5 n% B; MC.
D.
1 Z7 x$ {" D6 L9 }# ~) l: _# k      满分：5  分
19.  下列陈述中正确的是
A. 二叉树是度为2的有序树
% @/ J: z: V3 F' {B. .二叉树中最多只有两棵子树，并且有左右之分
C.
D.
      满分：5  分
20.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
, T& c7 ^2 b  l& RA. 5
3 T5 r: j( t# HB. 6
C. 16
D. 17
4 Q$ p+ X" n" w, F      满分：5  分

' h+ i$ t; F/ D+ Q% q谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。