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

谋学网

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

6 r0 P! O1 p3 W一、单选题（共 20 道试题，共 60 分。）V 1.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
& I: v* `" ~% b& ^% cD. 归并
      满分：3  分
2.  如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
# m8 m7 D" p% o: f  c7 R0 A8 N# {A. 顺序查找
B. 折半查找
C. 分块查找
* K8 x2 Z9 \8 s2 C: `, lD. 基于属性的查找
      满分：3  分
3.  假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
" j: @# ?; T! g! ?A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
0 D5 ?$ v4 P9 K% N      满分：3  分
4.  一个有向无环图的拓扑排序序列 () 是唯一的。
A. 一定
4 I$ s  `4 M! W4 D$ i- M, kB. 不一定
' o+ f/ e# u7 w6 n  l) r4 uC. 可能
D. 三者均不对
8 F6 K5 k- h1 b/ o& P* s. F      满分：3  分
9 Q$ f# |) n! I( E0 U' O5 `5.  设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A. 1和1
! r& d; R7 u* tB. 1和3
C. 1和2
D. 2和3
, i, }, b; B5 k) L$ R      满分：3  分
# t% D; L; Z) z# G/ L6.  有n个顶点的无向图的边数最少为 ()。
7 W* D8 K$ W6 _4 m, m" xA. 0
B. 1
: z; B+ c$ g7 H! Y& T8 n. ?* e* ~C. n-1
; t9 d2 f0 `7 ]! Y, x1 ?  [* eD. n
- g, Y1 p. \- U) k+ d% n      满分：3  分
" Z, y1 K8 o3 e2 I$ m0 n* p4 o' J7.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
3 p0 i) J6 N, C) x2 }3 ]A. 前序遍历
" O) C0 M) Z' v! \' c$ b/ x$ @B. 中序遍历
C. 后序遍历
D. 层次遍历
      满分：3  分
6 I$ |) [  n! F" e6 T: `8.  顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
* O/ r0 d- l4 s- VB. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
      满分：3  分
7 j2 |! x# z0 u9 z4 N9.  下面哪些方法可以判断出一个有向图是否有环（回路）? ()
A. 广(宽)度优先遍历
. j& @8 B$ F/ I# h8 u5 @B. 拓扑排序
/ w" Y9 a3 b! y2 W0 YC. 求最短路径
D. 求关键路径
! f1 y% a5 y& b0 k7 l3 |- g4 U      满分：3  分
10.  广义表 (( a , b , c , d ) ) 的表尾是 ()。
A. a
B. ( )
1 r6 ]( ^7 d3 P' S8 |C. ( a , b , c , d )
D. ( b , c , d )
% a/ I7 x) G5 \      满分：3  分
11.  广义表 (( a , b , c , d ) ) 的表头是 ()。
. S. G# e6 C6 f+ EA. a
B. ( )
# K5 `1 O+ I4 j; l# N2 QC. ( a , b , c , d )
& x  J* _* p! @! YD. ( b , c , d )
      满分：3  分
0 u1 M7 O0 e# @1 k! `12.  数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
  L  l4 H$ x. @# |: {8 XA. 直接选择排序
8 q$ f# G8 J* d* Q5 D3 M  |+ _B. 冒泡排序
C. 直接插入排序
% R6 @  l7 c$ V: `" U2 m/ {D. 堆排序
+ p$ D$ i2 l6 s; [/ R# B( `6 q: L      满分：3  分
8 _) G$ ?/ ?3 h! e- j# \13.  折半查找要求结点 ()。
- B$ }* j& f% M5 pA. 无序、顺序存储
$ [$ A  g, N$ o9 p6 J0 x! bB. 无序、链接存储
C. 有序、顺序存储
& V) Z* J2 @3 |: u0 t/ ]% F) o' v  ^D. 有序、链接存储
5 e9 s9 G" ]- a1 H8 R5 j      满分：3  分
4 {" h* N  }' o; D! d14.  在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
A. 直接插入排序
' E( r: G* W. n) g9 ^B. 快速排序
C. 直接选择排序
D. 归并排序
      满分：3  分
15.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A. 堆排序＜快速排序＜归并排序
6 i; Y( L5 ?0 D- [B. 堆排序＜归并排序＜快速排序
$ D, X+ W9 L& p( K4 MC. 堆排序＞归并排序＞快速排序
D. 堆排序＞快速排序＞归并排序
! p# h# d1 g$ d/ [' W4 z      满分：3  分
- T( J8 h  p2 Y8 q6 _" Q16.  有n个顶点的无向连通图的边数最少为 ()。
A. n/2
B. n-1
7 D5 M* \& F3 L& ^! rC. n
& S. K7 ]9 J. s& Y- RD. n+1
      满分：3  分
* G" z! z8 l7 x; }' k7 U3 S! Z0 Z17.  存放在外存中的数据的组织结构是 ()。
0 e8 K2 R; n( j8 b7 X$ C, }A. 数组
B. 表
  R  b$ X$ R2 `C. 文件
- X9 t% x) o+ [4 wD. 链表
; ]/ a( m0 E; X2 R6 r0 ~5 W* S: |      满分：3  分
18.  设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
9 j- K' h- v) D- ~B. Ο(log2n)
7 \5 b( U! `8 L, V$ l9 |C. Ο(n)
D. Ο(nlog2n)
      满分：3  分
# d1 |% M9 ]5 L( g7 j6 ^8 g3 N/ N$ N19.  在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
A. G中有弧＜Vi , Vj >
0 \* @9 F- `* T' }. e! XB. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
3 X, y0 k9 ]9 g( V/ X6 }8 }7 P8 y" \3 _      满分：3  分
, k% m# s' G) `20.  在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
A. 希尔排序
B. 插入排序
C. 归并排序
1 u1 m: T9 X) j( {2 l% DD. 选择排序
      满分：3  分

! w( O# o) h% L5 w& H6 ]0 o& `二、判断题（共 20 道试题，共 40 分。）V 1.  最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。
A. 错误
3 D9 K4 c+ J( D: a; AB. 正确
      满分：2  分
+ y3 V" F4 a2 o/ Y) y1 l2.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
6 ^( ]. v4 n4 C0 sA. 错误
  ^7 z& p& O  O1 W3 j, S* cB. 正确
      满分：2  分
3.  最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A. 错误
B. 正确
      满分：2  分
4.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
A. 错误
B. 正确
      满分：2  分
6 B% T- F; W' \7 ?1 {5.  邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
A. 错误
4 b- k/ x3 ^; M2 PB. 正确
8 Z1 x+ ?& v+ k$ A' K% C      满分：2  分
6.  在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
A. 错误
B. 正确
6 n9 I, B. N2 u, G8 l      满分：2  分
/ q0 {: C- e; O/ H% _7.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A. 错误
B. 正确
      满分：2  分
3 A4 n4 U% f$ l3 w' z8.  数组不适合作为任何二叉树的存储结构。
A. 错误
B. 正确
$ r' t: R, ^( S4 L9 ^      满分：2  分
9.  AOV网的含义是以顶点表示活动的网。
A. 错误
/ Q- C2 |: C5 ^, vB. 正确
; i* `4 L7 @& F3 `, k  l      满分：2  分
: H7 {, `: M; M5 ]8 s8 G10.  哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
A. 错误
. J9 a+ ?4 x5 J3 x0 J( zB. 正确
% K( U1 D, f" s6 z  ~, T      满分：2  分
6 ~. c- T5 l7 u* g# }, k11.  连通分量是无向图中的极大连通子图。
' L, e; y" K" I- b* |) e. y7 ?A. 错误
. C* t! l; \7 F; D1 l$ J3 X, @B. 正确
      满分：2  分
! f9 e' _8 [5 F; ?12.  归并排序在任何情况下都比所有简单的排序方法速度快。
A. 错误
: J5 r$ Z% H% Z7 hB. 正确
# ^; H6 K3 Y0 s* P7 X      满分：2  分
# J. y5 z: x1 m4 a5 ]/ ~13.  倒排文件的优点是维护简单。
A. 错误
B. 正确
      满分：2  分
14.  在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
' m" I& y$ D% {- H+ \4 [/ UA. 错误
6 B) v2 d8 R1 ~  f: V* h0 B- IB. 正确
5 i: a% P: ?* n" w# {( M: O% N      满分：2  分
# m3 ~' _- j+ b% [15.  对有序的单链表不能进行折半查找。
A. 错误
% U8 h7 p  h7 R* f/ v5 }7 FB. 正确
      满分：2  分
0 H/ b: w+ G: \: m0 ^5 S& x4 p16.  归并排序的辅助存储空间代价为O(1 )。
* {( B# B/ D0 }0 OA. 错误
B. 正确
      满分：2  分
17.  用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
9 B! U- W- ~+ [A. 错误
B. 正确
      满分：2  分
18.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
A. 错误
B. 正确
& H% R! }1 Y2 f8 y2 j& |2 M      满分：2  分
19.  有向图的邻接矩阵是对称的。
3 p& ?4 O" z7 H1 V" e9 tA. 错误
& a6 \% S, w) i& M  HB. 正确
      满分：2  分
20.  快速排序总比简单的排序方法快。
$ Z5 ~4 U5 n5 Y1 h% a: o, h/ Z: uA. 错误
B. 正确
- b2 H3 ], j0 E' v  c      满分：2  分
/ e1 ^- T  E* O( G0 `7 S
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。