|
|
一、单选题（共 25 道试题，共 50 分。）V 1. 图中有关路径的定义是（ ）& \7 \) Q: m; s" t
A. 由顶点和相邻顶点序偶构成的边所形成的序列
, @7 g; g+ c2 t0 UB. 由不同顶点所形成的序列
$ l3 `3 \% Z! q z4 wC. 由不同边所形成的序列6 ~- @7 }5 o2 ~8 o
D. 上述定义都不是
+ ^ _" @" x+ [: W- i3 I! ? 满分：2 分
- h2 ]$ G% ~1 U$ G2 `+ s! P2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
" G/ x6 I3 \- K6 z* XA. O(0) G, E K1 v9 Z) C8 j! m6 Y- @/ P
B. O(1)
& S. ?: H$ H0 [. k) w- O4 N2 tC. O(n)
1 n* _6 Y$ n9 M5 LD. O(n2)7 Q9 A- j5 B8 A \
满分：2 分8 e( }5 u' A. _+ m% N/ y
3. 下面给出的四种排序法中（ ）排序法是不稳定性排序法。
4 d# q3 |+ L) V9 mA. 插入
$ M; Z3 I* s( {4 dB. 冒泡
9 y0 L7 N$ X: I' }2 M4 \C. 二路归并9 ?4 N, {# Y. y% c6 E- B% i
D. 堆
" ~3 S0 P1 W) Y$ ^9 h" ]; P* ?9 N 满分：2 分6 Y8 P0 i. B4 k1 B2 ]6 |3 q
4. 链表不具有的特点是（ ）
. J+ I) ^6 D& G" T# ^A. 插入、删除不需要移动元素
7 O5 b5 Y' W) oB. 可随机访问任一元素
7 U& S! ^; s5 sC. 不必事先估计存储空间8 S4 u0 v7 }4 O! r
D. 所需空间与线性长度成正比/ d, R% w7 H/ V" O; |) l
满分：2 分
4 ~) @7 s3 n% @5. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
7 n4 K3 J5 c" A tA. 9( H& t# M& L% V+ ~) w- T" d
B. 11! E/ T% D% C. z2 o( D$ _
C. 151 S4 _4 S8 l' V" O8 j) e
D. 不确定: M+ q) |' B2 T
满分：2 分6 @& K( m3 j2 Y9 S* j
6. 栈和队都是（ ）0 n. [+ A, H7 W4 K5 Z' y6 Y( I( U. B
A. 顺序存储的
: V" m/ X9 u0 I' n9 WB. 线性结构' _. Z9 X+ D! \# J3 F* T
C. 链式存储的
3 h: J4 C1 D; s& n- \+ P7 jD. 非线性结构
7 x8 z; g& a8 d6 g 满分：2 分7 a1 m! y2 Z. W h4 O( D
7. 连续存储设计时，存储单元的地址（ ）
$ X9 M! e+ w# ~) ]' x: i: jA. 一定连续
; g% P9 s0 h$ ^: x. GB. 一定不连续 ] Q) {; z/ {; d9 g2 l l# h
C. 不一定连续% Q+ ^+ [0 y1 X) O; y* q0 ]* r% E) Z
D. 部分连续，部分不连续
7 v: E3 e5 s8 O& ~+ U1 z 满分：2 分
$ X. N1 s' _' k5 n$ @2 p8. 下面有关算法说法错误的是（ ） H7 e% k& B, e4 ^. e
A. 算法最终必须由计算机程序实现
& c9 |: Y, r" p6 k2 K `B. 为解决某问题的算法同为该问题编写的程序含义是相同的
: r# m3 i, j$ K) m8 ~) a; YC. 算法的可行性是指指令不能有二义性
]; Z. f* T! F( T0 s- i' S% _D. 以上几个都是错误的: S8 w1 f% ~1 R
满分：2 分
4 `4 {4 h6 i& x+ q7 h4 `9. 关键路径是事件结点网络中（ ）2 A" H, @: J8 S5 J
A. 从源点到汇点的最长路径
; _# B* Y" r5 C3 XB. 从源点到汇点的最短路径
2 c0 u+ `3 X: [, G7 u; B& }- B3 LC. 最长回路0 J4 w1 R7 `3 o4 h+ S. @2 T
D. 最短回路
5 K7 J9 T7 Q6 e5 x9 u6 j8 q 满分：2 分, P! y9 n+ G; I# x
10. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）7 M4 j! f# p0 W& u
A. push,pop,push,pop,push,pop
( i' l8 B) Y. c3 O- j9 BB. push,push,push,pop,pop,pop
# S: A4 \5 ?, ~& V oC. push,push,pop,pop,push,pop
* y$ u5 j" M) t0 [' n2 }/ Q3 m( l8 dD. push,pop,push,push,pop,pop5 `6 | t( ?, o* N* Q
满分：2 分
& A4 m0 z6 I! P5 B3 `11. 设无向图的顶点个数为n，则该图最多有（ ）条边。# U3 h& h/ ^$ [
A. n-1
+ t& y0 n n+ P( nB. n(n-1)/2
8 \. [. Q5 X3 P- SC. n(n+1)/2
: g g% X+ b' S7 {% uD. 03 B' g+ u3 `; f8 b
满分：2 分0 i2 h0 z3 e% M w
12. 在下列存储形式中，哪一个不是树的存储形式（ ）
! D) {8 s2 q6 t" M/ l8 Z. jA. 双亲表示法
- G7 T3 }: r; k& B1 y0 ~7 JB. 孩子链表表示法4 K0 \; \8 M8 E2 Y. u
C. 孩子兄弟表示法. @$ F& F: `$ T3 L8 o; O
D. 顺序存储表示法: L$ E1 P% ^* ]9 L# o2 ?, ~
满分：2 分) [. a4 h) H' Z$ V; h' l8 E
13. 以下数据结构中（ ）是非线性数据结构
$ S8 q0 S- f: c! |' G& YA. 树
1 _1 {* Y) |1 tB. 字符串
( Q6 B9 D* E4 y8 Q9 I! a: {C. 队
8 w/ S- a( y: A+ p+ v: rD. 栈
N" S7 h# o( A) Y: O6 { 满分：2 分
+ ~$ T; N( A" w14. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
* F/ ^+ T* J& ^5 d- F8 sA. 直接插入; i+ v( { ^# C
B. 直接选择4 x. K9 e% e3 J ~' z! i: P
C. 堆+ g2 B3 @8 J" d- g, T2 h2 j) |# b1 w
D. 快速2 E; w6 d4 S. n+ }6 c! B8 O5 F
满分：2 分
) D! G% X1 N; `5 t: U15. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）
4 `- @+ g2 I8 [0 ?A. (c,d)
* s3 m+ A: u4 K4 oB. c,d2 W) Y8 o7 ^8 _+ z9 Q) c
C. ((c,d))
6 h9 j8 M; c2 w: PD. d* Z6 N; m) o! H0 }8 @$ G
满分：2 分
3 ]1 q: }9 ~. @+ H' u" |16. 设给定权值总数有n 个，其哈夫曼树的结点总数为（ ）
! S0 b7 w! B% }' s1 n6 G% S% XA. 不确定+ U" i( F! p% ~4 h% }3 t- d+ ^. y5 t
B. 2n
3 x9 J5 Q+ k. z' d6 k7 hC. 2n+1
- W* k- H! f/ r: lD. 2n-1
3 m: v ~) l. `; R 满分：2 分
! E. I- e& d$ O17. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）, ?# p: y0 _# o5 N2 V
A. 不确定
- K' f4 { h3 M! L1 _2 sB. n-i+1
# r) z5 v) Q, E" ?9 t0 fC. i
# N/ X* `( p% XD. n-i' }4 l i0 a- c) |& }9 J
满分：2 分8 [% ]6 V3 `3 P( _7 b; j) Z
18. 由3 个结点可以构造出多少种不同的二叉树（ ）
6 z# T/ w3 {* X7 oA. 2. Q1 ?; }2 u J/ @- r. U6 ?$ p
B. 3
7 F- U( P/ [0 E3 \0 i1 K9 ~! V8 LC. 4& f- M' [( j! u
D. 5* L; Q3 @( \/ \$ |0 m7 [
满分：2 分
$ Z# N8 B' o- ]5 k6 |" [7 g19. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）; B6 {) S! U( G9 I# `
A. 1和1
P3 V( ^5 ~: q! e: _B. 1和3
x- C' ~* _, g$ G) K- a" o( GC. 1和2
' X5 K1 J- e3 J2 c; b# GD. 2和3
# j$ G2 |+ I% ?' u, C 满分：2 分
, X) f ^% n7 i7 T20. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）0 r* M' [2 ^! ~' v2 o- F
A. (2,5,12,16)26(60,32,72)
8 ^ O9 k5 H* w' _B. (5,16,2,12)28(60,32,72)
9 q( H/ Z7 M7 \" KC. (2,16,12,5)28(60,32,72)
1 U; c! ~, y4 @: c P0 @1 ^D. (5,16,2,12)28(32,60,72)
0 j5 ?$ H# O; N1 y 满分：2 分( A2 |( i' P% ~. \4 M4 j4 w
21. 在完全二叉树中，若一个结点是叶结点，则它没（ ）
7 S( e- P( L5 jA. 左子结点$ V4 L2 f+ c# C1 w- V6 {
B. 右子结点6 |2 T% U$ D* w0 W6 t7 d- \ {
C. 左子结点和右子结点, g' V1 O: F, c
D. 左子结点，右子结点和兄弟结点
- Z0 a! h( L6 R 满分：2 分
0 ?- |9 o0 \: g$ ^) |, S22. 栈在（ ）中应用。
# `4 u6 W2 I; m8 d) d, L. }A. 递归调用2 j+ b! I, s3 Z6 {* T) k$ t
B. 子程序调用$ Y. D9 L+ @; D/ k5 n! z: W
C. 表达式求值$ h7 C, N0 E6 N, z/ @ r+ U! w
D. A，Ｂ，Ｃ; C/ f# M! W, A+ ~% E' ?% e
满分：2 分
8 z8 b4 Y; |3 D7 O) k1 I23. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
" \0 ?$ ^& R" L5 ^! d7 R. N$ ^A. 选择- G ~3 ~. @ w3 c
B. 快速) P6 I* |8 P* d# ~
C. 希尔0 v( b8 N' i3 ^, Q+ ^
D. 冒泡
m( v: u! T- n( | 满分：2 分! t# s# |" D0 j! ^% F% ^: Z
24. 就平均性能而言，目前最好的内部排序方法是（ ）排序法。
7 F) q3 [9 o8 ]; W8 }A. 冒泡
4 }0 x% B5 V8 k6 y8 A1 z/ ?B. 希尔插入& x: l; W; z7 l1 _
C. 交换
+ }0 h: [6 `/ FD. 快速5 a$ B3 l: C9 N) r2 R
满分：2 分
: s. D2 _8 s" H, E! L25. 下面叙述正确的是（ ）( I3 S1 U% d; o& C( |- M" O
A. 算法的执行效率与数据的存储结构无关
8 e+ W+ I& \ \: \) K7 SB. 算法的空间复杂度是指算法程序中指令(或语句)的条数
1 |: t. }( M2 n: wC. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
* d! K, n9 r4 Z$ D# n& TD. 以上三种描述都不对
3 p5 B7 e% t" u! _5 ] 满分：2 分 9 | f3 ?) X( }9 {+ K8 ~7 ?
3 J, m1 _* r X1 d4 O2 `7 H二、判断题（共 20 道试题，共 40 分。）V 1. 栈是实现过程和函数等子程序所必需的结构（ ） W# P; v7 `( ]$ Y" k5 z6 G
A. 错误
2 ?4 ?! D$ X0 t) n( QB. 正确
* T0 v& c- W8 G. L 满分：2 分
0 [! Y# U; D( A( @2. 对一棵二叉树进行层次遍历时，应借助于一个栈（ ）8 D6 H; w! Z R! V0 C6 \# t- E
A. 错误2 G$ t9 ]- H* j. v# _
B. 正确
6 B* U2 v; ^- }4 e# a 满分：2 分0 q& s/ v+ b& e6 R5 F( k
3. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）2 r% G6 f0 e) {$ f4 O) j
A. 错误
# u, |' O7 _, A) }1 HB. 正确
% @) E/ J' n9 G$ q6 f* X2 x R 满分：2 分
/ u5 P: @) _5 g# U7 o6 Q4. 对于有N个结点的二叉树，其高度为log2n（ ）" d5 h) R$ d N& b( g) e0 \5 [
A. 错误
* P6 c/ m% r' j$ PB. 正确) [( N) Z5 b4 h* y
满分：2 分
4 c. f K4 u" x$ p% P- o5. 若一个广义表的表头为空表，则此广义表亦为空表（ ）
, ?3 B r4 K' f% C: T' H2 Q2 UA. 错误
- Y4 I6 y1 G2 r5 H9 O% }1 xB. 正确
5 `$ I! ~1 ]8 }4 U- {7 v+ Q 满分：2 分
; x ?; k5 j n( m0 { X, ^5 c5 t6. 循环队列通常用指针来实现队列的头尾相接（ ）- Y, E. V0 S# C7 h
A. 错误4 d! t- w; f4 e- g" d+ ^) K+ [
B. 正确 x+ r: u6 ^7 S+ O; A' \
满分：2 分& t) s! o/ \* ^4 V" Z, N5 p
7. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）3 M) m2 n0 _$ M9 P+ F/ R8 p0 `, k
A. 错误
6 v( D8 v# O0 P4 N( kB. 正确- g$ o4 ^* \' F( e, n3 r
满分：2 分
0 q, L, i+ x! E0 k% }8. 链表中的头结点仅起到标识的作用（ ）, K. `6 g1 x. x7 h
A. 错误3 N+ z& u. s8 m- r
B. 正确. \6 F8 M! j9 _! l# X+ I- @2 ]
满分：2 分
1 j' X. B, ~2 Z- o1 w9. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
3 B. m9 `. c$ n" z9 z) ]3 SA. 错误2 b9 [4 k* C/ l# ]* `
B. 正确' b2 @9 `9 l& O& ?
满分：2 分
, r# M6 d# k% ~# V& t- b10. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
+ c9 Z' @# m& T: ^$ IA. 错误
1 v+ T2 O9 p5 c% N! {B. 正确" ?, q6 W I7 _8 }( U% ~2 k( Z
满分：2 分
H0 t, x: U/ Y X. f11. 内部排序要求数据一定要以顺序方式存储（ ）
) ~) p: A7 g K4 I5 W2 q7 e8 yA. 错误0 f t( }! o' w6 y, }
B. 正确& V5 N* y% Y: C6 ~, E
满分：2 分7 _) ]& e) r( f0 X+ F3 p8 n9 Y
12. 二维以上的数组其实是一种特殊的广义表（ ）9 \% {+ {9 T0 Z" C
A. 错误
, [% M; a2 k6 I; ^B. 正确# w9 W2 P' V1 Z
满分：2 分/ h2 d# C- D$ u6 f9 N% `4 m" j" i$ u( _
13. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
: I4 O! l$ i3 mA. 错误
/ i% n7 p6 f; GB. 正确5 [ U" S! Q( n( m- k# I
满分：2 分
" m* [ Z# e3 _/ \( q8 d [14. 循环链表不是线性表（ ）- d8 e! B% E! q' C% ?/ Z# l
A. 错误$ R9 J- X4 {9 ? {
B. 正确8 S+ W5 N5 M+ s& R! B5 s( N" g- \
满分：2 分! r4 {2 k. p* v+ Q
15. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。 W, Z5 h; y- F
A. 错误
6 O0 L9 f W, j0 d- RB. 正确
0 a$ @ X; n% x& C; w2 z 满分：2 分4 i: f" K1 T6 t0 n# P1 V
16. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的
5 H& N% v3 ]* d5 Q9 zA. 错误" K' A4 T5 l; ^
B. 正确; M G3 n) _' R9 H+ s
满分：2 分
$ V: h) I( h- N17. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（ ）。3 A G6 }" \) E
A. 错误1 B: J! J$ n G6 k% B( U
B. 正确- h5 t" r& b% l! G: |( B& c Y
满分：2 分# |! \) | _* \2 u2 x
18. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
( I* l; M$ d( f2 G" pA. 错误
& B5 h& G9 ]% F" M$ lB. 正确
: W! E4 j5 |/ G7 o( m8 h6 s* u 满分：2 分3 Z6 i3 ]5 ~7 U1 R% Z0 j
19. 折半查找法的查找速度一定比顺序查找法快（ ） l6 D8 b% \: @( u& D7 R C0 c
A. 错误
- i5 b2 Y' R, e; S8 jB. 正确
9 E' i( G K1 P4 r. P+ x 满分：2 分
/ h- k k7 S9 R9 d7 P! j1 |20. 二叉树是度为2的有序树（ ）
6 }8 f. ]( U2 ZA. 错误6 F, Y$ v# [! D- Z; X* `' N' K J
B. 正确
5 T/ X( Z: D4 d1 k 满分：2 分 2 y9 a# L2 O# L
7 V2 \% E0 E! A. k3 H( X- S8 I三、多选题（共 5 道试题，共 10 分。）V 1. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）
4 L! q+ ` R- K0 YA. a，c，b，d
& f2 p/ D$ D1 Y/ ]B. b, c，d，a3 {% \0 S$ p+ Z! \8 z
C. c, d，b, a( Q9 p$ l8 j& M: M6 g! k
D. d, c，a，b* l6 `7 b1 B; h% A4 H9 c, z! U# P
满分：2 分
( P, ^) c( \8 h: Y( v, T# @$ e2. 以下数据结构中（ ）不是线性结构" z# ^9 U R9 d- c& j# V) n% h
A. 广义表
$ X& A( l4 |' o+ h* ?- ~7 `: LB. 二叉树
$ y3 |. i- L( @) G5 A( GC. 稀疏矩阵
0 s( s1 G i- ]7 b$ D1 Q5 u2 J& Q. {D. 串
. L; _7 S- F3 A% t% E4 ~0 Y 满分：2 分
( h) ]' |+ N# T. `9 e% Y/ x" h' w3. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（ ）7 }9 l5 _( y7 s% P
A. G中有弧<Vi，Vj>
* u1 ?4 r8 |* d% N6 rB. G中有一条从Vi到Vj的路径
" h7 H) {9 p2 Q- r$ YC. G中没有<Vi,Vj>/ b d6 ~, H4 p& {4 B
D. G中有一条从Vj到Vi的路径
4 _% P# Z; k/ F+ K# T 满分：2 分; |4 f2 g- z0 c6 I: f
4. 在下列情况中，不能为二叉树的是（ ）$ V& K! g8 _! M# P: ^! O5 l+ y
A. 每个结点至多有两棵子树的树& ^) } B- [0 k8 K! Y( [
B. 哈夫曼树) f: n+ c2 L) [+ E, n+ W; C- v
C. 每个结点至多有两棵子树的有序树
7 ^# i; x2 ~- @D. 每个结点只有一棵右子树
( @; t+ l7 d* ^ 满分：2 分
9 ?, e4 g, M0 @/ w5. 下述哪些不是顺序存储结构的优点（ ）4 R; \0 s0 Z# q Q( ?
A. 存储密度大
& C$ }- R* |$ }# NB. 插入运算方便
8 E+ E% Y& f/ W! f$ I+ q! s4 mC. 删除运算方便, |3 f% C9 E+ q" G$ ]( _2 j) L
D. 可方便地用于各种逻辑结构的存储表示
; v2 `$ O5 @6 G 满分：2 分 % |2 u5 z9 e( J6 |
, `! r& ?, \ \5 Y5 y |
|
IP卡
狗仔卡
发表于 2012-7-14 17:40:16
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
