|
|
一、单选题（共 15 道试题，共 75 分。）V 1.
. C g% d% S* _3 H1 y; }$ c! \! [% L5 h用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
+ b5 e5 d; o% T* t9 t
3 e1 _8 T' c1 p9 ]. AA. ) h+ p% Y- d( I5 w1 r& F
逆拓扑有序
4 p1 ]6 I/ c5 {7 |3 Y- k5 M3 t# ^0 f
B.
; l q! }3 K, g0 M4 L 拓扑有序 6 C" W$ F6 M9 G( A5 Q' K$ y1 r
/ }! q: H6 }0 k$ t6 Z$ v. u
C. ) ^* N4 G+ @- U
无序的 2 ]) i* B5 B' Q K+ r; h
3 P8 J, Y0 K( U: U! F
D.
7 Z' v2 ~' O% A: s, T& f( }A和B
" g1 A! r) ~* A: f8 I8 \* o4 h5 y3 y# d |" b) N
满分：5 分 m0 E/ a9 }4 p2 v- ^7 q, d; l
2. # R5 e! R! O" ^
无向图中一个顶点的度是指图中
, C% T4 k3 x7 y$ y4 i2 ]
. D( L; S& R$ ^7 [' v) m 2 m3 d6 t& O9 n
% A4 _+ o% m* T0 _4 e; `' \' P0 U
A. 通过该顶点的简单路径数
. J' L" G. m- d+ O; W! XB. 与该顶点相邻接的顶点数. E" {6 T d- m* j& q
C.
+ w1 U w) a* v0 A7 ] 通过该顶点的回路数
1 r3 d) s4 u; t" a
: S8 D* j5 O: {2 eD. 与该顶点连通的顶点数
0 P/ E9 J! O1 s g s9 \6 l 满分：5 分" F( c% p/ L. e& I
3. 2 P' @5 U) u5 l: j" ]5 a5 Q
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为% m: Y3 X u$ @3 O5 a$ x1 F( E
1 m8 g4 t0 {2 u/ B: Y # Q8 h3 I6 g8 j5 I
9 U7 @) z6 {4 `" {* V6 N7 x+ f( iA. O(0)
# ]: w5 M: k1 W! SB. O(1) # @9 N* V |2 ?% j6 d& {4 W' [
2 \0 t3 i, h$ E7 I8 C7 d/ [; O7 \. e% V
C.
6 Z5 X1 I d# `) z: Q y$ u O(n) 6 R) |* b4 i/ E' x) i$ q
. ]) A8 X3 m' p1 E8 b+ E5 ZD.
& s& @; |% {- I% A# p& uO(n2) ) S9 B+ |4 ^! X p$ H
) B$ u! P1 U3 o4 R
满分：5 分
/ Q2 _% ?6 u" @$ r1 f4.
& w: C3 N/ S/ i5 [) l ]用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
1 _! Z& c0 \1 H7 t7 r
; E2 H2 Z. p a- u- Q6 U. IA. 5
9 t" h; C; M% y+ sB. 6
( j0 B; V$ u k( j4 tC. 8
" ]7 |' g2 ~% {& j' OD. 9
0 s- ?" O7 ^$ s4 X4 S5 |) i4 ~ 满分：5 分
% I; x% U# N D+ D+ |- |5. 0 m7 Y8 _0 x- d
而解递归方程的最直接方法，就是采用( p9 D" x) V8 o& O2 c; ?: j
! D; W; X2 W/ ^/ r4 Z; J" H
A.
* v( D1 {+ E( l1 l8 \% m递推法
' x1 _3 P! h) U/ E5 T, Q0 J: q: g$ y; n, P
B. * e9 V5 V' Y0 H5 ]
穷举法
. `$ x( U/ ]' n* l9 ^" h
% `+ ? F* I8 \% [6 s- G: T3 C- kC. 0 N! n- }7 t- O$ A2 b* [, N* ?
搜索法 : X9 c3 d; h6 q6 x
! I1 s) M+ n$ L; L* t( n Y7 M8 L( g$ ID. ) ^4 `6 X0 x w8 X; |
贪心法
# g9 ?& [5 w# ~! r/ n8 f; X) `7 `9 Z' Q5 ?! K1 s
满分：5 分8 b2 J$ d# P$ R8 W& Y2 l
6. 2 }7 G- D6 z( Z, [" V
图论问题主要是研究数据结构是图形结构或树形结构的
& l, e5 d! h2 l; p3 S
$ @ I6 I9 F$ ]) w/ UA.
6 ?- F$ F4 X, g/ x5 [( Y$ U0 n/ S结构 % ]9 J ~4 F, M v* u$ ~' ?
% k! f! N8 k6 I
B.
1 a" b; s/ [6 s( R; [8 U) H3 p: x定义 . Z1 x& C- p* n7 b
0 j2 Q: _, F& M UC.
7 {+ J! ]' L6 R- [+ z/ p算法 5 V8 l2 q! x( o! Z7 k9 @0 x' Z* R
. }8 A( Q: w+ x; f( D$ [D.
% P2 X9 U& O& p% L$ G2 ?& G) z9 C数据元素6 V. r z! P2 f) c0 W& p
/ |1 g6 P2 Y1 Z6 e' j! _; W 满分：5 分
, ]3 ?% }' n6 f0 z7.
9 R) E4 M5 R e% o' p; V若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 ( a0 R8 b' d3 j- }% E' i9 |, v
1 L! h1 `' z9 t1 o& a- @ H4 s1 W
A. , E0 F2 s0 J) x: K2 G4 z
一定存在
9 v" s' A' E4 k6 R/ S' f( D
/ D8 S4 ?- k& g4 q1 G* x/ bB. . u0 z5 J. G4 q( @6 J! O" I: W. x
一定不存在
, Y- R: l* S$ F8 r: V. ~' d) C
0 |8 i. z) B5 n: oC. 5 B% c2 Y8 a+ a
不一定存在 + {5 U8 X* v ?+ n! b
- Q. t; {4 S5 Q' f( h- ~: X6 i4 J; w' LD. 8 L! e7 |: X7 N2 i
不确定
7 I6 G" E+ m5 O6 F+ ^% I4 i: y+ p, i
满分：5 分
5 n5 f& @( Z5 j& ^6 y9 }8.
0 U, Q ^+ R, {( a0 I E2 P若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
1 g$ F+ r- w9 @) [& S4 n( k0 U9 K% k6 e+ c: X3 w$ w) x# h3 s
A. 3 |1 p+ I9 T0 W1 a9 W1 I
2，4，3，1，5，6 : F2 H' P9 R$ P; R8 p8 M5 s7 P+ H" l
$ \* x; \% n) J" L& a/ s
B. $ K+ v$ z, ?! {. S- F: O0 e
3，2，4，1，6，5( [& w9 h: J2 A2 d a0 T9 ~
/ T B- T7 s) PC. # p, ]. P+ ]( l0 m
4，3，2，1，5，6 ] | [2 ^" E8 ^" ~
5 ?5 k/ ?( y- Z3 Z* ND.
# }( \7 Y* s. x3 j/ |' z2，3，5，1，6，4% P; R' k* F4 s- P8 _+ E
6 z2 W! e. `) h 满分：5 分; g4 x6 d! ]: L& J
9.
5 n5 `7 m& h% g2 v多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
! P( h4 x6 |6 z" T! ^1 \/ d
! i9 n' I, b# a- |% b9 i7 i HA.
8 P/ A& |4 v0 v0 x6 k数组的元素处在行和列两个关系中
" [' ^6 k( V# m1 y
8 V" O) T6 m5 i: L; K7 E# n7 v3 [B. ; g6 i8 B/ P5 N9 G5 [1 X& n
数组的元素必须从左到右顺序排列
: H/ Z. b. Z8 [- ^; d; q( @* k2 c# R1 P
C.
' U H! h2 M- Z& v, @+ Y- Z数组的元素之间存在次序关系
4 f' {$ ]3 u6 M7 d! X$ ?
4 g# x( A" j3 K; T* mD. % _. k3 _- l( e% }7 p$ \4 {+ }
数组是多维结构，内存是一维结构8 J# }$ s5 a3 r: X$ m! o3 f
6 a& H( b$ x' p1 c 满分：5 分) x" W, E- f- `& K: m* O
10.
# A6 `8 R& T, s% J若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，
) j% x* _/ I5 i7 c* a8 b; l9 E; [' B+ h+ k* d
再加入两个元素后，rear和front的值分别为
+ \, R, @7 f2 S Y2 N2 R* E5 { ]1 }' b
A. 2 O: @1 H- ?/ |8 Y. @$ Z* A0 J
1和 5
+ Q* |6 V* |: U: {5 ^# Y: r5 J" z+ N: J, I- U! l/ v
B.
+ F+ ~- C1 p- g7 _ 2和4 5 z; y, e3 H. G5 R# s
/ f# D, f- H) N/ L; ^/ qC. q, I: A* }3 ]( h- {$ S
4和2
# n# z6 e" I& _3 A5 U0 Y
& q- r- Q* A% gD. 8 u: `! {$ l, Q# W8 y, |
5和1 & R8 d( a- }* i8 Q: r
( @( ^7 n- ^% E# X 满分：5 分
# [( _; B- P J; U* T' z1 L11. 3 @8 y$ a' D" K' Y; r
已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为8 Q' _- ?$ ?9 @
( E: {: Y! I7 d B- r6 @0 j# y# R* B
- w' t E, ^4 o R
+ ?9 o8 R5 K' c, Q8 n: C$ p$ JA. 5 T, Q( z* C2 O6 o! J v9 n. |# [
B. 8) j% q& _ W* K) _6 d, n7 r3 }+ p' T6 P
C. 11; m* Q- i8 W) R R2 A' F) A
D. 18
c5 j5 f! \' h/ I* p% ] 满分：5 分0 ]$ r) r- G2 D& U% V; D
12. & N/ E5 J) X; s' a' ?6 m- c
设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是, P. r0 U9 @% {/ `. `
% K" L+ P E) ^' h
5 d. l* ]; ^" b6 }7 k- H4 k2 L1 d/ ?
* N% N% C+ `: v, Q6 l. W8 r; z5 P+ ~9 V( MA. 23 ^3 `' P6 y# @7 Q/ ~
B. 3" h1 z; ]( X" y3 ~2 T% R
C. 5
' B6 f/ s6 C) r, J4 hD. 6
- b0 b, _( F/ @" [, N 满分：5 分6 N! R0 a; f: ^: [: s/ E
13.
% e; @ V4 y* h已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
; W+ X& x2 L( G( r
9 Y; j3 i1 C- j# S* ]. Z! N6 t
m% S, V# O1 Z; o, ^, c5 p9 q
* }$ _4 X: F+ W( H0 K2 pA. 1.0 ; Q+ o% }* y$ x; Z' h/ Y
B. 2.9
5 @& m; z* u+ u3 m- J3 a) c
" f$ t0 Q6 N: D/ a8 r
9 K0 P% a2 p* lC. 5 D0 q8 ^$ y( E) V$ O
3.4
0 t& [9 k/ _" U: n* L/ F$ p5 o7 R3 |; g, |+ D! V; @
D. : z( v$ H6 P1 |& N& }* b( \
5.5
" E/ {! e0 u$ u' O9 p0 z( G% {5 k# k( _+ [; i2 M |4 Z
满分：5 分0 U: _: z; p9 E8 e; q2 q
14.
) d% F! T6 d0 Y利用迭代算法策略求解问题，在确定迭代模型之后的工作是! h6 Y" L; S0 q: {
; ]9 m; u# s( T1 T
2 f. d( s! c0 P7 s; Z6 k
) F2 i% v c6 ?3 M# Y+ L
A. 控制迭代过程
' @+ k" ?# R% p( _5 HB. 建立迭代关系式 - ?" }8 d3 B- k" x
C. 建立关系模型
/ X: P N) n" V2 m# n( S0 z$ E8 B( iD. 分析迭代关系, j7 y' E' D# B2 v
满分：5 分
M1 e% x% y& n& t% e, w2 w# o15.
% }2 P; x( N( w- Y( {6 o6 k" \排序算法的选择取决于问题的处理环境和本身的
6 E1 i" R2 y$ i1 \, C- {+ F# b- ~/ K( c5 w: W
A. ' s$ g; y8 }" R+ X$ E: Y7 J/ A
规模 6 k' e8 }/ Y6 J# ?& b; D
4 O$ R4 }0 x2 G8 t
B. 5 X9 l8 D/ d8 v1 d h
特点 : z6 D7 l9 v! D$ ?+ k8 N* Z0 m
/ a, k8 k% E1 [' n' XC.
5 W2 B% M+ }+ z+ ?" `结构 , z j6 ]; O* u6 L$ \4 ~
8 F3 V5 y: e9 |2 D! o, X3 CD. " C3 q. g3 y* R0 J `
作用
$ u d& Z# n G9 C" E& i5 [ ?& N
满分：5 分 1 V9 e! ]- G4 i+ O2 Q
3 \0 S6 \8 }0 @
二、判断题（共 5 道试题，共 25 分。）V 1. 9 L3 b/ W2 Q0 I
Hanoi问题的递归算法的时间复杂度为O（n）。算法的空间度杂度为O（(n)）。, @6 d5 \$ c6 |* v+ Z* }( s& w
+ Q2 x; Z8 @; P6 [5 s% c
A. 错误$ @" r0 @( w; Q" C U" _
B. 正确
, [4 G& f; T) W: g2 Q- K 满分：5 分3 L/ c8 k* H: y
2. 克鲁斯卡尔算法的时间复杂度为 O(eloge）, 它对稀疏图较为适合。
) j' ]5 k) |. o3 s" d _A. 错误
8 R( u. W! `2 b) u% w/ {9 X4 W" ^B. 正确; _1 @2 I+ ^' \( @
满分：5 分( O. q Y2 U" o8 E! [5 W
3. 记忆化限界搜索算法在求解时，还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来。
# t; }; e3 }5 A) H: b0 y2 f9 x0 yA. 错误
( @% j3 X+ R- j6 n3 NB. 正确 D: Y: b; F# o$ n$ N( g
满分：5 分
4 P/ c. U4 L# z2 i4. 索引文件中的索引表指示记录的关键字与物理记录之间一一对应的关系。
. r4 z5 r6 U$ D) LA. 错误
9 f2 K! Y! p; `. N- TB. 正确
) e* d4 U3 c4 S- J, Z+ e 满分：5 分
' A6 k; t$ } e4 C! I: Q- y5. 可以在多项式时间内解决的判定性问题属于NP类问题。- j' a" H/ \- j
A. 错误; t+ j2 o5 u+ m
B. 正确" z5 y' Q. x% Y6 t- @
满分：5 分
7 W$ N# W2 ?1 T7 }: E3 ]
8 Q0 `% x: K+ K |
|
IP卡
狗仔卡
发表于 2012-12-19 13:54:38
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
