|
|
一、单选题（共 15 道试题，共 75 分。）V 1.
: _+ A$ r6 g/ Y* |. s一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。这学校共有的学生人数是
9 f, F5 W9 j' | U t- U
2 [* `# D$ k1 s& r9 nA. 300/ I# {2 i5 A8 r6 t; q8 d% y+ `
B. 336
! ]1 V0 g; p' Z) N! [" @ d$ zC. 420) y5 ?, B: z, _4 D7 S9 T( `9 @" b3 M
D. 430' X* G' F: C# A4 K4 O* M% O" \
满分：5 分& z$ q' I9 q/ S( M
2. - _" i9 m$ o5 f8 q0 M
用计算机对问题求解，问题的本质是
: L$ ?- N4 U+ d! o& h) k U2 {. f ?$ J% S2 k5 e
: ~* f) A; ^- L- ?- H
# s% {" V3 K! g
A. 数据类型
" R ]9 }; r( QB. 数据结构
+ J* U, j9 ~5 Y! ?& v7 fC. 算法编写 h, m7 A1 N3 A! o1 t
D. 程序设计( ^; j& Z8 a, Z- m1 V) u
满分：5 分( W0 J! v& ]& g7 f4 v5 z
3. ; m& m; |$ _6 S) @1 [
无向图中一个顶点的度是指图中
, H' v* }! W: |1 T$ q) U
' F: H6 D. G0 m1 v( W
% e J. U0 z6 F' x+ j w
/ x6 ]* T' r1 F# L; o) ]A. 通过该顶点的简单路径数
' i+ n2 |0 A* F" j( yB. 与该顶点相邻接的顶点数
& q& q1 r/ s6 zC.
; Z" e5 `+ o4 I# f( i; U 通过该顶点的回路数
8 n% o+ [, i5 e0 x1 G2 W( s8 n& G0 K7 U2 F0 B- y
D. 与该顶点连通的顶点数
. f! c/ W, M: p4 V& B 满分：5 分
! ]! L5 `: E \# g$ S* h- }7 |4.
, ~& B- N; q, F+ ~含n个关键字的二叉排序树的平均查找长度主要取决于, ^8 l0 X, N. }) [3 o( f
3 Y$ U6 e7 y' ^, q L 2 R$ K6 t, P' }0 h# `
1 b4 N& G6 j/ y/ ^7 QA. 关键字的个数 # j; r! A7 K3 ?
B. 树的形态
! l. m0 i5 V5 A9 }: R
) {+ k3 `6 g2 {9 J, R5 ~* d# `( x: d$ j% S" a. f. v: k+ a
C.
# _4 i K! A t- n! x G关键字的取值范围
) ~. x, V( x6 _) W' _
3 M5 p% W* I+ D5 i- LD. / W3 Z7 l: d2 I8 j m% J8 q
关键字的数据类型: X) I5 f5 y5 z0 {% @
' Y. _9 H9 m- @/ ^2 i, p6 L1 j9 D
满分：5 分% I/ \" y9 r& Y! D
5. ( p# n3 s$ S/ W/ v6 K2 z
用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 {/ }1 u8 B) X- L; e% c
s& P2 y3 n. n" a# ?) t+ V
A. ! }& M; [% x. k8 p+ R3 C
逆拓扑有序 + s9 s9 i0 I3 h9 V- d8 x- \
) C2 _. l: m% WB.
8 }5 s6 h% |7 b& b7 Q8 s 拓扑有序 ! _: U( R \5 l
; W& C T+ m% d& C, A. v5 e( jC. 7 q+ Z# D' P+ \. _0 a( c0 l
无序的
# N0 ]( i" [! m( I" v0 \0 y
6 {$ J9 \. T% Z. _7 H* k5 qD. . [+ ~* @! ]/ y/ y- h; J. R
A和B
6 B9 z0 S" y$ [; E6 p$ n( W9 r4 e
$ j* P: P- ~! x" ~/ f) ]: V 满分：5 分
! X- a! d9 d* ~# Z B0 a# l6.
' T0 L! A: {5 m [若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
3 i) ` E7 {( J7 {1 C- Z4 {
0 l8 B) G. t! h' D* } {A.
3 s. \3 f+ M6 c& L9 Z( ~7 _ 一定存在 - \; l6 _/ O8 m) T2 t- Q
1 C$ H8 v3 Z7 w f& l# J. Z
B.
7 k3 C5 G. n0 _; G* `- R2 {* o 一定不存在
- F$ L5 O) h9 Q; A! O4 ]* ^' M& \ L/ g" l
C.
+ d1 ]. r1 p, n# W( k5 `不一定存在
3 K! I9 F' C1 \; f. k2 F8 D
8 _4 t/ [) s" {% o5 @. oD. k6 a3 f5 g, l; [0 ^
不确定9 C& ^/ m9 Z, I; C. O: R( X# Z. Y
/ m0 s: b7 K6 {. t
满分：5 分3 I, H4 {. f. [5 d; x7 `
7. & d* T+ z$ R$ p' w; M6 V0 W# {
为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为5 F" @/ S- j' m! {/ D
9 @2 w; F# g4 l7 T7 D4 h5 E" _
' p$ O" m" u R$ x
& s7 X; V* c; @A. 05 ! N0 T- o/ L! |6 f! u7 g# ?# p4 I. i
B. 37
6 M0 j" l3 a# }
3 f0 Y* q! J8 C, G* n* M6 y$ o2 g. k0 L; @0 v' w6 e
C.
9 x/ v$ P1 {: a4 S% q% X8 V41 ' w5 A+ X5 X8 I4 |/ C
- m' N# D: e( v/ i
D. 62; E3 G$ ~. w6 p$ a8 _8 L" s# S
满分：5 分5 ~1 a2 r. P0 j% T O& ]4 \
8. ( L/ N5 o9 [' E0 g' r
设T(n)和f(n)是定义在正整数集合上的两个函数，若存在自然数n0和正常数c，使得对所有的 n≥ n0 ， 2 p4 T/ \" ?* p* D+ N
( R* D# W1 y1 ?5 F
都有T(n)≤cf(n) ，就称函数T(n)的阶至多是; p% t: K+ I1 w8 L. U4 X) W0 U
0 R. g: r: { h! O. ^, u' cA.
- P9 _" b8 f+ z6 p O(n) : `9 ^+ }4 f$ Z% J) I/ `( O
4 p: N# x# J; x; A
B. : N9 `/ u8 U/ Z6 X G& O) Q1 l
. O(cn)
/ s% L: H4 q- g7 \
3 b" u! Y c* }% HC.
3 d3 @" g8 `4 v+ A f(O(n)) : o+ D6 B8 Y _" A" z! E
+ Y. f8 A$ [" c+ I) {8 U, d# K
D. 6 z* o. k, k+ s1 {2 u) u
O(f(n)) & a. V5 s* V0 [0 U8 e& @
* ~* d' W% ?$ T; {. X, f
满分：5 分
, G. y5 l) j( l/ E M9.
+ g9 t, G) a* ]2 f" Y/ y在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
. m# O, K; a/ B6 H$ V2 L0 ^0 Z! z' P9 g3 n3 y# R8 X
A. . u$ i2 Y8 a- ?" m. ^# s3 ~" c! m
O(n) " x* H/ O: N! e9 b ?1 v+ r& c
' I( \. z) E3 s4 g8 t1 ]" X4 j
B.
- J; y6 _7 Y$ Q- z% H0 F$ M/ L O(n+e)
& g" r" e0 F7 H. G2 O
6 K6 d& N! [" r7 G7 bC. 0 \4 P' ~# G0 d) T. X
O(n2)
6 {" J. G" h1 G$ p8 ]* A( a5 O* p6 k7 v! b# Y7 p
D. 2 E/ C j4 i- X2 h$ T: y
O(n3)
; V9 J; x# G& y& N, y, ~ N5 f+ I
( x2 |. N% b% h, A. W! i" | 满分：5 分- G5 M! R/ n" e6 ~! S; J4 d
10.
O+ i4 u5 }; e1 W5 l5 V在进行递归算法的设计时，通常先写出问题的递归定义，递归定义由两部分组成：基本项和7 @5 s2 o: Q; s( w
9 ^* K9 w& h* U: ?
A.
* D" d0 u! i' c; _& _$ m: j L扩展项
2 W1 D+ s# @3 _1 @% K$ L
$ O3 n! u W$ p+ uB. ! z0 l% B( ?1 y7 P
常数项
. w6 J) V- O, u* j" v7 K' @. W4 f& C4 b: ]0 R9 b
C.
: y+ c+ P! O: q3 L8 b归纳项 ) P& \8 H: j# n' J$ k
' k' Q+ x4 l4 Y( Q; {$ AD. & H7 n! N& D. e6 J" N# x
递推项
2 N: j+ d [; y. h3 t6 ?0 l* ^
5 U* `* H' |. l 满分：5 分
# _- h& l6 j2 E11.
# ~4 K: {; Z T& \$ `在待排关键字序列基本有序的前提下，效率最高的排序方法是
- Y/ {1 m& H& b' y7 u7 o
% q8 O7 a% [* l1 ~0 _A. - o5 F$ D5 @8 f" J1 j7 S: r
直接插入排序 / v7 }0 q- H2 j: x* U' A0 b2 K
1 o; d3 v5 f5 Q% oB.
@% a. K7 \! ]( D+ |! [1 a快速排序6 f7 v* I; `/ D
! G+ J" T3 l. L% g7 o: C' X
C.
- t9 M4 [: S* s- t# n( s) N, c* { 直接选择排序
8 z" p8 @' n6 d* v2 ?- C% S h3 I' g
D.
% B4 m1 F% _: w2 d! ?9 n归并排序
7 s; V* V: j9 K7 i+ Z( F: t9 u
% o& ], t4 g' M3 d 满分：5 分3 F& Y. K, |$ t1 g( d- V" I
12. , {) x! S3 l& u+ t7 \
利用迭代算法策略求解问题，在确定迭代模型之后的工作是3 D8 z2 b/ Q9 h
) V7 C* V i6 \0 j3 @/ _3 J
8 i+ Y4 ~) A" D5 O
J' [8 i2 c$ z& F; DA. 控制迭代过程 3 o% ?9 E# Q9 h; C
B. 建立迭代关系式
. l7 L! _( V( X- k3 _2 M; VC. 建立关系模型 $ Y6 j. Q: z1 X" u) O0 ], Y
D. 分析迭代关系$ l. c7 z K$ e
满分：5 分
8 s# Y( M, Q, a! x/ a13. - X& R2 l- n$ D+ X9 m& D
下面的叙述不正确的是, R' H; l' J- R- r
+ C$ F; I. b: }# v3 Q/ w5 t( ?8 lA.
: r- Z1 o+ K7 v, a Q线性表在链式存储时，查找第i个元素的时间同i的值成正比/ R$ q4 e4 [3 ]
/ I. y# C: H6 o
7 a" w) W; W6 E: ]6 ]& |( W% D5 x1 J I) Q( |8 a' u" x0 a
B. 7 Z+ v, _4 }; N; L: p
线性表在链式存储时，查找第i个元素的时间同i的值无关8 e( S) E+ k# \- N% l
j2 J. l+ G7 ]! ~. p9 i2 l
C. 1 C! v4 }* w0 j2 |' L- I9 O
线性表在顺序存储时，查找第i个元素的时间同i 的值成反比/ T5 D4 k8 R& D2 l6 U+ O! K& p
8 n- {& U, a$ g2 c# G4 u0 RD.
* v! [8 H2 i% g
7 k7 e# k" y- q2 I% B; h& M" ^
% M0 |+ h3 T5 @- q) D线性表在顺序存储时，查找第i个元素的时间同i的值无关
/ a2 ?4 ~ _& X, E4 F/ x
! `( A' ^" Z1 c2 V4 L4 c* F 满分：5 分% p6 p, N/ d4 C* @& j# ]! h8 q
14.
+ J# d6 v+ U, l- O 分治法算法的关键步骤是1 Q: a0 g, P3 t" c
% v" q/ _7 Z- y4 ? ]) L
A. ( n$ M; [3 Z2 K- ]$ [( i, u( k
划分 ; N# W& B+ W' ~. J
9 V+ D4 K! C0 J& l5 M; X$ _
B. 4 t* C; R/ t+ D+ Y! W
分解
7 k9 f1 ]7 ^. t8 P: h$ S6 ]5 c) _$ l, |5 t5 R
; z r3 p- X9 _( `! \+ a
0 g% b" y1 `$ X3 Z3 @4 ?$ ~
C. 2 F% y; E1 }( h1 g7 c
合并 * |4 a* b: L, |8 d! n [
6 Y: r$ }3 O. r0 CD. 3 v* F. v: u8 n2 t$ O9 U: V" B
划分与求解2 s- e. l/ w+ |
5 d( D' c5 C: c7 z 满分：5 分
Y7 a% N# z; Z7 k15. 1 K) c S; }4 m) D. ?
用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。若该吉普车以最少的耗油量穿越沙漠，则建油库的第1站是在距起点的9 [# Q) n" V, l& L9 f( q
$ V. e5 a7 T5 d) G
A. 3 j6 B5 \" y2 ]3 p
1/5处 1 @# A. v$ ?5 r7 i
. O* [* r4 i/ c' L: `$ O) `B. $ _8 x4 p6 S( o+ H3 f: Z
1/4处
8 t3 k$ h+ R5 S3 v. }; E1 |
X/ z) A F3 KC.
, c+ p% Z% c' b8 [9 U+ O1/3处
3 ^" n" N9 ~8 X: g6 o: ~1 y& ^$ N# c8 u" t" u) S# e; \
D.
) \9 }2 ]: p% s( |2 X1/2处0 j& k4 w! W! q& T. D. ]
. p$ a" k0 k6 A; W! z 满分：5 分
% W ]3 A \/ Z/ D7 g8 W! L+ n" [
3 r3 w+ C0 R* h! l- x二、判断题（共 5 道试题，共 25 分。）V 1.
H! S) S) l6 u( S5 h递归算法是一种自身调用的算法，递归调用的层次，也称为递归厚度。
, j6 P$ ?* U$ }. e+ E$ B% v4 s% y+ V# J" i C
A. 错误+ g4 s2 o: P ?; K1 J4 K3 ]* B, {
B. 正确
- R( I. ]4 x( _) t) `7 A 满分：5 分) p: d5 J# o+ w# q* H1 h
2.
! X" B0 K- l) X# B/ Z& D. W7 Y动态规划算法通常以自上向下的方式解各子问题，而贪心算法则通常是自项向下。. L1 \: u5 G$ C0 P2 r, C; q
4 R$ V& s4 _2 L+ u& [3 c
A. 错误. G1 x, h I- C
B. 正确" ]4 {: s% w4 \9 t8 Z# o: ^
满分：5 分
: b. J& a* O6 r$ u( w" [" L3. 通常深度优先搜索法全部保留结点，扩展完的结点从数据存储结构栈中弹出删去。
5 \- p- j7 {- F/ g0 r3 I8 Q3 EA. 错误
' I& O- b9 I0 P: ~6 TB. 正确 {) x& a3 c% V0 H$ w
满分：5 分 `$ J, Q& H' H, Z/ c
4. 文件上的两类主要操作为检索和维护。" v" ^# y; v. v* T9 q
A. 错误1 z, k( W8 X' w N2 t8 B% l5 k
B. 正确' R2 B4 Q! M) N' c
满分：5 分5 {+ B5 Z; W: P6 m2 ?. V
5.
4 d2 H5 M9 C7 W2 [4 Y递归算法中的递归出口，描述了一个或几个递归过程的初始终止状态。
* S: A( [3 ^; S9 i! B& q+ W. A3 Q, T/ w* B" i
A. 错误
# D. s8 [2 r1 ` F5 [9 F+ D0 B5 [# l: cB. 正确
- l, c, \/ s% W6 Q6 U 满分：5 分
9 c4 K* y9 B, h6 S& B8 U+ W2 ?6 {9 ~4 J+ N) t, \2 z0 o# O
|
|
IP卡
狗仔卡
发表于 2012-12-19 13:47:16
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
