南开12春学期《数据结构》在线作业

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。

; Q' E' A, V' ^一、单选题（共 20 道试题，共 40 分。）V 1.  广度优先遍历类似于二叉树的()
3 x  k/ G1 i: o( Y  aA. 先序遍历
  f; @* n  T+ ]% P& HB. 中序遍历
/ u# W" m: E: z% vC. 后序遍历
! M5 C# u" [& U' X8 d- v! HD. 层次遍历
      满分：2  分
2.  下述几种排序方法中，要求内存最大的是()
1 y/ X, C, u4 S) I- `5 h6 i' sA. 插入排序
B. 快速排序
C. 归并排序
D. 选择排序
      满分：2  分
3.  对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
* G1 _3 |$ u$ M6 U% jA. O(n)
6 R0 x( V8 ~8 v  a, T9 CB. O(n2)
  t! o, C0 W( [- _( DC. O(nlog2n)
0 \0 e7 y* S7 [- ^! uD. O(n3)
$ k* d5 {0 N9 h      满分：2  分
! f  E$ R" c& e& K6 W+ u1 `2 n4.  在一个图中，所有顶点的度数之和等于图的边数的（）倍
9 b, P% U+ y# {9 @& S1 X) zA. 1/2
B. 1
C. 2
D. 4
      满分：2  分
5.  判定一个队列QU（最多元素为m0）为满队列的条件是（）
A.
QU->rear － QU->front = = m0   
8 E. L1 }% ?- q5 u- Q) TB. QU->rear － QU->front －1= = m0
7 h- _/ b' X( K1 UC.  QU->front = = QU->rear   
3 V. e0 T# b: S! q9 @D. QU->front = = QU->rear+1
      满分：2  分
6.  
' ~; `8 q8 f* M' ~; l; q) ?! r! v0 _ 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）


5 y. t4 l6 @! b# h( M
A. 循环链表
B. 单链表
C.  双向循环链表
$ s: y" i" i" f6 b/ ?7 |D. 双向链表
      满分：2  分
7.  不含任何结点的空树（）
6 O' s% x( x; h9 s& r# @8 XA. 是一棵树
1 {4 R) Q& C( X; }, f' L8 BB. 是一棵二叉树
C. 是一棵树也是一棵二叉树
D. 既不是树也不是二叉树
2 C" P/ h+ o: w- T      满分：2  分
8.  用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A. 栈
B. 队列
C. 树
D. 图
" H0 j+ n  y7 s      满分：2  分
9.  若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
% K# o- `0 H' s, RA. 38,40,46,56,79,84
6 v! Y* F9 X0 r$ I- s1 n3 KB. 40,38,46,79,56,84
$ K$ P' C: [2 X. DC. 40,38，46,56,79,84
6 t) h: K" W8 {) \, FD. 40,38,46,84,56,79
/ a. n0 g  w3 w8 r6 A1 T6 ]! n      满分：2  分
10.  用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A. 栈
B. 队列
. l4 p& L) |5 C5 ^; k% [C. 树
D. 图
      满分：2  分
4 d3 P0 }- a# U$ }% U2 m11.  链接存储的存储结构所占存储空间（）
6 Y; E/ e: u7 @0 B: X9 lA. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
0 E& q0 y. ^0 E) @! y5 OB. 只有一部分，存放结点值
5 `' z: b2 b) s" o0 q* rC. 只有一部分，存储表示结点间关系的指针
D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数
4 ]/ w; f0 ]' J8 U: X) u5 {6 h      满分：2  分
12.  引入二叉线索树的目的是（ ）
A. 加快查找结点的前驱或后继的速度
7 ^. n6 w, B. c& U* VB. 为了能在二叉树中方便的进行插入与删除
# h$ x$ s/ K1 W7 {- D- aC. 为了能方便的找到双亲
* Q; L0 t# k4 RD. 使二叉树的遍历结果唯一
) I% e  H- U% i5 X& U, j      满分：2  分
; ~& M. o. L; Z; d13.  设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A. n-1
) J. y6 |+ w$ iB. n
# ?) g( {& R" u# Y& b+ cC. n+1
D. n+2
      满分：2  分
  N7 ]" F6 n0 @' y9 T4 Y14.  栈中元素的进出原则是（）
9 u  t* g' B# r8 C9 U  xA. 先进先出
% g& I; J. x8 T! AB. 后进先出
4 E( z% f% h9 {; Y6 V$ Y1 g, uC. 栈空则进
D. 栈满则出
      满分：2  分
15.  
已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
. t0 E# y1 H( M5 w+ V

* s3 I: Q2 J4 v; g* f6 g! N4 P
A.
6 S0 x! N+ p5 l: I- m' Z8 I1 R0 D7 S% a0 2 4 3 1 5 6      
   
% x1 p7 V9 O8 n) WB. 0 1 3 5 6 4 2
C.
/ h+ |8 Q" e6 b+ `0 4 2 3 1 6 5
: L+ K/ B6 h+ \2 a1 FD.
5 m2 e. `* y( B5 q/ L0 1 3 4 2 5 6
0 E# |% m* S" p2 f      满分：2  分
16.  排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A. 希尔排序
B. 冒泡排序
# _2 B+ a0 Y% ?0 G( L0 DC. 插入排序
D. 选择排序
$ J* O8 \2 W* p      满分：2  分
9 {6 |+ q4 u4 K$ P: W. d) ?17.  堆是一种()排序。
6 G# \6 a) ^! R$ {. g; OA. 插入
# m0 O2 u  a3 d3 R- O& p9 q/ G4 IB. 选择
- J' D+ F1 ^. b3 X4 u' b0 ~C. 交换
D. 归并
" O% u' O, Q8 D$ V4 D+ @) J      满分：2  分
18.  
4 ~. p' w( u6 [1 x! F* R+ F+ A已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）

6 w1 ?# E; a: n# F6 W  M4 A
9 o5 \5 x0 i3 I  P
9 G( L, Q9 d- RA.
9 p8 L$ R% T; S  N+ O0 2 4 3 6 5 1
     
  W5 j8 L4 W: X9 K4 r  
$ o. A- g7 X# u3 E7 h! u6 f2 cB. 0 1 3 6 4 2 5
: h1 Q( Q1 s4 h/ n/ N. DC. 0 4 2 3 1 5 6
D. 0 1 3 4 2 5 6
      满分：2  分
19.  从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
, R5 Q* _- K) T  WA. 希尔排序
- G. f8 i3 y0 c" H: `, SB. 归并排序
! ^; `. K* B( c$ B% \; NC. 插入排序
D. 选择排序
7 z) q) i- p% b; x: f      满分：2  分
5 j! K0 B( x0 Y/ I1 {1 b$ y20.  把一棵树转换为二叉树后，这棵二叉树的形态是（）
& b% m0 {+ t" LA. 唯一的
* k2 r8 Q' f2 h8 E- W" bB. 有多种
C. 有多种，但根结点都没有左孩子
7 d& ]% ^% j& x3 f- j8 Q& kD. 有多种，但根结点都没有右孩子
      满分：2  分
! x/ B8 g/ `  L( B0 c* H6 e( e( Y7 k
' ]4 ]5 b. n+ K二、判断题（共 30 道试题，共 60 分。）V 1.  线性表在物理存储空间中也一定是连续的。
' W) ~1 g- O7 s: f/ k4 z( ^/ JA. 错误
B. 正确
* y5 h% f% [$ d% W5 h" y# j      满分：2  分
: N( v% |& E% O: S5 R2.  顺序存储方式只能用于存储线性结构。
& S+ b3 B. H# `) g3 d# T+ vA. 错误
- i4 V; l: O% b; m7 p% GB. 正确
      满分：2  分
$ M/ a- n+ F5 ^% Y; e3.  二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
5 r7 h) d) P$ F. O) i& ~2 Y) ?A. 错误
B. 正确
      满分：2  分
4.  一个栈的输入序列是12345，则栈的输出序列不可能是12345。
6 s& x: w( L( Y, ?) T) ], YA. 错误
B. 正确
      满分：2  分
* H  |& D; y' [  V5.  二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A. 错误
B. 正确
      满分：2  分
6.  线性表的逻辑顺序与存储顺序总是一致的。
; ?6 }  V: G6 F1 eA. 错误
- D# p/ N5 P0 x) JB. 正确
      满分：2  分
4 q' l, |/ e! l! r2 }0 ]7.  栈和队列是一种非线性数据结构。
8 d) Q4 R/ U+ ]# ~8 u4 t9 KA. 错误
B. 正确
      满分：2  分
8.  具有12个结点的完全二叉树有5个度为2的结点。
A. 错误
3 a: R" o6 U! d' c3 xB. 正确
& A- z9 o* r9 t" `      满分：2  分
: e6 g# ^% V. c5 A9.  两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
9 b- M$ i0 K! |! k% m: GA. 错误
6 r1 i, @$ c* Q- q# \% l8 iB. 正确
' t" }' ~2 r& E9 Q: G) z      满分：2  分
! O$ I6 I0 d! C' _. Q6 F* I10.  链表的每个结点中都恰好包含一个指针。
A. 错误
9 ~2 k; p& F3 F' R5 LB. 正确
      满分：2  分
11.  队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
" G  k/ s5 z' P" I! W- bA. 错误
B. 正确
      满分：2  分
  s2 M0 e/ `7 {) E) v9 ^2 t' j12.  栈和链表是两种不同的数据结构。
) K" F2 E0 q: x, `6 i3 Y5 `A. 错误
B. 正确
% N* ~- P2 b* E3 _" q: c      满分：2  分
13.  栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
A. 错误
B. 正确
      满分：2  分
1 e( ~% Q4 L% ?' U0 R14.  二叉树中每个结点的两棵子树的高度差等于1。
A. 错误
B. 正确
3 U/ V- Z7 V5 X( b5 q" W/ o      满分：2  分
15.  用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
4 n9 O" `5 X( o* x: ]A. 错误
) K+ y! W. G" ~$ Q! ~$ [( p/ w$ m$ x. jB. 正确
      满分：2  分
9 a+ r% F: q# {6 Z16.  栈和队列的存储方式既可是顺序方式，也可是链接方式。
3 q) v* u& W, z3 c+ VA. 错误
B. 正确
+ }6 h& Q8 ]$ |# n: g- {4 q      满分：2  分
4 s4 r  s4 C8 I; h5 J17.  对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
9 L( w$ B2 y  u! n7 h" vA. 错误
+ z5 x, M  q- i' ]2 o& [B. 正确
      满分：2  分
18.  若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
A. 错误
B. 正确
9 V. H% P8 Q4 ]/ z2 O" h. h2 T. M      满分：2  分
: T& @5 [) V! ]19.  二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
A. 错误
B. 正确
& Y$ x( A& `' C8 X      满分：2  分
20.  顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
, q5 x0 a# e, h# Q* B; o) c0 ZA. 错误
B. 正确
$ a6 }6 w: |9 ~0 L& v7 T      满分：2  分
21.  在表结构中最常用的是线性表，栈和队列不太常用。
4 m' G* v! ]9 L% C8 J" QA. 错误
5 Q6 _. C$ j& t0 ^& v3 s+ d! {" N9 V: lB. 正确
      满分：2  分
22.  对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
A. 错误
, \: j! L) O6 w# [5 O) ]B. 正确
& D' ?% K7 X! b  [  ?      满分：2  分
23.  线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
5 ]6 g7 W( h6 A3 L; u+ r- x, X2 yA. 错误
% h7 d$ I% D+ i# T, M: LB. 正确
      满分：2  分
24.  线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
. Z  A5 [! E, Q' oA. 错误
B. 正确
# n# j: o$ Y$ W  v6 r+ d, S      满分：2  分
25.  二叉树中每个结点的两棵子树是有序的。
0 x9 s3 Y. ?2 F3 q! M) rA. 错误
B. 正确
; y0 \7 V3 I4 H, d9 p# h8 v      满分：2  分
26.  线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A. 错误
: {3 c; y6 q$ f" DB. 正确
      满分：2  分
27.  链表的物理存储结构具有同链表一样的顺序。
A. 错误
$ M: j1 T# k  p& ]! P- b: @, sB. 正确
) Z, ?# q2 n( Q3 @5 N% M      满分：2  分
28.  顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A. 错误
, N1 v+ `( F' tB. 正确
      满分：2  分
29.  链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
A. 错误
) v2 ~# r0 T. }, I: a8 X/ b% |B. 正确
- Q9 R6 H( y9 z" u  V* l7 M      满分：2  分
30.  二叉树中每个结点有两棵非空子树或有两棵空子树。
A. 错误
B. 正确
      满分：2  分
- O- m$ {# v! H1 Z$ R0 ^8 B" P
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。