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

谋学网

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

0 L' o, Q! j2 O8 M% o" ]# U一、单选题（共 20 道试题，共 60 分。）V 1.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
! G+ I; W5 q! ?7 N6 ]% i( @) PA. 直接插入
B. 直接选择
C. 冒泡
D. 归并
- }3 f- i8 B+ P, g8 j* \      满分：3  分
2.  如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
A. 顺序查找
B. 折半查找
C. 分块查找
D. 基于属性的查找
  W) p0 K& n& @2 Z+ D+ R      满分：3  分
3.  假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
/ n3 O/ o# f  y1 |& s      满分：3  分
4.  一个有向无环图的拓扑排序序列 () 是唯一的。
6 t( ~8 P; G) _4 K* KA. 一定
B. 不一定
C. 可能
+ T0 j/ I9 ~9 V% L  @0 ZD. 三者均不对
      满分：3  分
5.  设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A. 1和1
B. 1和3
C. 1和2
& t1 N0 }. v! x+ n+ VD. 2和3
      满分：3  分
6.  有n个顶点的无向图的边数最少为 ()。
A. 0
B. 1
C. n-1
; }' |4 `/ A/ ^/ K# S$ C, _3 e# DD. n
9 d+ f3 L- R1 t9 B7 Q      满分：3  分
( @  T) z" d+ z% ^1 u6 V  q, z# R7.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
! Q/ Z! O" i3 Q; E1 }$ m5 P% IB. 中序遍历
7 R* [4 E5 y# u8 p4 }C. 后序遍历
6 a; e& Y' Z5 z$ m: F0 b7 oD. 层次遍历
9 q& a! l" p- M6 e/ ?8 Z      满分：3  分
8.  顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
# i0 a  m9 m. ^" L% ZA. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
      满分：3  分
: w# A3 A0 p! d  y/ E+ i. b9.  下面哪些方法可以判断出一个有向图是否有环（回路）? ()
  |- d1 P6 `, }6 l, N: XA. 广(宽)度优先遍历
B. 拓扑排序
C. 求最短路径
0 }2 b2 n8 [8 j% c- PD. 求关键路径
      满分：3  分
! S0 }. ~* K% ^. g+ e4 R10.  广义表 (( a , b , c , d ) ) 的表尾是 ()。
3 x0 s/ \1 E4 o9 gA. a
  N# Y" j# [; `2 |" _; J" yB. ( )
1 A" x/ ?7 S' f( p4 O- yC. ( a , b , c , d )
D. ( b , c , d )
0 L/ j/ i* P  Z, G$ I. f      满分：3  分
11.  广义表 (( a , b , c , d ) ) 的表头是 ()。
A. a
+ h! N+ _' d4 X* U% [B. ( )
C. ( a , b , c , d )
D. ( b , c , d )
& S  B  L" A: y) S2 C; }      满分：3  分
+ C2 j6 a$ \. _; W  ]) |" S. y/ U12.  数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A. 直接选择排序
B. 冒泡排序
' _& }7 N' `9 u) y, s! tC. 直接插入排序
D. 堆排序
      满分：3  分
13.  折半查找要求结点 ()。
A. 无序、顺序存储
+ }4 B. R. v# D* T, W3 k2 H7 {9 J6 @B. 无序、链接存储
! g" ~0 ~4 c5 `& c& {- ~C. 有序、顺序存储
. n9 |) B5 f7 G5 r8 i4 P  HD. 有序、链接存储
. s9 l5 i7 _& u$ `0 b) N% F      满分：3  分
5 _: b# l1 H6 B& s5 L" U14.  在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
2 t; V, Z. L5 n5 z/ [3 y- G, lA. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
      满分：3  分
9 _; _/ `7 s$ N  {: @15.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A. 堆排序＜快速排序＜归并排序
. |* D- t0 {$ i+ }/ z6 B- X6 gB. 堆排序＜归并排序＜快速排序
) t! K2 y  f) }  n% S& x$ AC. 堆排序＞归并排序＞快速排序
D. 堆排序＞快速排序＞归并排序
      满分：3  分
/ x( p+ `' D+ \16.  有n个顶点的无向连通图的边数最少为 ()。
6 T7 }( Q3 r0 e! y' V, n; D# ]A. n/2
4 v7 I5 o) u2 T! q( {B. n-1
) Y" ~) ~& Y8 ?: ]) ~C. n
D. n+1
" Z( {' A1 y2 G9 R      满分：3  分
3 X0 H! A2 T! b+ l+ b: x  Q2 n5 a, h- d17.  存放在外存中的数据的组织结构是 ()。
) P6 d* A1 W6 v: `% A' I0 t4 cA. 数组
, O7 t& v5 Y7 z  X2 ]& RB. 表
5 G3 f( a) [& \" a6 u- k" ^C. 文件
. z( R% ]- J/ i6 v/ f+ V" J4 U5 YD. 链表
# E; |- ^7 S; c5 r2 G/ I2 X' p9 b      满分：3  分
! q) W" H+ M5 }6 Z( ~) C18.  设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
5 _7 l3 [0 b' e" aC. Ο(n)
D. Ο(nlog2n)
, w5 F. t- t9 {" o  t+ W  ]      满分：3  分
! g' `- i- q: a! j19.  在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
" X0 h+ `3 r7 g9 y3 Z3 XA. G中有弧＜Vi , Vj >
" _) L5 s& g" X( f9 B( hB. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
      满分：3  分
; S# P2 N/ w+ m+ Q9 L9 [20.  在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
& Q- o9 d* z0 u- T# CA. 希尔排序
B. 插入排序
C. 归并排序
D. 选择排序
' `6 [  b, P0 M- P. x+ R) S& A; m      满分：3  分
! v: h% @3 P  G" x% a3 [
二、判断题（共 20 道试题，共 40 分。）V 1.  最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。
A. 错误
6 L# R% k, A* u" NB. 正确
      满分：2  分
2.  快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A. 错误
B. 正确
& C5 b( E" X1 `/ V! ^# W; u      满分：2  分
3.  最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
: O3 ~/ f. r2 I. H8 |A. 错误
B. 正确
      满分：2  分
! c$ N8 v" j- X6 ?( }& u9 d9 X4.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
A. 错误
# Q. |6 k4 @" v" Y# _5 pB. 正确
      满分：2  分
5.  邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
A. 错误
& h7 z2 i+ a) t: M+ OB. 正确
* V$ c: d. K8 P0 Z/ A4 N      满分：2  分
6.  在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
8 v, x) Z! k0 T2 n& u0 zA. 错误
B. 正确
8 K) K3 M' N( A( F5 b      满分：2  分
7.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
3 q/ N' Z- a! fA. 错误
B. 正确
      满分：2  分
8.  数组不适合作为任何二叉树的存储结构。
A. 错误
B. 正确
      满分：2  分
9.  AOV网的含义是以顶点表示活动的网。
A. 错误
7 q) z# O- s: @8 b! i) r* O" r+ `B. 正确
      满分：2  分
  O1 i  A% W( r10.  哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
& q  d1 z1 ]; S: q/ S4 [A. 错误
5 U& i: Y! G7 b% F5 S+ ]$ yB. 正确
3 I$ H" P' f! r$ Y* ~      满分：2  分
11.  连通分量是无向图中的极大连通子图。
A. 错误
B. 正确
      满分：2  分
, V) ^- ~; D1 T* ^; a% _12.  归并排序在任何情况下都比所有简单的排序方法速度快。
A. 错误
B. 正确
4 T% R5 V+ o: t: Q( X# U& F      满分：2  分
13.  倒排文件的优点是维护简单。
A. 错误
4 q5 i9 P, E* i; Z1 k- LB. 正确
      满分：2  分
& C" g' _  H, e$ P14.  在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
A. 错误
B. 正确
      满分：2  分
( ]# C- k& B6 Y$ R7 q' ?15.  对有序的单链表不能进行折半查找。
A. 错误
! b9 {% \3 t0 b1 ?B. 正确
      满分：2  分
. S; x6 }0 a9 y16.  归并排序的辅助存储空间代价为O(1 )。
A. 错误
$ R  w5 _2 _* t: _- r' P  iB. 正确
      满分：2  分
) c& F0 Y6 A7 s. T17.  用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
A. 错误
6 ^2 c9 x% o4 T' a: Q& aB. 正确
      满分：2  分
; x3 h: r4 E) {( w18.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
" T% C: C+ C4 ]/ PA. 错误
! m3 y- n- \0 \' e, u) XB. 正确
      满分：2  分
2 D* W4 k8 m8 u& N, s19.  有向图的邻接矩阵是对称的。
% l  w4 G' @& T* [: s" O) e4 bA. 错误
B. 正确
. L  f4 M! R# y/ F0 B      满分：2  分
20.  快速排序总比简单的排序方法快。
A. 错误
3 Y( _& t6 _2 E8 }B. 正确
: M. A1 k" J; ]$ ~2 B      满分：2  分
. G7 \$ m0 W/ Y2 |* }
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。