|
|
一、单选题（共 25 道试题，共 50 分。）V 1. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
; S" Z' V8 z& P# T- P3 H- xA. (rear+1) MOD n=front
' J+ c9 N6 y9 z5 p: S6 jB. rear=front
0 v& l- n: ~. G6 dC. rear+1=front i/ b& ?; @- O6 _0 ^: J6 R9 D8 z
D. (rear-l) MOD n=front
5 l6 F+ L" G- n' p8 i5 U3 f 满分：2 分* b* p# @% U* V G+ M
2. 由3 个结点可以构造出多少种不同的有向树？（ ）2 R4 V" h# v r$ |4 O
A. 2" q2 C1 T" t0 p5 q
B. 3; z2 W7 s/ ]1 j7 {
C. 46 m2 z {3 a% H& f* r# S
D. 5
9 i# ~+ J8 m. q) X1 h* L 满分：2 分
; Z( C' w ^" H) |3. 栈和队都是（ ）: R' X. t# b" d) j" V) Q
A. 顺序存储的 Q- T, k$ M' s% [- g
B. 线性结构
( _0 j( h9 }4 t2 u5 v. G8 YC. 链式存储的
! W/ r: W( p# W. ?3 X" \D. 非线性结构
% e6 o1 T0 d1 Y, m 满分：2 分" B7 S' ]* f) G
4. 下面叙述正确的是（ ）
) L$ h* T2 H ]A. 算法的执行效率与数据的存储结构无关
9 f, {/ d8 x+ o5 F" v- c9 s1 K% iB. 算法的空间复杂度是指算法程序中指令(或语句)的条数& }8 ?" X C5 e7 e3 z3 t0 z
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
; e7 j. g/ l$ [. l# O6 h% lD. 以上三种描述都不对# ~, e1 B. z: o
满分：2 分: L! H+ D- k2 a* f9 v5 d Q% n6 D
5. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。. }9 Z' D" m- ]2 D9 l: d
A. (2,5,12,16)26(60,32,72)% q/ C" C7 `# q0 B3 c; N+ m+ D+ F
B. (5,16,2,12)28(60,32,72). g1 n2 G0 L X- N. `$ f
C. (2,16,12,5)28(60,32,72)1 w" |. y+ {4 x7 t, y5 p, ]+ s9 f" c
D. (5,16,2,12)28(32,60,72)
( N8 y. y4 s! I4 l6 I0 D5 @: I( ] 满分：2 分0 `5 C; o5 V$ k; s# d
6. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
4 W: Y* e5 r d5 cA. 线性表的顺序存储结构: A* t8 @ y2 A$ q) Q
B. 队列5 g' I+ D, Q: G8 U* Q
C. 线性表的链式存储结构
* J O8 n$ I/ bD. 栈
. z$ W9 R2 H& k, }3 t 满分：2 分4 Q$ F q$ [. p
7. 若串S=’software’,其子串的数目是（ ）。6 B2 b$ J7 U y6 Z9 ~4 w: j0 J* O
A. 8
) i# ^6 e; w& ]3 lB. 37
# t* ?# ]5 U0 ^7 U7 Q! EC. 36
4 b! n" V" ?4 k" RD. 9
( L \- X4 X4 E/ Z& J, F Q$ j' e. i 满分：2 分9 _0 c% n. H2 D8 @3 S1 C* s
8. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
. @6 c! Z/ S! [4 F- qA. 3/ f0 s+ o- Q& e! u% ^# L
B. 102 ?: Z% {3 o- U
C. 15
1 s2 |, D }, AD. 253 b& k6 x; [4 \" M
满分：2 分2 i5 H. q# [3 o& ?$ G/ |3 f
9. 若要求尽可能快地对序列进行稳定的排序，则应选（ ）
a$ d L6 U! d$ dA. 快速排序3 j/ o* g* n3 \
B. 归并排序
; F a& U4 ?+ o3 R9 T" u' Y! [% nC. 冒泡排序( i$ M2 O8 | z& W6 H s
D. 堆
! K& k# w. G0 J7 k 满分：2 分
$ l) [9 K9 a/ F# ]8 V0 c10. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。
% X. I- E! ~( B1 ^A. 分快查找
9 `6 K2 Z! U# I5 A% s2 b [B. 顺序查找, L1 c9 h8 o+ u! S& e
C. 折半查找
# u7 j# w) ]# W! F+ eD. 基于属性
+ }$ ]) p9 m7 n 满分：2 分: y- \9 u. O9 n! ~& W
11. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）) Z6 z5 L8 x7 f- j0 ~& Y( F( |$ g
A. (c,d)' x- ?) _. x5 m' M1 n9 P9 m
B. c,d
$ p( E" |, D& A# U1 dC. ((c,d)), C/ w9 Z- N/ \, w3 E
D. d
3 K0 Q$ ?# S5 I% U, w 满分：2 分
* V- q3 k4 P! F+ D; b/ B5 X12. 在下面的排序方法中，辅助空间为O（n）的是（ ）, B8 \9 C$ Y. k" a! @
A. 希尔排序
. }" a( r5 O0 u3 ?0 qB. 堆排序+ o/ X7 K U) F- U8 T( R
C. 选择排序# u) R3 D# r4 m0 Q2 C# ^" z1 f* S
D. 归并排序" f2 l# G& G% z `) E
满分：2 分, m5 N( K( X d7 S, U
13. 以下数据结构中（ ）是非线性数据结构; Z" [3 n1 ~+ E( }# g
A. 树4 I* D) h. Y) d! B. G; U6 R! ~
B. 字符串, s* |; v4 i! r; Y2 N
C. 队
' g2 }2 \' g$ zD. 栈
* x/ x% C0 N$ f0 ? 满分：2 分9 \, z( [3 @ o- k! {- E% {/ c
14. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。$ d/ m/ K1 j% T' _3 I) w+ Y4 E$ z
A. O(0)0 f6 y0 D% z+ T8 i& d# j
B. O(1)7 D- D1 p; f# j
C. O(n)
. C7 j+ F# v: z) G' G: y& vD. O(n2)
; e* u( E I/ g( p1 I 满分：2 分* I6 R% @2 r5 C& E8 n- c
15. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）: J, f$ z% n8 o
A. 5
, \( K6 e" C Z5 \9 fB. 6
; ?, x2 F- O+ ~! Z& ~, r% `C. 7) \# q( ]* c- X# J: O" s
D. 8
. K, _& p% t6 g4 b 满分：2 分" `' o3 w2 {- F2 D
16. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。0 f) x" c0 p# X% s5 S) `
A. 最大概率
! V0 o F( R$ s. n: k9 v5 MB. 最小概率7 Y$ c/ q+ D. P: \0 L* I) x6 q# g
C. 平均概率7 s; |6 n5 F5 _9 t
D. 同等概率
7 P. k8 s- M4 I- K9 Q& j! S* | 满分：2 分
* y0 Z# c6 B7 p. Q/ T! ]/ n17. 在下面的排序方法中，辅助空间为O（n）的是( )$ Z& x7 n" Y: t4 D) f& \
A. 希尔排序
4 L1 c: O# n. F, l# YB. 堆排序" J. \& e2 @+ p" V2 N! \0 Y
C. 选择排序
7 ^9 r) b! X$ m; M* T% ZD. 归并排序
6 X% v" t( v* Z4 l/ p# f 满分：2 分3 z" |. Q ^+ F% a6 m
18. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
0 K% ~# e6 L" z5 |A. m-n
% C( Z( E) l. s6 e3 e& _* CB. m-n-1
: \% c! q7 `: l1 ?C. n+1
v8 W, O+ X2 a& ?) M: Y. C) }D. 条件不足，无法确定2 ~! _/ _6 Z& i _$ q: d
满分：2 分
) c; k! o' |7 w! R+ C+ I. N: S0 I19. 求解最短路径的Floyd算法的时间复杂度为( )。
* Y$ z# {) i" [) P4 l8 eA. O（n）) R3 J* D! r* ~: r7 d2 E7 T
B. O（n+c）
9 _! S! w! k7 B- }* V" FC. O（n*n）
, h. F$ j* M* [D. O（n*n*n）
& o: c( Z m5 g" w 满分：2 分. B/ v: y4 X$ A7 `# Q+ f
20. 下列排序算法中，占用辅助空间最多的是：( )
* J/ p% n, M, o+ N& J7 n" W! qA. 归并排序
6 z+ c; _+ d1 L$ XB. 快速排序
5 V& N' o; s) z* s' e5 GC. 希尔排序& t4 |, i I6 Q) [7 W# {
D. 堆排序
' _0 U. I" \& d" m+ f 满分：2 分 g* a* w* \ X! W
21. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
4 r9 Y$ z+ l) i* Q) \+ H. ?A. 前序
1 R6 B7 w; ], H- l8 U6 N7 I* V% mB. 中序 _. W0 A; }3 b, M, G W" e
C. 后序* Y! t5 } }2 }# ]2 b
D. 按层次2 A5 B+ c- F) |
满分：2 分
6 B q4 l+ G5 S. N22. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）+ Z2 | y0 W. k- J
A. push,pop,push,pop,push,pop: X8 [8 g6 L$ U6 p/ ]
B. push,push,push,pop,pop,pop
3 Z; E4 F/ n& r$ aC. push,push,pop,pop,push,pop
/ V# b6 m- ^/ PD. push,pop,push,push,pop,pop
; }6 U" e0 W: d' i5 Y: ^- G 满分：2 分. e5 I: @4 ?/ d# ]6 s# @7 w$ G; S
23. 设无向图的顶点个数为n，则该图最多有（ ）条边。
& u8 z; R: ^* `A. n-1
' H' _; V( U6 W$ v4 kB. n(n-1)/2: i, m' u$ e* x. F% G G
C. n(n+1)/2* \+ b- i6 i! X3 e
D. 0; G- U( G2 E1 b. j
满分：2 分
6 x( W% J u; d8 n# _* F0 o24. 要连通具有n个顶点的有向图，至少需要（ ）条边。
* ~& f, Z+ E5 hA. n-l+ q( k' A6 ^$ E+ c
B. n
' ?& A: ]0 V- P# {2 PC. n+l5 C- |! |2 l4 I7 D, _3 O
D. 2n$ @+ C/ i h3 o7 m
满分：2 分3 U$ G; R% W8 \" y' o& ]5 \
25. 具有12个关键字的有序表，折半查找的平均查找长度（ ）
/ [( t* b% `: p0 y3 K" J$ O& X- ]8 mA. 3.1% q, X' O& H: | [0 h$ K$ p
B. 4
7 a) |( Q; U9 m* X2 [$ rC. 2.5+ R+ t8 `' T M) L x$ O
D. 5& [# {/ ^7 f( h$ {
满分：2 分
8 e* m* ~+ j( c- M: Y; Z
! A, l$ q% e+ B+ M. h# f二、判断题（共 20 道试题，共 40 分。）V 1. 二叉树是度为2的有序树（ ）2 t) |. |5 n1 N& u, @7 B6 [( }! P: \
A. 错误
3 f1 c9 W- I& q' L8 O' O, _7 e: UB. 正确
9 j% N, O/ k- J+ k4 z$ a 满分：2 分% X( _: h c' d* z7 X6 ~
2. 集合与线性表的区别在于是否按关键字排序。
' ?! D& ~$ x; X/ {+ e2 gA. 错误7 a- w9 V" _5 V+ M
B. 正确( e& Q0 w+ G8 ^
满分：2 分
( T) Z X' `' Y' R& [3. 队列逻辑上是一个下端和上端既能增加又能减少的线性表（ ）。
+ H& C! z: z/ c. ?9 {A. 错误4 M. E* h2 H; P1 T: r+ U! d4 \! a
B. 正确& @: |$ Y. w( M) t
满分：2 分6 v' J4 a6 f+ _: ?7 |% U
4. 顺序存储方式只能用于存储线性结构。
. F( v8 G* T0 s5 hA. 错误9 o$ H0 G* K( X5 T
B. 正确
5 A Z# [$ B: p 满分：2 分
% p3 F. A# s# P# f, K, L5. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的 M7 x; _0 j$ n1 w/ ]) _4 _
A. 错误
6 b( q5 w& u; c. _2 aB. 正确/ \) Z0 g, L' e) X) g7 t
满分：2 分% N" }2 c+ o+ R
6. 二叉树的遍历结果不是唯一的（ ）
) B+ u) T7 o4 s& B7 ^2 _1 eA. 错误, z& u9 t* H' o5 M4 e; x
B. 正确
4 b" N2 B: L8 N7 T4 u6 L+ o1 D 满分：2 分
! t& c( Z& Q, d/ v" e+ [0 o2 W# a7. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）( o' d! p% Z. ~9 u/ Z
A. 错误
" s, D M7 J6 `4 a2 kB. 正确
0 q: Q( V, s. S 满分：2 分
2 e/ } {. T* e6 z7 n8. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。7 A7 o* `4 ^9 a+ }' N9 p/ S6 L0 ~9 q( B
A. 错误# _7 b$ P0 a5 j4 m5 m
B. 正确
; d' g' N& C6 i1 p% X 满分：2 分3 J+ x U; ]6 f1 k
9. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
( J; g, _ g r: oA. 错误+ o1 O5 O$ c$ S: {. n# S( Z7 r
B. 正确% O6 o" F, l- d
满分：2 分
7 j1 i# o4 t3 q" g: W/ p; L2 |10. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）5 v6 w9 b3 r9 e% D! ~
A. 错误& ~8 ^+ t1 o1 T! j
B. 正确. Q6 N, K4 B3 N* q/ A6 D
满分：2 分: W! a3 Z6 R1 y& M$ d
11. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止
/ g, |/ {/ d6 c* N+ ^3 T/ @A. 错误9 L: n4 U! x" m5 S9 H J& E- N4 I
B. 正确$ j" C9 U' s! m; j- N: _9 n; O5 r
满分：2 分
/ E* c- z7 t$ ?- V7 z12. 对任何数据结构链式存储结构一定优于顺序存储结构（ ）。: z3 j) v2 g% b) p
A. 错误
l, T X: d+ \- v# wB. 正确
8 J$ G' Q- l2 w' g, t8 ?2 |1 d 满分：2 分' ]3 R% j" h; W7 U8 B4 a, `
13. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
+ s# Q) F# W: \: u9 b3 w" I& BA. 错误
1 r* i9 Y5 @7 ^" {% j. JB. 正确
; c5 ?0 m$ M6 @' A( Y 满分：2 分
) w5 [4 E+ y% K, n* X& k: `% k14. 顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）0 z* I' F% Y9 |* V3 G% W
A. 错误
2 ] r. u W p$ Q8 \B. 正确9 ]" E4 Q. d* Q
满分：2 分
$ x6 ?, R! B9 ~15. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素$ ]* m x! K% r9 m# [7 k
A. 错误
+ C: w+ z* S/ DB. 正确
8 x2 ]* N: {6 f- J6 V( g" }3 u 满分：2 分
* j5 h7 p; V; S% q* [/ ]0 r1 o. C* \: O16. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。5 U% U( q( p }( k# l5 r6 j
A. 错误
+ U1 c% W9 C5 ^0 c: z/ ~1 tB. 正确
% ~& q5 p: h* I, G) u 满分：2 分. k8 k+ {% S% y
17. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
8 r! Z! [2 r0 t# R! BA. 错误
. Z L+ D k- F) D8 A$ U5 `B. 正确, R& \: o7 V" q6 C
满分：2 分) z. ^9 |5 {# [- C# |; n' M
18. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）1 _6 `# q/ S/ h7 D
A. 错误' r0 m1 w% e, V6 X8 `
B. 正确
; k, M j$ H9 {, h% s6 E 满分：2 分/ u; f [) e6 P) x5 m
19. 对一棵二叉树进行层次遍历时，应借助于一个栈# ]/ h4 }+ J5 U
A. 错误& @1 O0 [) m/ F+ ^. B1 b
B. 正确
9 r5 w% @% T9 h9 h+ ^ g 满分：2 分
6 J A) @( L: Y" ~) ^0 {) p' }* `" Z20. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。
& x# o3 L4 P- }4 v% n7 ?A. 错误+ [6 L4 F6 s0 @& G8 H2 Z# j
B. 正确4 T, h$ H3 t, r- _7 c7 h$ i
满分：2 分
! ?- h0 A k7 r: v- n5 p: x: Z# g% {
* a7 S! t! K2 K* {& ~. q3 z3 |三、多选题（共 5 道试题，共 10 分。）V 1. 有关二叉树下列说法不正确的是（ ）
6 u8 x+ G' e8 J8 ^! @9 LA. 二叉树的度为2" e' v) s0 v( d8 y2 t
B. 一棵二叉树的度可以小于25 A; g) D' ?4 {. \) x/ B" v6 z
C. 二叉树中至少有一个结点的度为2
/ f1 N+ n% Z0 x8 Q, Q! CD. 二叉树中任何一个结点的度都为2- M: T: Q; ^+ m$ [1 a" L) d
满分：2 分
) w! u! l9 i" v" y, \9 y2. 下面关于求关键路径的说法正确的是（ ）。
! Z% _/ M: o- x. H) ~0 n# G/ r# `A. 求关键路径是以拓扑排序为基础的' u+ D. F5 U6 X, [. H: i, m
B. ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
& K$ T Q; W. x' T: ]% VC. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差, V" j; v; p- [
D. 关键活动一定位于关键路径上
2 t0 J' k& r9 O8 @6 i1 ]: \ 满分：2 分
4 ^/ @0 q( c7 v5 _1 j) a3. 下面关于二分查找的叙述不正确的是（ ）( \8 f7 N4 Q/ K Y: Q
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
4 I* R0 k0 }$ O: v' CB. 表必须有序，而且只能从小到大排列; H- x( o9 i8 ?, \, f" H$ y2 L0 N1 j
C. 表必须有序且表中数据必须是整型，实型或字符型
8 [7 n+ l1 ?3 A) o/ sD. 表必须有序，且表只能以顺序方式存储
& Y$ S0 Z8 @( j2 h5 ] 满分：2 分4 e# U7 {! e# \* i) x
4. 下述哪些不是顺序存储结构的优点？（ ）
; ~: s8 U8 `2 q: o# PA. 存储密度大; s7 |. S4 m7 n, I
B. 插入运算方便$ U7 }! F" [$ b7 o! K
C. 删除运算方便
8 \' \) H- M' v: I* r+ mD. 可方便地用于各种逻辑结构的存储表示
7 r) ~. q- C6 ]. v1 _' w( b 满分：2 分
( G: u q( ]5 `# ~3 @' N( F1 I5. 在下列情况中，不能为二叉树的是（ ）* i- O+ r. ~2 Q1 I1 i& L( c. `" B
A. 每个结点至多有两棵子树的树- {" ?3 E" u, M3 J8 p, m' g
B. 哈夫曼树
% y, R4 N4 k/ x( r4 c# ZC. 每个结点至多有两棵子树的有序树
1 U7 R! c( ]4 H$ DD. 每个结点只有一棵右子树8 I, Y7 F* B( O V( d
满分：2 分
& S8 N2 t1 J7 x- o# M8 v) E
- G3 H2 s! z' j8 e如果资料还未上传请加QQ：1306998094 谢谢 |
|
IP卡
狗仔卡
发表于 2011-10-28 20:17:03
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
