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

谋学网

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

一、单选题（共 20 道试题，共 60 分。）V 1.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
) }  z6 m- V  x8 A7 i$ k$ w2 uA. 直接插入
0 X# ^0 w' _' D. P, Z1 hB. 直接选择
# a, C/ H7 I% q& N" i; o" I$ h- bC. 冒泡
D. 归并
      满分：3  分
2.  如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
$ d4 X2 y& l$ n% z  M8 V4 eA. 顺序查找
B. 折半查找
$ n  K/ f6 @; ^8 l$ [' zC. 分块查找
6 N9 I$ I9 e$ e6 c+ TD. 基于属性的查找
3 ?) Y7 l7 U1 o5 A8 d* z6 e      满分：3  分
) [, b6 R. ?- K9 N7 @3.  假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
4 [3 N) F( j' [! {8 `A. k-1次
B. k次
" F2 ?8 g& m1 F' h) G" b8 PC. k+1次
D. k(k+1)/2次
      满分：3  分
4.  一个有向无环图的拓扑排序序列 () 是唯一的。
+ T0 z/ Q& G! m5 DA. 一定
B. 不一定
: a5 x, Z' `+ r( ]" f% oC. 可能
D. 三者均不对
, |. ^1 t2 b: |  u8 w      满分：3  分
5.  设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A. 1和1
B. 1和3
C. 1和2
) ~, _0 t, G/ Z% [/ U) cD. 2和3
      满分：3  分
6.  有n个顶点的无向图的边数最少为 ()。
A. 0
4 Z/ [& i. \. K# A, ZB. 1
C. n-1
  d% x+ F; Z+ M. M6 D! gD. n
# v3 U# e& P4 k( f; w9 N% m! P4 Y      满分：3  分
7.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
/ T& Y' \" q9 W% b+ g7 K' u" B! jC. 后序遍历
7 {+ o8 G( K- I. T8 B$ x. uD. 层次遍历
0 A; a$ g% v" d7 D+ W      满分：3  分
8.  顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
& Z% q2 Z# @0 ?% C6 f2 a6 G; @A. 散列存储
0 @1 v  R! }% w4 g9 QB. 顺序存储或链接存储
C. 压缩存储
% ]4 O% h( H' C- y; ~D. 索引存储
$ r; N. }9 z- k9 _8 f      满分：3  分
9.  下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A. 广(宽)度优先遍历
0 P' X; j- `' F+ \+ M; iB. 拓扑排序
C. 求最短路径
D. 求关键路径
      满分：3  分
10.  广义表 (( a , b , c , d ) ) 的表尾是 ()。
A. a
B. ( )
C. ( a , b , c , d )
D. ( b , c , d )
      满分：3  分
11.  广义表 (( a , b , c , d ) ) 的表头是 ()。
& E$ g+ l; U1 j" F( ~/ N8 uA. a
B. ( )
& ]7 D  h+ ?0 m6 y6 P) g. V5 a# `C. ( a , b , c , d )
6 A6 @" C( K7 |D. ( b , c , d )
      满分：3  分
% }, Y# g- v+ \12.  数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
% @: c! e8 m2 A) pA. 直接选择排序
B. 冒泡排序
C. 直接插入排序
9 J& n+ |+ J& n) kD. 堆排序
3 k7 O# E# x; j- r5 P      满分：3  分
9 x" I8 l7 {; o& V. a/ T13.  折半查找要求结点 ()。
A. 无序、顺序存储
: ^) l% [  Z. @; k9 P! X# h! LB. 无序、链接存储
C. 有序、顺序存储
D. 有序、链接存储
      满分：3  分
( y' u% f0 t) ^8 S+ L14.  在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
8 [4 r/ h/ N/ U; i0 VA. 直接插入排序
0 I% \; {5 v' yB. 快速排序
) }: C! G+ f# s5 F( oC. 直接选择排序
D. 归并排序
( L4 [7 E$ X% `0 W% n* f      满分：3  分
/ G2 \! c6 Q) z  j' v15.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A. 堆排序＜快速排序＜归并排序
B. 堆排序＜归并排序＜快速排序
( n/ |  L! r4 B% tC. 堆排序＞归并排序＞快速排序
; V- N% z8 Z, x/ AD. 堆排序＞快速排序＞归并排序
      满分：3  分
  l6 m8 M; _' L16.  有n个顶点的无向连通图的边数最少为 ()。
6 `# h1 N9 u+ w. x7 |- lA. n/2
  f: S' s$ r$ ]7 ~) ]B. n-1
C. n
& t9 ^& z% }- O) ^' X6 g1 y& c* }D. n+1
1 @; k8 }) E: m* D- ]: T      满分：3  分
5 x2 H, {0 l! `0 b0 n, ]+ Z17.  存放在外存中的数据的组织结构是 ()。
A. 数组
; O5 P; u8 X5 e7 AB. 表
C. 文件
D. 链表
, |6 ~( Z* m2 z. p+ _9 V1 [; N      满分：3  分
18.  设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
4 c+ m2 X# D8 t$ ~. C0 LB. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
& i; {( n; k) a( \; R( M' u5 v/ k7 |      满分：3  分
% C4 ~( h: {& B4 N" F( G9 R19.  在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
A. G中有弧＜Vi , Vj >
. l9 k) ^# j: R2 ZB. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
      满分：3  分
  v2 B8 m5 Z* X! V20.  在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A. 希尔排序
8 ~0 w; M* h) C' w) Y0 WB. 插入排序
C. 归并排序
D. 选择排序
% |0 d1 r: e; ~$ U6 g      满分：3  分

& A- P2 T  H4 \1 e  ^% i二、判断题（共 20 道试题，共 40 分。）V 1.  最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。
8 F  N- ~4 D6 l  ]( Z" fA. 错误
# R" `$ s$ p4 H1 TB. 正确
      满分：2  分
6 T, M* l% {9 Q% v2 B2.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
, b& H$ \9 Y" B% KA. 错误
! W4 V, o& p' c( xB. 正确
3 V6 D% B: l1 @/ B      满分：2  分
3.  最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A. 错误
7 C" w( J% z$ N( A' k8 OB. 正确
      满分：2  分
4.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
  M/ ^# S! J# H8 L  vA. 错误
B. 正确
      满分：2  分
, P" u: F% V8 i5.  邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
A. 错误
B. 正确
* |( }$ d- _9 G# V      满分：2  分
6.  在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
A. 错误
B. 正确
7 R4 o4 M5 M1 u( G3 U( W      满分：2  分
7.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
3 w* ~5 c' k6 }# J$ ]! r$ X7 XA. 错误
B. 正确
( F) @! P# q% L+ f/ l- q9 q      满分：2  分
8.  数组不适合作为任何二叉树的存储结构。
- I, o& _/ w0 p5 w3 _A. 错误
B. 正确
      满分：2  分
9.  AOV网的含义是以顶点表示活动的网。
: U0 J# d5 H! JA. 错误
B. 正确
      满分：2  分
8 J4 I+ b0 T6 j10.  哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
; j+ m% V* ~* O" ?A. 错误
: x8 H1 T% T+ m% d! g4 sB. 正确
      满分：2  分
1 _1 W& }/ P  E11.  连通分量是无向图中的极大连通子图。
+ n) H$ r9 j, u# P/ I2 bA. 错误
. P) A  D, X. t  b& bB. 正确
      满分：2  分
2 u+ b* G# R$ K) {2 ~2 W; Z" i8 c2 F12.  归并排序在任何情况下都比所有简单的排序方法速度快。
A. 错误
! u6 Q; j$ [! [$ `, T& M$ Z2 QB. 正确
( H$ m2 J, K6 f8 _; e9 w/ p      满分：2  分
5 f5 r* W* r- e# t13.  倒排文件的优点是维护简单。
A. 错误
; P; |" l8 G$ \" F8 R0 ]) I# lB. 正确
      满分：2  分
7 E1 o( z  V& _7 A& |, b+ B) [6 b14.  在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
  t. n/ W- @- Q/ x: A' c. }. LA. 错误
B. 正确
      满分：2  分
, ]6 h- v9 Q- V( ?2 E# B15.  对有序的单链表不能进行折半查找。
: [- B6 Y7 |1 FA. 错误
4 h1 M$ h9 a% ~0 d. c. EB. 正确
      满分：2  分
5 \' v# n' }% k8 }' u5 D16.  归并排序的辅助存储空间代价为O(1 )。
A. 错误
3 t7 z: {2 q; n5 W/ G$ h0 b8 EB. 正确
      满分：2  分
+ w5 q- l, R; ]0 E$ Y17.  用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
A. 错误
B. 正确
5 u; h( _: K7 k      满分：2  分
18.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
7 B: |$ k  U& f6 dA. 错误
5 J6 W, Q) |, I3 c8 H/ dB. 正确
      满分：2  分
19.  有向图的邻接矩阵是对称的。
A. 错误
B. 正确
: o% a! J! I8 @  b      满分：2  分
8 ?, {) ?6 W& [  y7 @  R20.  快速排序总比简单的排序方法快。
" Y! e+ T; d2 j* f( K" r5 M+ ~A. 错误
$ o% _' R  d+ b" x8 }- d7 aB. 正确
; x. M4 [( a$ e/ ^. ~0 |* Y* l      满分：2  分
. ^; r' d. `7 |3 N- a
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。