|
+ E! t' ^5 f3 Z3 a" G4 b& U: d13春学期《数据结构Ⅱ》在线作业15 B" Y6 |' z- x! ^- V1 J. U
' }& ?7 J4 R* |单选题
% F; x# P6 D8 _$ \6 X0 h$ |) _" z9 i; S
% a$ H0 }2 Q9 C6 H一、单选题(共 20 道试题,共 100 分。)
, h# k* A- q' h1. 5 O9 {! K- ]6 u1 c/ b- V
在分块索引的在顺序表中查找,算法中采用的最佳技术是. Y/ C1 @& h2 P( h
A. / J9 @: |4 @6 c' h- O
穷举法 3 ?, [& Y q) n1 ?9 @
B. 0 p6 Y3 @! i" M- E: G
贪心法 $ { L6 v; @) P P; z
C. 6 |# u/ M) W* W, o5 g7 v5 P
分治法 1 \0 }. j" ]. l- V, b0 q
D. 1 K/ n3 y t K8 \5 U
分支限界法
+ [$ C+ P; C: G! q* j, X1 ]% K-----------------选择:A + w7 D @8 w h4 W- z5 {9 } u
2. " ]2 u7 X+ d' a8 Z( w! I6 n
若要在单链表中的结点p之后插入一个结点s,则应执行的语句是
1 m( y& d% j/ j! y& o$ V 8 g3 Z$ ~9 ^5 [) G
A. s->next=p->next; p->next=s;
4 p3 W+ |, I P: h$ OB. p->next=s; s->next=p->next;
5 [1 g( c+ k8 H
+ l1 c4 ~% i6 v( HC. : h4 t! r- @" ?* T, r
p->next=s->next; s->next=p;
8 @# e3 q, S2 l! mD. 8 F3 Y( ]. U5 Y" a/ X
s->next=p; p->next=s->next;
" A* G# ~$ b. B2 a G-----------------选择:A + f4 F8 E: L+ A% H5 \ |
3. ! g% p4 T, S0 B& j8 W1 c4 m7 e
下面说法错误的是
4 f. b# d* k3 o: g& [# n, a (1)算法原地工作的含义是指不需要任何额外的辅助空间( l8 |3 p! E3 v8 t. [
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 % w5 l% i0 Y' L0 h
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界: U- F3 v" B |+ S7 y0 B3 X {5 I
(4)同一个算法,实现语言的级别越高,执行效率就越低2 E# P/ n7 Z' z! [: b `! c
A.
* b6 X# c0 s" ] V+ b! P; W, P (1) 2 m6 b' E, q" G3 E7 x: }/ e7 p/ K
B. ! C$ N W/ M- N+ b" ?, X3 I1 A6 z
(1),(2) ) `. c+ W# W Z; F1 {5 F5 d# d" s
C.
. |+ M1 {& Z2 ]3 A2 c6 q (1),(4) % p$ X& B( V* N* B% `( z
D.
3 y1 c* b/ z' I2 Q! @ (3)+ k0 f6 l# j: ^
-----------------选择:C 2 m& w$ i0 j6 S0 e. ~( p t: s
4. ) A* y; C# K7 c% P9 ]
某带头结点的单链表的头指针为head,判定该链表为非空的条件是' G/ u8 [4 f, a) V
! q8 M6 x. G( ~1 G: d9 LA. head==NULL # T1 _9 m9 }! {/ S
B. head->next==NULL
! ~/ M$ C& q2 [' E, F. g" f0 c
: W2 r7 s7 o# a& B, @8 c1 nC.
9 \3 R7 S& M% P1 mhead!=NULL 5 ^" G% p. |/ \ ?. Y6 t
D. head->next!=NULL
. ~% |! o( S0 i3 W) J-----------------选择:B ) `! [# }/ w5 `& d
5.
, s+ {! Q( T0 g. _3 J) n. P9 h在对n个关键字进行直接选择排序的过程中,每一趟都要从无序区选出最小关键字元素,则在进行第i趟排序之前,无序区中关键字元素的个数为* R9 b: D# Q2 h: y6 X" l
A. ' b" B/ b, B/ @/ U
i / {/ o' w; Q7 F- Z8 |) ]
B. , B/ L& L5 h$ g! j4 m
i+1$ t$ T3 C& g$ ~7 g' B' [
C. ! [/ s' Z% h/ a# A7 M+ _9 R
n-i
. @/ X) v- s. i9 Y0 d3 BD. . U5 |4 Y( [) e1 w! X0 ]/ m
n-i+1
1 l& ]3 w; I6 H' n-----------------选择:D ( N, t3 I4 ]9 T0 G7 ^) b
6.
8 C* ]0 X( W; ^3 }( f* \3 T已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是8 H9 N; G* o6 f9 F/ E' E; x* l4 q! u
A.
" R* i& v, d) E& u. J.{25,36,48,72,23,40,79,82,16,35}
) c2 l$ R* D/ m$ J7 y4 K. u$ NB. 3 W) R" O/ O6 k1 e$ g
.{25,36,48,72,16,23,40,79,82,35}9 ~# T. Q; @9 _ ^5 _9 ^* u
C. . |2 r9 d, Y) K2 K x# @
.{25,36,48,72,16,23,35,40,79,82}
, g1 ~, a, D" o+ J K" cD.
1 I3 a5 q8 t) ?* F0 a! n.{16,23,25,35,36,40,48,72,79,82}
" E- ?4 x9 n9 B5 I8 Z. \% |-----------------选择:D
; c- n* t4 Q, H5 l* K/ B" a( ?3 W7.
$ y/ S% t- U5 }在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为
. q5 n, i6 @& J
, i& ]* }/ m5 RA. n-i+1
' |7 d" r# H9 L; e( J2 _3 U2 \B. i
, J7 ] @3 u1 Y: }* q0 b
- _& ]; T+ a, |# f. EC. i+1
9 X, |1 r3 ~4 X S1 Z) cD. n-i' s R8 \" Z) }% r0 [8 p6 K
-----------------选择:D
- x0 U, \6 a, ~" w. C8.
4 [' ^+ H4 p: w7 ^+ ^( Q. K( f数据元素及其关系在计算机存储器内的表示,称为数据的
5 |8 x* P$ ?( w6 Y' D
, c. D% G2 H; C% N2 P! aA. 逻辑结构
, E, b1 |' f r, J, O8 oB. 存储结构
$ R7 L) m) S2 p7 ^0 U& w# u
9 {! w' g2 R8 b) l3 ~9 h3 W. iC.
$ X$ P. A3 R) p! _线性结构 . q2 a1 r) p! j4 s' {9 L
D.
8 v! m+ l' y7 X5 X非线性结构: F" _7 }8 N0 \' Z" l' T
-----------------选择:B
6 n: g$ r1 o3 U) s9. ' b9 P9 R( r* M
假设以数组A[m]存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位置为
6 T( g0 G5 z- M; t ( p$ h. l7 |7 j9 i! u
A. (rear-length+m+1)%m
( R( P! P4 ?8 t; q$ } ^- o# lB. (rear-length+m)%m
- L( m9 x" d% E ( M; t! |5 w6 ^* | P G6 u. p8 O
C. 3 c* r* e4 }7 p
(rear-length+m-1)%m ( F( `. G- B/ q* F. b+ o5 j$ _$ r
D.
1 p* [. R2 d3 s7 M(rear-length)%m
) k: }- L2 Q y0 ^# S" X-----------------选择:B
2 ` @- p2 R9 M10. ; i% E. L9 p+ P
在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为- E0 o* {" _& |6 d
A. 7 O: S1 v4 a$ Z$ C
O(n)
' g# j, _$ ~; N5 h9 |. lB.
; m& q: F- X8 ]9 v9 F0 b O(n+e)
* c" R# `( ]. g$ b, J" kC. ' f9 u6 t; t( m# c5 W8 X6 J1 I: A
O(n2) 2 b2 L( _' v! O8 H! S
D. 1 y; y( x$ [" [* H
O(n3)
3 I- V- j; a7 Q* |+ M' a+ N' K-----------------选择:B $ M% t) G9 x e1 F
11. " \/ A3 T* d! }* d( z: d
在按层次遍历二叉树的算法中,需要借助的辅助数据结构是6 \% _/ Y! X: j3 B. G9 `
' J# ^# _9 F, T5 E& o; Z) y2 m
A. 队列 7 r* c/ a# q9 |7 P* F5 z& _
B. 栈
, W# B+ o. r& H* e' y! r. n
5 L5 c; q+ c# a! B: IC. 线性表 $ R9 W; L& v! |8 j: {
D. 0 _& \* [- h5 o+ s8 f- P) R
有序表
, [5 {6 }, w8 b* O! |' U-----------------选择: , w" D5 O8 v5 o6 C E
12.
7 I- e& d5 D" ~! T. E* S6 t三维数组A[4][5][6]按行优先存储方法存储在内存中,若每个元素占2个存储单元,且数组中第一个元素的存 储地址为120,则元素A[3][4][5]的存储地址为
7 f; `) @5 y& Z; h7 g" b 2 N! p: R' k) a9 N
A. 356
\; G! Z% V' ZB. 358
0 U9 t. m9 a" m; a4 RC. 3608 W3 x9 R4 U+ \3 n1 o4 p% e+ X
D. 362
$ k" A. h0 R; H) }$ |-----------------选择: 0 S$ B P, H1 M$ [% q
13.
5 e9 b. |+ V* i4 y# D7 r! F. W能进行二分查找的线性表,必须以3 A N8 Y5 w T2 M9 B
; Z6 m2 n3 w) k$ g, w+ \1 g; nA. 顺序方式存储,且元素按关键字有序 + O: l) J9 z4 V1 r O. m' w e
' ?9 W! l9 e c1 g) O
B. 4 A/ u" v `) L; v% ]2 B7 c) q
链式方式存储,且元素按关键字有序
7 V* L& c; S1 ~7 Z3 R
( l% f& F! ?) n, |5 X7 XC. : a- x* ~1 \# f F6 t7 D
顺序方式存储,且元素按关键字分块有序/ E( y+ D9 Y0 K* i) a
, b& _ I) F3 A4 bD. 9 b; a4 _5 \! I0 s4 x
链式方式存储,且元素按关键字分块有序$ h8 d% _3 P9 ^# R2 h
-----------------选择: . N }/ k" k5 F, K1 F4 X* \& D4 i
14.
+ \8 q+ X, Z6 e8 k; B) T2 Y# f对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为
/ g% Y. U! G; Q8 Z0 \' QA. 3 M- M. W( x8 ^! B0 |6 Q) ~; w" F' X
(19,23,56,34,78,67,88,92) ; o# j: K/ `3 {" S. V q5 P
B. / I9 Z( W" d3 W( A: V; z0 x: c
(23,56,78,66,88,92,19,34)
3 i( m3 f0 g7 z% q7 J: w% _* f; r9 iC.
# X' G+ B* c# m) k(19,23,34,56,67,78,88,92) 0 r1 i$ C& T2 o, d- J
D.
7 _2 T5 S3 G0 @+ N4 o5 M (19,23,67,56,34,78,92,88)6 a# R# }, W4 i! E8 M2 y
-----------------选择: ) `9 s# `, @: F* P' s7 N: e3 r
15. # F3 y+ U3 C" n8 z% Q' B7 w
用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为
0 d; I6 x8 J' \, y/ |" I c+ n5 k3 UA. 5+ p! p" v2 I3 }/ k2 o5 N- C* m& I$ @
B. 6
" x; g4 Z; r0 N5 c& XC. 8
7 l# a, R m8 \# p( l$ r: jD. 9
: G. L: j& H. [1 b-----------------选择: / A3 f, i( T9 a1 @' H1 g% D
16. q# A$ `' P- b: {1 A
下列编码中属于前缀编码的是' [ R/ `$ y. n, s0 w
$ @3 z3 x8 @2 b% l0 R7 l
A. {1,01,000,001}
; f8 H4 n* X) NB. {1,01,011,010}
5 Q7 y- g r2 S + ?4 \% G/ N* R$ R9 i
C.
9 @9 m, H0 ~2 | H3 `; O{0,10,110,11} . r& q8 {/ {4 y2 q1 w* I7 E. O
D. {0,1,00,11}
/ `+ E6 N: m1 }# s- o' ]# |9 Z-----------------选择: ! }1 Q, H4 D3 S- Z
17. 8 n, ~# _; B# ]8 ~; Q
下述哪一条是顺序存储结构的优点
3 `- O: _ G5 m' q LA.
; u& w2 {- O- i# Y2 o2 Q存储密度大 4 Q# U" N& U3 u2 r, k% x
B.
# Y$ K% g' q9 ?+ W3 D. A0 e插入运算方便 2 P$ N* ^. {% X; R9 {
C. 9 I7 I+ }2 O6 h- F& m5 L+ J |
删除运算方便
u3 o- ]7 o QD.
; D. a6 i5 s1 A+ O可方便地用于各种逻辑结构的存储表示
7 S9 T) ~) R+ ^4 z3 v& A-----------------选择: Y+ q5 x3 [9 d. [1 G( C1 B8 g
18.
- E4 b+ W. Y, W7 p) g下面的叙述不正确的是
- s) ]) M+ i1 S9 ~
3 o0 I4 `, c6 mA.
5 Y# p2 t/ C4 [9 E线性表在链式存储时,查找第i个元素的时间同i的值成正比
; x& n/ P7 ^1 b8 Q; w* @8 b Y! GB. 线性表在链式存储时,查找第i个元素的时间同i的值无关
* D# B& y/ d N& T ZC. 线性表在顺序存储时,查找第i个元素的时间同i 的值成反比
' v3 @! C0 f |/ L4 aD. 线性表在顺序存储时,查找第i个元素的时间同i的值无关7 H( l% v/ g( G8 r& p
-----------------选择:
* X- \. l$ |2 m, c19. . q# F# Q- j) c: [) F; M
若采用孩子兄弟链表作为树的存储结构,则树的后序遍历应采用二叉树的- u* E) x0 S% W; M/ b
; a- c; z8 V& s: i% h8 n8 i
A. 层次遍历算法
5 D* j4 T9 ]$ v* mB. 前序遍历算法 ' D u2 v6 ^6 \ B" p7 s9 Q( A
$ D3 o4 y* ~# q3 O7 SC. 4 [# d3 t# Z5 ?+ T
中序遍历算法 % v) U: Z9 z. n9 g) x- e+ b
D. 后序遍历算法! b" g. g8 i5 U' L
-----------------选择: . G3 b- H+ _9 t& [) d
20. 9 W0 h2 X2 s8 y
在平衡二叉树中插入一个结点后引起了不平衡,设最低(最接近于叶子)的不平衡点是A,并已知A的左、右孩子的平衡因子分别为-1和0,则应进行的平衡旋转是
/ w. @/ p+ n6 U5 P4 p) V! N0 a2 X
0 t F8 s, X4 l* c: T7 O6 w; z) _A. LL型
8 Y0 s+ [4 W' S+ T3 N; zB. LR型
- a+ K. [: o. `/ d# k# J9 G3 t$ v4 t, o # Z+ N1 b& x; ]
C. 2 z% f- o; |- G4 `! M$ f, C
RL型
9 b+ @3 K. m; o0 O% H( N& yD. RR型) B8 ]9 [# o! l. C% n( ^6 j' H0 a
-----------------选择:
, K. X$ O- m# b* P2 y# ?+ `& H2 U* G1 G* c2 j$ `
/ B$ A3 H* m- q3 T+ i& N |
|