|
谋学网: www.mouxue.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。
; L+ k+ C: [9 ~) t+ o( ]
) Z8 r6 s3 K6 ?) h) H: k一、单选题(共 20 道试题,共 60 分。)V 1. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
. m1 x, @' L6 e5 w& tA. 直接插入
# `! h1 D0 a/ B, @1 Z9 VB. 直接选择
" G# g3 m4 g0 U8 gC. 冒泡6 z4 {# n+ M1 A
D. 归并
* \5 L8 G, k5 B7 X& P# _7 [' s 满分:3 分+ K6 ]! W) Y6 k1 K I
2. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求,则可采用的查找方法是 ()。
, N9 x# |7 C n* g5 Z; h. kA. 顺序查找5 @6 X( i D( V! P3 T+ y s
B. 折半查找# r0 a6 P' D. m" S: d( b
C. 分块查找
+ c9 `- ~" O3 |* g: mD. 基于属性的查找
: E1 V3 I& {/ g* w5 R0 z 满分:3 分
6 k, z- b; H* Q% G: ~+ d- v2 Z7 r3 l3. 假定有k个关键字互为同义词,若采用线性探查法把这k个关键字存入散列表中,至少需要进行多少次探测?()- S/ E6 m: ~1 N* V
A. k-1次
" U: n1 d* K! J9 uB. k次. F/ n1 O- u* R1 E( U
C. k+1次
/ r9 w7 p7 Z: BD. k(k+1)/2次- H5 L" t B0 i% m* q! A* z0 E
满分:3 分
* B% T! \: E) d7 T! k! q4. 一个有向无环图的拓扑排序序列 () 是唯一的。8 H9 X6 i* P1 f1 a
A. 一定( {4 S. Y$ {3 I# w
B. 不一定9 k6 V6 \' b5 _" A: k: u
C. 可能$ ?6 z& U- j% ?: K6 N" L- k
D. 三者均不对1 l x( {! L* F) t1 n& D8 b
满分:3 分
8 p/ |" }! y N% `# T( P5. 设广义表L = ( ( a , b , c ) ),则L的长度和深度分别为 ()。
: y4 p6 o+ u' s- P% vA. 1和1
# _8 X5 g: b1 j( L$ ^7 M: p. n- HB. 1和34 T( Z2 d! O/ M* o, ~2 `( F
C. 1和2
6 l8 }. F/ R+ ~& x" _/ q& J* `% ED. 2和3
. g5 ^0 X% e# \ 满分:3 分
0 u5 C5 J3 ~" E$ G7 c+ p6 I. p6. 有n个顶点的无向图的边数最少为 ()。
! g0 w" O* c( P% T) K" M$ N, o7 EA. 0
8 R8 _" ~/ J2 y) h% t, KB. 1
$ K6 e6 Z1 D! W# c7 e/ T# zC. n-13 W+ D' C% ^+ U* g) Z% L
D. n
( Z4 r, n1 l6 A" `- g% P5 p% F$ q# G 满分:3 分. c+ [* M8 h7 r
7. 采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。' M2 S) O: f6 D
A. 前序遍历
4 w3 \" _& J5 \9 G) OB. 中序遍历3 U ~/ l) l7 ]! k
C. 后序遍历+ O- s1 T# S" {
D. 层次遍历! e1 S3 H' y: f4 t
满分:3 分
# g( a+ v9 B# M) l8. 顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。! e7 t4 e; d1 U) X
A. 散列存储% R0 c# A. V# S4 E" v" G; d
B. 顺序存储或链接存储, l/ L; O, a; @: n: P, {! f& @" X
C. 压缩存储! {. u* i0 m* S1 H
D. 索引存储
: f4 t/ j# z- O& A3 f k- m 满分:3 分
4 o, m+ |3 L$ N% F2 t$ q0 l" I9. 下面哪些方法可以判断出一个有向图是否有环(回路)? ()
4 z7 C* l- g5 ?4 g3 _3 k0 SA. 广(宽)度优先遍历
$ k, }5 @+ g" }1 `B. 拓扑排序
/ X; Q7 r5 z6 z9 D8 NC. 求最短路径
7 r; }* b% `0 Y$ g5 ~8 zD. 求关键路径+ c& _! R& N3 b. ~2 I
满分:3 分" @* n- T R6 C. h- }& k7 r I
10. 广义表 (( a , b , c , d ) ) 的表尾是 ()。
- h6 u* G1 m/ H7 RA. a& d5 L8 R6 n% b& [! x! Z/ j( C2 B
B. ( )
6 J. O4 U3 T9 C: w! G" f4 MC. ( a , b , c , d )9 N; L! c1 E& A
D. ( b , c , d )
$ A0 K1 g- t0 e" o9 } 满分:3 分
( v! s3 v4 U4 n' E# B11. 广义表 (( a , b , c , d ) ) 的表头是 ()。+ }& w) I! r0 Z0 L# I' ~: t9 f. ^+ g
A. a. j" \" t: p) T' |
B. ( )1 ]( m1 s& M3 z0 G: @
C. ( a , b , c , d )
) i2 w i8 r6 G. v/ OD. ( b , c , d )2 c8 o& ~2 {1 o( o! ^
满分:3 分5 Y ~* ~, l+ l
12. 数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
1 p, ~ C( m. l9 k* i4 w1 RA. 直接选择排序
3 N! c9 Q2 K, o4 H: a d4 Z6 M: sB. 冒泡排序* N5 C0 _, _' R% q1 L
C. 直接插入排序
* w! R' Y! C9 \/ y5 zD. 堆排序
) ~! r2 b8 `3 O R/ @ 满分:3 分7 [6 b, R, P! a. Q! }: f- D
13. 折半查找要求结点 ()。0 `7 I- [' e; N- L; L
A. 无序、顺序存储+ N! }& y, s/ y5 e4 X, g( b+ j
B. 无序、链接存储
. I. \: E* m! Y0 YC. 有序、顺序存储3 g4 o/ }: X. t9 l" }. {& S
D. 有序、链接存储& Y. b4 {* y/ U, {% e
满分:3 分# m: ]0 \+ @ F
14. 在下面的排序方法中,其比较次数与待排序记录的初始排列状态无关的是 ()。
! @8 G& P) U* U8 \7 O0 g8 [ J fA. 直接插入排序& s' G2 L1 I% A) I
B. 快速排序8 X9 D' T7 @4 f) d' |5 G
C. 直接选择排序! e% ]# G3 J; {2 L' U4 }
D. 归并排序' ?" i8 t1 B3 b
满分:3 分9 _! E% Z3 B* K& @9 U; L
15. 就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是 () 。
: [/ k( ?# [6 r5 r5 x7 h8 PA. 堆排序<快速排序<归并排序: c, t9 N# q. T
B. 堆排序<归并排序<快速排序
6 B1 m" \ ] x$ Q& Y6 v9 R9 eC. 堆排序>归并排序>快速排序
; {7 T$ Q. c0 g8 Z# F' ?5 @* S" z# ZD. 堆排序>快速排序>归并排序
0 L+ ^( d! Z' m9 N# B 满分:3 分
+ f5 b# D" \: j @. r y/ }5 c& H$ O16. 有n个顶点的无向连通图的边数最少为 ()。
/ x9 t. \" X; W1 V1 }) g" l. B5 fA. n/2
0 o, o G4 T3 E1 f B" z0 pB. n-1
- `0 g9 X( Q d+ F5 v! L& eC. n0 V1 V' g8 u, m( o
D. n+1; `+ d7 J$ }5 g
满分:3 分) @; t# X& Y7 i6 U8 ^
17. 存放在外存中的数据的组织结构是 ()。
) ^' R5 n' a3 gA. 数组' W& F6 P" r; O2 M+ c. B' y
B. 表8 o0 l" ~2 J2 v
C. 文件5 G- w. O5 C% Z* g a- c' Y
D. 链表7 ~& L, p# A$ K
满分:3 分
# w5 I5 z- X8 s18. 设有n个结点的二叉排序树,对于成功的查找,最多的比较次数为()。9 Z% T6 f3 Q% j9 r% |# E7 G
A. Ο( 1 )% G8 q; g) A4 h6 ~/ Y+ J
B. Ο(log2n)
+ Z d( a# ~$ r/ T1 H4 ~' o" SC. Ο(n)
& q5 }6 S1 k% m# {D. Ο(nlog2n)
. \7 n2 N* P- u6 ? 满分:3 分
7 ?( r0 A% ^2 H0 }& O19. 在有向图G的拓扑序列中,若顶点Vi在Vj之前,则下列情形不可能出现的是 () 。2 X3 j: c& X* d5 f) M& {; h4 b
A. G中有弧<Vi , Vj >0 A1 g4 ]+ J2 e( @% ~
B. G中有一条从Vi到Vj 的路径
, k. v4 H9 ^9 m, m8 rC. G中没有弧<Vi , Vj >2 j1 [8 z1 l& |9 B
D. G中有一条从Vj到Vi 的路径6 b5 w( s7 @2 Y5 B* q; K# C
满分:3 分
3 b! n4 ]/ l& A# D20. 在排序方法中,从未排序序列中挑选记录,并将其依次放入已排序序列(初始时为空)的一端的方法,称为 ()。
\, y" k5 l2 p6 Q' Q% uA. 希尔排序
' Z) k6 f8 C3 e3 ~2 A% `! FB. 插入排序
- x7 c ]" A2 k- k' w* V; NC. 归并排序) q4 ^% \& G4 [! W2 p6 F
D. 选择排序
$ Y0 s" C% l, z5 e 满分:3 分
) Y4 t) N, e1 ~8 D4 G m6 K* n8 n: L5 |) k; `
二、判断题(共 20 道试题,共 40 分。)V 1. 最佳二叉排序树是静态的,而平衡二叉排序树(AVL树)是动态的。
" S% w W; g1 o: m YA. 错误: L @/ p `" ]1 ~% k, w9 q
B. 正确
! S- x4 s; W+ K) R$ B, t: E 满分:2 分
% T ^7 ` I6 _( p: h2. 快速排序的速度在所有排序方法中最快,而且所需附加空间也最少。
; A z4 d! ?3 k. d, `* J; mA. 错误' ~2 B. e* z" G1 r/ v
B. 正确5 Q, D k+ z, C; S1 Q9 z* w9 {, ?* C
满分:2 分; Q/ s( G) {% W( `
3. 最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。4 g" K. C) w6 [1 e0 q
A. 错误* L+ ]" k0 \8 L2 d% p U2 u
B. 正确
1 z, O1 j: \ d4 i 满分:2 分
5 [. ]% t. m1 `: a0 x( T% m# ^. c4. 对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
6 F# |. a. e5 z# ?# h# dA. 错误0 Q$ Y: \( ?1 X; t' `7 K7 D/ [. G4 o
B. 正确
2 |+ C; b( s0 |- t' _ 满分:2 分9 X: Q0 Y' T# A9 W h9 `1 j: X& v
5. 邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。
4 r2 o' U9 L! Y" SA. 错误
1 i# B: k. O0 M. Q# f1 @3 ]B. 正确
6 w+ Q0 u- W( H+ B 满分:2 分
" w2 p$ [6 n/ }" A' K6. 在图G的最小生成树T中,可能会有某条边的权值超过未选边的权值。
5 N8 D7 L2 u& o6 ?% i0 I& y- MA. 错误
4 Z7 r. K7 A3 \" c; a3 x: WB. 正确! n2 B( c2 ]: M% l
满分:2 分
4 N% f9 }6 n6 p! C5 \7 n; \0 o7. 哈希函数越复杂越好,因为这样随机性好,冲突概率小。3 S& a4 O C ]) u4 ?
A. 错误" b+ L2 X8 ~+ N
B. 正确( A5 h. H" x$ h H
满分:2 分
/ a" K: c% P t6 }" m8. 数组不适合作为任何二叉树的存储结构。
7 H3 r# _/ m' z# L: T$ V+ F4 s- uA. 错误
9 g- m p4 _, z5 ?" _4 TB. 正确
3 d: a$ y) D/ r. h' x! p9 f+ o 满分:2 分9 d6 G4 r# q- y7 V8 N7 t
9. AOV网的含义是以顶点表示活动的网。. A: s, }3 ~/ [" |
A. 错误
4 q( Z% P" c2 \; ~7 x5 B* WB. 正确
9 W, e |4 b$ T* o 满分:2 分
3 n P$ I- q: C+ [4 ?( _0 ?10. 哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
7 x' p/ k# }. L8 ]A. 错误
p! G9 I; ^* x+ f6 ]) yB. 正确0 \* u9 J9 b& U ]# r' D: u
满分:2 分( |( F, A" ^; a
11. 连通分量是无向图中的极大连通子图。8 t: N; T' X% {3 y0 ?
A. 错误
5 [2 t# @+ l# D" v" t4 @4 XB. 正确
, l. Y! H# Q2 N/ m% }& ~' z 满分:2 分
/ c6 ]/ }! }8 h; [7 p12. 归并排序在任何情况下都比所有简单的排序方法速度快。
) U! Q) w' G, X! U; C/ ~A. 错误
" I3 k+ _" Y+ \* a2 e. bB. 正确- A. k6 R' @" h1 K
满分:2 分. l/ \& i& O7 f% Y
13. 倒排文件的优点是维护简单。1 X& }' ]3 w& c
A. 错误
# i( k! t9 `, U: ^1 L MB. 正确
: |# q. \ n! g5 l" v3 e 满分:2 分) [- m/ u# U8 l, |" x ~
14. 在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”。
, B# n: s6 u: P8 jA. 错误
8 V$ S4 N1 ~: |: w) v. H! m+ z, D- ~B. 正确
; `# G/ @7 N. ~$ a2 K6 H8 }( P5 t 满分:2 分, K: I1 B9 s6 Z0 `# F- z" f% Q
15. 对有序的单链表不能进行折半查找。5 _7 D* L. F( a
A. 错误, f2 p1 t3 F; a
B. 正确8 t e3 P( s9 b9 _ o
满分:2 分
/ ]! ?9 C9 j8 P/ [1 v" D+ I0 {" P16. 归并排序的辅助存储空间代价为O(1 )。, }- ?/ z) u4 ]$ i6 ^" C0 u$ R
A. 错误& B- C6 Q6 k) p
B. 正确 u$ J0 b5 N' _' ?2 T) c# _1 l
满分:2 分8 M" c0 T# @3 j9 S/ C8 p- k8 V( U
17. 用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。' z8 Y- v/ i3 p7 R- j
A. 错误& u( Z1 ~# d& T7 ?
B. 正确9 U9 S2 M5 r. N& e, }: l
满分:2 分/ @+ K" U1 ]/ a6 S& H( L
18. 广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。
; ?: o. c# n( Y. ?7 k1 J; j+ j6 wA. 错误
) \5 C- E: r1 z5 F0 jB. 正确) f5 R8 A9 b2 l0 }1 X
满分:2 分0 U& W9 O# M% w4 j
19. 有向图的邻接矩阵是对称的。, [+ K& T$ J2 p, n
A. 错误
) F/ `+ U4 S, d4 T% |6 rB. 正确: l% T1 n0 T: S2 u& \" w
满分:2 分
9 p ]2 P4 S, m5 P20. 快速排序总比简单的排序方法快。
9 q% Y( `) f' T i: xA. 错误
" I, s0 a# Z6 M; p8 I- B T: w* rB. 正确; R3 `$ {. e, ?9 o+ ^* n
满分:2 分
/ f& i8 u8 h/ O( I. g a6 h0 @ B$ h: o
谋学网: www.mouxue.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。 |
|