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

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
! m1 t& r1 F' R; s9 V; v8 J* T
. A& t. R7 `- R( I一、单选题（共 20 道试题，共 40 分。）V 1.  广度优先遍历类似于二叉树的()
A. 先序遍历
1 V- j! T+ c2 J! a5 ^3 }4 Z/ mB. 中序遍历
C. 后序遍历
D. 层次遍历
9 B: B* N+ N/ ~% J) }! j1 j      满分：2  分
2.  下述几种排序方法中，要求内存最大的是()
A. 插入排序
6 j: v- |& [0 [' B9 YB. 快速排序
C. 归并排序
0 U. Z5 B  T4 s! g- K& P: eD. 选择排序
! P% R6 h# u" [      满分：2  分
! L; Q& W" t8 b0 M9 S6 \! ]+ C8 _3.  对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
A. O(n)
B. O(n2)
8 E" ]) C! G/ ]8 FC. O(nlog2n)
+ o2 g3 K- G9 k8 GD. O(n3)
      满分：2  分
4.  在一个图中，所有顶点的度数之和等于图的边数的（）倍
6 I% ?/ v: x. S: H1 h/ YA. 1/2
B. 1
) }7 ^8 g, i' L  l' Y8 jC. 2
- C" A4 j# P6 M! K! Q& ^. zD. 4
- p0 k" B8 r' B& b. v* |5 y      满分：2  分
0 y, ]  t* g/ W3 R2 x$ H* Y9 E6 G5.  判定一个队列QU（最多元素为m0）为满队列的条件是（）
/ b& f' Q3 ^, V# d, \A.
3 t8 l2 l2 ^7 R" I6 R7 Z& r+ M7 B! ? QU->rear － QU->front = = m0   
9 R# S- y7 s% \3 f; |B. QU->rear － QU->front －1= = m0
% q# T% `% F: a! e# f* |* bC.  QU->front = = QU->rear   
# n4 h! A6 j& e: t! kD. QU->front = = QU->rear+1
1 n1 R* l; ]8 X3 Z" O* A% d7 e      满分：2  分
9 J9 R2 A/ ]1 D7 }1 O6.  
设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）


; t4 d0 Q1 n3 b; U" X
A. 循环链表
) F& r: {5 k. X" HB. 单链表
. h# z, V. h5 QC.  双向循环链表
D. 双向链表
$ l1 Z  R$ T* J& P      满分：2  分
7.  不含任何结点的空树（）
A. 是一棵树
& c) H, W" \" l! n$ Q) HB. 是一棵二叉树
C. 是一棵树也是一棵二叉树
/ @; R+ t3 A. `  x! UD. 既不是树也不是二叉树
, q2 M9 y# e. b" l2 g/ w' c: N  ^! M      满分：2  分
8.  用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A. 栈
B. 队列
! P! K& U. ^  }- |% X9 d% g/ eC. 树
D. 图
      满分：2  分
& L+ X) W* k* v  D9.  若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
( L9 Q8 e( x3 G0 W9 }- vA. 38,40,46,56,79,84
B. 40,38,46,79,56,84
- B8 O# A, Z4 _& Y9 T) bC. 40,38，46,56,79,84
( A* r9 u  H6 g( `. F" Y  CD. 40,38,46,84,56,79
5 h7 f) `. \! ~' d      满分：2  分
10.  用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A. 栈
9 h7 U( w! |& A! WB. 队列
7 @! _+ C. }2 R. ]1 I- H% ]2 OC. 树
, R1 g+ y# R  vD. 图
      满分：2  分
11.  链接存储的存储结构所占存储空间（）
9 x, V& P7 I) _, ?A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B. 只有一部分，存放结点值
C. 只有一部分，存储表示结点间关系的指针
  |' d3 w& ]$ F- H5 E4 Q, G# v* ^5 vD. 分两部分，一部分存放结点值，另一部分存放结点所占单元数
      满分：2  分
12.  引入二叉线索树的目的是（ ）
$ {/ p0 {$ S* q& O& a: bA. 加快查找结点的前驱或后继的速度
- G  L  r: c; p# S! X$ e4 x% tB. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
, i% j5 o2 @6 T$ v5 jD. 使二叉树的遍历结果唯一
+ {4 P0 R# I; _# C9 \/ v% ]4 X3 |      满分：2  分
/ N+ a5 C7 T8 D13.  设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
% ?' i+ x" O1 `' ?: {& |  B  O4 vA. n-1
, X, v& O* U$ h8 U7 \5 @B. n
4 Z2 F& I# G& n" rC. n+1
D. n+2
      满分：2  分
14.  栈中元素的进出原则是（）
4 z4 |3 i$ |2 |; Q0 U* k5 a5 VA. 先进先出
  u" y- K3 a- H" sB. 后进先出
C. 栈空则进
. k5 f  w4 k4 K! D1 Y$ }8 }7 ND. 栈满则出
      满分：2  分
8 }( F. c# B* p4 `$ D, j15.  
9 T" M  l$ j8 [$ [2 i已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）


% ^* g9 I8 A1 `
1 u  m) N. d0 c- d% e$ qA.
0 2 4 3 1 5 6      
   
B. 0 1 3 5 6 4 2
C.
/ w* @# `) t, X* y0 n  b, o0 4 2 3 1 6 5
D.
. l1 B; r# M$ Q0 1 3 4 2 5 6
- @6 C, S1 J+ L# J) P$ B8 v      满分：2  分
16.  排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
: l7 s: @1 j. T7 a, ZA. 希尔排序
B. 冒泡排序
C. 插入排序
D. 选择排序
; H6 L% [; C% N! q      满分：2  分
17.  堆是一种()排序。
8 ]; T8 X+ x1 y/ [3 t  H- }A. 插入
B. 选择
: I, D9 M. k  ~* d& J( OC. 交换
! N+ o& L8 R- `( `4 oD. 归并
      满分：2  分
18.  
2 `( [: r/ Q2 a6 l: L, C+ i$ U, i已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）

- |* M. _' N& g: y6 T
* M5 w, a: U' z0 w9 d6 O
A.
, I5 w1 t. b" `# m- y+ V2 e3 h! E0 2 4 3 6 5 1
     
  
  X1 l* j4 c  ]0 KB. 0 1 3 6 4 2 5
" |# D$ K- V; m$ bC. 0 4 2 3 1 5 6
- C2 Y" ]0 c) ~# v: VD. 0 1 3 4 2 5 6
      满分：2  分
19.  从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
9 w9 h% i) k2 q$ UA. 希尔排序
* F, ?! r, ~+ Q; q9 xB. 归并排序
C. 插入排序
& |. p7 t: H  D3 |$ [D. 选择排序
& t, `1 U" c. p; L      满分：2  分
, [- w- C2 o9 F2 a8 k+ N3 c" Z( G20.  把一棵树转换为二叉树后，这棵二叉树的形态是（）
- A) J% u# H. z- Z6 P. ]  d, bA. 唯一的
B. 有多种
+ w3 R/ b& D# |: v  V) b. M+ OC. 有多种，但根结点都没有左孩子
7 [! K& S/ i/ M" _4 V5 ?+ d2 YD. 有多种，但根结点都没有右孩子
5 L. ^  N/ |5 O  S9 \8 j) P( t      满分：2  分

二、判断题（共 30 道试题，共 60 分。）V 1.  线性表在物理存储空间中也一定是连续的。
+ p. q9 C. Z( p; D6 v1 D6 Z% VA. 错误
" U3 R9 t1 X  q* [B. 正确
; C3 o  B) A$ [( h/ W, O* G      满分：2  分
2.  顺序存储方式只能用于存储线性结构。
. i! r: }2 Z  i  ^- `( c# aA. 错误
B. 正确
/ ~  j0 U+ I. c0 S% J+ A( H      满分：2  分
3.  二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
* |0 D# F5 d; b3 Q7 [, {" {A. 错误
* B4 X2 V* [4 s6 g9 S5 iB. 正确
6 L( c* v/ {: \' e      满分：2  分
+ e5 n- u6 g3 [4.  一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A. 错误
( {  b4 t6 {+ UB. 正确
      满分：2  分
5.  二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A. 错误
B. 正确
  a" w# Q6 ?0 f' [) I* n( a      满分：2  分
7 {* T' o* M2 F- j. d6.  线性表的逻辑顺序与存储顺序总是一致的。
A. 错误
B. 正确
      满分：2  分
7.  栈和队列是一种非线性数据结构。
A. 错误
' I* _( h# W% L0 Q8 o  o3 y  VB. 正确
9 ?' U2 r) f/ u- d" s5 G( W0 B      满分：2  分
/ N' A/ \2 F( p8.  具有12个结点的完全二叉树有5个度为2的结点。
; r( {- p+ _1 k; L% |, b% QA. 错误
B. 正确
      满分：2  分
2 ~$ J4 X* ^0 n9 Y+ p5 O" m7 r# d9.  两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
: L, i0 C3 ^3 b! u) hA. 错误
B. 正确
+ ~, Y9 Q( s! ~      满分：2  分
/ _$ w5 n4 z+ O5 ^! _1 s/ q- |! l10.  链表的每个结点中都恰好包含一个指针。
7 ~% M" i5 i, k$ ?' EA. 错误
) A5 }3 i) ~4 f1 w1 nB. 正确
      满分：2  分
7 ^; V3 J) x8 X& \: A: K. Y11.  队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
9 z0 j, K2 s. M$ {9 |- G3 `$ x! ?A. 错误
B. 正确
3 e, n+ J; C- _9 A      满分：2  分
: e. ^' _0 \6 F7 B2 o+ }- s6 Y. T# i12.  栈和链表是两种不同的数据结构。
( l; B- I: e* Y: DA. 错误
B. 正确
& w* Y1 ~1 ]9 u2 |6 @0 L      满分：2  分
13.  栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
A. 错误
' ?7 W/ n+ W  u- p; ^2 KB. 正确
      满分：2  分
& {9 J3 z$ ~( P* f. ?2 i$ _# b14.  二叉树中每个结点的两棵子树的高度差等于1。
! S  y- b9 l) P* Y7 R/ _+ Q/ \% @A. 错误
  J; l' X6 d1 Z, PB. 正确
3 t$ F: X- ^6 H& v5 g# h9 p2 o& x      满分：2  分
15.  用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
A. 错误
- W4 k1 h4 F6 I4 G) x5 H( G9 @2 dB. 正确
, ]' z9 V0 b0 j" Q. m; x" F      满分：2  分
  Y& p6 ?. t2 ]. q& J16.  栈和队列的存储方式既可是顺序方式，也可是链接方式。
A. 错误
& o/ q+ O' B0 M7 ~1 m% {9 XB. 正确
/ p' v9 [; K; Z      满分：2  分
17.  对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
, w4 c2 w) {6 B  i( c) tA. 错误
( G( g- }5 J% Y2 @* \# I  p- xB. 正确
      满分：2  分
) W0 E( e' l/ n& }/ v* a0 ]' O18.  若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
A. 错误
/ G1 i. }" V' L1 O2 U$ a! }B. 正确
( d0 m, y& {6 q, h; ]      满分：2  分
19.  二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
A. 错误
+ l/ F3 V" l! l! Q2 iB. 正确
      满分：2  分
* ^; j8 T4 ]0 B7 i5 x20.  顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A. 错误
B. 正确
, n0 V' K' x: V/ S# w& d' _      满分：2  分
1 ^% O+ _, t# t$ ]* z0 l* ?21.  在表结构中最常用的是线性表，栈和队列不太常用。
A. 错误
B. 正确
      满分：2  分
+ g2 P: u- p5 D4 J22.  对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
A. 错误
$ t6 C% }3 C: F- O0 Y/ U8 m( cB. 正确
  C4 e2 b& w6 L& y      满分：2  分
23.  线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
9 r4 r5 m) x3 J' D1 a: AA. 错误
B. 正确
      满分：2  分
9 G" v9 k4 r0 H% l24.  线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
7 e& Q- {2 n8 F6 P) HA. 错误
- d# n1 e1 ^, |+ s& V. G  kB. 正确
      满分：2  分
# ^9 _4 p* @7 N8 Q5 ~4 f$ P. W' s% o25.  二叉树中每个结点的两棵子树是有序的。
A. 错误
5 M! s" a7 d! N$ EB. 正确
- S8 ]2 l+ @. R8 \+ b6 r" g      满分：2  分
26.  线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A. 错误
B. 正确
% |4 J; ^7 ]" M* L1 k" r) z      满分：2  分
4 K/ d8 Y) @0 k2 d, K8 ~27.  链表的物理存储结构具有同链表一样的顺序。
A. 错误
) g& |+ g, V. s1 h# m3 @B. 正确
& I6 _/ e  _4 B2 Y% g      满分：2  分
  }! |0 e% c- e, M28.  顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A. 错误
B. 正确
4 E* y* m- M- G7 f0 a      满分：2  分
' G0 o$ E$ E3 R29.  链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
7 Y. M5 L2 D* R8 t& WA. 错误
. I2 j9 h$ o3 T& l3 u. ]B. 正确
      满分：2  分
0 G1 N- M5 W* T# W' u3 J0 y! D: ~3 \30.  二叉树中每个结点有两棵非空子树或有两棵空子树。
A. 错误
( r) a; Q4 u( M0 LB. 正确
      满分：2  分

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