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

久爱奥鹏晓林

一、单选题（共 20 道试题，共 100 分。）V 1.  高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
  y9 f1 V& S  p1 v! u; PC.
D.
$ J& g: U7 b6 \' R; l      满分：5  分
2.  ．以下与数据的存储结构无关的术语是
A. 哈希表
% A* Z; W8 G/ ]B. 栈
( ]8 X% N' q* {0 E+ @8 o: J& A+ lC.
! Q  L2 D, o3 E* a8 O7 @$ MD.
      满分：5  分
3.  链栈与顺序栈相比，比较明显的优点是
" |4 Q+ m; m" a' ]& yA. 不会出现下溢的情况
( M; S4 K( E* N. H- j  x* }  a+ UB. 不会出现上溢的情况
! K, x5 s' T3 @7 I2 J( nC.
" P! m" Z2 ]0 b/ d, R" N# [3 cD.
      满分：5  分
4.  若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
  C2 A; l5 C& lA. 中序遍历算法
1 t2 u; W3 ^! i7 g: e& tB. 后序遍历算法
C.
D.
0 `! x: ]: Q% B, R4 z0 g      满分：5  分
5.  下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 二分查找
B. 散列查找
C.
! v1 H+ t3 I  G+ U% K( ?. N8 MD.
$ }' k$ N) T5 h, I" U5 l1 x$ D      满分：5  分
6.  设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
# M, z) F8 c5 e$ L3 o5 N  UA. A，C，D，B
; }  H2 q0 ~0 }  Y" FB. D，A，B，C
0 v- l* n5 t0 Y0 J! Q0 LC.
9 c3 U$ U3 E6 y" j0 }4 U" F( ]6 zD.
: w( j% ^5 j/ d2 U; ?      满分：5  分
: u# b* A: p' o1 Y6 Y; ?3 |7.  引起循环队列队头位置发生变化的操作是
A. 取队头元素
B. 取队尾元素
C.
. r6 k4 s" u' b( h( A% U3 Z1 k# pD.
      满分：5  分
* n: ?- U" j9 ]8.  一个有n个结点的图，最少连通分量的个数是
$ H# V8 I; ?4 P  ~/ N1 f3 WA. 0
B. 1
C.
5 [& w9 ~2 y/ I" B0 _0 Z3 G% ]D.
! O0 N5 ~% D& }# o! t9 A* n      满分：5  分
% s3 v; Z% T, \4 y2 @' J9.  图的邻接矩阵表示法适用于表示
$ A' t7 {( F5 ?( `+ |1 ZA. 稠密图
B. 稀疏图
C.
2 U4 L- _. q* @) p7 m# T1 ^* n) ~D.
% j. ^% v2 P; t! W' s      满分：5  分
$ v5 l1 r2 G5 v3 F2 w6 r! p2 I10.  已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A. 16
+ @& n; |8 W/ N2 i- d2 W) @B. 17
C.
D.
; m- m! Y3 X3 m" ~/ C1 m' W( o      满分：5  分
! n; i, y5 U0 o11.  队列和栈的主要区别是
A. 所包含的运算个数不同
0 A- J, g, r' ~* h6 k  jB. 限定插入和删除的位置不同
8 H7 E% x5 z0 }$ T: lC.
  N: V& [2 ^! ]8 AD.
7 }; E) T0 R+ l( K, `  O3 @- f* O      满分：5  分
12.  栈的两种常用存储结构分别为
9 ]% ]* W! D- S5 p& _) zA. 顺序存储结构和链式存储结构
7 T7 O8 h3 z* NB. 顺序存储结构和散列存储结构
C.
D.
      满分：5  分
13.  假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A. (rear-length+m+1)％m
B. (rear-length+m)％m
C.
D.
; g' {# F( y% q! e7 L      满分：5  分
2 Z8 [  T' _! j' l: q0 M14.  导致栈上溢的操作是
A. 栈满时执行的出栈
B. 栈满时执行的入栈
5 p1 ]% W2 M; I- P" FC.
D.
      满分：5  分
: f2 q# t- E3 B" z15.  在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
* `& y; t6 `9 mA. 队列
B. 栈
C.
" g# c( ~$ u) y8 _) M) y8 z5 eD.
      满分：5  分
16.  设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
" s* O) z8 {# X1 c% ~* rA. 4
; C1 n8 S' R  z: [, F8 v/ rB. 5
5 d& O) _! }; Y  l) q! ^& uC.
, U4 X( _; _! o2 o% p/ O( UD.
      满分：5  分
17.  假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在
A. BT[2*i]
5 f" A$ O& K( R3 h7 D3 L" J/ C5 F! nB. BT[2*i+1]
C.
7 r0 }% m6 D. |2 H$ QD.
1 a3 E/ H9 T* i2 F      满分：5  分
18.  已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
5 F8 T9 q) Z" i, M. S) xA. ABFCDE
* x! m% v6 y0 F+ T& b8 uB. ABCDFE
& r. M* S1 i4 F8 O* m( K: o0 cC.
) k+ S% G2 i) n& J/ R0 aD.
7 o, R7 {" n. A4 y      满分：5  分
19.  设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
" ?1 Y6 Q. r8 h0 CA. 2
B. 3
C.
D.
      满分：5  分
4 u! @- a1 s6 j" j( V) Z20.  n个顶点的强连通图中至少含有
A. n-1条有向边
% t1 q. b5 j/ K7 G% g) C  f- S+ MB. n条有向边
1 l4 m! F, f1 ^1 e- j* I5 ^C.
D.
      满分：5  分