|
|
谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。0 a- R: M) a/ N* H+ U4 b5 ]
* v6 x( N9 F- V+ ^% b
/ t( K( a( P8 ~ A }3 A. c" w6 r一、单选题（共 20 道试题，共 40 分。）V 1. 任何一个无向连通图的最小生成树()
b5 r9 t8 [' ^$ |% I- g; @A. 只有一棵
8 W' |! g& h' T& DB. 一棵或多棵
- f5 V6 M, q8 m8 ~, a: ?% PC. 一定有多棵
2 r# Z+ j! y1 E1 {D. 可能不存在! L# z& @% ?* x' b
满分：2 分
( Z7 I2 V) m5 N4 x2 ~5 |- E2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
9 }8 J# s% J% G, P1 EA. 8
5 N) w6 P. |! U; |B. 63.5, F. q2 K% v. V' W7 L- y
C. 63
9 ~, o9 M- T5 d9 G& s8 ^D. 70 ]# f) D' Q ]( l" s+ z
满分：2 分
\4 c# j) S: t3 p) {0 L3. 链表是一种采用 存储结构存储的线性表3 S/ H4 ]' L, p
A. 顺序
3 |: \3 I; {. D o3 _+ PB. 链式# V4 Y+ m) D) C/ i" T
C. 星式2 X% I- a" P# a' `. [* N/ x
D. 网状
4 D$ U. s" h; w) a+ ?% B 满分：2 分, Y; C( v, ^ H6 J4 r# R
4. 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()! _/ v2 I9 e7 J* {
A. O(n)
: b0 j, q$ u. E! H uB. O(n2)
" M7 U: W% s% x. x' y. WC. O(nlog2n)
9 g& x7 @! m) g/ S) ^) N. S, YD. O(n3)9 t. O2 f. g" K, I7 V' A
满分：2 分
/ N s( C5 h; c; q4 I1 R" _5. 下述几种排序方法中，要求内存最大的是()2 f9 d* p4 ?* B9 `6 U) `3 b" j% X
A. 插入排序3 B2 [2 v) V+ s8 Z* D! C2 d) u; P
B. 快速排序9 U3 p# d# q# X" z+ N7 r
C. 归并排序& P6 J7 I2 L; E5 j
D. 选择排序
% D) Q* }6 z. D& r" w 满分：2 分
, W f7 N5 g3 e. ~/ i6. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）' U. {- N) [% X$ c+ A0 R% d' }
A. i. f2 b W6 k( U+ s1 g; M
B. n=i7 S* ^5 t1 U7 p P7 Q* |9 l m
C. n-i+17 W& ]" A9 M- V# n
D. 不确定
5 B. @0 s8 P6 t3 G5 x9 b( V 满分：2 分$ V# `, e% R/ }. g
7. 将5个不同的数据进行排序，至多需要比较()次
4 m, E" F; [# K, _; i6 N9 o6 uA. 8- ]8 o- g% t& w6 ?- X- p
B. 9: ]) l( e& e4 ^0 Q3 Y
C. 102 o. r; s1 b( T
D. 254 W+ W n7 f3 a1 L
满分：2 分6 ~' n6 D R) g& i; h% c
8. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
% s5 R4 ]" Q2 ?A.
" Z, [1 Y9 P' m% ]7 @/ NB.
3 r) U1 T' `9 d: P1 ^- c( [: tC.
; j" A3 l% m$ L2 k: H8 C; zD.
- U/ k9 B* w. j! Y% @- @ 满分：2 分
1 c! v' `! N: `/ {4 m: `; M9. 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为1 A5 k* F j& W( B$ S
A. 38,40,46,56,79,84' f" ^7 Q7 q, E! b
B. 40,38,46,79,56,84
1 F8 z3 m5 C/ s5 o' nC. 40,38，46,56,79,84" b m: ~6 t6 a5 R8 F; h- F
D. 40,38,46,84,56,79
, {0 K6 A+ |5 W: U 满分：2 分
3 M& G( l+ H1 Y8 @, V8 ?$ R10. 线性表Ｌ在（）情况下适用于使用链式结构实现。3 q4 D# z6 {7 F( L
A. 需经常修改Ｌ中的结点值! @. ?# L9 g5 d3 U& z) E/ @9 F. G3 V5 I
B. 需不断对Ｌ进行删除插入1 m$ W/ M0 Y# t
C. Ｌ中含有大量的结点 t% J; W8 J* U3 H! y6 i: e5 F
D. Ｌ中结点结构复杂
" R' O, B" u& o% B% s 满分：2 分
6 m- V! [1 n: s- n( X* ~3 Y4 q11. 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为% g k$ R0 Y, j' S+ o0 V: m
A. r－f$ z; F# z7 O8 D+ o' O
B. （n＋f－r）% n
# Q. O& p9 W, bC. n＋r－f
' B! i1 V% ~, b( B3 P% i, c8 {D. （n＋r－f）% n
6 c2 o4 J0 s& w& M6 ` 满分：2 分: P# T; Q3 H( C$ c
12. 在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）
: e' ], n& ?0 T& D. i2 a, t/ mA. ＡＳＬ＝ｎ& U! X5 S$ s- Q. ^4 K" @ T
B. ＡＳＬ＝（ｎ＋１）／２
7 j i+ I: F& e7 WC.
- _) H: r0 H7 b2 c2 Y' ~1 w/ X5 GD. ' }, m5 I7 {5 f! u0 o, \3 n+ I
满分：2 分
6 r2 X, P( @" j$ ~$ j) d13. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。% l9 E) P8 c" P
A. 1/2
: Z: r! ?5 }5 eB. 1
$ C5 ?# k% I) \0 eC. 24 j7 i" M' y/ M9 ~1 d/ s) D
D. 4- L: o* Y" G2 `2 S
满分：2 分6 {/ j# M6 u) J$ l
14. 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()2 y! E. ]( ~% A# p8 G4 p0 }
A. 从小到大排列好的7 z; N* @& \/ j; z8 W* k
B. 从大到小排列好的( n* b. P. A* s0 l3 s+ f
C. 元素无序1 k6 {8 M# G% _: U9 @
D. 元素基本有序
4 [0 I, Q& u% X5 g 满分：2 分. y/ S1 w$ |5 I/ T0 `$ |) B
15. 单链表的存储密度（）$ _3 O% K# L9 N9 O" N
A. 大于15 U0 [ {0 T2 V; L
B. 等于1
) K2 v/ Y6 s9 M3 \( N3 i; QC. 小于1
" s5 \' J8 S3 z9 \% J- OD. 不能确定
8 g+ b! V% O, ]+ u( g3 ?9 W 满分：2 分
4 o, X3 _* h" | p8 i5 i16. 堆的形状是一棵()6 m3 Z) \5 H6 x# s7 `
A. 二叉排序树
' K9 N& C& N5 N5 S0 `B. 满二叉树9 d2 S& P Z7 B' X2 [) F) a
C. 完全二叉树
. t* o' T# \% p/ VD. 平衡二叉树: {, P" v: s# D6 p. P
满分：2 分
3 b% Y j( F- ?% y7 j4 N17. 栈中元素的进出原则是（）
: b' N# z8 C0 X6 wA. 先进先出
- ^4 e4 `8 x$ G$ `& n. @6 ]& e% L3 C# xB. 后进先出
) }6 t Z8 m/ u5 cC. 栈空则进% \. K, ?+ D6 \: S- \
D. 栈满则出, }% r- {3 P$ n
满分：2 分
; F& J' y' {5 H9 t2 k18. 用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的 r6 O' @# ~0 F4 U
A. 栈
" ?, ^+ v2 O; [ ?B. 队列
+ L% S% ?6 B! j% x5 A* }0 eC. 树) `* f: G! j: l/ J8 V$ F6 Y
D. 图# t; Y' t: c0 `- G( {, r" I- b
满分：2 分) I' V% e7 ^/ \1 N
19. 折半搜索与二叉搜索树的时间性能()
/ i) e* p w" R" n" ^A. 相同
5 V& X# U/ C0 W9 bB. 完全不同 }/ b7 \* `2 o+ m
C. 有时不相同: k; G* X4 t! ]* }" Y9 _. U
D. 数量级都是O（log2n）
' \1 Z5 v( R u( j; ] K 满分：2 分
+ c) t! ^ M: h6 d20. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）0 |/ h1 [* D# ^2 J: Z
A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
7 j4 g* E3 b7 \5 ]1 `" B0 KB. 在第i个结点后插入一个新结点（1≤i≤n）9 V: L. W5 `. l* w: k8 ~& d
C. 删除第i个结点（1≤i≤n）
$ t( w& \% `& k4 qD. 将n个结点从小到大排序3 x& s0 ~+ y4 a8 x& ]
满分：2 分
- m; \4 _4 f: g2 i% m6 U/ l' Q9 C4 P+ u4 Y8 p* o4 [
二、判断题（共 30 道试题，共 60 分。）V 1. 在表结构中最常用的是线性表，栈和队列不太常用。& V! G$ X" L, f7 G
A. 错误 _. Q) v) D5 H1 e/ ], m
B. 正确
5 b! r" R. B* L# C7 e. ` 满分：2 分
9 G4 L/ i0 O% J3 s- W8 P2. 链表的每个结点中都恰好包含一个指针。' C5 L3 q! ^! K8 B
A. 错误
* n, H) U+ y# t& A* _% SB. 正确
2 ]: q3 @* J, I7 Y0 h6 U 满分：2 分% n' n) A: i+ \3 V) j( k9 S
3. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
1 _) u" `6 B0 F3 _; ?0 aA. 错误! v$ H* p, o, w
B. 正确
3 ]5 ?& f* M5 @. ^2 [# j 满分：2 分5 r( a5 k: U' A# N. T
4. 链表的物理存储结构具有同链表一样的顺序。: }2 h) F$ K6 m+ ]
A. 错误
- U n0 E# v! s& h* H: B) FB. 正确- Z0 {* |/ k$ `& w; o
满分：2 分4 c- U9 ^5 S5 ?/ E& J/ P9 b, B9 p
5. 二叉树中每个结点有两棵非空子树或有两棵空子树。
* k* ?, d, w2 j5 e! O6 G" s0 kA. 错误
4 |+ I T% r: U9 i/ d. @, X5 @B. 正确0 B+ B- [8 R% }, N$ s) i
满分：2 分
# S' n5 s. _/ C; K" N. K! k W6. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。" ^2 d) Z) H7 y% h8 {, {2 v$ W! ^
A. 错误( K* X( u4 f, N* C
B. 正确
0 Y0 N" H2 l+ d' ]7 o# p3 p8 T 满分：2 分+ h4 G3 s' G( T
7. 二叉树中所有结点个数是2k-1-1，其中k是树的深度。
& O! M5 m1 K) K" PA. 错误
# g( l/ m! T0 f" m, r' t- HB. 正确
_- \+ E9 V- H5 H& C 满分：2 分
6 Z9 D0 k1 _1 m3 \; A8. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。) Y3 k" @7 Y/ H% m) H3 Z" \) Z
A. 错误 E+ D- Q* _- `/ }9 W! C/ l- w' a) {
B. 正确 Q1 N% ~6 q: |/ r' v0 J# D, E
满分：2 分
/ [- w+ z' ~$ R$ r9 E9. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
+ o1 ?& s! n: M% qA. 错误% N W7 K& p" s& |6 n1 z, v; O3 C
B. 正确
; y- P! H& ^1 X5 f, f% j 满分：2 分) v0 L$ \* e/ Y' D) s/ k% [& B6 R" _
10. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。. a; \% T$ o! q: f
A. 错误. @" }0 l, N1 L( A* M
B. 正确
6 S& ^* Q1 A8 \% |2 r$ B 满分：2 分4 a4 ~# X, T' N& @* V
11. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
% R( e* _/ h1 i# H+ }- D ?2 _1 {A. 错误) Z# z( c6 A" y1 ^& U- `
B. 正确9 d6 p! g, `+ _5 t" c5 p* o
满分：2 分" }0 s! m) [* x: ~- h- W
12. 具有12个结点的完全二叉树有5个度为2的结点。
+ s$ \1 L- z! q% r5 p- K; \1 G9 hA. 错误
p1 Q" U7 ]6 a' l6 i' PB. 正确
* Y8 _. i% d! T! X$ @5 |. c& n 满分：2 分
# F" M- S9 b+ K. u4 X5 x$ }13. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
) L5 {( p8 w$ ^A. 错误6 ]; W" p9 d9 O' G. C/ H
B. 正确( D* N! Y: G2 m8 L" J
满分：2 分
' X/ _1 Z) ?; [" N14. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
- W2 q% w4 I2 fA. 错误
2 s! w' k7 H% S+ N7 pB. 正确& e1 u: Q* _5 [$ S
满分：2 分1 y( U9 g; E! o, n! J
15. 顺序存储方式只能用于存储线性结构。
- f9 p# J: j! r* Y, e9 a: e* tA. 错误
+ C B8 Q4 ?' o# [' \1 H l6 zB. 正确7 S6 t: s6 T3 m( J
满分：2 分
, h Z2 J7 d/ s+ H0 e16. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。" e E5 W$ ]4 ]4 N! q) l
A. 错误; r5 B5 w# b N/ u4 V R/ r2 G
B. 正确
* O& Q1 v7 @% q* o+ H 满分：2 分* b! M% O# h7 R1 V5 }. L- ?
17. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。0 l! w9 ?5 h) `: d9 P
A. 错误
+ k# l# k! c6 Z% @0 NB. 正确
" H" t4 I/ i. V 满分：2 分
5 v1 n K* h) y |7 r18. 线性表的逻辑顺序与存储顺序总是一致的。
- [4 J& a# A8 y; a8 U3 FA. 错误3 Y: w3 e( D) h: W7 j, \
B. 正确7 L: G( n2 x- u1 B. R7 H! _0 i0 [
满分：2 分
3 b3 w: a* J" }+ Z# Y2 a1 X19. 线性表在物理存储空间中也一定是连续的。! I' {( I& x% q8 e. F
A. 错误8 F$ x0 k; ]7 l, Q$ w
B. 正确
9 B# i2 S: t `; ~' \ 满分：2 分$ P# q: ]+ p) X! o& i
20. 栈和队列的存储方式既可是顺序方式，也可是链接方式。
0 _5 ?# U( b3 s1 w6 L8 CA. 错误
) s* o6 Q: o6 b: p8 I+ w. _4 X# y5 cB. 正确( F, X7 H+ f7 t5 e. |. l3 y
满分：2 分" @) x6 I7 f$ P: A* p
21. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。) M& j& }* D1 ^; y
A. 错误
7 c; Z$ O# {( _* r0 e* rB. 正确
) i' J/ C4 o( z; a 满分：2 分
0 j7 H# k1 V B! d) P22. 二叉树中每个结点的两棵子树是有序的。
% a7 J, U6 X( n; {8 f, V8 TA. 错误
. x: A! y6 A H2 G" O$ QB. 正确) t8 v; i# L% ^) t$ m
满分：2 分
/ M2 y* K9 V- \& b3 G. \23. 栈和链表是两种不同的数据结构。
$ U7 q3 n! z9 s- qA. 错误
# x! M# J6 w8 W6 q! p+ kB. 正确! F f7 y* {" G6 M; }
满分：2 分4 o" G8 ?" ~2 b9 [& M- p1 F
24. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
3 J0 Z. v& _3 ] a, FA. 错误) z6 v- e) O6 [: @% h
B. 正确3 b! o9 _2 C0 r+ G2 ~
满分：2 分
# ~7 B+ \: G7 K; t25. 二叉树中每个结点的两棵子树的高度差等于1。, g( h, W3 c2 ~/ U; X7 R
A. 错误
B. [* K6 J# d& kB. 正确
7 b1 r; A! ^4 ? 满分：2 分) K0 P/ N# }/ j- y
26. 栈和队列是一种非线性数据结构。! L5 i. _" Y5 w/ z# C; p6 F! r
A. 错误
2 F- y! Z, M9 g/ r- i* j/ ?, Y5 TB. 正确
) Z& o8 M0 K9 J! }) l3 s- C 满分：2 分
; i( S! @0 X% O" } g6 e27. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。6 n1 H& g; }9 \
A. 错误
6 D) R! x& s3 w3 CB. 正确
: U: }" s0 |# E+ S2 B 满分：2 分
9 l& K$ J+ u$ h. y) |" k28. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。) b; O0 z4 P% l) ]& D- p7 @ t
A. 错误
# i% B, p3 b9 `9 x: a9 t3 }B. 正确+ P* m# O( B( Z1 R% w2 m- ~ }* q
满分：2 分
; c# k/ ?* v0 ]7 _, a6 t. o- z) `$ n29. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。% D$ N3 b; [5 p5 r& ^- ^2 ~5 r
A. 错误
' A) l8 z& C$ {, J3 h) M3 kB. 正确
1 t1 w! S2 f$ r* q* g 满分：2 分; p6 I# Q& O0 g4 t3 G1 I
30. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。, L5 }) N5 P- A1 r' k8 i6 @
A. 错误$ F7 Q: i! [$ O+ B( y
B. 正确; X9 \: i2 V* v% b
满分：2 分 3 s' | R$ V9 f$ G) t0 K$ x/ {
* L$ `, `' m7 F# E$ j* N
谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。 |
|
IP卡
狗仔卡
发表于 2014-5-27 22:48:51
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
