东师《数据结构（高起专）》2012春第二次在线作业（随机）

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
; L+ k+ C: [9 ~) t+ o( ]
) Z8 r6 s3 K6 ?) h) H: k一、单选题（共 20 道试题，共 60 分。）V 1.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
. m1 x, @' L6 e5 w& tA. 直接插入
# `! h1 D0 a/ B, @1 Z9 VB. 直接选择
" G# g3 m4 g0 U8 gC. 冒泡
D. 归并
* \5 L8 G, k5 B7 X& P# _7 [' s      满分：3  分
2.  如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
, N9 x# |7 C  n* g5 Z; h. kA. 顺序查找
B. 折半查找
C. 分块查找
+ c9 `- ~" O3 |* g: mD. 基于属性的查找
: E1 V3 I& {/ g* w5 R0 z      满分：3  分
6 k, z- b; H* Q% G: ~+ d- v2 Z7 r3 l3.  假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A. k-1次
" U: n1 d* K! J9 uB. k次
C. k+1次
/ r9 w7 p7 Z: BD. k(k+1)/2次
      满分：3  分
* B% T! \: E) d7 T! k! q4.  一个有向无环图的拓扑排序序列 () 是唯一的。
A. 一定
B. 不一定
C. 可能
D. 三者均不对
      满分：3  分
8 p/ |" }! y  N% `# T( P5.  设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
: y4 p6 o+ u' s- P% vA. 1和1
# _8 X5 g: b1 j( L$ ^7 M: p. n- HB. 1和3
C. 1和2
6 l8 }. F/ R+ ~& x" _/ q& J* `% ED. 2和3
. g5 ^0 X% e# \      满分：3  分
0 u5 C5 J3 ~" E$ G7 c+ p6 I. p6.  有n个顶点的无向图的边数最少为 ()。
! g0 w" O* c( P% T) K" M$ N, o7 EA. 0
8 R8 _" ~/ J2 y) h% t, KB. 1
$ K6 e6 Z1 D! W# c7 e/ T# zC. n-1
D. n
( Z4 r, n1 l6 A" `- g% P5 p% F$ q# G      满分：3  分
7.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
4 w3 \" _& J5 \9 G) OB. 中序遍历
C. 后序遍历
D. 层次遍历
      满分：3  分
# g( a+ v9 B# M) l8.  顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
: f4 t/ j# z- O& A3 f  k- m      满分：3  分
4 o, m+ |3 L$ N% F2 t$ q0 l" I9.  下面哪些方法可以判断出一个有向图是否有环（回路）? ()
4 z7 C* l- g5 ?4 g3 _3 k0 SA. 广(宽)度优先遍历
$ k, }5 @+ g" }1 `B. 拓扑排序
/ X; Q7 r5 z6 z9 D8 NC. 求最短路径
7 r; }* b% `0 Y$ g5 ~8 zD. 求关键路径
      满分：3  分
10.  广义表 (( a , b , c , d ) ) 的表尾是 ()。
- h6 u* G1 m/ H7 RA. a
B. ( )
6 J. O4 U3 T9 C: w! G" f4 MC. ( a , b , c , d )
D. ( b , c , d )
$ A0 K1 g- t0 e" o9 }      满分：3  分
( v! s3 v4 U4 n' E# B11.  广义表 (( a , b , c , d ) ) 的表头是 ()。
A. a
B. ( )
C. ( a , b , c , d )
) i2 w  i8 r6 G. v/ OD. ( b , c , d )
      满分：3  分
12.  数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
1 p, ~  C( m. l9 k* i4 w1 RA. 直接选择排序
3 N! c9 Q2 K, o4 H: a  d4 Z6 M: sB. 冒泡排序
C. 直接插入排序
* w! R' Y! C9 \/ y5 zD. 堆排序
) ~! r2 b8 `3 O  R/ @      满分：3  分
13.  折半查找要求结点 ()。
A. 无序、顺序存储
B. 无序、链接存储
. I. \: E* m! Y0 YC. 有序、顺序存储
D. 有序、链接存储
      满分：3  分
14.  在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
! @8 G& P) U* U8 \7 O0 g8 [  J  fA. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
      满分：3  分
15.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
: [/ k( ?# [6 r5 r5 x7 h8 PA. 堆排序＜快速排序＜归并排序
B. 堆排序＜归并排序＜快速排序
6 B1 m" \  ]  x$ Q& Y6 v9 R9 eC. 堆排序＞归并排序＞快速排序
; {7 T$ Q. c0 g8 Z# F' ?5 @* S" z# ZD. 堆排序＞快速排序＞归并排序
0 L+ ^( d! Z' m9 N# B      满分：3  分
+ f5 b# D" \: j  @. r  y/ }5 c& H$ O16.  有n个顶点的无向连通图的边数最少为 ()。
/ x9 t. \" X; W1 V1 }) g" l. B5 fA. n/2
0 o, o  G4 T3 E1 f  B" z0 pB. n-1
- `0 g9 X( Q  d+ F5 v! L& eC. n
D. n+1
      满分：3  分
17.  存放在外存中的数据的组织结构是 ()。
) ^' R5 n' a3 gA. 数组
B. 表
C. 文件
D. 链表
      满分：3  分
# w5 I5 z- X8 s18.  设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
+ Z  d( a# ~$ r/ T1 H4 ~' o" SC. Ο(n)
& q5 }6 S1 k% m# {D. Ο(nlog2n)
. \7 n2 N* P- u6 ?      满分：3  分
7 ?( r0 A% ^2 H0 }& O19.  在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
A. G中有弧＜Vi , Vj >
B. G中有一条从Vi到Vj 的路径
, k. v4 H9 ^9 m, m8 rC. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
      满分：3  分
3 b! n4 ]/ l& A# D20.  在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
  \, y" k5 l2 p6 Q' Q% uA. 希尔排序
' Z) k6 f8 C3 e3 ~2 A% `! FB. 插入排序
- x7 c  ]" A2 k- k' w* V; NC. 归并排序
D. 选择排序
$ Y0 s" C% l, z5 e      满分：3  分
) Y4 t) N, e1 ~8 D4 G
二、判断题（共 20 道试题，共 40 分。）V 1.  最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。
" S% w  W; g1 o: m  YA. 错误
B. 正确
! S- x4 s; W+ K) R$ B, t: E      满分：2  分
% T  ^7 `  I6 _( p: h2.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
; A  z4 d! ?3 k. d, `* J; mA. 错误
B. 正确
      满分：2  分
3.  最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A. 错误
B. 正确
1 z, O1 j: \  d4 i      满分：2  分
5 [. ]% t. m1 `: a0 x( T% m# ^. c4.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
6 F# |. a. e5 z# ?# h# dA. 错误
B. 正确
2 |+ C; b( s0 |- t' _      满分：2  分
5.  邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
4 r2 o' U9 L! Y" SA. 错误
1 i# B: k. O0 M. Q# f1 @3 ]B. 正确
6 w+ Q0 u- W( H+ B      满分：2  分
" w2 p$ [6 n/ }" A' K6.  在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
5 N8 D7 L2 u& o6 ?% i0 I& y- MA. 错误
4 Z7 r. K7 A3 \" c; a3 x: WB. 正确
      满分：2  分
4 N% f9 }6 n6 p! C5 \7 n; \0 o7.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A. 错误
B. 正确
      满分：2  分
/ a" K: c% P  t6 }" m8.  数组不适合作为任何二叉树的存储结构。
7 H3 r# _/ m' z# L: T$ V+ F4 s- uA. 错误
9 g- m  p4 _, z5 ?" _4 TB. 正确
3 d: a$ y) D/ r. h' x! p9 f+ o      满分：2  分
9.  AOV网的含义是以顶点表示活动的网。
A. 错误
4 q( Z% P" c2 \; ~7 x5 B* WB. 正确
9 W, e  |4 b$ T* o      满分：2  分
3 n  P$ I- q: C+ [4 ?( _0 ?10.  哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
7 x' p/ k# }. L8 ]A. 错误
  p! G9 I; ^* x+ f6 ]) yB. 正确
      满分：2  分
11.  连通分量是无向图中的极大连通子图。
A. 错误
5 [2 t# @+ l# D" v" t4 @4 XB. 正确
, l. Y! H# Q2 N/ m% }& ~' z      满分：2  分
/ c6 ]/ }! }8 h; [7 p12.  归并排序在任何情况下都比所有简单的排序方法速度快。
) U! Q) w' G, X! U; C/ ~A. 错误
" I3 k+ _" Y+ \* a2 e. bB. 正确
      满分：2  分
13.  倒排文件的优点是维护简单。
A. 错误
# i( k! t9 `, U: ^1 L  MB. 正确
: |# q. \  n! g5 l" v3 e      满分：2  分
14.  在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
, B# n: s6 u: P8 jA. 错误
8 V$ S4 N1 ~: |: w) v. H! m+ z, D- ~B. 正确
; `# G/ @7 N. ~$ a2 K6 H8 }( P5 t      满分：2  分
15.  对有序的单链表不能进行折半查找。
A. 错误
B. 正确
      满分：2  分
/ ]! ?9 C9 j8 P/ [1 v" D+ I0 {" P16.  归并排序的辅助存储空间代价为O(1 )。
A. 错误
B. 正确
      满分：2  分
17.  用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
A. 错误
B. 正确
      满分：2  分
18.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
; ?: o. c# n( Y. ?7 k1 J; j+ j6 wA. 错误
) \5 C- E: r1 z5 F0 jB. 正确
      满分：2  分
19.  有向图的邻接矩阵是对称的。
A. 错误
) F/ `+ U4 S, d4 T% |6 rB. 正确
      满分：2  分
9 p  ]2 P4 S, m5 P20.  快速排序总比简单的排序方法快。
9 q% Y( `) f' T  i: xA. 错误
" I, s0 a# Z6 M; p8 I- B  T: w* rB. 正确
      满分：2  分
/ f& i8 u8 h/ O( I
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。