|
|
一、单选题（共 25 道试题，共 50 分。）V 1. 若要求尽可能快地对序列进行稳定的排序，则应选（ ）* {5 A8 l' i% s1 D# f
A. 快速排序
" ]; p- c% V& Q L, O9 {B. 归并排序
+ ], [3 N" y) V k) x; H' W( z. S5 NC. 冒泡排序2 D" f$ j1 }- F
D. 堆* f2 {7 w$ s- L `6 _
满分：2 分
, G1 Z/ u) J$ M8 |2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）
6 n y: ]7 T* m5 b1 f9 qA. （N+1）/20 Z. Z6 ?" {3 A7 B3 }2 p) o( k
B. N/2
$ v: F& h# E' Y+ c0 ]C. N. `3 l/ ~$ g- x2 K
D. [（1+N）*N ]/2
6 |' q* C, J2 K( C6 J8 @! Y' ] 满分：2 分! w2 c! d: J, g% S
3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）0 N( q6 y) g/ L: P
A. 9. \; d) f3 _$ i) g
B. 11
, e" ]& ?& }1 p! x, i1 SC. 15
( l# y1 ^1 h9 B# `D. 不确定
$ K9 |: d+ Z/ C; _ 满分：2 分! o/ n* ?4 q* z! x3 q3 G
4. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）0 d$ a2 @ S$ `: C3 I" ?
A. 55
8 l$ g! Z& C3 o* P3 B- g. d) m/ Q iB. 45( j3 A G( }/ I/ z! y0 ?% `
C. 36
/ o E) u; m8 @9 SD. 16
( S, H$ D& A: p/ s2 t5 J 满分：2 分7 l/ J+ w7 S- j; _8 I5 H6 M
5. 线性表是具有n个（ ）的有限序列。3 U1 }" x+ x- k) F' D2 u
A. 表元素
3 R W- C( n" i1 s3 iB. 字符& D0 k* C* ~" U; c
C. 数据元素3 v7 L" j1 h+ u" n- y7 _: n
D. 数据项
2 v6 Q8 ` l: I6 C( B/ _ 满分：2 分
3 v- {. j- ?, L X7 M6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
0 D( M* }3 c8 V# rA. m-n1 o* b! D6 r/ a
B. m-n-1( ~5 `) b4 l+ A2 ?% n) G" r, z ?
C. n+1
6 i- |& ?' A+ k# @D. 条件不足，无法确定
- ^: Y1 U( C$ O# s" k- k- H 满分：2 分
# }0 w& J$ O4 X7 _7. 在下列存储形式中，哪一个不是树的存储形式（ ）. w/ r% B8 ~! Q& N/ x
A. 双亲表示法
9 N: b4 B; L6 M' ^1 dB. 孩子链表表示法* B/ @0 }- N' b- G/ p
C. 孩子兄弟表示法" S% D$ N, T2 Z, h+ D! q! v4 d2 f
D. 顺序存储表示法5 R6 \7 K2 V5 v4 e+ g" p
满分：2 分* O7 [6 s& U3 V! p
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
S! s4 T; w" C! \( LA. O(0). T- f' x7 e4 P( Q
B. O(1)8 R. _: B7 h1 Z3 s: f
C. O(n)4 W' x! ^1 F2 s5 h' z2 k
D. O(n2)
- P: m+ b! x: o% E 满分：2 分) C4 ]4 d9 ~* e
9. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
6 b6 n) r K7 ^% Z* jA. 82 W& [ K/ ~) F3 Q4 O
B. 9- X- b d; q% U3 B
C. 10/ K% b6 d ~4 H* H- A3 [
D. ll
% U% K" F0 x$ z; x' \; F" k1 U 满分：2 分
7 ^, V: }( D5 O8 }10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
7 d( Y9 E; c. t1 r$ `A. 线性表的顺序存储结构3 x% c* m0 |6 i% j/ A' ~1 d. [! Z9 n
B. 队列
) n! ]2 W1 f$ g% M& VC. 线性表的链式存储结构4 i+ t% E& Q; P, I5 F. v
D. 栈: ^; G9 a+ I$ F7 M F
满分：2 分
9 o" F# [ F9 g% n2 E3 n11. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
7 a* ?( H4 Y. C5 ?A. 求子串
- b' W% F; g0 b& H# Z/ F% oB. 联接
: ^5 P) n* H: U$ X- ^& tC. 匹配/ Z% V! J3 ]5 J( |
D. 求串长
( s& d+ F/ J& R% Q 满分：2 分/ Z1 Q4 j5 e! Z1 d
12. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
; q! q8 w" k( S# e* hA. 插入* G a; x+ h/ e$ Z3 b' w
B. 选择
: |* T8 V4 g! L% `, f* v* S( d; @C. 希尔- V6 g# d8 F) G* M( A
D. 二路归并
( v. p; n/ y W 满分：2 分
8 j$ \7 \8 p, y' }2 g$ D9 r& M9 k13. 若串S=’software’,其子串的数目是（ ）& {- L* R) E3 R \$ j% |' ^' { y
A. 8
; E" G: ^5 J! D# C# o9 lB. 37
# T/ F$ x! Z. J( @& r6 V: N1 lC. 36: X1 C9 B2 V4 ]7 [
D. 9) I7 ]2 _( k' O) {& z
满分：2 分( ]: y9 A6 {5 ~8 f# p# I
14. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）* g- \ v7 _3 ^/ m: X+ g
A. (rear+1) MOD n=front
! c/ |( H. J9 K0 H) S5 m$ |2 pB. rear=front
0 o/ [3 g, y& i* zC. rear+1=front
/ g$ O5 ^1 Q. x P7 @9 H! A3 X5 kD. (rear-l) MOD n=front
1 _4 B. c5 }4 x3 `5 c n 满分：2 分5 H0 x. T/ w4 m5 g5 i( i3 U& @1 P
15. 从逻辑上可以把数据结构分为（ ）两大类( J/ |" N' X4 o, ~
A. 动态结构、静态结构2 a" K/ `0 }* P8 z& d
B. 顺序结构、链式结构
7 E- \$ n2 E4 b5 e4 v( VC. 线性结构、非线性结构- k" ^1 C/ X* ~3 y0 D& v5 N
D. 初等结构、构造型结构
: j% W: j4 Y& Z7 z/ } 满分：2 分
" c/ R; u' j y4 i- y3 ?16. 有n个叶子的哈夫曼树的结点总数为（ ）1 ^& Q7 G' [- U$ ^( i$ B5 o
A. 不确定
4 S0 k& q7 M+ \ x' u& qB. 2n' `+ J u: B1 `
C. 2n+1& M# r. {4 g5 Q4 E' ^' o6 Z) X
D. 2n-1* ], g% G1 A6 f& B8 f; x' b7 _
满分：2 分
5 f0 B# E' E q. o5 T17. 一个递归算法必须包括（ ）1 Z2 ^) m4 y8 D$ j0 {8 \9 \8 K
A. 递归部分/ ~- ]3 ~& c6 K& F0 x% n+ C
B. 终止条件和递归部分
& u! b6 X* u5 g; }6 t7 kC. 迭代部分
9 i: B. b/ ^. L3 s$ Z1 G8 S. c4 dD. 终止条件和迭代部分$ C. ?1 A' N- O; s$ }! T& E A
满分：2 分
: g) d6 I, d N& v f& m/ V18. 在完全二叉树中，若一个结点是叶结点，则它没（ ）8 U& B: W8 P6 ^0 O v% k* C
A. 左子结点
0 a! ~ y" ]2 O2 h; f5 iB. 右子结点' p2 J# l h L
C. 左子结点和右子结点
+ g' g! Y/ U0 [( Q4 I1 t% WD. 左子结点，右子结点和兄弟结点; Y. V( J( [# [6 Z4 R8 R% W# F
满分：2 分4 L# \6 P/ R3 `" P" Y- o# O8 a
19. 下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;+ X8 ]1 M# l: M. g6 u/ H
A. O(2n)
0 y& B0 O: z; L1 _ Z( AB. O(n)
* f% q+ M( e1 c$ F2 r0 j+ N8 cC. O(n2). V7 A& d2 b* D% K1 ?
D. O(log2n)# @$ {1 k1 v' I
满分：2 分
% I0 @/ c( q0 P: g I0 Z( X20. 下列排序算法中，占用辅助空间最多的是（ ）' B' ]0 C" [, k
A. 归并排序7 h F w" D5 H! T( G
B. 快速排序8 m0 Q! d5 l- A+ n" v, d
C. 希尔排序
7 b0 t& U* h' L* UD. 堆排序
% V% [/ |- [0 o* t6 R, n 满分：2 分
1 j% @8 ~9 F7 C. S* Z21. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）0 x. E+ @1 }8 e% a. Z% C. @* H
A. O（i）* k; S6 w# o$ u/ @) T( `
B. O（1）6 K. g' h( F6 A0 r
C. O（n）8 A4 _- ~6 x1 U# ?1 o3 l; Q! M
D. O（i-1）8 a3 W# @) @- n8 k
满分：2 分3 J: e+ p# n b+ k3 v
22. 设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
. o0 F& H8 I- C& o" ]# F1 oA. 不确定9 Z6 R( c; D9 X6 g i- W6 J/ n
B. 2n9 K+ ~: z. I# E7 [
C. 2n+1
, R) N9 M6 z; q* P" F# p8 AD. 2n-1
: W" S1 N! e4 j h( B6 } 满分：2 分5 q: a, G+ U4 i
23. 链表不具有的特点是（ ）
& P/ R! ^3 c! a; hA. 插入、删除不需要移动元素
: S5 [5 F9 i6 N7 i* bB. 可随机访问任一元素
d/ U$ u- S0 l" AC. 不必事先估计存储空间
- N! S1 u. X1 f. K. i6 [D. 所需空间与线性长度成正比/ A2 @( {. k' g
满分：2 分- [( N, F- r$ ]) H* @
24. 适用于折半查找的表的存储方式及元素排列要求为（ ）
- z( n- P% x M7 pA. 链接方式存储，元素无序 V; n* H* N: j# ]- Z$ ?- M7 m* R. i
B. 链接方式存储，元素有序1 a$ w1 r+ w' }! R
C. 顺序方式存储，元素无序
% R o3 r3 x8 kD. 顺序方式存储，元素有序
6 S8 U% Y U( I' R- X+ S 满分：2 分6 D3 O( s/ x% \' x* J
25. 就平均性能而言，目前最好的内部排序方法是（ ）排序法。
) l" F4 ]9 Q& f, g3 E8 b3 UA. 冒泡 r# X6 [- C& H: q
B. 希尔插入/ b; |2 \- V- n( _3 R6 w* Y
C. 交换- q4 N2 N/ s, _2 M; {
D. 快速) I3 E$ z8 D2 o J j9 N
满分：2 分 : k7 ?9 c9 ^: a V' b0 N
4 Y( h9 }6 E' r$ z+ f! f9 c: z( E9 F1 i二、判断题（共 20 道试题，共 40 分。）V 1. 算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
6 K2 e1 |: C/ |% }A. 错误
& ]% L m3 [) u! |# hB. 正确$ x' ]/ W6 X. @& n( f; r# }& u9 }
满分：2 分
g: s5 l+ F4 }" `- Q2. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。) {* ~0 S, i" W" d7 z1 o7 m
A. 错误( D0 q0 T5 | q
B. 正确
: V7 P y0 f, b8 ?5 ~5 Q 满分：2 分/ s' ~4 q4 ]; X/ R: E4 Z* L- f
3. 通常使用队列来处理函数或过程的调用（ ）
$ o+ F& e4 H& b* S4 ]8 N. ?A. 错误
# _6 o4 D8 r" k& ~ w3 ~# y" TB. 正确& c9 }: O# \3 ?7 `
满分：2 分
2 x0 r( K$ `' W( n j, e+ R$ \ A4. 顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）( }7 G4 }; A, `' Y# z5 q; D6 D; T
A. 错误 p. r/ {: O$ P$ \* x
B. 正确- ?3 d6 }4 X) X# w8 q
满分：2 分% @$ Z3 N1 p2 _* h) J* u" H
5. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
9 U" }2 Z' p5 C5 i6 z) ZA. 错误. y$ y" P U3 W+ n
B. 正确, F5 `( o5 `; F8 ^
满分：2 分
) r6 q% r0 b! {2 C7 b2 g) |6. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。5 E% n$ ^4 {0 ]9 G0 ?
A. 错误
% u4 X* O8 f* CB. 正确6 C$ B8 v4 {2 Z0 b8 {) D
满分：2 分
1 H5 x1 ]# M* ]# p8 G! n7. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）4 u( F/ n& L/ a [
A. 错误
, |0 ], I$ p3 v$ o6 O8 U$ AB. 正确
- a8 x( K9 o1 [' @+ g. I 满分：2 分
( G% o) Q4 u' K% W9 z. h* M8. 栈和队列都是限制存取点的线性结构（ ）
9 B" V* @% a( x WA. 错误
! t% ?) B" H: \1 N: IB. 正确, F1 G: g3 e/ O+ U7 m# G" z' d
满分：2 分1 c1 D0 P8 |% x0 D3 D! q5 z; q' ?
9. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）0 E- V- I M( Z+ v @' Y5 ]
A. 错误; E7 p: ^3 L; H( K* j: ?9 q
B. 正确
. }/ K v9 R2 U8 W( v6 E 满分：2 分
- V; W1 h+ Y& H: m. L3 w10. 排序算法中的比较次数与初始元素序列的排列无关（ ）
5 @# z0 d/ P- y/ [$ {A. 错误
3 b7 b- f5 _9 F0 T+ W% t8 K2 IB. 正确/ u4 H \! u! J4 U0 |) V4 a* m
满分：2 分! {% I4 ~- R7 B* s- W& K6 ?) K
11. 顺序存储方式只能用于存储线性结构（ ）
/ l% t3 N2 c6 q% f& {A. 错误
, g& v/ j q6 ?. M& Z$ XB. 正确
2 I4 Y, c; h" ?/ y! _2 g# G6 ^ 满分：2 分" Y+ p' Q, I: Z' r
12. 循环队列通常用指针来实现队列的头尾相接（ ）) a% J; |9 @. H& L3 e+ i" q' y
A. 错误" K0 |5 u* ^+ v
B. 正确
) S* c, P9 ]. s) x) n/ {' W 满分：2 分$ p* Q3 f% J1 {7 _1 S3 g! Y- z* P
13. 二叉树的遍历结果不是唯一的（ ）% Q( K; V4 C" a8 Y* h2 h, m: Q
A. 错误4 b6 _4 w6 x5 |
B. 正确
) _0 d9 n, w/ R4 J: Z! ]5 _ 满分：2 分# Z2 f' Q; s% P6 {8 x
14. 对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
1 R: M+ {+ O. \( \ vA. 错误0 \" p! r* y5 v$ R% \8 d- B/ Y" `
B. 正确9 j. J, ]% F' @. T; q
满分：2 分
1 T& o5 j* }7 l ^7 E, T15. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）; j# ?/ g! [( [
A. 错误' N& U& ?7 w" T* Z9 i
B. 正确
- l: I* b& g3 `1 \- g- r: L 满分：2 分
$ [7 S& C9 Y' m2 |0 D6 f' `1 A3 B16. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）! g. Y; ~& G3 G8 o, z
A. 错误9 a+ c- E1 a8 ~/ L
B. 正确' o6 _( a8 X" Y' ^1 |3 l
满分：2 分
3 ]; P1 P: C+ ] S- R5 K- s17. 在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
% R" {3 z, `" z5 W6 \' |9 ]A. 错误
- ^5 Q+ R9 I5 ?, W) iB. 正确6 T( u( F5 Q3 `& N. @
满分：2 分9 k* z; _$ q( {! X9 {+ E
18. 若一个广义表的表头为空表，则此广义表亦为空表（ ）
Q# `6 I" T% C- c* y0 pA. 错误
4 D/ K$ j4 ?2 C) W; q9 L1 EB. 正确( d! C. ^$ J7 D, b, ?, B8 J
满分：2 分" T/ X7 e" q) R$ ^0 M4 v7 T+ k# `% N
19. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）5 Q. t$ d% O9 V7 V3 S4 u) W" L
A. 错误- [" r# a" [7 H4 V* v- N4 I
B. 正确: B! p+ G! b1 @
满分：2 分
8 a$ {# X( ~) v4 U20. 内部排序要求数据一定要以顺序方式存储（ ）- O2 z% h2 Y. g3 N& y' _2 M
A. 错误
8 c0 s0 _; P7 ]3 D5 |; l4 LB. 正确
4 _% ?( ]8 {' Q' K% m0 e! v 满分：2 分 9 F4 r2 K$ g$ ?
4 U2 c- a. }8 |- \0 q/ }( X
三、多选题（共 5 道试题，共 10 分。）V 1. 下面关于哈希(Hash)查找的说法不正确的是（ ）; j9 ?+ }! N+ Q0 D5 ]
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小) L+ F4 M- }( I' m2 x5 Q5 E- z
B. 除留余数法是所有哈希函数中最好的
9 |. c+ W4 z5 l* |C. 不存在特别好与坏的哈希函数，要视情况而定! r5 |" X2 o) J8 Q# m
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可0 R4 }8 b) N. B$ b( w! n) U
满分：2 分5 w5 d' \( D" I/ s u
2. 有关二叉树下列说法不正确的是（ ）
/ O: B* i' z9 o0 E0 \8 _A. 二叉树的度为2
8 B+ c! }# \' ?" m9 [B. 一棵二叉树的度可以小于2
( }8 m( b/ D# V' t6 t8 a% YC. 二叉树中至少有一个结点的度为2: S8 Z3 B- O) @% {+ K
D. 二叉树中任何一个结点的度都为24 X- R1 X! S' e
满分：2 分
1 q: @' C: y1 D0 c! D6 [7 n3. 下列说法正确的是（ ）
9 w" ]$ H! o, c/ W7 u8 BA. 图的遍历是从给定的源点出发每一个顶点仅被访问一次" E7 ~: d/ J9 Y
B. 图的深度遍历不适用于有向图% J. F0 z& f4 v4 T0 c1 e
C. 遍历的基本算法有两种：深度遍历和广度遍历
& d% g1 A7 T4 T$ s, K; QD. 图的深度遍历是一个递归过程
/ j8 y. G2 e& z: G Z 满分：2 分+ d6 j" C, M7 N1 H& W: _% r
4. 在下列情况中，不能为二叉树的是（ ）: l& n8 A& y& F# F7 }# C8 A4 P
A. 每个结点至多有两棵子树的树, O% f" b) C7 @' r0 K8 z
B. 哈夫曼树
" u. n# o" u6 p9 ^9 T& m( h4 }C. 每个结点至多有两棵子树的有序树/ E8 m) b o3 W( i6 u
D. 每个结点只有一棵右子树
; {/ u4 G4 }, i. {8 B: ]- h 满分：2 分, c: Y9 i/ |. _4 \# e5 P
5. 下面关于串的的叙述中，正确的是（ ）% K$ B1 u: O4 g3 A8 ^4 Z6 z
A. 串是字符的有限序列
/ g8 V, T. \- t; iB. 空串是由空格构成的串
; P/ T' m* ~6 sC. 模式匹配是串的一种重要运算
, l9 a3 F! x3 ^$ z6 V( |D. 串既可以采用顺序存储，也可以采用链式存储
3 r! a6 i v9 |) C% I3 Z 满分：2 分 9 s+ T8 o% D7 {4 `9 K& E- R; A ?
) q% r# }" b. L |
|
IP卡
狗仔卡
发表于 2012-7-14 17:43:37
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
