|
|
一、单选题（共 20 道试题，共 40 分。）V 1. 就平均性能而言，目前最好的内部排序方法是（ ）排序法。
* Q6 R# r9 [8 T+ ^' X4 r/ bA. 冒泡4 T; i0 g: i Q) g
B. 希尔插入
8 t1 a; v- f, I) h; g& K4 uC. 交换
; ^, \: M) @5 j/ \4 t# S: F3 JD. 快速+ l7 u; ~* a' y& }& j N, n# v1 O" ?
满分：2 分5 _* b& n" w& _1 C% u
2. 从逻辑上可以把数据结构分为（ ）两大类
% U: Q! ]0 r% H1 M3 X: y: I- UA. 动态结构、静态结构
( s1 s; F: M- J2 x9 cB. 顺序结构、链式结构; ~8 P, s& S6 Q( G! M- z
C. 线性结构、非线性结构3 i% h: W4 u! y# r
D. 初等结构、构造型结构4 }: m0 o! D+ H
满分：2 分
, J1 n- \* p2 o Q: n) E3. 在完全二叉树中，若一个结点是叶结点，则它没（ ）9 ^* X1 e- a- G' Z1 [. M. @. s
A. 左子结点
k+ V0 Y4 I, X1 t# ~B. 右子结点
& W9 W1 |' q/ F" qC. 左子结点和右子结点: A" L4 \% V! j9 J: l# E
D. 左子结点，右子结点和兄弟结点( p% r3 r* R, t2 t! [( x% e
满分：2 分
5 X1 E- u, u# v) C4. 用二分（对半）查找表的元素的速度比用顺序法（ ）0 D9 d8 Y# g' O' U
A. 必然快
; r" q5 T8 q. s2 ^5 k) aB. 必然慢) e. ~; @% G3 }8 T1 E7 m
C. 相等
5 v! v2 g3 i! z6 Y3 G* t0 RD. 不能确定# L5 L0 I, N x }5 ~& o+ |
满分：2 分+ Y* Q4 q( O& G/ i6 q
5. 算法的计算量的大小称为计算的（ ）! A& ]/ E8 D4 j: A% E
A. 效率% B6 E3 I ]! b8 W9 f; t
B. 复杂性: I' O+ J% }# J, g0 A! {
C. 现实性9 P C ?' p& P1 Z1 Y3 W( y
D. 难度
% T0 {+ m; M2 g" t' Q% f 满分：2 分
5 y+ q& t$ g0 T( P/ ~4 h6. 以下数据结构中（ ）是非线性数据结构
9 a0 b! {! s+ f, s8 ]9 J; DA. 树; ?8 |: [8 [3 Q0 Q _
B. 字符串, I" ~: W7 S% E# d
C. 队: Z4 ]5 z2 N, a9 A$ g5 L
D. 栈
$ b- F* Y1 D3 T! o# {- g; ] 满分：2 分9 I. [' q4 L4 l
7. 下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1; V6 t2 B9 u. }3 J) n1 \ e
A. O(2n)3 P8 c- l8 e3 F; C; j
B. O(n)
" ]; L7 { @( f" Y, R1 |9 a jC. O(n2)) d7 c- ]/ g5 q
D. O(log2n)
; l0 ` \8 G: q+ C" l$ L 满分：2 分, g; E J9 ~1 p N9 \4 \% i
8. 散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
2 E+ m. i, n- O' n8 n% gA. 最大概率
3 g5 f; V; e: E3 QB. 最小概率* f! [% n3 F8 X' \9 f* w& [
C. 平均概率6 c2 A) g- u: J. @5 w
D. 同等概率8 i1 W, h e+ ?+ S
满分：2 分
' v' \- _5 N7 K- o* H6 Z$ D9. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）& W" j0 h, F; o; a7 V/ j2 j
A. (rear+1) MOD n=front. s8 o" e3 p! L1 v# V- O# |7 F
B. rear=front) a+ _/ X! B) N2 t
C. rear+1=front5 S/ i7 t# d+ {4 b) m, x8 B2 H
D. (rear-l) MOD n=front [' B0 ~5 H% F9 _; U; ~
满分：2 分
1 @+ p: h0 u& |8 h/ g2 c* G7 z10. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
# d3 v6 g9 ~0 p( [' }$ c& s" {' u% VA. 直接插入
; x! p" M- `, b' AB. 直接选择
( w! y' Z2 W w, x1 J- DC. 堆
& A8 N) O0 ?+ W- [D. 快速
. U( d# \3 w# @8 Q9 y+ c 满分：2 分# K" ?* R* a5 W4 ]" {8 x% g
11. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
& u8 r( v, j9 fA. 线性表的顺序存储结构2 g) x* @5 T& Y0 A' A& ?; `! P
B. 队列4 K0 T2 i$ s6 m$ s
C. 线性表的链式存储结构
, t1 k& x. I2 w. o- A( X; YD. 栈" B8 \, R! Q" Y# W8 `+ |' y# M
满分：2 分/ {; G/ S$ C" a3 l: q- a
12. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
- `+ {/ ?- N1 q1 X0 Y1 f4 y! AA. 1和1
c0 c- u$ G2 a7 Q' k' \5 X8 M0 ZB. 1和35 S3 M0 b d2 | R0 L6 @" a
C. 1和2
1 m4 m. G/ M2 P1 r( f1 zD. 2和3- D6 @9 R4 K" U1 S; E3 D
满分：2 分
' T, @8 y6 a0 D( @13. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）' r4 `8 o/ L% ?1 a/ v# ~7 O4 r% G4 y
A. 不确定
H3 f! T+ W' g1 I& HB. n-i+1
1 ?% G: _- I! F+ }8 F& @! N. s7 g$ MC. i
+ K- k. ?. U: r) B: F# }: E' j! ?* wD. n-i+ y7 B: R5 \& [1 Z9 I" y, ~7 {
满分：2 分
' c# v# ~3 L* w, U: @3 z( d14. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）: x) N) c' q# v0 y& p: V# f- a
A. head==NULL5 a# O# \* B& ^! q: L
B. head→next==NULL
4 k! x6 n: M2 z7 l! ]) HC. head→next==head% A3 r9 K% K9 j9 D; @) z
D. head!=NULL
7 R5 {6 u+ ]% p, j+ }4 _9 T 满分：2 分5 @8 Q: w( u7 g& ] B* }* D. J
15. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）1 S' q# C# O& P) {0 ~
A. 13
# _' W! T" `2 ]& F. Y9 J1 GB. 338 G, S( G% G2 n
C. 18% ?2 v+ V' [5 Z/ j( h
D. 40
% O0 L, J/ m0 c7 N 满分：2 分- q3 C3 S. ]0 j) h9 R
16. 求解最短路径的Floyd算法的时间复杂度为（ ）。
0 R. }" W7 g, P5 \; U5 BA. O（n）* I! ?, n4 e6 \0 L7 o$ w
B. O（n+c）5 r- y! J0 }8 |8 g) g+ p
C. O（n*n）7 w7 p. y. V' H" W
D. O（n*n*n）
g; e3 J7 u- r; r 满分：2 分
' X5 P1 q+ f8 {# k3 q7 t/ g" p17. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）3 y2 Q2 p7 z& c7 U4 [ N/ j
A. CABDEFG
& Z2 c: E9 F6 s: T! B; mB. ABCDEFG
! i! L ~' m9 k( L. ?4 `C. DACEFBG6 y8 }7 ^, U8 V' B# m2 V
D. ADCFEG$ D3 B+ D. C) o) J5 K& F9 s
满分：2 分
: j u8 }, a) x1 x+ W5 ?4 }8 n, Y' Q- _18. 要连通具有n个顶点的有向图，至少需要（ ）条边。
8 y `! O9 Z, h( Z+ d2 K8 }A. n-l
" S( s8 @( i$ G0 @+ ?B. n
0 Q0 d$ [" t% N x3 f3 f* KC. n+l; W9 J; P9 Z) L: I/ [7 x* A
D. 2n! r- O, @: b1 S* C
满分：2 分6 K) C6 m. g: C3 {# i# i
19. 由3 个结点可以构造出多少种不同的二叉树（ ）% s0 q/ |$ y1 {0 l/ h
A. 2
# m! _5 ^# c: T, p, r, VB. 3 p8 z# W& T* O. N) y- J7 m
C. 4
9 v: f2 C# s9 N1 f4 mD. 5
0 A$ q% J1 j- |2 L+ d! {0 j* d 满分：2 分6 x8 @. B5 }& W h4 C
20. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
b9 s# \$ L$ l- ]3 uA. 插入
. y: L* Z* P8 V. z- H9 |B. 选择* v4 {* z1 A& y
C. 希尔
/ V$ p( l1 }3 L9 K& PD. 二路归并
T, S" E' F+ \! e- h' B5 a, R 满分：2 分
- S/ Z- p0 `0 p+ N二、判断题（共 20 道试题，共 40 分。）V 1. 顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）# i, m" C9 B: v) P
A. 错误; w4 H# L3 i: T
B. 正确
^: S/ }5 X# v+ ^+ x; _% q1 L/ _ 满分：2 分8 d! i; \1 A5 n) A
2. 内部排序要求数据一定要以顺序方式存储（ ）+ H4 r5 {- i* _6 v9 T5 c
A. 错误* ]1 Y7 e# U7 D! d
B. 正确6 B( B7 C, T) P5 h# a
满分：2 分, t0 M! Y; A8 y7 o, ~# S/ s) \9 X
3. 消除递归不一定需要使用栈，此说法（ ）
3 I3 W* \7 X$ r5 K9 e- uA. 错误
; k2 r" Z. f# gB. 正确% S' \, r. X3 L
满分：2 分
8 R, p. |4 d- |1 x4. 若一个广义表的表头为空表，则此广义表亦为空表（ ）( l; m9 ~2 Q- A& Q, K9 ?1 v7 |$ {
A. 错误
8 i7 U2 `5 o$ _8 Q4 [! S6 \1 O5 LB. 正确) S' l6 u2 P' z# X
满分：2 分2 y" r3 l3 I1 Q8 c' _, L
5. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）% v! p: b* `/ H5 S+ f
A. 错误
* A( X2 Z7 J# W% M; n0 wB. 正确
, _! C/ ?0 E% c. Q 满分：2 分
8 x9 d& j, H1 y7 ]- c2 I9 J6. 顺序存储结构的主要缺点是不利于插入或删除操作（ ）1 s9 J7 p1 S& T3 i1 Z% X- `
A. 错误
/ a1 i# w# f" G* T* yB. 正确
9 G% N6 y% D# z% U 满分：2 分, L( P0 k4 k, v, L& ~/ x: T
7. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）& n! p7 O- Y) V. x
A. 错误0 b# M$ J. f$ j& J( h }
B. 正确
9 \' c/ y, x' B 满分：2 分
$ e2 ^1 ^8 j0 L- x7 m8. 顺序存储方式只能用于存储线性结构（ ）- E) m/ z q, s9 K- z2 V- ~
A. 错误
' r6 r/ W4 ?1 F5 T. t# Y# v( y. cB. 正确
$ ~# G) A6 x" a: Y$ ` 满分：2 分$ d/ M( S6 P. p* ]' [" W# t
9. 折半查找法的查找速度一定比顺序查找法快（ ）$ m5 v9 `0 S5 x" F4 K
A. 错误' p+ d( k# @% ~; }! _( k5 x8 e
B. 正确
% C$ K& y7 _4 @) S# v 满分：2 分
2 d/ r* S! s3 s5 }% i7 e10. 栈是实现过程和函数等子程序所必需的结构（ ）. D% o$ A5 @) j& J8 _! j6 ]
A. 错误
. B; a9 s! k9 T' t/ oB. 正确
1 @8 a3 n% X6 a 满分：2 分1 K0 _) g& O$ C6 y' b, ]9 B8 M$ m$ o2 a
11. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
; W" T, s+ ^) D. F' PA. 错误
* z! A2 L. z" K: }7 EB. 正确
! X. L( u6 M& { 满分：2 分/ J1 E, G" D0 Z
12. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的
4 I+ M( V4 a( P& sA. 错误& v, S6 V9 d$ U( @" o7 i
B. 正确
7 P/ k& I: k& p, M+ A8 N) x, [" G 满分：2 分
( c3 P' l: i, ], x% a/ D8 r8 I4 K13. 链表中的头结点仅起到标识的作用（ ）2 K; L$ N; s, W. A6 f
A. 错误! M+ O _% P9 G( n" x/ b8 W
B. 正确
( {2 p/ z3 Q t( L5 t 满分：2 分
' ~% T6 H+ w& f14. 线性表的特点是每个元素都有一个前驱和一个后继（ ）% v( M9 I1 K y4 W8 N. M( A! ^
A. 错误& \0 z! {. v& s+ \/ d
B. 正确0 D3 u& L1 \4 R5 Y
满分：2 分7 {9 j. z+ U9 |. f" ]# ?
15. 当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）- ~3 Z, ?7 ^3 L: R' D' D4 t- d* r
A. 错误
( g& ~- [) ^+ O5 aB. 正确
$ ~8 V* ?) f, A: X( S. Z" Q9 e 满分：2 分5 F- L9 m3 @/ V) j
16. 任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ ）
: h9 D" q- ^1 X: yA. 错误
3 N0 m5 ]. M% s' QB. 正确
1 F2 S& h: \ P6 n9 H4 ?7 R+ ~ 满分：2 分2 C+ `; E5 A- I5 g0 }; O: s
17. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）0 n' d/ f8 Y" Q, l6 k- v
A. 错误
1 c! j6 p/ a/ v$ pB. 正确! @. _9 P2 ^' M9 z+ H( ^ \
满分：2 分6 U& \$ _ F1 I9 N3 w% p
18. 栈与队列是一种特殊操作的线性表（ ）
5 D, Z0 Y8 _$ e* EA. 错误' E2 t e B( B" o7 o
B. 正确
5 V5 U3 y; b8 V* ^ 满分：2 分8 C4 [$ W6 B3 S6 k+ A0 H6 d
19. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
: @8 g6 j0 n" O! [6 V, a! o& eA. 错误/ d, l4 S* J3 k) N+ P& j) B
B. 正确
& f+ k) j, W" ?! e 满分：2 分
. I, T& q) A$ P0 R$ U: ~20. 二叉树的遍历结果不是唯一的（ ）
4 L: W5 [* e' a9 ]! LA. 错误
- W! m, P! ^3 N1 u$ ZB. 正确' o* t! t7 V6 l1 ~& p
满分：2 分& O- p0 r" w" r& V/ ^' t" J: [% G
三、判断题（共 10 道试题，共 20 分。）V 1. 二叉树是度为2的有序树（ ）
9 V4 C, ?. |8 X5 X3 M0 f4 B- O' [1 rA. 错误5 w! j. J& M( |, x6 G0 K7 x- d* P
B. 正确
( |8 i$ a( s4 o1 t 满分：2 分* U1 M1 H9 i3 @7 e' H+ f+ g- q
2. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
; q$ Q2 N. T+ ~A. 错误
0 Q1 [2 e( y( K: l" B0 x! P$ KB. 正确
9 e$ v( O) e1 `9 Q6 ^6 y5 t- Z 满分：2 分' R3 O) K+ l( q/ d$ {3 A. g
3. 线性表只能用顺序存储结构实现（ ）
' o" K X; p) E; O2 J; F+ c. |2 lA. 错误' f' p' X' Z! n: E* |' K
B. 正确 ]& Y) f. N9 D* @0 g2 l
满分：2 分) o& g% J3 p& o. O
4. 算法的优劣与算法描述语言无关，但与所用计算机有关（ ）# q3 r+ J: {9 E* `1 v# F( m" j
A. 错误- V$ R, [. j+ L0 y1 b2 M
B. 正确
9 V& O1 g9 l! d- F4 G1 R 满分：2 分
$ {& J+ w' ^% t+ e6 z5 y) M2 }5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
! F2 v( K# R3 q3 f( SA. 错误3 k0 M$ H" Z: Z; ?; H) [7 F9 n9 x
B. 正确( g( x. W! ~6 ]; a
满分：2 分- ]$ v9 o( g) J; S5 q! G* D
6. 对无序表用二分法查找比顺序查找快（ ）
, h$ @- V: p0 z! G/ T- rA. 错误
" [ J4 V7 Q# b! i- sB. 正确
4 B/ {/ M. a+ s, f/ i 满分：2 分% R3 d# W! A7 `) D
7. 栈和队列都是限制存取点的线性结构（ ）
- e# d2 Y6 W8 k# qA. 错误
+ ?. `" l+ i/ y; s3 g* f2 IB. 正确7 f! ?) O8 u M6 J- B
满分：2 分
' J( l; F/ b4 j8. 循环链表不是线性表（ ）& X9 `$ [ J& }( T: o8 J+ j
A. 错误& J0 h" n& F; X1 }% y! ]; N
B. 正确) c! `- C, r' {" W
满分：2 分& H+ m$ W0 A# O/ _3 K, a3 M
9. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）8 z1 ~. H( b4 h/ N4 Q# h; Y
A. 错误
- A* L* ?5 g) {. fB. 正确" _5 i& X1 @9 ~( L" O! {
满分：2 分
+ _/ H7 h9 J8 W% S; m10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
0 i( C3 F1 H8 I: }# @1 PA. 错误
0 o0 S% p% Q6 b1 RB. 正确
! ~ ?! E# H, ]2 n5 O 满分：2 分 |
|
IP卡
狗仔卡
发表于 2011-5-10 09:17:33
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
悔悟卡
匿名卡
客服一
