|
|
一、单选题（共 20 道试题，共 40 分。）V 1. 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
5 x: g* w! ] [) j4 `( hA. 从小到大排列好的+ `8 n2 z0 e/ |/ [+ M- {3 |
B. 从大到小排列好的
- a$ A4 P' a' C- B, Z, X. I( ]C. 元素无序
5 V! J, s! h) m1 zD. 元素基本有序5 m; B' h* p7 L# X5 B) b& F8 W
满分：2 分
: [3 X) o( s! X! Y2. 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为" ~8 J) k# }1 ]+ ~/ h
A. r－f. l/ Q M7 p9 _
B. （n＋f－r）% n
; \* W4 F0 d, X& c/ N$ g: cC. n＋r－f3 `) ]* V& F2 S! j
D. （n＋r－f）% n
5 l/ o6 C6 A' I3 P 满分：2 分8 {" c- a! Z; G* O- ], s2 J
3. 任何一个无向连通图的最小生成树(); Z% @8 B6 Y+ e; l
A. 只有一棵
6 M, c B* C& U( SB. 一棵或多棵3 F5 \# g/ C' Z( ]
C. 一定有多棵
0 T4 i* H2 @; u. b: T( q+ oD. 可能不存在' f# r$ ~2 e7 q0 e
满分：2 分8 }, A5 H5 t& @! W. g) b
4. 链表适用于()查找$ y8 f6 |/ `1 Z" d! m, k: h
A. 顺序
+ w- \5 E2 O$ Q) r2 j% Z2 Z! sB. 二分法8 C; M/ ^( i& Y& u1 T
C. 顺序，也能二分法' o+ w Z; H; c
D. 随机' l; V0 W8 a4 R( Z6 A* i. g
满分：2 分
1 ]4 L8 o' V8 ]1 O6 U+ J$ X5. 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为()$ g. U- Q d3 K7 ?# q- w
A. n+1
0 ?% X2 t* K; U+ r3 n5 O5 q+ D4 u* TB. n. D3 j9 ]' [) i' y( W7 Z
C. n-1# P9 o5 o' @! I3 c
D. n(n-1)/2# G, N8 m% g* O. }, s
满分：2 分
+ G( a0 B. J" Y1 e4 ]6 |0 L6. 线性表Ｌ在（）情况下适用于使用链式结构实现。
% g) `( W2 g% n" [& d* ~/ _& n3 ?A. 需经常修改Ｌ中的结点值
, Q8 L; K# @- R" _. I; Z" VB. 需不断对Ｌ进行删除插入7 G0 C+ v& Y' D) w7 q( }/ W7 U! l
C. Ｌ中含有大量的结点) B* t8 U/ q& D) Z- r" K9 _4 ^
D. Ｌ中结点结构复杂0 g/ q" C3 q3 ]" t. m+ Q8 T9 t
满分：2 分
3 k- o: f. x3 w9 o7. - h |% G7 e! o7 C; |; P* J
已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
9 w9 G0 X" |/ B+ D2 X& Q
$ J7 m/ L- e1 _' W/ ]* {# v# x8 c7 S7 \4 U0 A: ?% {! t
- j6 g f, w; e1 ]2 zA. ! {$ [1 Q% F9 e4 S
0 1 3 2
H [: S( s2 M, z1 oB. % T2 ^- X" _' ~6 f, k# j
0 2 3 1 k2 d x2 _( m# a/ w
C. % L4 J) A1 l7 A% R# e
0 3 2 1
, S' j/ o9 y3 X8 p5 b2 _1 oD.
1 Z# i `8 E/ J& j2 a# U3 ?' j0 1 2 35 {% S- A$ Y" d9 C$ A
满分：2 分
2 x, r, e4 W: C8. 用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
" ^3 b$ g9 D4 p0 JA. 栈$ j b d# w+ _1 g5 \
B. 队列# m/ I8 K% ?5 C( q, g
C. 树
" P4 ]- O- u$ W! O' \ ] P" FD. 图9 {) R0 n4 [: d h
满分：2 分
7 h% v) C- C3 g9. : x" C6 P/ N6 c9 ^+ H2 W# i6 p
设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
, j5 q) K; x, {
* A' q' e$ k6 b( `
3 [ l# f. t% t- n* j5 n! L1 E, o! G
- b1 E8 ]2 u$ B4 g9 I! P2 sA. 循环链表
" L+ h8 ?& g. @* w4 J9 Y0 N- \4 y* UB. 单链表
4 c2 H' Q& _0 l, i! w& J6 S0 WC. 双向循环链表
7 z- j Y! S+ ?/ J t& TD. 双向链表" I4 C& [# h* y( ?# C9 K! A# e
满分：2 分4 D2 K$ h2 `9 a* Z5 N7 s1 a4 K/ @/ G
10. 快速排序在下列哪种情况下最易发挥其长处()
. M: Y" H* h+ y0 }/ b3 T- f7 G" dA. 被排序的数据中含有多个相同排序码
6 l* o" `1 r+ y" m& w6 t7 aB. 被排序的数据已基本有序- i8 ]; r, m i: D
C. 被排序的数据完全无序
8 N4 i: A6 \6 C( e% ~/ v- _D. 被排序的数据中的最大值和最小值相差悬殊
! \4 a2 a' a9 Y9 v4 B! a% y1 C$ \ 满分：2 分' }7 ^" ?, a3 S/ ?' y& A# S5 _
11. 6 _% M1 {) I5 q6 e1 e1 q$ X
已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
2 k$ h7 P$ Q8 B0 d3 V- {% a4 Y8 {0 }. s3 B+ k* O! o( g$ C/ {
/ B# ~6 Q# ]; J' |3 e# W6 z5 E: ?! x
A. 0 3 2 1 $ y' N; w! g9 v1 q
B. 0 1 2 36 G( E6 L1 ]5 o) X1 c0 j
C. 0 1 3 26 h( c, J% t/ F- i+ j+ h7 x+ d
D. 0 3 1 2
6 {1 H9 ?+ G8 o1 y- \ 满分：2 分
# Z* Y2 P2 M' |6 e$ x12. 有8个结点的有向完全图有（）条边" g, U6 q1 q' T2 R- x* W* S
A. 143 T! y( w% a5 S& x+ r
B. 28
M& T1 `* `" K0 @( S+ @ J* t+ R* j5 |C. 56 L* `( @1 o' c+ a
D. 112$ h$ R1 e% u2 u6 W
满分：2 分
; X9 w/ B* \, d8 h) h: }, X: q* H13. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。1 q# M, m; a( H' B M
A. 3
: D, T; t- W' {6 SB. 4
: }" L1 S& i0 p1 u4 m) FC. 5& k2 v9 A" Q, z n" a$ |" j8 h( F
D. 6
1 s3 M* }1 m. ?7 @2 p. ]: Z 满分：2 分6 c% d' V8 @ p4 a& Q
14. 用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的6 x5 p! w2 _; Y7 k
A. 栈
4 J T' D( b H8 W8 HB. 队列# X% s" W$ o& u
C. 树
' b9 U% [5 J' Y( `3 B; ~D. 图7 K2 M. V; R0 [- q# v2 E! L
满分：2 分 u1 m, f& Q+ G3 b9 D9 f
15. 堆是一种()排序。
0 u; }2 h- ]" ]! IA. 插入- |7 B* [8 E- J6 A$ L
B. 选择7 w) u- J$ v$ ?) l
C. 交换0 n3 H( ~+ Z; z! K
D. 归并
3 h# U" ]3 |* V' A( Q, B F/ i 满分：2 分
8 D, Q# @0 v$ B9 T& Y! t16. 链表是一种采用 存储结构存储的线性表# r7 M4 I: T5 L3 g' \( N# v
A. 顺序
) \: O8 D8 L. E% k( M1 yB. 链式8 y2 x) M1 _- }+ ~5 n" { {
C. 星式! r1 b4 ?. C* {3 y* n8 F2 i* I4 T
D. 网状
6 P C1 D1 i5 j8 R 满分：2 分5 D# ]0 D8 {& b% J7 \6 y$ K+ v
17. 广度优先遍历类似于二叉树的()
& Q" k/ {; i* t; VA. 先序遍历* s* `, P2 k7 x+ @4 q+ h8 Y- P
B. 中序遍历6 X- [$ X' v$ B! ^+ e
C. 后序遍历1 M1 P2 T' o+ U
D. 层次遍历3 r+ `) g0 B. O K/ p! ]1 e& H2 |
满分：2 分
- X& P+ a7 D) \2 c" a( M18. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
) t2 e) E2 q6 G" K7 V* iA. 20，70，30，50$ v- a4 R' _- M/ w
B. 30，88，70，50
`; @5 Q I8 i( \4 r+ _ VC. 20，50% m' f3 F/ x- C
D. 30，88，505 e6 q6 Q; d5 L. t6 h
满分：2 分
/ n6 d$ g) s9 Q! Z0 ]3 b2 Q19. 判定一个栈ST（最多元素为m0）为空的条件是（）
2 Y+ o; {1 [! J. o$ XA. ST->top<>0
# Q- y7 a# y( G& SB. ST->top=0
2 ~+ K3 A3 C- S, q [8 f8 KC. ST->top<>m0) s, [% O2 I- H. G
D. ST->top=m0
% C4 j7 R# ~" h# u 满分：2 分4 i3 J) ?6 D d# ?
20. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（）! F1 K1 b; e1 i( ^! r9 P. {
A. BCDEF/ L& a4 @- P3 a8 T6 R
B. BCDEFG
U( C y$ c/ w8 |% T; s5 _C. BCPQRST
7 z4 `; _+ y1 w! bD. BCDEFEF
) M3 `* k9 _$ t. U 满分：2 分
$ V s! X* {8 q+ w: @+ D% l' B% G/ X8 v9 C
二、判断题（共 30 道试题，共 60 分。）V 1. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。7 F9 c- B4 X. ]: t
A. 错误
4 n5 i1 l) B, xB. 正确1 R+ C" f1 d/ L4 \
满分：2 分
( N R9 O8 H/ J8 H* s, {9 m2. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
5 f% g) t& Z9 b/ M' LA. 错误
$ T9 l! V' N$ o; [B. 正确; z; u& I) z8 M% c! I6 ^
满分：2 分
5 I$ O. F6 Y4 Y- Q3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
- j2 C) _. L; n: pA. 错误3 B" z$ f* k+ \7 N7 }( ?' w) N8 z
B. 正确
) {+ h# k3 f4 [ g9 l1 O7 s, ~" I } 满分：2 分! e" O- M7 Q/ p( e1 M. r$ `/ }
4. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。# w# V4 N6 k8 f0 B
A. 错误
3 ]. b: @+ B/ _) uB. 正确6 M" b: v+ k$ M& X% Z4 c
满分：2 分. \ X1 _. M( E
5. 二叉树中每个结点的两棵子树是有序的。
4 a A6 |7 B, I- U0 @A. 错误! i Z( g* p# L. K
B. 正确0 Y5 h0 \4 X2 }' b- T
满分：2 分
) O% Y" j+ \& o* l9 U: ]/ B$ X6. 二叉树中每个结点有两棵非空子树或有两棵空子树。
, M" u6 V1 Y3 `A. 错误) C! f& B1 N8 n. X o- \
B. 正确
: M- a( i0 d! k3 q( W: O 满分：2 分
) G' f4 ~' a1 h# Q7. 栈和链表是两种不同的数据结构。
0 r6 P2 K6 ~7 U/ w2 U5 \A. 错误
, ` ?: w7 J) N; a9 e3 m9 u/ h( YB. 正确6 c6 z9 o6 b- g6 v' h+ S- d, D
满分：2 分
% L6 V5 Y- ?3 i" q3 ^8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。& v6 o& y! ^. P1 G
A. 错误/ n5 f! W n5 @3 l% |0 \
B. 正确, L. \* y3 Z: x6 M, ?5 I% e% E
满分：2 分
9 L/ j4 ^2 f9 n: M2 j4 z' ?9. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。, p# Z5 T0 f- T3 C
A. 错误( k) x9 Y. R, Y& T1 V' [! e5 l
B. 正确
c( ?6 v; \0 q: J7 h7 B4 ~! y2 j 满分：2 分) g$ ~7 r' f* `# N# u+ d
10. 线性表的逻辑顺序与存储顺序总是一致的。$ [- Q6 l0 o0 g
A. 错误
: G$ _# T4 D7 I3 p% j* z& q* {B. 正确4 K0 S0 \8 L* ?0 O/ o. e/ Y8 L
满分：2 分
2 w! [2 L% d9 A( C+ ~1 E/ c11. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
X7 k3 {* ?7 H* Z4 U; F% LA. 错误
0 ?- K( F7 d+ _' o9 yB. 正确( ]+ H' U( `0 Y2 c3 @! E; L
满分：2 分5 r/ S) s% c0 ~" h0 d
12. 在表结构中最常用的是线性表，栈和队列不太常用。( e' `& B/ x$ { F& ~
A. 错误3 N G' C; d1 z) b6 B/ {" v* W! u
B. 正确" `8 `: [: ?0 }2 q0 a+ c. }
满分：2 分
: N8 j% Q6 q5 x+ _6 c2 M13. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。; _3 x9 Z: g8 ?" }7 k% n0 }
A. 错误
# X/ e" `( V! h' y, q5 b0 E3 g5 A, ]B. 正确: Q, C" f$ _* R; f/ I6 w6 |* j
满分：2 分
; x2 E- r9 H9 Q14. 栈和队列是一种非线性数据结构。
2 m: N: l. x2 e7 fA. 错误! T. b0 H4 ~6 e7 ^( |! J
B. 正确
8 ~1 m# S) w+ F( R: x4 v7 X 满分：2 分
: O* g( y2 t- w* `/ `3 _+ u: i15. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
4 O" E0 q, `( AA. 错误" J( Y# r( x! e: q9 x
B. 正确% Z" [ j/ z6 O! ^, K% W$ G! k
满分：2 分# ~8 q+ @! @4 `
16. 具有12个结点的完全二叉树有5个度为2的结点。. r) x( e+ Z# ~/ v, I
A. 错误5 ~! i; B+ Q; b3 p* x
B. 正确
# M \: G+ B/ J3 q1 ~$ U& P& d6 M' F 满分：2 分
8 y6 r: a3 Q+ t, P$ f; q, O1 P17. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。
P* ?/ \! |5 w6 NA. 错误8 D, \3 t" v3 y" B1 s4 w
B. 正确: ] ]5 B3 k, }& j
满分：2 分
% F K1 J+ G5 |9 G6 z9 y: s7 {18. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
7 i! V4 N+ o2 ]$ d8 G$ OA. 错误
7 x1 r1 Z! X- E4 ]; s+ WB. 正确) b. g' r6 R- z+ I8 N0 F) X* q
满分：2 分' j0 f! `7 |/ _' I6 y# u' ?% X0 p
19. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。7 l6 k6 N2 e" C: ~4 k% d+ Y3 h
A. 错误
H/ C9 [! m# MB. 正确
6 [+ {, d; B* X! M6 k. I 满分：2 分
' P5 [- l, N6 x) k2 z6 u) K# R( l+ K6 J20. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
+ i/ y/ u4 A, n% Y" }A. 错误 B6 {, ^7 w% {
B. 正确/ \' Q7 M* V: H6 ^9 E+ L6 K
满分：2 分. R% a! ?% n$ y) ~* o
21. 栈和队列的存储方式既可是顺序方式，也可是链接方式。: ?) n% I2 N5 w* d
A. 错误4 [' t# l } n1 }* e' p
B. 正确3 f: L: m' Z7 @. X. @' @
满分：2 分
! E/ U- J# @$ f$ v1 l) g22. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
7 z$ S7 ^- ?: e$ m: o3 y* QA. 错误
2 `0 d! C7 `3 F& o( `B. 正确
* f9 z! ?) K2 U5 _4 p. \ ~- d 满分：2 分
5 `. c9 f7 [: c% U2 S' y23. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。+ J2 q% w( r$ S( _
A. 错误3 `0 V" {5 b* T% I E
B. 正确
: `6 m: ^ k+ c* p( l9 {4 z8 ?9 U 满分：2 分6 E8 x5 X, R8 J4 R0 w
24. 链表的物理存储结构具有同链表一样的顺序。- q( T3 [' `2 B+ V6 J
A. 错误
9 l5 E5 N: r) }( a% W; O9 w- g, uB. 正确
! ~/ \2 \3 d/ `& K 满分：2 分" Y; X" v# @/ O, B5 q( g5 d
25. 二叉树中每个结点的两棵子树的高度差等于1。
9 s8 y( h/ O/ y" c' nA. 错误! }; n4 t7 g3 b& d
B. 正确
+ `0 M# `, n. q, Z 满分：2 分- }/ ?7 m7 I/ G
26. 顺序存储方式只能用于存储线性结构。
, q& ?: T3 V: d, ?( R" \A. 错误
2 c# |: d' M9 pB. 正确
8 N* j4 x c6 @/ V* J0 H6 \ 满分：2 分9 a9 L' D. c- m* i) W9 t: u
27. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。9 z; R; g0 N* v6 g1 k
A. 错误
; Z) l f/ o" Q9 m; ]1 Y: \B. 正确7 ?, g: o3 i5 v/ D) y
满分：2 分
. v S, g. H# E, [8 k& h* d" U28. 链表的每个结点中都恰好包含一个指针。
# E4 S1 ?6 t% d# l( Y6 G9 ]: |2 q& jA. 错误
' a3 C0 I: w1 X- F8 f/ M" }2 k% LB. 正确4 r, m1 u# ^( o: v! C
满分：2 分4 d3 B) W7 j, Y$ P# R
29. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表' P, g/ Y. V7 w0 Q. W0 L; o6 q7 R7 N
A. 错误. M8 {/ p# T* M+ k1 T, ?
B. 正确
3 G) ]/ {' G" F 满分：2 分9 Z- g& n# \( N; i U% j
30. 线性表在物理存储空间中也一定是连续的。, _6 D a3 C$ s
A. 错误
" L& i7 [& W5 e) kB. 正确
8 n( A ]0 s# u 满分：2 分
( ?4 s9 b0 S1 r8 O. e2 Z" t- w, ?; L1 e' N9 d) Z5 |, @/ Q5 e
|
|
IP卡
狗仔卡
发表于 2012-11-16 09:29:35
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
