东北大学11秋学期《数据结构Ⅰ》在线作业资料2

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
2 v" L1 Z! F8 I, t$ x, GC.
D.
      满分：5  分
  ]7 e, ^& p, J8 a2.  ．以下与数据的存储结构无关的术语是
A. 哈希表
B. 栈
. z/ X( M7 d) L6 R8 SC.
D.
: O2 g$ X' z! g      满分：5  分
3.  链栈与顺序栈相比，比较明显的优点是
A. 不会出现下溢的情况
$ _. f# j) O- j: {2 GB. 不会出现上溢的情况
C.
0 Z$ v. [3 D) nD.
      满分：5  分
4.  若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
9 ~2 ^8 L7 _8 P0 aA. 中序遍历算法
0 N& ]9 @' N2 F; ]/ `% lB. 后序遍历算法
8 @  o5 H, Z/ hC.
D.
5 L. L: V' f* m3 B      满分：5  分
) C% p# N" `- D1 _" R' P5.  下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 二分查找
B. 散列查找
: P# }0 r! \& m) _! f* \" y) }C.
D.
; J. J$ y) n$ C- v- H  x1 I      满分：5  分
6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A. A，C，D，B
) l7 X3 p7 s+ A8 i% h. K4 g7 FB. D，A，B，C
) G& S* c$ ], h  _. @C.
. a! Z) V$ R  \$ W" `4 H9 p0 R: OD.
9 U, m. B; ]$ n/ F: u# ~# }      满分：5  分
1 x. E# p2 i2 b. @/ B7.  引起循环队列队头位置发生变化的操作是
+ a. b0 o9 l4 W3 QA. 取队头元素
B. 取队尾元素
' b3 \% d+ a! t; S. A& mC.
) h6 [9 `" {9 j: fD.
' M& ~! X9 X$ c' J      满分：5  分
8.  一个有n个结点的图，最少连通分量的个数是
" i  i" U* C+ {A. 0
B. 1
: D, ]) S+ [2 G+ ]( B+ jC.
D.
      满分：5  分
* e1 L, l5 y  Z! M+ X* U9.  图的邻接矩阵表示法适用于表示
9 H4 e2 T* f: k( y" J3 G6 X& }8 dA. 稠密图
B. 稀疏图
$ Y- v% {2 l( w, Y! o4 j$ ]: mC.
D.
, [% f6 `) P1 [: C      满分：5  分
10.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
/ x3 h0 m' M% i: N% ]A. 16
B. 17
& \. _* @. T1 g& C- B% e. gC.
* c" C1 N+ q  c' u9 ]+ tD.
8 R9 z- M  d5 d: @- T      满分：5  分
2 w- B( @0 A" o" _1 w- h11.  队列和栈的主要区别是
A. 所包含的运算个数不同
B. 限定插入和删除的位置不同
C.
D.
$ I3 D9 d$ {1 r0 I! k9 |      满分：5  分
) Z% U7 Z2 K/ N8 n: j7 o12.  栈的两种常用存储结构分别为
A. 顺序存储结构和链式存储结构
/ z, @" y$ e- C& j) FB. 顺序存储结构和散列存储结构
2 [4 |- q; [3 ?8 i* MC.
/ N  ?3 F1 t" A  u% c& bD.
* u0 @6 w3 [* H" d4 Q      满分：5  分
. c! w# I2 p7 \) X5 N1 G7 I13.  假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
5 x$ Z, x  Z( B7 lA. (rear-length+m+1)％m
B. (rear-length+m)％m
C.
; @# b* ~1 N% G2 R: b3 {# z/ h5 L4 ?D.
' k0 F) t3 ^- w0 N* e      满分：5  分
' l1 }: @4 O" r: S14.  导致栈上溢的操作是
A. 栈满时执行的出栈
B. 栈满时执行的入栈
C.
- e' A2 q  [# F6 A2 K0 `: ^' `D.
      满分：5  分
! j9 L  w$ b( F, x15.  在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
A. 队列
B. 栈
C.
D.
      满分：5  分
16.  设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
1 e; s% C2 V8 E3 U; a* D: }# @) NA. 4
3 T' E5 z' X& Z# |1 c# l8 }B. 5
+ s) }! U( d; ]$ cC.
D.
      满分：5  分
" b+ I% o" t6 z6 S2 q" }+ i17.  假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在
5 I) Q* _" j7 C; H  KA. BT[2*i]
B. BT[2*i+1]
0 x3 y7 q3 K3 h) {9 c/ J/ tC.
) H+ C+ t+ ], LD.
      满分：5  分
; x0 U; X4 I, Q0 t18.  已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A. ABFCDE
B. ABCDFE
C.
D.
! f: ~- t  _; s      满分：5  分
19.  设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
, X7 v1 b. x/ K( J8 _* p6 HA. 2
B. 3
9 r. @9 S0 ~- zC.
D.
5 O; y. u4 J9 o% t7 r      满分：5  分
0 N8 U! B/ f, f2 l: O20.  n个顶点的强连通图中至少含有
& N7 T2 A. b5 T  ZA. n-1条有向边
B. n条有向边
' M: u6 r0 Q* h7 ?C.
D.
      满分：5  分