|
" s& Y4 u- m4 Z, l* H7 M) E《数据结构2264》16春在线作业1/ }4 C9 K' p% _9 s; c+ [0 \7 M
2 K6 P% b$ a9 V5 g, C( o
^- m" p, Y e! C& b. D9 ]
" s- ]# F- o+ ]/ G. v5 i
' ]$ A$ c7 x9 s一、资料来源(谋学网www.mouxue.com)(共 25 道试题,共 50 分。)
" L& V1 b7 O/ A- ^5 T5 \) I! X# Q5 U. C+ H" n1 {
1. 设有一个二维数组[m][n],假设[0][0]存放位置在644,[2][2]存放位置在676,每个元素占一个空间,则[3][3]存放位置在( )。
0 l; a: t e. |) z5 b4 ^9 C/ A: X. 688
! O+ T' ^2 t! o! o/ ?! F. 6781 l" u/ }- O. z! A1 M
. 692# i3 K' Z. V \/ q u U& n3 O
. 696
0 y" r1 Y0 s' l$ y) t0 x H正确资料:6 V+ q/ U+ ~ Y5 ^
2. 假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行( )次探测。; X i/ d1 W9 Q" d# E5 J
. K-1次
% g! K% K N9 r- a: v2 P C1 {. K次3 q, ^: |) ^( u/ _. F1 P5 A
. K+l次. [: y% E( Y( n% t- @% v
. K(K+1)/2次5 s4 Q+ x0 _ s# I
正确资料:
5 g: R4 S# I2 p1 ^+ Q+ U5 H7 Y4 E3. 设Huffmn树的叶子结点数为m,则结点总数为( )。# j \/ A z7 q8 R- @, _4 s
. 2m: Y5 K2 f2 ?8 e; [
. 2m-1! Y. Y r2 \8 p" q+ Y
. 2m+1+ j5 p0 Y2 G5 i; x' Z% j# [
. m+12 D( l9 q# A6 \9 |# [
正确资料:7 Z, [8 j% X% y2 `/ w- O w( T! C6 Y& L
4. 在数据结构中,数据元素可由( )。3 [4 G1 j& ?6 S- w- u- |
. 实体3 }. p$ g! ~7 v2 ]9 e, F5 Y4 @" X d
. 域9 c0 y8 j3 s+ U& @9 K2 G
. 数据项
9 \$ r! d$ G5 \/ V: }$ i' E. 字段
. x6 j2 o( e" [$ N+ n5 N! ~正确资料:! X o1 ~; A% i" ?; \4 T! D
5. 若某二叉树结点的中序遍历的序列为、、、、、F、G,后序遍历的序列为、、、、F、G、。则该二叉树结点的前序遍历的序列为( )。
+ M$ j; u/ S; |1 S- i. 、G、F、、、、
8 j8 J; [% Z3 x% w3 @/ N5 }. 、、G、、F、、
6 W( v# h" f( i. a" L) R. 、、、、、G、F" g0 q6 F0 N' H8 t |! s$ R
. 、G、、、、F、( N" F& T: Z6 ~' _, e
正确资料:
2 ]" V& U `4 _' O& e8 F% p+ J6. 对n个记录进行堆排序,所需要的辅助存储空间为( )。
) ?2 b& {" M- |. O(1og2n
6 m A. e( z" r. O(n): [" k, b( h1 Q5 t h v
. O(1)
( b* j+ A ~1 Z, e) q T. O(n2)- P2 r6 P9 k R* F1 o. j% W, {3 _. [
正确资料:6 R# ]# U: e# {, n& @; E8 ]6 D7 ~5 B
7. 对一个算法的评价,不包括如下( )方面的内容。
' P8 h# x" s& ?. 健壮性和可读性) [% y, Z/ F3 t% J
. 并行性
5 s* n: v- h1 a9 f! k. 正确性' j) m5 n. a& T7 F. N1 z0 r8 F
. 时空复杂度
% o( e7 R* B7 P. B* u正确资料:
4 t. e8 j u/ u {( H8. 已知一个图的顶点集V={1,2,3,4,5,6,7};边集={( )3, ( )5, ( )8, ( )10, ( )6, ( )15, ( )12, ( )9, ( )4, ( )20, ( )18, ( )25},用克鲁斯卡尔算法得到最小生成树,则在最小生成树中依次得到的各条边为( )。* `* ~0 W0 P. D5 c- Y1 P+ I
. (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20% \% X/ S. V# |* ` v$ G V1 V1 J4 d
. (1,2)3, (4,6)4, (1,3)5, (2,3)6, (1,4)8, (3,6)9
6 z8 E/ ^: \" x2 ?. (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20) |, G) @ G+ c8 e' p0 h
. (1,2)3, (1,3)5, (1,4)8, (2,5)10, (4,6)4, (4,7)20
. v& Z- e! Q7 `6 O. {" u4 r正确资料:
2 i7 A: Y2 q1 S4 k9. k层( )二叉树的结点总数最多为( )。
' M" d, y4 \. `2 `7 R; Z. 2k-1
6 a/ a8 l& v" V( ~7 N1 A5 l6 T. 2K+1
1 k, ^7 v9 b l, u' V. 2K-17 k: @+ ~0 m1 ?+ W) O/ N+ G
. 2k-1' l R, L! f( |2 w" D( x# g
正确资料:
6 t( b1 c; {- u+ W6 V5 h" `# G10. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( )。& o& z. K! P7 Q+ M
. 2 3 1; h7 V! J1 m E0 X- f5 u/ K
. 3 2 12 Y1 F% L" |0 w1 |/ l
. 3 1 25 _3 ^6 ^9 v) ^3 u2 e6 R
. 1 2 3
) P( {" i: R3 F/ R+ o* v正确资料:
" D( g6 x, |0 R4 o J1 c- ^( E11. 含有10个结点的二叉树中,度为0的结点数为4,则度为2的点数为( )。
9 Z; n% C. G7 J+ J3 i1 c. 3. ~& B8 O# \$ B" w6 R% d
. 4; J0 [8 ?& j: b7 n
. 5, D# O, }. V8 l, D
. 6/ T; ~, k9 h9 [
正确资料:' I( j' E# c$ f
12. 如表r有100000个元素,前99999个元素递增有序,则采用( )方法比较次数较少。8 H9 z1 N: A% f2 ]% z: P5 J
. 直接插入排序
1 R3 K: u7 l1 D* t. 快速排序* a Q# X5 h2 A1 H% c2 c- I6 Q6 j
. 归并排序4 Q9 u, z/ D( V1 F
. 选择排序
. p6 I4 i7 Y3 o: m4 u正确资料:
) z: a; ~ E, x) V/ U7 m13. 对一棵有100个结点的完全二叉树按层编号,根结点编号为1,则编号为49的结点的父结点的编号为( )。
; H2 s$ x2 A4 X# c) w; e; P. 24
+ }/ }' D& P6 ^5 A3 E. 5) t. S% {% y$ D3 h* w* x- F
. 98" n* A& ]( E, O
. 99+ [5 S5 E3 A, s1 W6 R
正确资料:2 Q' _+ r0 v# c! k
14. 对线性表,在下列哪种情况下应当采用链表表示?( ); X- N" t) P" L" D; q
. 经常需要随机地存取元素& m( D* w M7 p" ~
. 经常需要进行插入和删除操作
8 t1 _; r) ~. N. _# V% J0 h+ L. 表中元素需要占据一片连续的存储空间
' d! i: c$ P5 p7 i6 G. 表中元素的个数不变( J! \$ D0 S, G: n+ m1 \5 `
正确资料:' D; B7 d, J# r' ^
15. 中缀表达式2+X*( )的后缀形式是( )。
& \7 B) X- k6 U$ z( o9 B" @. 3 Y X 2 + * +$ y& h# ^$ w3 {* z
. Y 3 + X * 2 +/ D7 ~ ?# ?; @& Q
. 2 X Y 3 * + +
. o5 p5 n' _( Y/ Q. @6 p& @' q. 2 X Y 3 + * +
" @- _, ?# f) ^8 M: c) q正确资料:
+ x ?' H1 B, R1 S: j, u16. 在对n个关键字进行直接选择排序的过程中,每一趟都要从无序区选出最小关键字元素,则在进行第i趟排序之前,无序区中元素的个数为( )。2 {% n- ^: ~, {$ P E& z, I! e
. i
& B0 p6 ^1 \/ {8 R. i+1
8 g# F2 ^ B2 W. n-i1 v$ L& Y+ E: C' t0 B# E
. n-i+1
8 f+ f$ k& p1 g6 s正确资料:
" y% l$ [' m$ ~; L$ d0 ^4 c17. 队列的特点是( )。: c' ~4 X- z6 E% ~5 a6 n$ B" i
. 先进后出
! ?: t; q9 S- |. 先进先出 w4 [& E* n6 l/ i2 R
. 任意位置进出
. _! F! y& D# n( q. 前面都不正确% i6 N/ N- n# Y/ V& m" C
正确资料:1 `3 o: F8 [% ?" {0 l
18. 对于线性表( )进行散列存储时,若选用H( )=K % 9作为散列函数,则散列地址为1的元素有( )个。+ `% Y" K0 f5 R, i6 g+ Y
. 1
: T! T1 Q) H9 L6 [2 o. 2) ~: i! ?, Q. S
. 3
0 e6 q2 u# Z H: n% j1 ]. 47 T, t4 ?3 ]0 x1 n& l
正确资料:5 A1 v+ C- J/ p
19. 若有18个元素的有序表存放在一维数组[19]中,第一个元素放[1]中,现进行二分查找,则查找[3]的比较序列的下标依次为( )。& ^' X. V# }5 ~5 G2 C S# J
. 1,2,37 o9 `- ?+ k8 U; r
. 9,5,2,3+ R. Z- m3 q5 Y2 S% S
. 9,5,3
. I2 ~% b/ Y" d$ C7 {: Y5 h. 9,4,2,3
9 Y( T8 \4 ]$ M3 d正确资料:
+ B2 ^0 r4 B+ ?, J+ Y20. 以下数据结构中哪一个是非线性结构?( ): X4 P7 u$ y& s5 ~
. 队列2 m' g4 F- Y' m; u+ ^. h$ T9 x
. 栈
0 Z- e" u6 G$ |* H) A) j. 线性表& O$ B% {0 `8 w8 d: F8 w
. 二叉树
* X0 W7 h. j3 }正确资料:$ A7 l, {' C& z: Z% V1 D+ d( ~
21. 采用开放定址法处理散列表的冲突时,其平均查找长度( )。% ?9 V8 `! K+ T; @7 H
. 低于链接法处理冲突
& X$ x6 l; l5 F8 ^& b3 v/ |. 高于链接法处理冲突
K8 z4 n* H5 g% Y. a8 [* P- ?/ y. 与链接法处理冲突相同8 Z/ l1 A( G; @- ~6 ] g9 u. Z
. 高于二分查找
/ \( }, P( W6 t8 q正确资料:
) V8 o. V: _ y! [( F22. 若有序表为( ),则在二分查找关键字的过程中,先后进行比较的关键字依次为( )。* L2 \1 y+ g$ O3 U+ V
. f,,/ ^1 J7 E/ j. N2 ~
. f,,: s) S7 X- ~1 V# h
. g,,
8 a6 X3 m4 y# L% p2 j1 J& e. g,,
# u& V( c# w0 F* K9 `+ Y1 U正确资料:
4 a& `# W6 x1 r1 u# |( W23. 从一个长度为n的顺序表中删除第i个元素( )时,需向前移动的元素个数是( )。
: ~! z e! D- |: i. m. n-i
1 Y0 e j- V( R8 l. n-i+1
! y( d, n! T: e2 M1 t. n-i-1, q9 J" Z& ^3 z6 X- I0 p
. i
" a) g% k# y4 B! U8 v/ x, _正确资料:% |. A: _; A q* ]
24. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。2 k0 k' z8 e" c$ G$ j1 }
. 53 O7 H1 y, _$ |4 _: y( M) @ ~
. 6% |* @% @2 N2 p
. 7
8 X/ [/ r! k' A4 d: U8 i4 ?. 8( g' a4 |( D! s6 o* y# v
正确资料:
, V s/ \" P# m2 }% A3 X& K8 U25. 从L=( ),( ))中,取出nn元素的表达式为( )。% q$ \9 ~* e v% e" R4 Y, y D, Q& S
. h(til(L))
I4 w- x2 x0 r* L" o) V9 U5 G. h(h(til(L)))
0 o& e+ ^9 t1 U3 D6 o. til(h(til(L)))* G2 t, N2 }9 H/ R
. h(til(h(til(L))))
8 Y% m, l! ~! n正确资料:9 @9 ^9 r# @6 f% `0 o' z( }2 |7 N
, I9 e; V( ^% z2 `
# O d2 t2 E; q. o
5 M/ Y+ F0 ]2 w9 V: V2 |# j《数据结构2264》16春在线作业1
2 e7 L! {+ o, O7 M2 w0 }3 ]
o+ Y( w2 N( {8 K. ?4 H3 W6 V D+ l. I3 I" A1 Y
" t* B1 A& C% s& E! B/ w' y8 h3 e/ R
1 T) z4 E( d+ ~+ |9 U8 a二、资料来源(谋学网www.mouxue.com)(共 4 道试题,共 20 分。)
" E8 y3 A9 w6 A$ @+ O/ j B, `' m5 ~+ f/ @/ b
1. 以下序列中,是堆( )的有( )。4 n* t9 i# f h- y% B. }
. {15,26,38,49,27,51,39,62}* k. F/ k0 ?% \# e# N/ I6 {
. {15,23,71,94,72,68,26,73}) [! m+ \8 }4 b. @0 U
. {15,27,26,49,38,62,39,51}7 j, O. v- R8 J
. {15,23,26,68,94,72,71,73}
" m8 x" d3 l% y/ G3 i k. {94,72,73,26,71,23,68,15}
3 e h s' k7 Z9 W) c% n) Y9 x+ x正确资料:
( w B! h, z/ h2. 对一个算法的评价,主要包括如下( )方面的内容。. t9 @7 i+ a( Z' y- N
. 健壮性和可读性8 a- _& \! |; \5 O" _1 P
. 并行性; \% x& Y {0 S
. 正确性
/ h# ~' U$ Z/ S# ]% _' |* |. 时空复杂度
3 e! m0 Y+ O3 w- O7 d. 界面友好性* ^7 S) d; ?4 l
正确资料:
, T& h1 @8 U0 `1 q3. 栈和队列的共同特点是( )。
: y/ x( E/ l* m. 只允许在端点处插入和删除元素1 y \0 j8 ]! j4 m7 Z3 I# Z x
. 都是先进后出9 v+ p4 t: X8 i! A& p
. 都是先进先出
* Y; A) K' ^; h7 n$ B; ?. 没有共同点; H o. S; z" [' U( e
. 都可以采用顺序存储方式和链式存储方式
$ a/ \0 ?# D+ i0 R% |- d正确资料:) w# ~1 d+ m; `( \- Y: x4 v7 [4 p
4. 下述( )是顺序存储方式的优点。6 }7 M1 R8 }5 E" j% l
. 存储密度大5 V6 e( M; l& H$ u5 A
. 插入和删除运算方便
4 Z, K9 M3 T( Z. 获取符合某种条件的元素方便% `% C. P; U, Q$ ~
. 查找运算速度快/ e- Z3 R( `9 K: U0 U3 Q9 Q' V, ^
. 可以很方便地存取第i个元素
: y& D4 b& d5 E3 T3 q O) P% t正确资料:
+ O- N( m: Q+ W4 j- Z A% o, T7 |( [. g W' W) f' @
. ?) Q9 {- N4 D2 a1 ` z5 F
% t( T( k9 ~" o1 F' I3 G" U《数据结构2264》16春在线作业1
9 N+ z% \4 o" S$ y" Q
0 d v# g8 b0 ^) A2 [: q2 w. y/ t( D O P
3 r. R/ ~" a( ?8 p( ~- E Q
8 E2 T7 n- B+ `& S, W& w三、资料来源(谋学网www.mouxue.com)(共 15 道试题,共 30 分。), _( o) _+ ^: W6 L, h
2 g ^, g( t- e! N O9 \0 c# f1. 对任何用顶点表示活动的网络( )进行拓扑排序的结果都是唯一的。" ]2 Y/ `* l% z5 s+ E
. 错误0 p @5 t/ J, \9 D5 e* r9 r; C
. 正确
. B/ v+ V; b+ _正确资料:& P0 B! \# N6 b" a( G; h8 \5 h$ \ Z
2. 用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点个数有关,而与图的边数无关。
. o" G! e# _8 K! U. 错误; b. d2 V' \; I6 f( Z) V/ R, j1 n _
. 正确
* G) Y7 s* u6 f2 @! u2 f正确资料:
$ X8 r3 i b( ?7 W3. 线性表的长度是线性表所占用的存储空间的大小。; Q) r2 D8 {. U, _/ E; P
. 错误: i% a7 o" L- }9 T7 m5 ^7 a& h/ S
. 正确# ]: s9 }9 @: A0 ~" k
正确资料:
6 `$ R1 K6 j* k. ?! ~4. 已知指针P指向链表L中的某结点,执行语句P:=P?NXT不会删除该链表中的结点。) i5 d0 m$ K8 x# |6 @
. 错误
9 }! R N, ?" B" a8 B. 正确& r p' u( ^' c# k
正确资料:( g1 | `! M( T" H
5. 有回路的有向图不能完成拓扑排序。
/ j+ H) V" y+ u& R7 F+ l2 ^% v. 错误6 {# {5 K/ d7 r* A3 G
. 正确: J4 G% {2 D c
正确资料:! \; C6 [/ S H
6. 在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行前序遍历和后序遍历,则具有相同的结果。
# l5 A3 F, M+ M( p' I. 错误
4 g/ V; p- M; ?# g; s: p. 正确 B$ Y8 V$ r2 \3 b. ?% ]9 J8 ]
正确资料:
Z6 ]% E' o" f# g8 Q7. 若仅知道某二叉树的中序遍历序列和后序遍历序列,则不能够确定此二叉树的层次遍历的序列。6 U/ e$ t$ q9 \
. 错误% w- _, M6 u3 k# S& R: X
. 正确9 l; l% v% w4 A& M$ i9 H4 H% G
正确资料:
; A* _: W5 t. u V' ?6 M, Y' b! ~8. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
, `$ h4 j/ ^ {: _' \2 h2 [. 错误
+ e+ Z8 G: c( m5 n9 ~1 r- Z4 G. 正确
& V; [& h5 a! E9 z# s9 M: B正确资料:
7 m5 q6 A ?5 n- ]) Z, N/ k9 k9. 邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。( O8 Q# ?" N3 s' Y& a8 C3 h
. 错误" h- ]3 g# ~3 _ w4 C, R0 Q- F
. 正确
$ Q4 q7 Z% C8 p1 `2 H3 a4 ]' o正确资料:2 S1 d& I, `$ y: `/ T; v
10. 线性表若采用链式存储表示时,其存储结点的地址可连续也可不连续。. q5 ]4 X$ @: ~, I2 U4 `
. 错误* V* H1 t) E. v9 S4 b- ]6 Q
. 正确3 z$ m9 F' v( r" Z2 ^8 W
正确资料:1 u& E8 y8 Q+ J* k
11. 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户根据应用需要建立的。. y; r1 u6 J7 `, M
. 错误
: T; p1 u. y4 b$ X. 正确/ ], {: H6 y' G
正确资料:, a* D2 m2 E7 Z8 S
12. 顺序表用一维数组作为存储结构,因此顺序表是一维数组。% Q7 q/ i: P A0 i# A: B( p
. 错误' K. B. J& t, y; B8 {- J/ l, n- l: o
. 正确% x" a. X" M9 o% @; A `4 B, E/ q
正确资料:
3 k7 c% e ]5 K/ D4 t# p13. 线性表若采用链式存储表示, 在删除时不需要移动元素。
# H4 c' \3 x! b: y. 错误
- T( I) h2 E) V2 o. 正确2 T# s4 N R' H0 c) B
正确资料:# m2 `+ D4 a: { T( p7 N! b" _
14. 在采用线性探测法处理冲突的哈希表中,所有同义词在表中相邻。( S2 _; \0 m* Q0 j9 `3 c2 b
. 错误1 F6 ` k; l. |# m4 Z0 ?# V
. 正确
% E" e2 `, Y7 }6 L* `# ~* e% r正确资料:5 g! |9 l+ x1 N$ b
15. 在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针。$ h2 T( I O1 I& Z! V
. 错误
5 ~5 v+ L+ y" V, s* A. 正确0 z8 C8 {: F- C1 \5 u0 k& s
正确资料:6 c. s2 m+ O A: D
/ }/ V1 m: ~$ |/ _" {7 O! H& w+ ~
|
|