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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  高度为5的完全二叉树中含有的结点数至少为
1 F9 {( {) G# r7 j, fA. 16
B. 17
1 [" J- A$ G& Y9 h' JC.
& _) R2 a# f( f! S1 ]" P$ HD.
      满分：5  分
2.  ．以下与数据的存储结构无关的术语是
A. 哈希表
B. 栈
% R* h& ?4 I: Z8 }7 @. S, BC.
  e; d- w2 k/ o; nD.
, j( i; t2 d8 J+ @  _4 z      满分：5  分
, [: l0 D" z1 c% J3 }3.  链栈与顺序栈相比，比较明显的优点是
A. 不会出现下溢的情况
B. 不会出现上溢的情况
5 {- ~9 Z: J3 v# O; IC.
D.
* |% Q# J  D, S3 ]/ P      满分：5  分
4.  若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
: h/ v! y0 P! F; L+ @: A, DA. 中序遍历算法
B. 后序遍历算法
# I. Q2 q& d# KC.
D.
      满分：5  分
5.  下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
  w9 ]- r( ~9 xA. 二分查找
2 T+ i0 O0 K. w) l1 eB. 散列查找
C.
D.
      满分：5  分
4 k# X. S' K4 s9 J( G3 ]# j0 e6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
" ]8 n! ~2 T  e% U5 O. QA. A，C，D，B
B. D，A，B，C
C.
D.
      满分：5  分
7.  引起循环队列队头位置发生变化的操作是
: A% r+ `" W1 i" A) V- {3 LA. 取队头元素
B. 取队尾元素
1 d  X) j) |4 Q+ m# s& }' `! ~8 x6 CC.
D.
9 i' f. w3 S5 T) E' u7 b      满分：5  分
8.  一个有n个结点的图，最少连通分量的个数是
& @0 Y5 {. a- F+ T7 A  _A. 0
# K  B7 _; D4 c; c* \0 ~B. 1
9 l$ C2 P9 [9 E+ t$ GC.
; T7 Q7 w" K. h0 y% nD.
      满分：5  分
9.  图的邻接矩阵表示法适用于表示
A. 稠密图
B. 稀疏图
C.
) Y, {6 |/ H; X2 e4 P* o, ND.
      满分：5  分
, ]8 h% S" w" o* y8 N" A10.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A. 16
' u7 z2 U! Z' Z! ^, @B. 17
% r  z5 e0 \3 T" j1 o% iC.
D.
      满分：5  分
11.  队列和栈的主要区别是
A. 所包含的运算个数不同
B. 限定插入和删除的位置不同
C.
. t: [; ~7 O% `9 [6 a; J- lD.
1 d: ^5 R8 x; C      满分：5  分
12.  栈的两种常用存储结构分别为
% e4 V9 D9 |8 R' ]3 C' VA. 顺序存储结构和链式存储结构
+ m* W  q& n# _, ~8 HB. 顺序存储结构和散列存储结构
# ^* S, N9 k6 J1 G  U8 WC.
. ^: g" E6 s+ P& TD.
; |* n/ p* Y9 t1 b      满分：5  分
13.  假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
+ L' P& R$ |! R! KA. (rear-length+m+1)％m
: v/ ]; L/ A6 `% P- O9 nB. (rear-length+m)％m
8 R$ x* I% c! D3 QC.
D.
3 W0 U( b+ M3 b, O' H: C2 F9 R; F      满分：5  分
2 Y/ ?  o) t! y" |, c6 ?3 ~8 O14.  导致栈上溢的操作是
0 o5 g# l5 D9 Y% oA. 栈满时执行的出栈
B. 栈满时执行的入栈
& W% t. g- N: C! l/ W5 QC.
5 }/ Y& m8 l. ID.
% `/ k6 S0 N5 s- y8 t4 m0 B7 u6 }/ f      满分：5  分
15.  在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
A. 队列
B. 栈
, T- w2 Q) h. H  h7 u: ]+ fC.
D.
! S) P3 k3 P) Q& \9 g- y      满分：5  分
6 X. h1 R: V2 Q- }16.  设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A. 4
B. 5
C.
D.
      满分：5  分
17.  假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在
A. BT[2*i]
B. BT[2*i+1]
C.
D.
      满分：5  分
18.  已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
5 @( G* ?* Y& R% E/ z( j5 {+ AA. ABFCDE
( [% t1 Z0 `! v5 V% m, z% c( i% P3 N: HB. ABCDFE
C.
D.
6 n8 q# G/ K* ~  }" K9 P7 q      满分：5  分
# z. t7 W/ z6 D& W, @19.  设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
& a$ \- S9 U$ f' D7 n* m% QC.
D.
8 w" E8 I+ _: f$ N1 B" z      满分：5  分
# |0 h6 j6 \: E0 u! ^3 b20.  n个顶点的强连通图中至少含有
A. n-1条有向边
B. n条有向边
C.
D.
! A0 Z( I/ x) }9 V      满分：5  分