|
谋学网: www.mouxue.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。: q0 b4 s4 G9 L# L* {
# m" w9 m+ c0 y3 F
一、单选题(共 20 道试题,共 60 分。)V 1. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
) } z6 m- V x8 A7 i$ k$ w2 uA. 直接插入
0 X# ^0 w' _' D. P, Z1 hB. 直接选择
# a, C/ H7 I% q& N" i; o" I$ h- bC. 冒泡* _- k7 W: g0 w( `1 m
D. 归并9 o3 g$ R/ a9 G& J
满分:3 分0 t8 S2 p) F& F0 ?# V& |/ A
2. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求,则可采用的查找方法是 ()。
$ d4 X2 y& l$ n% z M8 V4 eA. 顺序查找6 i1 S U' r% B" ^
B. 折半查找
$ n K/ f6 @; ^8 l$ [' zC. 分块查找
6 N9 I$ I9 e$ e6 c+ TD. 基于属性的查找
3 ?) Y7 l7 U1 o5 A8 d* z6 e 满分:3 分
) [, b6 R. ?- K9 N7 @3. 假定有k个关键字互为同义词,若采用线性探查法把这k个关键字存入散列表中,至少需要进行多少次探测?()
4 [3 N) F( j' [! {8 `A. k-1次8 p# f: ^" A7 ^! C
B. k次
" F2 ?8 g& m1 F' h) G" b8 PC. k+1次2 v1 q7 ]0 T6 I& Z \ W
D. k(k+1)/2次- ?8 u8 [6 l/ e% J
满分:3 分5 X1 H+ S/ w! ?* t. x4 D8 m, \
4. 一个有向无环图的拓扑排序序列 () 是唯一的。
+ T0 z/ Q& G! m5 DA. 一定8 g5 n3 t) m5 x# {/ @7 u1 `3 `$ e
B. 不一定
: a5 x, Z' `+ r( ]" f% oC. 可能$ ~" l: {. q3 @4 J
D. 三者均不对
, |. ^1 t2 b: | u8 w 满分:3 分# {# W. `9 M) I$ q) j
5. 设广义表L = ( ( a , b , c ) ),则L的长度和深度分别为 ()。) ?: z ?6 Q4 D! H3 C4 K
A. 1和1; }$ L: u/ ?: h- p2 y$ b8 ~
B. 1和3& q9 |; k2 K) Q' b0 x
C. 1和2
) ~, _0 t, G/ Z% [/ U) cD. 2和3; ~% z! X( }, A4 Q& y6 |3 s
满分:3 分) @$ l& ^/ t* E% ~0 U4 I/ }- k
6. 有n个顶点的无向图的边数最少为 ()。! _7 |$ a6 i# S- T7 W3 L
A. 0
4 Z/ [& i. \. K# A, ZB. 1% d* T, G9 Q9 U
C. n-1
d% x+ F; Z+ M. M6 D! gD. n
# v3 U# e& P4 k( f; w9 N% m! P4 Y 满分:3 分3 k; j; j H' E+ n( S
7. 采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。; u( M+ i9 [9 y5 @' g3 s
A. 前序遍历3 \! I# F3 v- {- s3 U7 k6 D" _
B. 中序遍历
/ T& Y' \" q9 W% b+ g7 K' u" B! jC. 后序遍历
7 {+ o8 G( K- I. T8 B$ x. uD. 层次遍历
0 A; a$ g% v" d7 D+ W 满分:3 分/ O- T$ |5 }( Y3 ^4 y; d
8. 顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
& Z% q2 Z# @0 ?% C6 f2 a6 G; @A. 散列存储
0 @1 v R! }% w4 g9 QB. 顺序存储或链接存储+ O& o5 z/ z. ]1 s7 B& N
C. 压缩存储
% ]4 O% h( H' C- y; ~D. 索引存储
$ r; N. }9 z- k9 _8 f 满分:3 分# M& x3 }8 E/ R. w6 M
9. 下面哪些方法可以判断出一个有向图是否有环(回路)? ()1 t5 u& S4 ~- q
A. 广(宽)度优先遍历
0 P' X; j- `' F+ \+ M; iB. 拓扑排序4 p# z/ }2 a2 ]+ J/ U
C. 求最短路径9 }: d, q2 S' E% F$ h' Y, t
D. 求关键路径# N7 [1 G _4 c
满分:3 分$ l4 v( V) y8 b$ k3 ]
10. 广义表 (( a , b , c , d ) ) 的表尾是 ()。: ]# M8 Q* U5 B, U
A. a+ J( o) n' B' F6 r% t: V# x
B. ( )8 I2 B2 T, }0 d# R6 n
C. ( a , b , c , d )5 i4 N1 ^1 O; d9 W- |. u& V
D. ( b , c , d )3 i4 ]) Y2 [* E) r& C
满分:3 分( _; E. \& L, w
11. 广义表 (( a , b , c , d ) ) 的表头是 ()。
& E$ g+ l; U1 j" F( ~/ N8 uA. a& }, B8 H7 u7 Y( R- `- I) D7 [
B. ( )
& ]7 D h+ ?0 m6 y6 P) g. V5 a# `C. ( a , b , c , d )
6 A6 @" C( K7 |D. ( b , c , d )3 S' k' e7 s- D
满分:3 分
% }, Y# g- v+ \12. 数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
% @: c! e8 m2 A) pA. 直接选择排序7 D* g2 u. G5 @ e
B. 冒泡排序$ G1 M y6 s$ H f4 i
C. 直接插入排序
9 J& n+ |+ J& n) kD. 堆排序
3 k7 O# E# x; j- r5 P 满分:3 分
9 x" I8 l7 {; o& V. a/ T13. 折半查找要求结点 ()。0 O# i) n0 q6 T. Z) I" L- v3 V8 }
A. 无序、顺序存储
: ^) l% [ Z. @; k9 P! X# h! LB. 无序、链接存储& h |; [5 P* @" @0 B- [
C. 有序、顺序存储( U. O+ ]3 S( S, C* {2 |) u, I4 u
D. 有序、链接存储4 V) ]0 T9 a3 [/ m9 j
满分:3 分
( y' u% f0 t) ^8 S+ L14. 在下面的排序方法中,其比较次数与待排序记录的初始排列状态无关的是 ()。
8 [4 r/ h/ N/ U; i0 VA. 直接插入排序
0 I% \; {5 v' yB. 快速排序
) }: C! G+ f# s5 F( oC. 直接选择排序1 Y* q3 ~ C3 @+ c# J& v* {
D. 归并排序
( L4 [7 E$ X% `0 W% n* f 满分:3 分
/ G2 \! c6 Q) z j' v15. 就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是 () 。8 t M& [$ z2 g
A. 堆排序<快速排序<归并排序" J. n l9 t( I6 ^* `0 T
B. 堆排序<归并排序<快速排序
( n/ | L! r4 B% tC. 堆排序>归并排序>快速排序
; V- N% z8 Z, x/ AD. 堆排序>快速排序>归并排序% U; u) W( n; g5 u5 w/ g! }
满分:3 分
l6 m8 M; _' L16. 有n个顶点的无向连通图的边数最少为 ()。
6 `# h1 N9 u+ w. x7 |- lA. n/2
f: S' s$ r$ ]7 ~) ]B. n-1" B2 n9 Z2 D% P! [" v! r& J0 S
C. n
& t9 ^& z% }- O) ^' X6 g1 y& c* }D. n+1
1 @; k8 }) E: m* D- ]: T 满分:3 分
5 x2 H, {0 l! `0 b0 n, ]+ Z17. 存放在外存中的数据的组织结构是 ()。! ^5 U1 L7 D# e# C
A. 数组
; O5 P; u8 X5 e7 AB. 表 O h& ^, R+ Y' ~8 R. L6 J6 q
C. 文件; _2 b8 O4 K6 U+ x
D. 链表
, |6 ~( Z* m2 z. p+ _9 V1 [; N 满分:3 分6 W. p; g {- y
18. 设有n个结点的二叉排序树,对于成功的查找,最多的比较次数为()。 l: B [0 {* c X9 c# q1 X" B
A. Ο( 1 )
4 c+ m2 X# D8 t$ ~. C0 LB. Ο(log2n)( |8 d) u" I& ?: I$ l
C. Ο(n)! G3 S" B1 {; h* `" ?
D. Ο(nlog2n)
& i; {( n; k) a( \; R( M' u5 v/ k7 | 满分:3 分
% C4 ~( h: {& B4 N" F( G9 R19. 在有向图G的拓扑序列中,若顶点Vi在Vj之前,则下列情形不可能出现的是 () 。+ A3 ` `* U: w0 J4 T) A8 Q
A. G中有弧<Vi , Vj >
. l9 k) ^# j: R2 ZB. G中有一条从Vi到Vj 的路径3 M3 z1 I) Q. X. x; ^
C. G中没有弧<Vi , Vj >9 D3 ]7 e* W: o; D
D. G中有一条从Vj到Vi 的路径. M. g: |# g) O, u
满分:3 分
v2 B8 m5 Z* X! V20. 在排序方法中,从未排序序列中挑选记录,并将其依次放入已排序序列(初始时为空)的一端的方法,称为 ()。& ^0 |" [% C$ z- d9 K
A. 希尔排序
8 ~0 w; M* h) C' w) Y0 WB. 插入排序* D# D- |4 [/ R- Z6 ^+ D
C. 归并排序 U! w8 W/ I/ w# j, E0 [1 K/ |
D. 选择排序
% |0 d1 r: e; ~$ U6 g 满分:3 分 : Z$ A: W8 D5 Q' V: o8 ?8 J
& A- P2 T H4 \1 e ^% i二、判断题(共 20 道试题,共 40 分。)V 1. 最佳二叉排序树是静态的,而平衡二叉排序树(AVL树)是动态的。
8 F N- ~4 D6 l ]( Z" fA. 错误
# R" `$ s$ p4 H1 TB. 正确" c3 ~! P' _! m8 k5 h2 G
满分:2 分
6 T, M* l% {9 Q% v2 B2. 快速排序的速度在所有排序方法中最快,而且所需附加空间也最少。
, b& H$ \9 Y" B% KA. 错误
! W4 V, o& p' c( xB. 正确
3 V6 D% B: l1 @/ B 满分:2 分) F$ W/ ]( `2 @5 Q* u
3. 最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。& {+ q! T i( v, }* n
A. 错误
7 C" w( J% z$ N( A' k8 OB. 正确/ R# w% U6 d* g: I( n2 ~
满分:2 分+ C% T- F& {' n; C! H
4. 对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
M/ ^# S! J# H8 L vA. 错误' h/ p4 L! v/ ~
B. 正确! H5 @: [1 |5 y, Y
满分:2 分
, P" u: F% V8 i5. 邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。) J$ ~ g1 U* y# R/ R; i
A. 错误8 g1 O- \4 ?+ |9 I
B. 正确
* |( }$ d- _9 G# V 满分:2 分4 {1 K S, T6 ?4 [6 V
6. 在图G的最小生成树T中,可能会有某条边的权值超过未选边的权值。5 n. [8 K. y- Y4 L5 J
A. 错误) ], O& _, L# {6 L+ f8 h: a/ ?+ w
B. 正确
7 R4 o4 M5 M1 u( G3 U( W 满分:2 分3 @. g. M ~9 t% z' M
7. 哈希函数越复杂越好,因为这样随机性好,冲突概率小。
3 w* ~5 c' k6 }# J$ ]! r$ X7 XA. 错误5 J6 P7 }* n4 |$ b$ x1 O
B. 正确
( F) @! P# q% L+ f/ l- q9 q 满分:2 分) ~' t! Y, Q: o# Q. U8 {( A1 B/ f- u
8. 数组不适合作为任何二叉树的存储结构。
- I, o& _/ w0 p5 w3 _A. 错误6 Z. Y# v& d, V* b4 `
B. 正确3 Q& G O6 s: i i/ e
满分:2 分9 J) y! B6 X4 N, \* ^5 i
9. AOV网的含义是以顶点表示活动的网。
: U0 J# d5 H! JA. 错误 g8 \ b/ a/ R
B. 正确% |' L5 r0 y' B& A6 v8 h y
满分:2 分
8 J4 I+ b0 T6 j10. 哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
; j+ m% V* ~* O" ?A. 错误
: x8 H1 T% T+ m% d! g4 sB. 正确; C' w9 S' t j: M9 t
满分:2 分
1 _1 W& }/ P E11. 连通分量是无向图中的极大连通子图。
+ n) H$ r9 j, u# P/ I2 bA. 错误
. P) A D, X. t b& bB. 正确0 w u0 i" @% X
满分:2 分
2 u+ b* G# R$ K) {2 ~2 W; Z" i8 c2 F12. 归并排序在任何情况下都比所有简单的排序方法速度快。# Q4 d# d6 u9 }# t; D
A. 错误
! u6 Q; j$ [! [$ `, T& M$ Z2 QB. 正确
( H$ m2 J, K6 f8 _; e9 w/ p 满分:2 分
5 f5 r* W* r- e# t13. 倒排文件的优点是维护简单。/ B5 H; r+ \" g$ r
A. 错误
; P; |" l8 G$ \" F8 R0 ]) I# lB. 正确4 D6 J; w( _; a* V" P. w
满分:2 分
7 E1 o( z V& _7 A& |, b+ B) [6 b14. 在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”。
t. n/ W- @- Q/ x: A' c. }. LA. 错误+ a9 x' b4 J Z( X) u' v
B. 正确. \9 L r3 U0 n) d* T
满分:2 分
, ]6 h- v9 Q- V( ?2 E# B15. 对有序的单链表不能进行折半查找。
: [- B6 Y7 |1 FA. 错误
4 h1 M$ h9 a% ~0 d. c. EB. 正确) |5 p, D' X- ~' Z2 I& L1 J4 r s( t) C
满分:2 分
5 \' v# n' }% k8 }' u5 D16. 归并排序的辅助存储空间代价为O(1 )。- W( `0 V: x' o- c' N$ G; X4 G
A. 错误
3 t7 z: {2 q; n5 W/ G$ h0 b8 EB. 正确4 T; n" ?) j% [
满分:2 分
+ w5 q- l, R; ]0 E$ Y17. 用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。/ }# ^: n9 H6 ^
A. 错误: ?8 w3 ~0 {3 W' i
B. 正确
5 u; h( _: K7 k 满分:2 分$ p' x& S1 V: Y" l
18. 广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。
7 B: |$ k U& f6 dA. 错误
5 J6 W, Q) |, I3 c8 H/ dB. 正确! Z# Y7 r& G9 F" B( D! O: S
满分:2 分( C& _' Q2 \& A: [
19. 有向图的邻接矩阵是对称的。: R- o8 `( X2 e% g: ^( ~' }
A. 错误" t# q2 T! U* U; `. ?' d
B. 正确
: o% a! J! I8 @ b 满分:2 分
8 ?, {) ?6 W& [ y7 @ R20. 快速排序总比简单的排序方法快。
" Y! e+ T; d2 j* f( K" r5 M+ ~A. 错误
$ o% _' R d+ b" x8 }- d7 aB. 正确
; x. M4 [( a$ e/ ^. ~0 |* Y* l 满分:2 分
. ^; r' d. `7 |3 N- a2 K0 t) b: h1 @2 ?. H# o& F T
谋学网: www.mouxue.com 主要提供奥鹏作业资料,奥鹏在线作业资料,奥鹏离线作业资料以及奥鹏毕业论文,致力打造中国最专业远程教育辅导社区。 |
|