|
|
一、单选题（共 15 道试题，共 75 分。）V 1. , r8 i3 w6 I( {* ^; C w+ D
一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。这学校共有的学生人数是+ e3 q% m* u6 }# h( R- W7 n$ I( ?+ n& g- ~
0 H( T- q/ \# g' K4 P5 V
A. 300
) N7 i( c4 I6 d9 q9 m BB. 3368 c" _, a) G+ d& K# ]$ M, c
C. 420
# N& ?0 Q- [/ J6 z( }* ^ RD. 4307 h3 r M3 \, I9 \
满分：5 分; ?8 ]. {/ g* c8 @9 k
2. 8 Z, I( ~5 U5 [/ l# E7 R
用计算机对问题求解，问题的本质是' b4 \/ n! k8 N' a( q$ F+ W
& M! z: j( Z' y% ~
# ]: l! G0 S; o
! Z: ^/ l, e: V$ ?A. 数据类型
0 ?) N" n6 a7 K* P1 H1 F" ~B. 数据结构 & U9 h4 a+ \! ?3 ~+ A
C. 算法编写 4 x" k" x$ ]. l0 D
D. 程序设计
o- @ `! {6 C* h# s. i' U/ @+ ? 满分：5 分
# b: ?" F0 x4 s9 G- i/ n2 g% l3.
/ ^# `8 Z0 `9 Y8 F' o无向图中一个顶点的度是指图中
) {: f; }# R- x/ j5 _8 e" u' e( X) F& s& X: W p& E4 k! N6 h
. \2 o. k& }- x2 {
/ F" u0 L+ X# t4 [( I. w8 v
A. 通过该顶点的简单路径数 # k9 ?: t) K6 ?% P" s
B. 与该顶点相邻接的顶点数
6 _8 p: ^$ T. n) f" J3 iC. 6 v6 |& b' c8 _. k
通过该顶点的回路数
* l7 \* W2 O3 [3 j
: X6 b7 G5 J! f* d7 {: T! a5 ED. 与该顶点连通的顶点数- N5 k6 a+ x7 n, O6 v
满分：5 分
4 E; w/ I0 A# f4.
" n7 }& h, o6 R* U& j! n含n个关键字的二叉排序树的平均查找长度主要取决于1 }; h$ z: S: |0 w7 I
) K; O: q3 p% @8 x C9 i* Z# W
$ S/ D2 S( _+ i I+ N! R* U
# l, y& E; o. e
A. 关键字的个数 ; [6 r1 K4 W2 `1 F3 V1 a
B. 树的形态
0 J' Q; |+ M8 ~0 p: S+ U
- F V1 {6 z2 l
1 M' R! r3 y7 l- q2 kC. 7 r3 c' G% P$ ~+ c
关键字的取值范围
- z( d' }+ ]9 i" d7 k" b+ x
5 Y/ @3 `: E& }% DD. ' g2 R& N; g) l2 ]
关键字的数据类型* v' _; g8 e9 l+ L: V. `" l
3 O9 M$ t4 U; ]+ z1 ^+ h& @+ W6 `- r
满分：5 分: a* p, I0 k. M3 |2 {) c
5.
7 e8 a% s P" [3 {( z# T" r用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
, o, r4 m8 u$ k+ \7 j- j1 ]. v. I( C6 n
A.
6 v$ ~0 L9 z8 A2 X4 X: `! V 逆拓扑有序
! Z8 U% p( _( s5 v. ~9 }
/ D' d+ @- x4 |: gB. ' f* ]8 C2 _5 _) J/ h$ l& M
拓扑有序
3 n% B8 D+ M" x' Y" ~* f P9 {! x# _ K. Z8 S3 Y. j8 K1 }
C.
# N* E) m& A+ F# Z8 c( s, j. B 无序的
/ r! J! W5 }% Y+ S- @/ e, S3 p" A2 e0 G; V) y5 n
D. & c; ^- w7 X2 ~! }
A和B
4 W( \) b0 Z- d: z8 s) Z# ?* O' t- f# H( ]0 t+ b- d: l
满分：5 分
: p( Z6 z" o0 v$ l9 ?! Z6. O! X% y1 J; ^) f- o5 `% D
若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
5 ]6 n6 a& W! S
" T. N1 k; ]9 p- S! @8 a) rA. , `/ E2 a) O P# D7 i
一定存在
4 V; `6 b' ^# v" |/ R
$ W# x& `+ Y1 R' C/ X" N2 }. `' \& ?B. h" G" F6 X; h* R& q9 Q
一定不存在' x* n" e! a: ~+ H& Y% Y% w
3 B# i7 P5 f; R9 R& cC.
4 t# R% v" {4 I9 l不一定存在 8 e! i% P" F. R# P
& [2 ^) `: S' v4 a; Z" r
D. - D* O% g& q4 Y' q+ ~5 D) f
不确定- o. C# |. C4 F* l5 w) S+ S
6 E$ z1 c( v8 `
满分：5 分: k% l: G: z+ n8 ?( |1 o/ n7 U4 t
7.
& }% p( L- _; n3 l1 P为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
+ N- d! n6 M& }' u
) c- z9 Y! ?% c& a! i + L8 H( C6 ]# B% A# q
9 c! \+ C+ [0 N5 S3 f3 ?7 mA. 05 ( ]2 \; v5 H0 {
B. 37
/ ]1 p, z: `. Z% F6 k 6 F) S* |# C6 K9 k
. q: K# M/ P1 |3 z' VC.
3 S E" s# N7 U- M+ F& P& O) [% E41
# `6 l8 x" a7 y' `, H! n9 ^4 b! j* R$ u+ v7 }; y
D. 62
3 Y% S0 h* Z- c% W 满分：5 分
$ f4 p" B& V0 g: N, i& m9 l( o8. 7 q) R' j. c4 M/ b) M4 h
设T(n)和f(n)是定义在正整数集合上的两个函数，若存在自然数n0和正常数c，使得对所有的 n≥ n0 ， ; D7 e% e' X, A1 g) s: t( i/ a
: t& {& _; S7 y$ U. `& `+ L: d
都有T(n)≤cf(n) ，就称函数T(n)的阶至多是
. V: A0 E$ u/ q6 v) A1 u1 D8 C! K( A
A. % f" b; b o) g
O(n)
2 ]2 ]2 v6 v1 X: I3 ~- l
+ K, J# e5 ?: o4 s# G. z lB.
% q5 H. q7 w K" @ y1 T/ p0 M. O(cn)
+ H5 \5 L. `! E3 ?1 {, ?, I0 O% E# M& }( I* r* ?
C. $ ~- b& d+ [4 H! O. _* B
f(O(n)) ' p, M6 h1 E6 f
6 c2 M4 Y4 m/ N; r; D3 {
D.
, [) n6 ?3 d; U$ ? O(f(n)) % l# X5 d7 v0 d; p+ V* _: Y: n
! r# Z- `4 I8 L" A' y0 v' ]& o
满分：5 分
+ S; R1 e6 H% c5 k1 `9. 7 }7 L8 z$ n) d, U8 z ?( j( t
在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为- z1 q$ k( v% _: y# u5 f
" T9 y- O o( y( G/ CA. $ _) L: c6 N; v- e. o. H
O(n) 6 [' e2 P, K6 d, }
5 f% o8 S! C0 M% ^( o
B.
5 x: ~! q- i- ?3 c: A$ _ O(n+e)
+ Z4 c, {4 w$ ^9 g5 Z y9 }
7 A0 S$ r6 E4 B0 k8 V" xC. + f5 F# y7 [+ w Q$ o- P8 [
O(n2) . g, p4 K6 I+ m* g' t* K$ y
, a& W2 ]: x/ b. } v& B
D. , F- U: F7 M w7 x1 G! ]! u* C
O(n3)
4 H, T; S" y# @% k# a% M4 p. g+ k( G* Q0 e: y9 h
满分：5 分) h2 n8 [$ @& b( d
10. * ~8 n; D; Y$ \0 P, V, G5 s* n
在进行递归算法的设计时，通常先写出问题的递归定义，递归定义由两部分组成：基本项和& k9 _% g- ~, j1 x9 z
& G. p. X- G, K/ Z" W+ `+ g
A.
- _ b- |5 Y1 s' J- s扩展项 3 |3 P: O2 ^0 d9 T n" b( P" s
/ n* u: t* A* h6 C1 f; }B. ( o( U" {; m, S2 j8 s+ ]8 V- m. ?6 r+ Q
常数项 * s& z9 U" ^# H' \
5 i: `# \: t7 c: M) Z; n! _: `C. 6 ?) w- F; M" F4 t" T
归纳项 ( L* B5 S4 _2 @# c
5 l/ n4 B& W3 ^/ o9 u) ~D. ' @, q& n2 V( n, F
递推项$ B; t: s% P8 v. Z5 A- _9 I
+ c' D4 J; ?: @ 满分：5 分
6 ?) v8 d9 y9 \/ L: {3 W; S) ?11. ( q+ y$ t' Y, X( R0 h$ U6 q5 r: Q
在待排关键字序列基本有序的前提下，效率最高的排序方法是
3 M! R! F0 B' e+ ^ g. A) @1 F* h) s4 z$ B3 R# a
A. , s% s; i6 `. y( e' O2 J
直接插入排序
# d3 e! e0 k8 q9 V4 {3 _5 I% J
9 l4 U# Y a( l9 V& X bB. 0 ]" z5 ~% F; J
快速排序
9 `; E/ L0 P8 l% H4 J4 }* N, p- T2 E4 B
C. ! k% v7 i8 `4 t- q) W3 o7 ~8 f2 ~
直接选择排序 . \1 \+ v/ k/ R
, X5 ~3 Y/ n( P+ U% d
D.
/ p9 \- ~& U! e) i, p. X归并排序6 r( O$ `/ x. m
: F+ F$ u* \% c( F# [6 l4 r: p2 |; `7 |5 o 满分：5 分
: n) ` }" D1 h7 w12. n1 K5 E! l, [2 k3 ~ b3 |
利用迭代算法策略求解问题，在确定迭代模型之后的工作是
/ I5 [4 Q0 G/ F3 Z9 Q2 b
7 e& M" O- J J5 F 5 @# b% ^; ^: x5 F6 p: [
" Z8 M. P0 P) ~4 qA. 控制迭代过程
* U9 Q# X2 L. }( i, R/ bB. 建立迭代关系式 ( @6 G# v- A6 f6 f2 N- p0 t" N! l( J
C. 建立关系模型
( I2 q* q6 J9 Q7 }3 aD. 分析迭代关系
8 I9 a) E, Y7 h0 A3 ~ 满分：5 分
/ k7 `( C$ G% y/ K13.
) K- z8 u( W, i9 l$ I3 }下面的叙述不正确的是
7 g) m5 i& Z5 a& p* |1 x
: ~. o2 r D; D1 i6 iA.
# f% `$ @1 E& N+ i+ p7 [; l线性表在链式存储时，查找第i个元素的时间同i的值成正比8 s! f, a8 Z0 _- ]& x, z
' t+ E, s$ v" [0 L% u9 B& y8 s
9 A0 J6 h# } S" P# B6 g: C6 z) `& `' O4 u9 N. g9 x. ~6 I2 S9 w) m! v
B.
& Y" d2 @, n9 f n5 \. E 线性表在链式存储时，查找第i个元素的时间同i的值无关
+ x7 ~2 L, A3 r# L3 w2 t( {9 r# r5 e) ^
" y- b' W/ K9 r6 f5 B/ fC. 1 V0 ^0 D6 l9 g. Z" C1 m j1 k4 ~
线性表在顺序存储时，查找第i个元素的时间同i 的值成反比2 D! \- N0 k8 o9 ]
. y/ @# d8 V" {: M5 zD. - s2 n/ S0 x) w: g9 X7 q
2 w+ Z4 Q7 w- W6 R* v
2 s; I" a, m6 a& S K/ V' T$ w/ A线性表在顺序存储时，查找第i个元素的时间同i的值无关: n& z' N/ f( c+ Q) z- t9 c. k
0 _1 G4 s" ?# \) B2 N 满分：5 分1 D$ J7 G% t/ _, ?
14. 1 K f0 X6 ]$ J8 T- g, M/ ^
分治法算法的关键步骤是
$ B9 ^2 D, [8 d# R# p3 { `
0 f6 x- ]' [( L. OA.
3 E, T+ P( ~6 `8 Z 划分
: J9 y# V, T- v) J# l8 z
6 J6 o+ M4 v9 a# Q# RB. 6 T) K# v* ]7 f8 h4 C( j
分解 2 z8 e: O+ S9 D! U
% o7 \3 B+ c7 S! C4 S+ Y' ` 2 ], r2 E0 @3 E. p6 s% L* M$ G, M
" Z1 S4 v1 }( m$ V& c% g
C.
. W/ E, N( ~; S$ K 合并
" w; ~% F) P# d0 U) q* T3 t. R) L+ T
# x5 g- K# ~( D( ^* o0 S: O: iD.
5 E5 w1 R" \" B5 ^5 e: _2 V划分与求解# l/ W* i4 Z$ c& s T1 J
2 o, M, Q" e4 X
满分：5 分
! g& E. R) D! y. T% `8 v15.
: q) A1 A8 U/ L- I用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。若该吉普车以最少的耗油量穿越沙漠，则建油库的第1站是在距起点的
l: I! c% E: r- T6 C3 q0 r/ T5 X) ?; ^- y7 d- [, [, _. g' Y" ?
A.
3 P3 s. A! z. P6 p7 f; s1/5处 0 a/ m) p% o/ w7 x, Z4 V9 ]7 _
1 f7 [* M) ~' c( z) A3 k( fB. $ k. \" R2 g' p2 u, J% d
1/4处 3 t3 x' C3 Q) r
& e6 x) z% `" m8 R% g TC. 8 P. D3 b( d+ o& S
1/3处 " @! ^- i2 q/ a# b) V5 k
; m7 K. i# S( V- r' k! }; Z% C9 @D. . \2 v$ a, P- H7 Q/ k
1/2处7 l& u. i& x: p) E2 Q2 A2 } H
) U; L5 V# Y( ]/ I: G8 ?% Y
满分：5 分
" i; V# R! ~- V6 P( |7 {! i q! i/ p3 ~- \. A
二、判断题（共 5 道试题，共 25 分。）V 1.
9 S6 l; O7 M% X$ U/ C& t, ]9 R递归算法是一种自身调用的算法，递归调用的层次，也称为递归厚度。
9 u4 {5 p$ k1 b$ @- v! z- W+ ~1 Z$ C7 h5 _3 u# {6 @
A. 错误
* M3 g0 k9 e7 d+ r% h) FB. 正确
0 W2 b+ u/ J5 s 满分：5 分
6 U9 N3 o$ W3 U2 }0 z: Y2.
1 N* m$ w! M3 Z' D9 x, Q$ g% h5 I动态规划算法通常以自上向下的方式解各子问题，而贪心算法则通常是自项向下。
/ n+ i3 I" u7 H6 ]* [' B; W: C) ~9 Y8 b% D
A. 错误
2 |5 R: ^" z$ x% p2 }B. 正确
) `) Z+ ?1 }- z3 }4 y9 } 满分：5 分0 i. T) @9 r: n
3. 通常深度优先搜索法全部保留结点，扩展完的结点从数据存储结构栈中弹出删去。
2 d3 i7 P7 F5 g" J7 b- B! X7 h3 Y1 HA. 错误, `; F2 w: C$ @3 u/ k/ o7 @$ E0 [
B. 正确1 t& i# f* t4 y% E9 u1 X f1 A/ O
满分：5 分! D% w; o5 H- c1 [3 \$ B
4. 文件上的两类主要操作为检索和维护。
8 L- V$ v+ u' J1 n* nA. 错误8 p" R% z3 [5 M- H1 B8 j! I: o7 a' M
B. 正确 q7 u8 \. Y: |; ^( Z1 R0 ~
满分：5 分
5 l) I' B% g% u5. $ y+ A3 `' C8 ]2 W5 |' Y
递归算法中的递归出口，描述了一个或几个递归过程的初始终止状态。
' }- q, j7 l% G8 {9 \/ r2 I* l4 O5 [3 m" ]9 o
A. 错误" v1 X5 }- \6 W, n* |3 \
B. 正确( W$ H y' N# i
满分：5 分 & N9 N, |5 d* a1 I8 i0 D5 U
; v0 I/ ~; T9 U5 _' z/ @) T d |
|
IP卡
狗仔卡
发表于 2012-12-19 13:47:16
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
