|
|
谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。5 Z# l: L1 E! C
# ^' l9 C2 t) h% [ a! I! s一、单选题（共 25 道试题，共 50 分。）V 1. 图中有关路径的定义是（ ）
! n$ h3 K2 J+ ]4 b; g' `A. 由顶点和相邻顶点序偶构成的边所形成的序列
( V# n1 v' T9 N) o, J+ TB. 由不同顶点所形成的序列
+ i( S$ I; b- u/ F* n0 N9 ZC. 由不同边所形成的序列
0 ]) T" d" F. M9 ZD. 上述定义都不是/ p' T# A2 B, N# L, S
满分：2 分. b# d/ M- ]* @4 S; p
2. 已知串S=‘aaab’,其Next数组值为（ ）. \) W) _; x8 d2 U
A. 01236 E1 y9 t9 Y \" B8 B+ o! E4 O0 h
B. 1123
7 B# m+ e* \* E) W" NC. 1231. C' l3 k' t! ]# L( g$ q) i
D. 1211" E0 N3 J6 X3 L, K2 s
满分：2 分
# j6 k, I+ C: c4 O# S3. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
. Y& m% u" c# p& S, m6 y- n* e8 ]A. 不确定
* I1 X6 l+ I* i5 h( G: \ cB. 2n$ A8 x) [1 R2 i9 Z% Y1 T: [) ?- j
C. 2n+1+ A0 X) R: T9 |" Y5 ?8 H8 S
D. 2n-1
3 o9 U, ]) D1 b% V& U 满分：2 分
, f8 [8 ~$ q4 X4. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
0 V# z; @+ r2 b" S$ ^A. O（i）& W( X/ A% w& V5 D/ n, C/ o0 _" Y
B. O（1）& d9 b6 I1 d. E! V
C. O（n）# T# `. t. X2 Y, [2 o6 e, U0 e" ?
D. O（i-1）! G( r# W$ f! |' n) h. X
满分：2 分
6 J+ h3 a2 g3 Q+ g; n' y5. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。% x! M1 m, ^% R2 \. ?' J1 [! c
A. 3
) b( G) o2 L/ v* SB. 105 }, `1 l; d* N1 x# e# m ?$ @
C. 15& w! w5 o6 L! `
D. 25# B f; M0 i$ \, U4 N
满分：2 分
# {; Q+ z* q( T6. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A)))))
2 |* B& `. _7 b6 {# GA. （a）
5 R+ }! e& Y( W/ d/ W, ^: a: h6 ~' \/ DB. A+ K1 y2 w; W) E; ?: k9 p( k- R
C. a$ [* r( r" o1 K2 c" l
D.
' b' ?' m3 j1 xd+ b t5 B' A& e% y) m4 H) @ ]! b+ a
. j6 Y q% h$ I& ]$ b* a# S6 V 满分：2 分# D6 d. A; _2 |) v
7. 若串S=’software’,其子串的数目是（ ）* e1 @; E% }. E) Q7 D( }# }
A. 8
* T# c/ _( w/ w, x1 A1 b! gB. 371 T8 {# r( l+ R& i
C. 36
( Z- m1 z, h$ T( T2 k' wD. 9
; f; Q- b8 B& L9 Z3 y% U8 v4 v4 N 满分：2 分2 N x( _9 t0 J0 R/ _
8. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。! c% h% G e2 x6 b3 `- ?
A. 插入2 l) g4 m* g% Y& L, o @
B. 选择9 K% {" a# v; _. |, `
C. 希尔 f. O! S7 J( K; w
D. 二路归并/ K1 ?: P- f! v. X, G
满分：2 分! Y1 j" g0 S3 W$ T3 N x3 I. m
9. 栈和队都是（ ）/ e% G2 d4 f- m6 h& Z9 `' |+ q
A. 顺序存储的
2 } Q/ J; g$ G4 f bB. 线性结构; T, [( W P: S O! a
C. 链式存储的
& k4 Y8 I8 k: p, W4 b. xD. 非线性结构0 m7 G1 j1 F7 f4 J7 o% w E$ U4 Z
满分：2 分& H9 }; l2 z; F" t' U! A2 _8 |! Z
10. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）
5 J0 d$ \ N0 a+ ~" NA. 55, y' Y# B" v# R# C& e4 l3 q8 _
B. 45
+ _) l0 J; _3 n( o8 ]C. 360 W: v5 |+ j. W, f: T" V! I( t1 v. f
D. 165 R# z2 W; a( z( A, j
满分：2 分4 e! }' ^3 S. P; {& l& ~9 R
11. n个结点的线索二叉树上含有的线索数为（ ）
! \& y& S5 [: E) `- x3 {: aA. 2n
( @( i% D2 Y1 X& t- oB. n－l) i, j( o8 f( z f1 L8 g
C. n＋l; n- V+ A6 ]& ]8 T, ~. r
D. n7 i0 C! d6 N. a/ [
满分：2 分
/ l1 _. _) u* E% r* d1 X* t12. 以下数据结构中，（ ）是非线性数据结构! \* }- l8 o# x9 Q0 G, W! g
A. 树% q8 m4 s' y: l; z
B. 字符串* a0 V6 P' T! N" Z' P
C. 队9 c% ?" F! b8 }' N( }
D. 栈' K' g( W! U) g2 V1 I
满分：2 分- p% }+ k4 n" {% k; I1 q2 p
13. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
1 U% u8 a. p! W- }( j9 P, WA. m-n
& _4 R3 e8 m6 w9 mB. m-n-1" I% N1 A( l. T
C. n+14 X' W: y4 r) g, r3 o1 W
D. 条件不足，无法确定. a8 e7 b1 H2 d
满分：2 分8 T' z+ w ?: z' h* @0 e
14. 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）, f3 K6 R) p" l2 r
A. O(n)
; N' n! Q; K5 t' J# w. s0 nB. O(n＋e)9 U& V& ]% H; {/ X* |8 q
C. O(n*n)
( |4 h) ]# p9 T8 b7 gD. O(n*n*n)" Y9 n/ Y" q, M1 T4 |9 N9 n
满分：2 分
" u8 Q- ?# k' u! j; C5 x, p15. 下面叙述正确的是（ ）. |2 z! G1 M6 j' `- A3 Q$ M
A. 算法的执行效率与数据的存储结构无关
2 H z! C+ `1 b. I: }& u3 [" ZB. 算法的空间复杂度是指算法程序中指令(或语句)的条数1 @6 R. U- i: Q$ K
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
& X D1 Z# A# f" O5 ~4 G* j6 |& X$ [D. 以上三种描述都不对
6 g) u$ M/ }5 @! Z+ W* ? 满分：2 分: f6 }3 |5 \" I+ U4 R& @ N
16. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。3 d% n q0 x8 s! s$ x. W0 t
A. 前序
( Q. M$ M+ K8 u) } K- g$ RB. 中序' {0 d% ]* X: Z. f2 Q: r
C. 后序
5 b7 L6 W) W* G6 i, HD. 按层次
0 x: V/ c6 T/ M/ O5 c 满分：2 分( m0 U6 Q9 Z/ B: v; _. {: ~
17. 对于栈操作数据的原则是（ ）# `1 W: Y7 e4 b& y5 ^$ j
A. 先进先出3 E; K$ B# p0 _# k" U" E1 F0 F$ R/ i
B. 后进先出
9 E2 l- i/ H; f: n: x6 mC. 后进后出
4 d# Y$ j2 C! N; Q5 x3 ]* @D. 不分顺序
7 m! N! e4 K3 a0 s/ K+ W) F U 满分：2 分( o1 Q2 }% S5 W8 _% a$ O) j
18. 关键路径是事件结点网络中（ ）。& Z/ h; ~ p1 t9 i9 w* I' P- b
A. 从源点到汇点的最长路径
* i& L, g# T% G( h& Z; r3 H+ yB. 从源点到汇点的最短路径
7 H5 g( ]$ Y5 w- b* {% pC. 最长回路8 `. Q9 [! s6 y
D. 最短回路+ t' O7 D) E& @) ?+ b
满分：2 分
" i7 W. E4 F9 X7 q( o. M4 y19. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序
5 A8 e. {; }% B% v3 E2 ]A. 冒泡! C3 S9 C. y' S
B. 希尔6 J3 u) J& Y( J" ^
C. 快速8 ? v' k# x4 E
D. 堆
# K" x, }# P, ?! N7 v9 a 满分：2 分
: J# i% ]) [. z( ]20. 下面关于算法说法错误的是（ ）/ B( B' J! @4 G! d, r
A. 算法最终必须由计算机程序实现
- [2 L X- S5 B. C' _7 wB. 为解决某问题的算法同为该问题编写的程序含义是相同的$ E! @+ V3 k, I0 B! ^) c
C. 算法的可行性是指指令不能有二义性
/ H& B) |' w# v' f9 S. }D. 以上几个都是错误的
+ v6 L0 p8 r. q3 W( f 满分：2 分
- T7 r: b( ?7 u. q n7 R3 e" w21. 具有10个叶结点的二叉树中有（ ）个度为2的结点，9 q3 {4 p: L" p; I. o! I; h
A. 8
1 m/ [# ^6 h, s# V% _- l1 gB. 9& k2 Z+ h+ _, r! Y8 I0 b* F
C. 10$ k7 N0 N2 M! d" O1 F7 I5 n/ ^/ U
D. ll
" N7 t F4 R, q 满分：2 分
+ L* _# e7 F2 O, n/ |' G. @3 e22. 一个算法应该是（ ）
: _( W# v) g6 K0 N4 J+ p; _8 uA. 程序
: Z# K$ g/ U% [/ [1 S4 O' O2 PB. 问题求解步骤的描述* \4 n! t+ E4 O
C. 要满足五个基本特性+ H0 N' g, p* [# u. S7 V/ `. Q" W
D. A和C.
, @/ q. B8 l9 T' }9 h, O, G 满分：2 分, z6 B# x: Y" ]" H
23. 设无向图的顶点个数为n，则该图最多有（ ）条边。" \1 b2 P/ w8 x N. e' S+ C- n
A. n-1
' ~. e6 W) d" P- {: r3 N( ~B. n(n-1)/2( X8 G+ v! ?+ i4 |5 y/ j
C. n(n+1)/2
/ S; l1 W; Y5 G, \, u/ q: E& r3 cD. 0) }' b4 O! P0 l" o
满分：2 分
( y. O& m$ f$ H( c; k24. 栈和队列的共同点是（ ）。
- i( R! p3 @$ C' v4 ]A. 都是先进先出6 ^4 n9 v8 [: g, J
B. 都是先进后出
, |, F$ I' p4 h7 c9 f0 iC. 只允许在端点处插入和删除元素
1 k9 g3 b6 }) g0 h/ V1 w' [: Q- aD. 没有共同点
- ]# o q, d: X1 \E. 限制存取点的线性结构6 z' J$ |/ L5 y8 Q j$ I& t
F. 限制存取点的非线性结构
2 |; P% B9 J t3 x# K 满分：2 分4 a! o, W3 l5 x6 u3 x1 h
25. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）Head(Tail(Head(Tail(Tail(A)))))
" O) l) T6 M3 [A. （a）
3 i# c' S2 x& _B. A' ]" y* ?* F; m
C. a6 v3 Y5 A3 }$ O: n
D.
; J4 T+ O1 `: x2 o Y3 l0 pd
; {/ W/ O2 ?. l; e9 Q3 ]4 Z0 k$ ?5 n3 g [# S3 N
满分：2 分 : R* A; W3 W# f3 c1 `% M
- J3 `4 @6 s L% y) x# d
二、判断题（共 20 道试题，共 40 分。）V 1. 排序算法中的比较次数与初始元素序列的排列无关。( v6 ~7 B |$ o3 W
A. 错误
6 j$ C$ U6 I" d; {* Z% l) aB. 正确
' C) t7 }" D, ~* @) b) F/ g$ I) g 满分：2 分
8 k# Q- s6 C% Z+ ^/ G2. 顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）- j+ s* T! l2 s/ f ^
A. 错误2 N2 N6 ?. }# w
B. 正确5 E8 }& G- G# k: N4 D- e
满分：2 分8 R' O* c; q9 S8 J. n/ D- T
3. 二叉树的遍历结果不是唯一的.& n; _2 l' G" K. G1 I
A. 错误7 [8 ^& k+ p- I
B. 正确9 X5 e, v* X U6 N) V. E( G
满分：2 分4 q5 u/ l$ r$ [# e6 T( ~
4. 在待排数据基本有序的情况下，快速排序效果最好（ ）
+ K% O2 X/ O6 |8 d/ k# fA. 错误
9 s) ~6 v" W5 M. wB. 正确
2 g7 q) D* y5 n* E5 A+ W# T. f, V( l 满分：2 分
# I9 D' X& P0 J9 r. x. ?) L0 S2 j5. 消除递归不一定需要使用栈，此说法（ ）+ C5 n4 @% c x
A. 错误$ x$ J% f% f% y
B. 正确
* w4 l: J) p7 } 满分：2 分
: C6 |( p; D" P3 Y% s/ a6. 顺序存储方式只能用于存储线性结构（ ）
! B; n8 \; b3 x7 f0 |4 `A. 错误
& E) l# T/ {; [B. 正确2 w5 k- U; f7 s7 j
满分：2 分6 |+ Z2 S+ B' U$ T7 \
7. 折半查找法的查找速度一定比顺序查找法快（ ）
6 k/ C7 h2 L: h; S# QA. 错误2 f* W0 y2 H" b' l3 v2 K( t
B. 正确" v) \; g! c4 Z1 y3 l: Q
满分：2 分
$ {5 e5 \ z3 K8. 直接选择排序算法在最好情况下的时间复杂度为O（N）。
6 G5 z6 A3 u& n) OA. 错误
: g j+ \6 K* C$ B9 T" sB. 正确
: Q5 M) s1 n! t9 j 满分：2 分
- v4 C* w& z" i) d; ]4 d9. 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。
% X3 T& \$ Y' \4 l5 G/ v! tA. 错误
; S) t' h8 x8 e1 c* pB. 正确4 h0 A# p# z2 o
满分：2 分$ B+ l+ s: c( x. ^" V4 A
10. 队列逻辑上是一个下端和上端既能增加又能减少的线性表（ ）。
/ W4 Z& w: I% {1 {3 d# \ M) iA. 错误& |7 r% q) y4 |4 k) A: b5 Z$ A
B. 正确3 h, s7 v* P9 V; ?
满分：2 分. g" v/ z( P+ K# Q* ^
11. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的
7 W7 O, {: e, g1 W1 h% AA. 错误
$ _% S A5 e4 w8 uB. 正确
# Z- B6 }+ w, U+ Q* y 满分：2 分
, t# r5 U! i0 f3 U7 `* V$ U" ?6 ?$ q9 @12. 顺序存储结构的主要缺点是不利于插入或删除操作（ ）0 e; g# F% M: W/ L8 A3 T
A. 错误% R2 N# P6 @5 q# O
B. 正确( j5 F2 {! q& ~0 s3 U4 ~0 `
满分：2 分
1 I) f" _' G, J) q2 {% P13. 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）/ Y* u. y6 ^# V) O5 N5 b
A. 错误
/ G$ `; {* `) R Z5 WB. 正确
9 A) } b4 ? ] U 满分：2 分5 y1 V o% |- G. t0 @- z: ~
14. 二维以上的数组其实是一种特殊的广义表。7 f' x% R8 b% C' _( I
A. 错误
; l0 \, @8 r( R6 fB. 正确8 `( u) T: A: Z, E6 p5 E4 N5 J
满分：2 分) \4 W0 D8 d0 P) o* Z1 h
15. 折半查找法的查找速度一定比顺序查找法快
2 p) z& ~4 w+ V, X0 W" T7 kA. 错误
( l* c% n/ Q* g5 ], O$ Y8 p" fB. 正确6 P6 C- {- @- t1 U6 z2 s4 L
满分：2 分
$ y$ j6 Z3 D z' Q$ s$ W& t8 B16. 用树的前序遍历和中序遍历可以导出树的后序遍历。
; f! }7 W" c, q/ `. AA. 错误
3 F5 H6 }& t3 [ h# Z+ a+ z, DB. 正确. S$ b! ?7 u8 E3 i
满分：2 分1 Y& z6 {& `$ f/ T. w$ R* T
17. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止8 x% [( @. g7 y4 ^
A. 错误4 C, g: I$ f. Q* O+ O
B. 正确
5 l- o9 r: N! U. O5 ~: x* } 满分：2 分( b' Y; _8 P) W
18. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.1 L- p) S3 l. \" Q2 {7 x0 q
A. 错误
2 R& y* M% Q$ G3 |B. 正确; N& i+ f* z: A% r$ r, m
满分：2 分. G, \; M7 T- o0 [# @) j
19. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止（ ）
0 k3 d% x x# h" sA. 错误/ z" [1 Q% R% a% H7 q6 ~. B
B. 正确
/ D- `: [! C$ I" m 满分：2 分0 C* ~6 i( R3 k0 D
20. 栈是实现过程和函数等子程序所必需的结构（ ）# A# W5 I; \/ B/ ~* n% P' h
A. 错误
+ U( u$ O5 g5 D F$ A$ QB. 正确
( x# L( M% S4 P* { 满分：2 分
6 }+ O2 T7 w! s, i" X3 z% Y2 u6 ^0 z$ C
三、多选题（共 5 道试题，共 10 分。）V 1. 下述哪些不是顺序存储结构的优点？（ ）
. W) u5 Y; ^' z7 A0 | |' wA. 存储密度大& s$ N$ o# o* G3 \
B. 插入运算方便/ {3 P" v7 J; l B# {4 `
C. 删除运算方便
8 k; U7 g# @5 |8 J, z# ?D. 可方便地用于各种逻辑结构的存储表示
( G r* h1 K( ^3 A 满分：2 分
+ Y- @! ~) T! n2. 在下列情况中，不能为二叉树的是（ ）
, S7 T: S" I3 x' NA. 每个结点至多有两棵子树的树' i2 s: y y3 o9 [: g2 ^: Q
B. 哈夫曼树0 v4 C( j0 M- e* I) s; |( {
C. 每个结点至多有两棵子树的有序树# J: m& B5 i0 f8 G3 @$ K& I
D. 每个结点只有一棵右子树
/ i; P" c0 W! L( Y) L 满分：2 分
2 z8 ~1 V1 \' O. e3. 有关二叉树下列说法不正确的是（ ）
7 }. ~( j0 P+ F6 r ~A. 二叉树的度为2
, G( R1 K! }% G. y, _B. 一棵二叉树的度可以小于2% v6 V# n6 p" j0 `- u; Y+ d
C. 二叉树中至少有一个结点的度为2/ E- q3 I" Y+ G& E: @
D. 二叉树中任何一个结点的度都为2
% @5 |2 D `. }& V 满分：2 分
: [" O y& C# P# w4. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）9 X9 ~" C5 q: I- u( J. D, D/ {
A. a，c，b，d
. D! S1 r T' `$ F, m, J: HB. b, c，d，a
8 t9 h; y$ l+ [0 a9 ~. y+ EC. c, d，b, a9 b# ^* B2 r% b2 _, B, i
D. d, c，a，b+ K# u6 B# w1 ?6 {# h9 k% g
满分：2 分
, h# t# n! x. ?, Q5. 下面几个符号串编码集合中，是前缀编码的是（ ）
; a* l( \0 b. kA. {0,10,110,1111}& }& z" n5 C& P h$ `' h! x4 D
B. {11,10,001,101,0001}/ J0 ?* n: }: H0 k+ u* N9 j
C. {00,010,0110,1000}
: P6 Q' Y. [ m1 E6 ~' W* fD. {b,c,aa,ac,aba,abb,abc}
1 P: F8 ]( z% D) O4 R* Z8 y" W( N 满分：2 分 * N, u! b$ S! e
# d, I3 j$ ~# l( t+ E! n
谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。 |
|
IP卡
狗仔卡
发表于 2014-10-20 22:36:38
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
