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

谋学网

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

一、单选题（共 20 道试题，共 60 分。）V 1.  顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量000，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
4 F2 a( s1 q/ S+ IA. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
- R3 w! C0 s" _D. 连续排序
      满分：3  分
2.  求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A. 无向图
B. 有向图
C. 带权的无向图
' [+ P5 t5 N* z+ S2 ED. 带权的有向图
) l  `6 g7 n. W& O( C' A      满分：3  分
3.  采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
A. n
9 H6 j9 L" ]% \  }* Z" s! OB. (n-1)/2
C. n/2
D. (n+1)/2
      满分：3  分
4.  广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
0 j6 i& ?+ q% M: n& aA. ( c , d )
B. c , d
C. ( ( c , d ) )
' K. K6 Z9 S: N2 [& d2 u- m% gD. d
      满分：3  分
9 X  w3 K  G1 n0 w8 {4 L7 q" v) A5.  用折半查找法查找表的元素的速度比顺序查找法()。
' ]: s" y2 A' A( EA. 必定快
0 ]1 d. c5 n+ b, cB. 必定慢
C. 相等
D. 不能确定
) L' r5 K/ x8 Y- }7 F      满分：3  分
. G7 p0 R0 h2 f; @) a/ K+ {7 B6.  排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
% F# O& E( Z4 a! _C. 冒泡
D. 归并
      满分：3  分
$ i4 @8 z& V5 S7.  平衡的二叉排序树(AVL树)属于()的数据结构。
A. 动态
B. 静态
C. 线性
+ E4 b, `6 `* [; F* {; \! ~D. 无结构
5 d* W5 `% k  R/ c; n8 T      满分：3  分
; p  R( Y9 ?+ P2 w4 T+ F% A/ r8.  一个有n个结点的图，连通分量的个数最少为 ()。
A. 0
1 {% j8 o( q0 W) k" t4 a: P; FB. 1
C. n-1
D. n
& I0 c% b' M9 o  Q4 M1 p8 _( o      满分：3  分
  D, x7 R* L6 k; [, d9.  设有100个关键字，用折半查找法进行查找时，最小比较次数为 ()。
: q2 o% a  g; ?5 T8 KA. 7
B. 4
C. 2
D. 1
, t# x; B+ i7 S" Y, _) ~- p      满分：3  分
' |5 d& [2 U+ J1 s10.  采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
      满分：3  分
11.  在下述几种排序方法中，辅助空间需要最多的是 ()。
6 L& b) R* y5 Z/ s3 N& ^A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
      满分：3  分
12.  下列排序算法中，其中 () 是稳定的。
+ Y$ |6 P# i8 Y; X" B: W% JA. 堆排序，起泡排序
; L6 q* l& b  V0 q/ oB. 快速排序，堆排序
  [' a; h  N/ B  OC. 归并排序，起泡排序
3 E* q2 e! f1 m5 `  B! S( {6 tD. 直接选择排序，归并排序
; C. b) D" V4 N2 F      满分：3  分
7 V) _! g/ V$ i6 }13.  对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A. 1000
B. 1010
C. 1008
0 _: a1 ^; v6 yD. 1020
      满分：3  分
14.  数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
% p8 v7 @. Y2 W8 t2 h* D5 ^) XA. 直接选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
) V% d+ j( D. ], Z      满分：3  分
; Q* s- y( R& K& F' s15.  求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。
A. 无向图
/ }/ j& l: n$ g' |' aB. 有向图
C. 带权的无向图
D. 带权的有向图
4 n0 E6 H/ @2 O2 r      满分：3  分
16.  下面说法不正确的是 ()。
: n- p( m, r' _6 l0 ~A. 广义表的表头总是一个广义表
7 L/ f, x$ N, K7 @! p9 KB. 广义表的表尾总是一个广义表
C. 广义表常采用链接存储结构
D. 广义表可以是一个多层次的结构
      满分：3  分
17.  稀疏矩阵常用的压缩存储方法有两种，它们是 ()。
A. 二维数组和三维数组
B. 三元组和散列
1 x. _; ?% X1 r7 O& wC. 三元组和十字链表
7 Q5 A1 w* g: WD. 散列和十字链表
      满分：3  分
+ Q3 A% j1 H7 T+ R! ?. W18.  用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
& G# `( [" ]7 K- L+ UA. 逆拓扑有序
B. 拓扑有序
# J- m! M. k6 }C. 无序的
1 a: Z- }2 n6 P. ?; b# dD. 部分有序的
2 K" m% E* f9 @" u      满分：3  分
3 D7 t, O) s8 {) ^/ ~19.  将一个A [1..100, 1..100] 的三对角矩阵，按行优先次序存入一维数组B[1..298] 中，A中元素A [66, 65] 在数组B中的位置K为 () 。
A. 193
0 n! h( }0 z  U  e4 hB. 195
C. 197
2 q/ ^, y( h% p. Z2 z" AD. 199
      满分：3  分
20.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
- o: J9 {3 \, f- F6 i5 N% j) ?A. 堆排序＜快速排序＜归并排序
3 S) P1 F" I! ]9 n, _6 q, L4 eB. 堆排序＜归并排序＜快速排序
C. 堆排序＞归并排序＞快速排序
  }3 ~8 m5 a0 s! Y6 O- ED. 堆排序＞快速排序＞归并排序
      满分：3  分
8 F1 Z: X! f' }
2 Y2 n% V3 [& K: R4 y二、判断题（共 20 道试题，共 40 分。）V 1.  数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插人、删除等操作。
A. 错误
B. 正确
2 y; X+ N) D. U; }. W( i2 x      满分：2  分
2.  对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。
. K4 G+ i7 i4 {9 t) _% g* E% FA. 错误
B. 正确
      满分：2  分
6 T' I4 \4 U% v0 k. x3.  对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
3 C4 t$ c- p& o( W5 Q" FA. 错误
. ]0 L; ]& H0 ?3 c  FB. 正确
3 o. S. v. l; i  s# n* s1 R; P      满分：2  分
4.  虽然关键字序列的顺序不一样，但依此生成的二叉排序树却是一样的。
& O8 ?( e" o9 Z/ L  U- p6 ~A. 错误
) {1 r! F' v" h" q- f( G! P+ z* ]B. 正确
      满分：2  分
5 n* E( P3 j4 F- f5.  分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
/ W: u$ P2 ]- k: V: \A. 错误
B. 正确
% _3 N( S$ S/ Q      满分：2  分
( v( ?; p3 c# `1 Z! V6 s. l1 w6.  二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。
6 ^4 ]$ a* y' b3 `# S# F4 L) A) N1 aA. 错误
; n2 S: m, j  A! a0 qB. 正确
      满分：2  分
8 O  z' F( O- W: O. K* x& C4 B7.  倒排文件的优点是维护简单。
7 z0 R& z8 B* o0 \! a! e+ rA. 错误
B. 正确
      满分：2  分
8.  有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。
A. 错误
B. 正确
1 ?3 O9 w5 F% f) |) s: E      满分：2  分
3 G2 G1 [6 ~1 I. g+ c( [4 B9.  强连通分量是无向图的极大强连通子图。
A. 错误
B. 正确
! ]7 j4 |7 Q' B      满分：2  分
10.  就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
) L8 X  h- ?$ ~4 R: tA. 错误
% G/ g! `9 `1 k. DB. 正确
9 Y" `  [& E# \( f      满分：2  分
9 ~2 X) X( r0 ?" Z11.  带权的连通无向图的最小(代价)生成树必是唯一的。
8 I+ n0 c( Z; Z# `- ?/ ~5 EA. 错误
B. 正确
      满分：2  分
6 Q$ a# U9 S& ?  n12.  内部排序要求数据一定要以顺序方式进行存储。
4 Q9 d$ L* i( M9 k3 F; Y" HA. 错误
B. 正确
      满分：2  分
7 \. b) W) \( a( B0 l; {! F+ h  Q13.  文件系统采用索引结构是为了节省存储空间。
A. 错误
B. 正确
$ ?. X* c( K& w4 @0 w) w# B+ ]) ^      满分：2  分
14.  在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
" Q+ B) K; V: ^0 ~( y( l' lA. 错误
6 G4 a! w5 V! m0 G0 IB. 正确
      满分：2  分
15.  哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
. z9 |1 B6 q2 s/ x/ G3 RA. 错误
B. 正确
      满分：2  分
16.  在有向图中，度为0的顶点称为终端顶点(或叶子)。
A. 错误
B. 正确
2 Y& m- x+ }( c) p; r( u/ z, A$ N      满分：2  分
17.  直接访问文件也能顺序访问，只是一般效率不高。
A. 错误
B. 正确
1 {0 z$ z* |; p) ]1 ?+ r      满分：2  分
18.  任何无向图都存在生成树。
A. 错误
B. 正确
      满分：2  分
19.  对磁带机而言，ISAM是一种方便的文件组织方法。
' K4 z6 ?$ Y1 ^A. 错误
  M2 f, ]+ z, |" O; `- G% ~B. 正确
1 J9 p7 p) U" v      满分：2  分
9 G2 p4 e! s5 A/ O" e$ g2 \20.  无向图的邻接矩阵可用一维数组存储。
; X& R  f6 P8 n# g0 lA. 错误
* ?2 t' l7 ]+ ^- BB. 正确
      满分：2  分
; q9 ?/ S# ?" k" V& |
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料和奥鹏毕业论文以及提供代做作业服务，致力打造中国最专业远程教育辅导社区