|
|
一、单选题（共 20 道试题，共 100 分。）V 1. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
2 R8 N5 {1 V) y7 a% {A. 1.0
/ V/ {+ m0 ]! ?/ E) M. I5 Q( vB. 2.9) D# ]( R+ q% Z
C.
* L( H/ s* P X' M6 _' XD. ) v, f; K3 J' f% f! B0 ?
满分：5 分 q1 V; X. _4 y F+ {6 V0 D7 l
2. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为* K* \/ z, U) E! E
A. X的左子树中最右结点
- R+ r$ d+ Y! I$ ?B. X的左子树中最右叶结点
) l3 y& I3 k; X6 E) C0 EC. E7 Z2 b$ R/ J' s5 O) {; v& U
D. 8 r8 v) l8 o% v" F( n* a
满分：5 分
- K' H; [+ h1 {1 W" d3. 在计算机内实现递归算法时所需的辅助数据结构是% Q. h/ s/ F" }/ t1 x
A. 栈
: J) X8 a* ^) b/ n% n1 R. iB. 队列! \8 h% q; o; f
C. 2 [7 E' J: X7 r9 W4 O. k3 J* x) T
D.
- Y4 W8 l4 V4 D9 D8 F6 z 满分：5 分
: s1 [4 V( u. r/ Y6 S k+ x- _4. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是
. J9 K3 M9 T3 r$ ZA. 索引存储方法0 O& V' E$ E3 p. z2 M6 K' w
B. 散列存储方法! ~5 }: n) X1 h' g3 B
C.
* t5 h7 Q8 P2 g4 M2 uD.
4 ^5 ^ ?; A5 p# u 满分：5 分- C; ~% O3 K" j d8 Y- `6 c
5. 解决图的最小生成树问题的prim算法，采用的技术是
P/ }8 q1 F% K% o* a% JA. 动态规划4 G, |6 x# |' }. [* B
B. 贪心法
0 |5 N& S1 O% n9 O1 }C. . O+ @2 K& ~6 `0 m3 k' V+ E
D.
! E# L- k" k4 W# ~! I% Q" ^% G 满分：5 分
' B3 q8 Y. z) U0 a" x4 \6. BFS算法可用来解决单源最短路径问题的条件是当各边上的权值& E p7 L& R* V: r5 @+ ?; S/ h
A. 均相等, v$ D$ k7 N+ T& q' a
B. 均互不相等
6 N9 V8 x- X- y% T/ RC.
P/ u) d/ y" I. Z- Z& p5 [D.
7 f" q1 D" n2 F: k& {; G, \ U 满分：5 分
& S4 z W$ k' i3 J u9 c7. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( |: v8 i) O: T2 [8 e7 j
A. 0
6 k5 ~% u, O' ?0 L4 m. qB. 1
- F# F1 i- W/ Z6 K; PC. 2 H: S; }2 x* K/ Y( l5 p" F
D.
8 R3 y* _; V6 i% |* h/ \; I 满分：5 分
1 q* v2 I5 V* M8. 散列文件也称为- b& l, h8 F6 T, t; n
A. 直接存取文件
, x( M. E/ b1 C9 \. p9 m! k3 SB. 间接存取文件& C/ P" z" Y4 S* p j
C. * W7 s, V' Z3 W( ]9 A7 Z
D.
! O( W! }' h( J! g, Y 满分：5 分' G5 x) w. N5 |: v6 L+ h" o7 Z
9. 在分块索引的在顺序表中查找，算法中采用的技术是
* ?, z F0 n/ d3 YA. 穷举法
z" D& s! _8 g5 s. AB. 贪心法
, V5 I( j8 [; X( l6 V3 AC. $ e% Y0 v9 Q; e8 H# b8 A, Q6 K
D.
7 j0 X& x$ ^$ E0 h7 u2 N 满分：5 分
b3 ^( |$ B F- j10. 下列关于AOE网的叙述中，不正确的是
2 E/ n; w) `+ P6 y* @; W, wA. 关键活动不按期完成就会影响整个工程的完成时间
! Y- F2 ]) H+ B5 \/ I- K: [: q: pB. 任何一个关键活动提前完成，那么整个工程将会提前完成$ Z" a& L, x; u" Q
C.
_# }9 j( }& j/ W3 ?D.
+ L. ]6 H) [! P% U8 P5 ? 满分：5 分
3 G! Q* L! ^- h: h/ ~' C6 c) S11. 对于哈希函数H(key)=key%13,被称为同义词的关键字是; z4 d( [% q0 v
A. 15和44
9 j8 }0 J& l/ C: ?8 vB. 25和513 d) n; y& S) ?6 T; X- F$ u
C.
: i( r: e2 t- v3 G& ND.
( G: S. C4 }' N5 A- ~. n 满分：5 分
' m+ Z! H' ]6 l; @6 x/ d12. 在一个带权连通图G中，权值最小的边一定包含在G的
. d2 l! a! B9 w4 ~7 IA. 广度优先生成树中
* ~' f6 x |8 D8 `- B# rB. 深度优先生成森林中
- @; f/ v" ]% S t: l$ XC. 1 Y3 s; M% v/ ^
D. 5 l5 L: O; f" v3 d1 P
满分：5 分
3 r* W; }% i- f: E2 l& b13. 设计归并算法采用的主要技术是+ E; O, t7 M9 s! |' \
A. 穷举法# e" f8 T0 I3 A
B. 分治法
8 `6 _3 R; T- t6 |9 X0 g1 y$ ~: nC. : ~/ v4 C3 L( s7 J5 G& z
D. % n2 z F) F5 o$ L
满分：5 分; X3 }/ n& ]0 \5 T P8 r6 g
14. 在分块索引查找的索引表中查找，算法中采用的技术是
: s9 G) u8 g( H9 qA. 分治法
) g" O4 x) _- m- ?8 i( ~. |% YB. 回溯法, s: a1 i7 u! p$ l
C.
: R0 k& t- V, I2 C* d3 oD. ) E8 u5 _0 E" e
满分：5 分
3 R* @% J0 |, z# x15. 引入二叉线索树的目的是
, I( B( A5 k6 X3 G4 f1 ?# KA. 加快查找结点的前驱或后继的速度% n' I# c) a, X. @0 i
B. 为了能在二叉树中方便的进行插入与删除3 F' d7 `# h- R7 U
C. z/ b$ `3 y) S& [$ b# d1 x" _
D.
1 e0 [8 t, b# a 满分：5 分
; G' [: {, F9 L r0 j16. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
. K; z' K$ s3 [7 P% ]; bA. 415 u( ^0 f+ I- W9 q/ a( R5 p
B. 62
8 S: Q7 ~0 K" V. N6 \C. 7 O) }. y- Y& A2 V- [
D.
+ X- h' m9 S A0 t1 g1 [ 满分：5 分
# M. F& i I w5 U: p' R, l0 b7 ]6 M17. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
: c6 o0 T9 H0 {2 g1 AA. 逆拓扑有序2 g0 t3 K: ]7 C' i; z& D! q0 ]
B. 拓扑有序
/ g9 h4 K ]. G ]2 U' S, @% m cC.
0 Y0 q" e3 X- R: wD. 7 F6 `, D4 A' ]; ~3 \. [
满分：5 分/ U4 Y8 H4 V0 N; r, R" N* h
18. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
) j* q& s0 ^+ s* l+ BA. .O(n)
3 ~, `! l" w! x, @B. O(n+e)0 ?3 @8 |: Z% r8 g9 V
C. , [2 S* X8 w# p5 \0 Y# \: W
D. / Q$ Z1 K, B4 \1 T: T4 A( O
满分：5 分# ^8 h7 T' f& K
19. 下面哪一方法可以判断出一个有向图是否有回路
+ j( z& S# [2 a: TA. 深度优先遍历
' x" U- R. r, N. W5 ?B. 求关键路径# u2 d. y1 O4 E
C.
; D1 t$ V# d3 [$ E6 p6 uD. 9 s, e) _& L. T! M7 `' V; i
满分：5 分- h) L G/ W% n& I
20. 设计求迷宫问题的路径算法采用的主要技术是
2 g, C; [1 A# `( x. I% C. X& lA. 分支限界法
7 n# S+ M# A, w/ V4 z/ @+ SB. 分治法
) E2 k: o, S8 [0 G1 YC. 4 r: \7 y4 Y( b! ]: Z
D.
" n' b, ]2 @) d0 ? 满分：5 分
3 c" a1 e' f+ U1 H1 s9 r( `
6 o0 c @8 E% S8 z8 l: n+ l需要满分标准资料请直接加QQ :1306998094 |
|
IP卡
狗仔卡
发表于 2011-9-30 12:41:39
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
