东师《数据结构（高起专）》14秋在线作业2（随机）辅导资料

谋学网

谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。


一、单选题（共 20 道试题，共 60 分。）V 1.  “堆积”问题是由于()引起的。
A. 同义词之间发生冲突
B. 散列函数
; {' f- u' b/ ~1 s4 B# rC. 不同的同义词子表结合在一起
4 K1 D/ C. z9 Z& r) s' ^D. 散列表“溢出”
      满分：3  分
4 r, |4 i9 [! W9 A% x) d" _2.  用折半查找法查找表的元素的速度比顺序查找法()。
A. 必定快
: u+ H  R) j6 {) a4 [' y9 hB. 必定慢
  h1 j& X! F: d4 r+ P. b" _( r1 d7 e& CC. 相等
D. 不能确定
      满分：3  分
3.  下面哪些方法可以判断出一个有向图是否有环（回路）? ()
8 N" L1 T+ z7 pA. 广(宽)度优先遍历
$ K) P& H4 |0 i$ kB. 拓扑排序
C. 求最短路径
D. 求关键路径
$ J( J1 o. h. T9 Z3 ^% O      满分：3  分
4.  ISAM文件和VSAM文件属于 ()。
8 C& a6 ^  Q9 c8 V' EA. 索引非顺序文件
3 q+ P" F# @7 [7 fB. 索引顺序文件
C. 顺序文件
D. 散列文件
9 s( I( K+ }# I( x6 e" q      满分：3  分
5.  有n个顶点的无向连通图的边数最少为 ()。
A. n/2
+ n" T5 e2 Q8 ?4 n4 TB. n-1
4 |' l4 f/ U+ ]% K/ @, xC. n
D. n+1
) |0 O1 @$ O5 ?9 i, `5 k/ {% b      满分：3  分
2 c9 I6 |" B1 T8 _, v6.  散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
3 k# c; K3 i2 d3 n5 bA. 同等概率
. o2 n5 J$ l& |$ v# DB. 最大概率
, Z, n$ u% v; L( ?7 W9 G, nC. 最小概率
D. 平均概率
4 {2 d& Q+ z) d      满分：3  分
. _; P0 W: s( I, ~7.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
" ~" V) O& s4 B9 `+ r, A  u4 oB. 中序遍历
C. 后序遍历
D. 层次遍历
      满分：3  分
$ C& G$ i- O7 E2 y% O0 w4 t' |8.  广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
A. ( c , d )
7 c: p& o* T3 D( w% U5 M8 IB. c , d
C. ( ( c , d ) )
D. d
      满分：3  分
! U. E! k7 w8 Q& r1 H" F5 t! k2 |9.  有n个顶点的有向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
6 k2 l. S$ t' x- I/ YD. 2n
      满分：3  分
/ r; E% P( Q. q. h. W10.  快速排序算法在下述哪种情况下效率最高 ()。
A. 被排序的数据已完全有序
. d: l2 ~$ s, s7 h) nB. 被排序的数据中含有多个相同的排序码
1 @( m7 C- O/ d3 lC. 被排序的数据已基本有序
D. 被排序的数据完全无序
      满分：3  分
$ X0 N" y- d6 e: |  U11.  求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。
' X$ _" y. X9 `  ]A. 无向图
B. 有向图
1 J* D( P3 Q; XC. 带权的无向图
/ ]# |+ q6 A1 ]  a; [8 g  QD. 带权的有向图
      满分：3  分
12.  用ISAM组织文件适合于 ()。
A. 磁带
8 X5 X# l( |" V3 F" wB. 磁盘
C. 光盘
7 k2 V, l4 f6 A3 K/ ZD. 外存储器
: S4 X' |) X# @+ `  C1 O4 h* Z9 W      满分：3  分
* q4 m/ C1 t8 X. `2 C, d. W* v13.  分块查找要求表中的结点 ()。
9 w4 @$ |/ a2 {8 n) U) kA. 全部无序
B. 块之间无序
, [! ^" X% k( _4 c! u9 C) UC. 全部有序
' H/ X4 }5 `. Z& v* n& a; H8 O$ k6 WD. 块之间有序
      满分：3  分
( W( z; Y8 Z9 o7 s14.  下列说法不正确的是 ()。
7 P4 H9 ~* r2 y! k9 t: m" b8 ~A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种：深度优先遍历和广度优先遍历
- u+ B3 e6 F* lC. 图的深度优先遍历不适用于有向图
3 ^: H) n/ m2 Q  R( [, E1 XD. 图的深度优先遍历是一个递归过程
* u' t5 ^1 D* k      满分：3  分
15.  有n个顶点的无向图的边数最多为 ()。
A. n
B. n(n-1)
; b9 v% s. `% SC. n(n-1)/2
D. 2n
. T' Z: C( u4 u& ~" c5 _      满分：3  分
  C, |1 ]# D. g: f16.  设有n个结点的AVL树，其平均查找长度为 ()。
A. Ο( 1 )
  X* C( R5 Q; X9 u* c& aB. Ο(log2n)
( u2 ], [( }1 PC. Ο(n)
& a- h2 r) M3 q  vD. Ο(nlog2n)
      满分：3  分
17.  设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[j]的地址为 ()。
A. LOC(A[0][0]) + (j*m+i)*c
+ n" H: i- j0 [$ gB. LOC(A[0][0]) + (i*n+j)*c
7 u1 o5 F# D/ c6 yC. LOC(A[0][0]) + [(j-1)*m+i-1]*c
D. LOC(A[0][0]) + [(i-1)*n+j-1]*c
, Y, [! h/ e3 c! ?! R8 V      满分：3  分
% L8 M0 a2 V  s9 v9 f18.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
A. n
/ b* G- [! c  B2 V& x1 GB. (n-1)/2
$ ^% d( `5 X/ [, _! [' TC. n/2
D. (n+1)/2
; W& C; C$ i/ [  v7 e6 a, B. m      满分：3  分
  I8 c2 \& {" i( x( m4 S% l6 p19.  若要求尽可能快地对序列进行稳定的排序，则应选 () 。
" T8 E% V' t1 vA. 快速排序
% P8 V* V2 ~% c) Y9 ]B. 归并排序
4 C( d' S* C, W& R) J- ^0 h4 z$ Z# w) AC. 起泡排序
D. 希尔排序
5 S1 h- v* c- |% V4 E0 d! {      满分：3  分
: g6 k# {. @1 G" J5 F7 i20.  顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A. 附加文件
" ]8 Y5 K/ n. Z8 c8 B7 {, gB. 按关键字大小排序
7 x3 b9 {! G1 \* N; {8 B5 ~C. 按记录输入先后排序
D. 连续排序
5 x; |+ [6 {, ]) Z- o! ?$ ?9 D" D      满分：3  分
; Q6 k3 b7 m1 r& @+ S% j  E5 U0 g3 J8 z
二、判断题（共 20 道试题，共 40 分。）V 1.  在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
/ V, {8 u5 O$ o: b7 nA. 错误
# m$ B7 h* }/ j8 J2 `( z6 b) \B. 正确
9 b; V* V& P3 x% r% ?6 m      满分：2  分
: E. F4 b1 c  ^" H- }; u2.  最佳二叉排序树是静态的，而平衡二叉排序树(AVL树)是动态的。
A. 错误
B. 正确
      满分：2  分
3.  在待排数据基本有序的情况下，快速排序效果最好。
# \) z  p- s) J6 K. L/ l+ J5 gA. 错误
B. 正确
      满分：2  分
# U. w3 N; c2 t" R4.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
A. 错误
0 C! q' s* T, A2 M/ b0 vB. 正确
! s8 N" T3 b- b4 z- `  T      满分：2  分
/ k  z; C4 p' ~* B4 a9 d5.  N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A. 错误
B. 正确
7 @7 [" c/ e+ s+ d6 m% I5 h( y      满分：2  分
9 j5 M: K3 L( p0 f" C# [) `6.  无向图的邻接矩阵可用一维数组存储。
A. 错误
B. 正确
      满分：2  分
. n8 _) s' c. k7.  归并排序的辅助存储空间代价为O(1 )。
A. 错误
B. 正确
! e* {8 Z% p, o; p$ P, @" i      满分：2  分
8.  对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
A. 错误
B. 正确
      满分：2  分
9 U2 G9 T4 ?7 y$ P$ }1 w4 ^9.  对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
' `. y# x( M, x9 sA. 错误
B. 正确
      满分：2  分
10.  在待排序记录已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
- M+ o. r) C4 \# U# xA. 错误
, g: b7 h5 d2 i! y$ a% C) JB. 正确
# w, o+ Y1 [. u8 u6 q      满分：2  分
11.  连通图的各边权值均不相同，则该图的最小生成树是唯一的。
$ I1 F; u) N1 y( lA. 错误
* Z  H  }. O5 Y! b4 gB. 正确
( m# ?. Y9 o$ w& _& Y      满分：2  分
0 g" u" x$ l7 f2 C6 h1 O: x+ Q12.  在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
" w8 N# [8 I( H# c) PA. 错误
B. 正确
      满分：2  分
% |* p# ]" R( d& O8 C6 B; o: }13.  在有向图中，度为0的顶点称为终端顶点(或叶子)。
* r# u" e$ b$ k3 ~A. 错误
B. 正确
      满分：2  分
14.  用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
. ?" z3 C: M, l. C3 `A. 错误
  \/ o' R: E' Q% E+ O# ^B. 正确
, y& G1 P# {' O1 \" ^% M% s) j      满分：2  分
* @% F( b" p& D. ?* c15.  对有序的单链表不能进行折半查找。
A. 错误
B. 正确
      满分：2  分
16.  当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。
, }$ t  g+ i: O3 J9 [A. 错误
B. 正确
      满分：2  分
17.  用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。
A. 错误
B. 正确
      满分：2  分
# z& p3 C5 T$ @) S18.  顺序查找法适用于存储结构为顺序或链接存储的线性表。
2 u' n6 O7 \6 r. z" U2 WA. 错误
  @# v6 a9 u7 ]& l9 d  W9 q& |# C& FB. 正确
      满分：2  分
7 c" W& x" Q- T0 U, s19.  文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
9 z6 ?  _  k" I9 aA. 错误
B. 正确
& a+ [. r8 r5 t4 I. V      满分：2  分
20.  哈希函数越复杂越好，因为这样随机性好，冲突概率小。
8 t+ {1 u! c- I# z& VA. 错误
+ G$ Z7 ^3 J/ g) y: aB. 正确
      满分：2  分
3 c7 M* o  {1 f" K8 s+ b% A' ~
- F# G# `( @8 [( ~) M谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。
6 \: e# Z3 I1 o6 R* U+ N: D/ I0 {: A