|
|
一、单选题（共 20 道试题，共 100 分。）V 1. 以下说法不正确的是
W) l0 k4 U: O4 ~* R2 q+ dA. 无向图中的极大连通子图称为连通分量$ p$ q9 G$ b7 _6 L
B. 有向图的遍历不可采用广度优先搜索4 w" y6 N) H9 f* u; j) G; k) y% s z: P
C.
. Z9 _: `! {( [& O6 \: sD. # x8 _- B% Z z2 s8 j9 }
满分：5 分+ U' P$ J0 j) C9 r9 q
2. 一个有n个结点的图，最少连通分量的个数是
}9 Q1 c3 M6 S/ `' `; HA. 03 y9 `* ]7 q9 k/ d9 z) ~4 b) {" Y
B. 1
, K+ j3 f5 Y: tC.
6 x# y! C: ~) ?% n% |- MD. 0 k1 g1 p* G( S" c6 v
满分：5 分
9 _3 X) k, Q; ~! B# k3. 栈的两种常用存储结构分别为
4 q& I a8 ?( @: i# G6 r) S$ s. gA. 顺序存储结构和链式存储结构' s) \$ n# m6 M; s
B. 顺序存储结构和散列存储结构2 F5 a) `6 i3 p# T# i
C. 链式存储结构和索引存储结构
1 S: z: K9 }, \D. 链式存储结构和散列存储结构
3 `' [& k$ ?) R' r6 ^& r, i 满分：5 分
* s0 o; o j: U: V5 {4. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是+ I, Y# ?( {3 Z: M
A. A，B，C，D* H! h; M) y- ~
B. D，C，B，A
+ T- x% F z3 K+ c- g4 ?C. A，C，D，B6 D: r: Z( \3 y* q2 Z6 u; N: O
D. D，A，B，C
7 O! T) p& [/ N) {3 F: z3 F& b 满分：5 分
! _' b) [# |& |( h. b9 g5. 判定“带头结点的链队列为空”的条件是5 D6 D$ j! y( X3 [7 r
A. Q.front==NULL
0 u, o0 M# a( L' l+ a6 S7 y: {B. Q.rear==NULL
' R& R' f/ @/ Y$ E$ _( [$ }C. Q.front==Q.rear
* u) G* q O. ~+ b4 Q0 N; l7 T) HD. Q.front!=Q.rear. C6 f- v$ a& D, t6 i; u
满分：5 分
2 W0 b. ?- K9 h3 t5 [6. 二叉树中第5层上的结点个数最多为/ n9 w% t8 B7 r8 I* [! i
A. 8
9 b9 B6 c, R/ O0 @( s0 @& [ O. wB. 16
# y6 \; r4 y/ x# fC. 6 t$ v, O& u; B: i
D. 4 P# e* @; g9 _1 C W+ U) P5 G+ y
满分：5 分
: q. s0 G5 g3 e, g7. 对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为, u& W0 @$ l, T
A. O（n）0 I3 X; c- D" t# y
B. O(n2)
5 G" A) V4 W; R/ q5 gC.
; ?/ _' D, E$ f( i2 uD. $ _" P3 I, h2 V6 j3 l% T/ _
满分：5 分5 g* o3 C, \- z$ \8 j- Q
8. 若<vi, vj>是有向图的一条边，则称/ ]+ B1 |5 h, z) z6 {8 p
A. vi邻接于vj/ b; s1 O$ ]( B* i. g
B. vj邻接于vi, r1 ^$ }! l, o# U9 _
C.
1 ?0 m: o6 i+ d7 X7 [( DD.
+ J" U2 s a* ~7 z' a8 r8 D 满分：5 分
0 ^# S/ F4 h7 Z" G$ M6 {4 Q$ s0 x' e9. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
! |7 Q6 m2 j. y+ kA. 有向完全图 h$ b9 @) }$ c* l
B. 有向无环图
6 m# E; Y' H& I( P* G2 w' [; W5 YC. 9 j" P% P! g% Y' y3 u' T- {
D.
+ A2 V6 M9 a# Q; }6 j9 g 满分：5 分# z3 W( J- F0 l& C9 g+ g
10. n个顶点的有向完全图中含有向边的数目最多为
) s; q4 L9 b" i3 A4 i* EA. n-1
7 u9 M0 b2 R7 Q3 ]; aB. n
1 S* V! R' x% v+ I& x6 F: e, l! ?, I% Q; qC. n(n-1)/2
- |& a1 N. {+ R. BD. n(n-1)* X3 l. X2 |! e
满分：5 分6 K0 J/ V7 V: {' q
11. 无向图中一个顶点的度是指图中
% p6 \6 _/ @2 @$ l- \A. 通过该顶点的简单路径数4 C7 S3 {& O j! w9 n
B. 与该顶点相邻接的顶点数
1 R* f/ w% V. k' \& OC. 通过该顶点的回路数
6 a- [9 U6 _6 l8 W0 gD. 与该顶点连通的顶点数, q& O% C- T/ y
满分：5 分
@# }6 V" v, c3 U2 u12. 一棵树高为K的完全二叉树至少的结点是- Y+ i5 F& B& x/ E7 P7 \
A. 2k –1
6 j' p5 d9 y) @/ F" DB. 2k-1 –1
$ a# g: Y, x B1 J* k6 B# Y) WC. 2k-1
4 _7 a( ^' O* mD. 2k6 e3 u0 t! V" E7 C+ T
满分：5 分) ~# v4 }" E3 ?& O) E& I' F
13. 下列陈述中正确的是' Z/ l6 s: `( q
A. 二叉树是度为2的有序树
$ D5 K$ ?5 T. P4 ^) @6 j* wB. .二叉树中最多只有两棵子树，并且有左右之分; z- [, q9 L4 Q0 P& C
C.
7 n& W- w( ]- X# \D. 5 ?+ @; E l$ i% Y) q
满分：5 分
3 |& S( U# L0 S7 g6 I0 G+ h9 f14. n个顶点的强连通图中至少含有
4 j6 [' @2 k: J oA. n-1条有向边( U& u0 r ~4 e+ t. n6 |) L5 k
B. n条有向边
5 [0 I T* ?" h3 X) tC. - p; t" h( [5 E$ D; T1 D
D. 0 k3 T' O6 r4 _# M L
满分：5 分5 U5 f( ~ X: e' {+ o
15. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在
( ]7 B' C/ y2 ~5 N: xA. BT[i/2]
' e8 W3 m" B! }& h: JB. BT[2*i+1]
9 R5 w/ U+ l, d2 |* G9 x8 OC. 3 _4 y8 ^0 e. ]3 i/ ^" A
D.
. `3 ~; I) @4 R- n; P4 L 满分：5 分3 E, f. {- V+ ]1 _5 M7 Z
16. 树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是, A# y6 ^2 A* b/ G; `# i
A. 树的后根遍历与其对应的二叉树的后根遍历相同: j: i2 ~- G) F: e* `
B. 树的后根遍历与其对应的二叉树的中根遍历相同3 v5 L6 e. U- `% W$ H
C.
: S" V3 ~& W6 F& { ZD.
* @3 }3 ^6 s, Q4 d9 ?3 I" b% N 满分：5 分
1 V' j: k0 v8 i7 k- Z5 F; U17. 深度为h的满m叉树的第k层的结点(1=<k=<h)数有
% o0 C* f& P _/ bA. mk-1) J* F& K& G2 g! E2 @3 ?0 e
B. mk-1
* p! S4 s* V# R: ]* K$ @5 dC.
0 |; \5 I6 l. ]1 Y) R8 S4 X9 xD.
* K, j0 Y! y1 c 满分：5 分0 ~9 O0 i* b1 a4 @2 a6 N/ @
18. 队列和栈的主要区别是
: D' @4 R; q3 H! BA. 逻辑结构不同- p- G9 X: X4 e" U% @
B. 存储结构不同
9 H2 C/ Q/ F4 l, NC. 所包含的运算个数不同
" ?9 L# e. l$ c! _' UD. 限定插入和删除的位置不同
! z$ T5 F: _ I( b4 ^7 g* f" o: G 满分：5 分
3 ^- F5 y3 i4 _$ _- O7 J19. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是
, D X# L- a$ L* _A. (rear+1) MOD n=front, V. E. S l5 A2 [+ B/ I. K, S
B. rear=front" B8 V2 L6 \. d
C. rear+1=front
) `; B- Q9 H: ?7 ~2 _D. (rear-l) MOD n=front
$ z, t2 i5 z l 满分：5 分. U- L" h2 r2 V( `
20. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为
- L% k. j- R8 O9 aA. Dout
! m- t8 M5 I; k6 r* b; l1 pB. Dout-1
6 G' t* t& Q" ^5 LC. 9 E! M! P- c) R- Q7 Z7 h" d1 v
D. # z, k( b; o9 u/ V) k7 {
满分：5 分
) W7 ~# _, ?9 |$ X* m+ @8 Q) n: l1 J6 n$ u
需要满分标准资料请直接加QQ :1306998094 |
|
IP卡
狗仔卡
发表于 2011-9-30 18:19:33
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
