|
一、单选题(共 15 道试题,共 75 分。)V 1.
3 A/ C3 q2 G4 A0 `$ ^( K9 B; G/ A9 N一个学校只有三门课程:数学、物理、化学。已知修这三门课的学生分别有170、130、120人;同时修数学、物理两门课的学生45人;同时修数学、化学的20人;同时修物理化学的22人。同时修三门的3人。这学校共有的学生人数是% }* W; C& }) x G1 \
F, N3 q3 s6 G7 t( v6 GA. 3000 A8 }# B m3 I$ W- e- ^
B. 3367 z! P: R A8 e; y) s D5 |/ k! X
C. 420
$ m7 o* F& U; q3 r, Q# B3 HD. 430- ^' f2 y O, b2 p# E1 L
满分:5 分2 p* r2 C, M5 P* y: @
2.
y$ N: P, a# d/ v. @4 ^+ q t" d用计算机对问题求解,问题的本质是$ O: q' u$ f# [3 B( h* Y- o6 D
4 g7 m5 [8 X7 O
0 ^+ s' D, P( S" B$ a, l$ x2 L& i* {3 N8 s; ~" }
A. 数据类型
/ q8 }! L: u' w9 a0 c6 O) V: xB. 数据结构
2 z2 n3 s* ~8 D1 ]0 d/ N1 B$ pC. 算法编写 4 H# f( e2 b' A- d) T6 O/ P% e! `
D. 程序设计/ |% v: s' D/ ` L( _* S( o
满分:5 分2 v0 V* Y7 z' F0 T" Q( f! s/ b
3.
D' d" Z& r: u无向图中一个顶点的度是指图中
; x; z z$ z" ^% E+ p: f# M% o, t$ u" V3 }) K9 Q$ W7 a8 D% _# t
, T" B3 f9 |' k7 c# D7 ]( Z7 X/ R1 {
$ x2 ~" O6 M5 P. H
A. 通过该顶点的简单路径数
" s& r* K& ~8 k5 I x$ O) EB. 与该顶点相邻接的顶点数- o& G8 G7 K6 b; x% \
C. 9 g7 X# q1 F0 u# ]# a5 k
通过该顶点的回路数 7 a; b. f1 {5 u- v
$ O5 ]2 y! q' v) \* }8 C
D. 与该顶点连通的顶点数% V$ {# Q/ S+ q2 d
满分:5 分
- P8 e8 w" P5 q; I% E' g4. ! [9 d9 X$ i4 f' W( X& y& y
含n个关键字的二叉排序树的平均查找长度主要取决于- o# x5 J' X" P# X7 w
, S0 [( q. \) Y% @, o
; ~+ s! }4 O. R$ f
3 I4 n$ \: e) hA. 关键字的个数 # u. s+ }/ v; c$ V. I
B. 树的形态
/ Y$ i/ |, n( G 7 {# w- k& F* J, p# ~
4 L, _6 i9 w e4 qC. w/ n9 t k$ D: P5 k
关键字的取值范围 3 b# C- R$ n% {0 `! V) o) a
1 E! o$ N( ]# V1 ^5 V4 l
D. , m0 i- m( S% c2 t0 t; J7 _' r
关键字的数据类型
, o6 K1 }! A# m+ I* ]5 J
- {( j5 X$ `' p; u7 H 满分:5 分2 N/ r" T, B' N* V7 s* ?
5.
2 j* T* N" K! U* t用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是
& M# n0 V! V1 v6 f' D0 h7 C, y( W( K3 `$ `
A.
2 r! y5 T7 H1 u( U" B8 X. n# g 逆拓扑有序 ) U% u* D R. C4 `& X. J/ E, O1 K& @+ j
: k+ N P( q1 @6 l7 e! v/ I2 A
B.
0 f% ^2 R! w/ Q; ?6 e 拓扑有序
3 I6 x; U* ^) U3 |) E6 J, s j% W5 `9 i6 x8 D
C.
, y* z1 G* Y/ E 无序的
% {5 b9 Y3 \6 p$ m7 z8 Q1 H5 r2 N% d: _, `
D. 5 d4 J6 v( s$ _" a3 }$ j2 L- Q
A和B
+ U7 Y8 a, o' n* R- T" s3 Y: D3 h4 r- @+ h, Z8 j
满分:5 分
) e Z& z/ g7 F: V6. " d) V" R3 n+ E8 |9 ^* g
若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 0 a, d1 Y$ C: O" r* [$ m
$ o" ~" H* ]. {( z e4 K+ Y+ C
A.
' C3 V% a4 Y4 o$ P. S 一定存在
/ w1 H p; k& P* I" G2 z7 U- E3 k4 P/ _1 |
B.
0 E# h& @) q7 S5 |. \# t/ U5 F 一定不存在
4 [3 E# ^4 ^0 C& m3 j' D) k; E5 Y1 u
* H `" `% J# n; J8 n) EC. " M/ D ]/ E) Y5 \
不一定存在
! g: f" w) |* J, A& a7 Y5 r$ W4 b$ q6 z1 w. d9 Y6 ]
D.
3 k" s# ?3 T8 r6 P2 t不确定# w0 w+ z! Y ^# T, @
- \, m: u5 M! F( q 满分:5 分
K% N: D9 _4 ?7 p, l# g7. ! M2 z: s+ J+ C; q8 Z, r1 G
为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
4 ^9 X: H3 m% ? K3 P6 \
* \8 j x0 L& k: K5 j" R+ M. s# _ 0 O3 O+ V+ j& N% [5 G8 n' p
3 b! z2 h$ D6 W8 {A. 05
0 }( L; M. D, _7 F2 P3 h2 i x4 OB. 37 $ ]7 k8 J P7 T: y' L: j
$ w8 }6 i1 q3 a h3 x" x- ?
1 d) i; u% @6 I6 [ O9 p$ U& X
C. 0 I& C2 u b l; t2 P9 b
41 , B6 @# u. Q) u6 e, b6 O! \3 K9 _' {
- j; K6 e; Z* n3 L) n6 KD. 62
% k1 E; B4 U% w 满分:5 分- X, f! e: W- I/ x
8.
: F0 u8 a7 Z) `* r设T(n)和f(n)是定义在正整数集合上的两个函数,若存在自然数n0和正常数c,使得对所有的 n≥ n0 ,
1 G. ?& I: e. d5 V$ ~/ E3 d( r A; }( `6 ?% y# m
都有T(n)≤cf(n) ,就称函数T(n)的阶至多是
5 [+ U$ G1 K: }; J0 m, T( T! h% h7 s
A.
" F" K j/ i# f4 ~/ g: r O(n) . h, }5 n9 I" M
4 o- H7 {& F9 Y' H+ }4 C% T* `9 m& IB. 5 y& y8 j. a; R% {; i
. O(cn) $ n& R! c" C* [! Z- l
z9 d/ X. i' [$ i* G" j, b- \
C.
$ h- Y R* `- ]8 Z# A! a f(O(n))
, \( A1 g$ p( n6 {7 H1 s: w U" k) z6 J& C
D.
) L M+ f/ b! ] O(f(n)) $ F. g6 p- g& A# ^
# r% Q6 @* J3 F6 w/ d+ }3 H( u
满分:5 分
3 a( B9 }8 ]( L( \1 I- a* A5 s- ~9.
, E; b( G9 s8 v) B' w在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为# ?4 s# @$ V6 W( c; ]
; e! O3 |% j1 p2 W% V, Y @A. , t+ [& `0 ?$ M# p, K
O(n)
9 V4 B* h, A0 Y6 i# [* w5 z! K
' Q- D) v; ~1 x" r0 dB. 8 m4 P Q2 ~- N
O(n+e) * N* \( h. [( A" v1 y% J* |
) g+ X+ _0 u2 C# b/ `/ D" Q3 L8 k YC. " ]/ _7 C$ \! }' v! k# w @/ \
O(n2)
3 E# U3 o8 F- q+ i
) |+ P8 E0 B' s: ^1 Z5 m& LD.
! T/ Q7 `6 V* _5 B% h8 k3 @2 V# i O(n3)8 S+ e# J$ ^- U7 g
. n6 m- R0 I Q1 A
满分:5 分) d. ?4 a! V- w+ W$ K
10. ; l% o# e9 F) W e% Q
在进行递归算法的设计时,通常先写出问题的递归定义,递归定义由两部分组成:基本项和
3 [1 A$ W5 G/ @; ?6 {9 a
" L$ g$ h+ L* {' xA. # \! A1 Q! z. [2 O# K
扩展项 4 i& P' d( c! K* |& Z$ ~% S) y
, Y6 }7 [2 V4 k5 C" P6 s
B. 7 ]; u; \& u! z
常数项
0 p! `. i, u, s0 i2 o( z( A% I |$ |
0 [8 O: I ^( G$ Q5 ^0 a( P- zC. # e8 }7 l0 W4 U( ]& N/ v
归纳项 . }9 ^& F# B0 j) _ S. R
2 k g6 D4 \+ E4 P8 U9 pD. . Y& O" M" Q5 K5 q& S
递推项
- t7 k0 `( v% u2 i( R5 T2 S2 A- u( W+ \6 ]: d: ]2 {
满分:5 分
h! W' i. R1 N% z% m9 f }+ V11. # ~4 l. D9 V# e; y9 B4 ? p
在待排关键字序列基本有序的前提下,效率最高的排序方法是# {3 b% ~0 e6 [, n" v( v
8 ?% P @; ^, e) eA. - }2 w7 R* @8 @+ E9 h1 [
直接插入排序
, V* ?" I; J5 z9 a) }! N5 H4 ]% n9 y! b& l7 h: ^! y
B. 9 d% Y! y8 Z; C; C2 A/ F
快速排序 C1 D/ G ?, N# v" S8 p3 S
* g! [7 Y! F: k0 \! o: hC. - D' f+ y/ j+ y3 w
直接选择排序 4 L' n' D8 q& e" K, f! W' S) x0 I
5 P: c- ^- q H2 ]# m8 Y, T; |
D.
, ~+ [' l0 U4 m" l% y归并排序
, b% `0 Q) N1 p6 N) g8 ^- P) q. l/ K
满分:5 分 F5 t+ V3 n; ]8 l0 T3 u
12.
7 _6 a; ], I1 \/ }( B$ g1 P6 X利用迭代算法策略求解问题,在确定迭代模型之后的工作是/ n* [+ l/ L) Y9 _( @; I
, g7 p b1 `* D
9 a* j1 F1 M" R0 ?% R
( l- A% a. M: Z& ]) N, ~A. 控制迭代过程
- H3 @7 [# T2 p) o3 Y+ TB. 建立迭代关系式
! Z( V% k! ^2 X$ _. i% PC. 建立关系模型
# T1 V5 D4 W4 d% v3 tD. 分析迭代关系$ o3 m* c7 t5 T6 w, N9 ^
满分:5 分/ E' [6 U( i1 w9 ^+ W! Z
13.
2 e% U: c: v5 l5 M6 Q; e$ g+ `下面的叙述不正确的是
4 l, A0 Y: h: P9 G: \
) K- X3 a i0 C) {# s, ]+ `; L" O6 [A.
* ]1 k) T z/ x线性表在链式存储时,查找第i个元素的时间同i的值成正比0 D: b' {; |2 m
5 M2 {' ]/ `. v# @6 }9 y) s& X 5 Q& v1 ]) a4 o: i- a/ r& ^
7 k& g! }! r; C
B.
/ O* ~+ t" _+ ]: Q& J Y 线性表在链式存储时,查找第i个元素的时间同i的值无关6 b7 ]9 }# I* c
0 H% D+ x6 w+ f. p7 iC. 6 r8 Z0 l$ }4 i V; T& g
线性表在顺序存储时,查找第i个元素的时间同i 的值成反比- o. }: B; P+ O
2 L# [0 ^1 e r2 g2 O
D. & Z! m: L" |. d5 A
2 r" o/ Z0 K5 u2 [. [9 k
S$ S, b1 c( I& Z2 P Z+ A线性表在顺序存储时,查找第i个元素的时间同i的值无关+ u( m% Y0 l: g4 o: n: x8 k( l: @6 r
6 r$ U& z( A# ^2 R- Z4 n; t
满分:5 分
+ ^1 b# _" D L" b! ]14. * Q; ]% _+ a' N. g3 }8 q3 L8 `
分治法算法的关键步骤是
$ c5 a$ C9 s) O
- Z7 H7 M+ o' q0 LA.
, v1 D* N) u2 z# c: {9 b; m2 P" N 划分 , A8 ]7 b; \' [' O3 x
2 A! f! Q$ T) X1 [7 t. P
B. ; u/ V1 |) @8 p9 T) H9 u" u3 h
分解
& D2 o5 p; d* x0 v! w0 T" z
3 s/ i$ ]$ l" R , p* P* U1 i8 ?
, b0 E* ~% r' P
C. : k9 t; N+ y' q# @& e
合并 3 m$ D' v* z0 }, g
9 ~: n% C: X. [5 E& J
D. ]% C- ]+ F% C1 U6 {
划分与求解
$ u" x- x2 y5 ^8 w2 {2 e# g* o2 p t8 [8 I
满分:5 分: @+ z4 W9 V3 D. V8 h
15. 1 p0 \4 S3 H/ g) S/ t: n
用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑,耗油率为1加仑/公里。由于沙漠中没有油库,必须先用这辆车在沙漠中建立临时油库。若该吉普车以最少的耗油量穿越沙漠,则建油库的第1站是在距起点的
3 @2 O: u( x' v+ ~' }: H. @- C0 ]) A( R- k V% Y: g' J! n8 J) J9 @* S
A. ( k" ~* ?* s% q* X. g! h! e1 L
1/5处
" Z+ H6 Y6 j+ O% g8 C& X/ F7 r9 I5 q1 \! c8 P
B. ' f4 G- R( c- I8 F
1/4处
; Q z7 t0 S5 F. a: J8 H5 J1 S7 D+ B+ A) w
C.
! w3 e8 u. @* m, v9 o0 _1/3处
$ Q' e. z5 b8 R7 y& c1 |' e9 e. [" w/ [
D.
2 [; t0 a1 z: G2 }' Q+ l1 z7 U1/2处
9 C" E" b# s+ c5 t
; Q# j8 W$ \$ u4 u8 v 满分:5 分 4 ]2 j" s& n+ T5 Q" |$ s5 [- W
! s! ?0 M: |6 W5 y3 p二、判断题(共 5 道试题,共 25 分。)V 1. + c% S* n6 `# y* o# f
递归算法是一种自身调用的算法,递归调用的层次,也称为递归厚度。
1 a* k* e* x: T$ a5 t
7 l/ X6 [4 l f7 B7 @( Y/ gA. 错误
2 m: k) Z: ^2 y) I6 s, TB. 正确# Z7 c N: W7 a$ t% k, K
满分:5 分7 T& C/ r1 A* @: Q7 v ]
2.
; [$ m+ `7 k6 Q3 @" a动态规划算法通常以自上向下的方式解各子问题,而贪心算法则通常是自项向下。3 U! J; i& p9 J$ r$ m0 r" N
% v k |' Z, ^* C/ c- I- B3 w
A. 错误
2 ~$ {8 B6 X' b; d9 kB. 正确
- D% F2 i- K' m% s/ M6 u 满分:5 分 n) w: P6 V! s( J
3. 通常深度优先搜索法全部保留结点,扩展完的结点从数据存储结构栈中弹出删去。
$ c4 j# p$ Z0 h3 n1 iA. 错误
+ h. d8 I9 w# F, s! RB. 正确: h7 O5 l# f* O+ A% b
满分:5 分
8 Y. z; ]( n8 [* l0 g4. 文件上的两类主要操作为检索和维护。
P H2 F) R+ S8 `6 o+ t7 b! BA. 错误, x K; ~! o. `) V' K9 m& W& _; X
B. 正确' r! N( Q4 E: v# }' e( w
满分:5 分
/ d: f3 ^# h- ?( F+ F: e& h& M5.
3 Q5 { \1 W, i4 N. `9 ^. |递归算法中的递归出口,描述了一个或几个递归过程的初始终止状态。
. }% }0 H C5 Z7 T1 {9 n& U; }6 I" V* j$ i+ m
A. 错误
3 l4 q% `5 b: S) U' ]4 n8 MB. 正确; G4 W* @/ h* L7 C. P5 ]% d! Q
满分:5 分
2 `. ~, h+ L$ G0 G* _8 A
2 T0 R6 d! S7 { |
|