|
东 北 大 学 继 续 教 育 学 院
* p, Y6 F6 E* ^' n5 f$ K5 @2 t& m3 H$ j* [: Q. H. S
数据结构II X 试 卷(作业考核 线上2) B 卷
9 q3 e$ D4 j4 I% H
5 U4 c# ~4 t# d学习中心: 院校学号: 姓名
6 ?: h, l; l% ], r1 q' ^: q! {4 J5 t3 z _
(共 8 页) + p2 J/ Q1 D4 i0 U$ d
总分 题号 一 二 三 四 五 六 七
- {7 `" z% ]* e2 x 得分
' r y. V- W7 ~2 f& R' R" K. U) Y; j$ @7 I5 l% Y
一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
& j5 X) P; I- E' @3 j( ?[ ] 1.抽象数据类型的三个组成部分分别为3 k6 R8 M9 a* P$ u& ?& [
A.数据对象、数据关系和基本操作4 n' W& R' T4 d) V1 _
B.数据元素、逻辑结构和存储结构
8 a3 Z2 e# y4 ^6 b" b C.数据项、数据元素和数据类型
) `' J+ q: s+ L* {# J D.数据元素、数据结构和数据类型# X L U4 r9 E* r; X+ T
[ ] 2.下列各式中,按增长率由小至大的顺序正确排列的是
) y# c) C5 q6 G6 G2 W0 v3 O. l" y A. ,n!,2n ,n3/2 B.n3/2,2n,nlogn,21000 Z# v3 z: R i+ g! N' @
C.2n,log n,nlogn,n3/2 D.2100,logn, 2n, nn
3 B8 N! |0 t: S[ ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为9 \ i8 ~' s6 ] X4 A; V
A. q->next=s->next;s->next=p; B. s->next=p;q->next=s->next;
0 H# x: a! A/ h0 X2 ` C. p->next=s->next;s->next=q; D. s->next=q;p->next=s->next;3 G) m+ \. H& H/ c4 }
[ ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为: ^8 r7 W, K1 t% e
A.374 B.576" r a. n }3 o
C.378 D.580/ v) `% s) x' M
[ ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为
) P- X) ~; o. A A.4 B.5 & H1 d3 i/ I( i
C. 6 D. 72 b# L9 Z% p* E% G: j( W" R
5 Q4 {7 `% \, H" L* z
[ ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为
3 a% m; m' c& i2 e A.5 B.6
& P$ a- x: Z- k- { C.7 D.8. h. r" l8 q& G' u7 F- Z6 r" {
[ ] 7.以下说法不正确的是
' [% }8 d+ u- h8 i9 c A.无向图中的极大连通子图称为连通分量: @8 O5 d1 H# z0 P- Q0 t/ Z
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点8 t! g$ C1 D* ?6 r- a1 u" E. k
C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点7 }5 I+ K" ?, L6 I. y% R# v& n. D
D.有向图的遍历不可采用广度优先搜索# k3 q L3 k! b
[ ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为
- e8 c- N2 C8 ? A. n-1 B. n C. n+1 D. n+2& @# A( f# {- y7 ~
[ ] 9.设置溢出区的文件是8 J. n# w3 r* N y, ]0 J V1 `9 E
A.索引非顺序文件 B.ISAM文件3 T* ], |4 T ^( v& k7 e
C.VSAM文件 D.顺序文件
, w2 U. e/ K1 `, T( ~0 v[ ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
( R g+ C, k1 B* U& hA.{25,36,48,72,23,40,79,82,16,35}
) Q3 x: e4 ?5 bB.{25,36,48,72,16,23,40,79,82,35}
6 Z% v9 D3 H& k6 y+ fC.{25,36,48,72,16,23,35,40,79,82}
+ \- y5 _) r+ f6 e+ \D.{16,23,25,35,36,40,48,72,79,82}4 ~6 h) p/ L9 l) ]! V I% z
二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)8 l5 Y3 b& }5 u* p7 w& q
11.下面程序段中带下划线的语句的执行次数的数量级是( )。
; b# r e' S3 O' qi=1; WHILE(i<n) i=i*2;
9 F5 F4 I, i( M12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是( )。
6 n# r" F4 Q w& t13.无表头结点的链队列Q为空的条件是( )。
/ X! G* @( n. D14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为( )。' z! u G# E& D. E; u- @3 @
15.一棵含999个结点的完全二叉树的深度为( )。1 g+ F" p- I5 ^/ ~
16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在( )。* i6 @% X' {- W$ R; y. e
17. 有向图G可拓扑排序的判别条件是( )。2 ~& ^7 j% J/ u6 }/ P+ f
18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是( )。4 ^! v% W: u+ m7 U3 v, l0 W% b
19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为( )。
- k" j0 ~; D# d. V. J20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。
g1 n/ L. k5 u$ `三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)2 [ h9 _8 s& t% i4 T- @: N
21.比较线性表和栈的基本操作的不同点。
# }6 h: {. r1 K% B( }( R* ]( n2 x# L
& {9 ?9 y9 {% e% v2 Z4 b0 I5 P
" U7 X6 C V) m' H& c5 |( t. y. \. Q% q2 J# A: w/ u
; T+ M7 B) _5 n; i7 i! k
5 Q- q& X1 b6 L& v `
. L" F6 m, X5 A0 Q2 I8 @
. |, @, \3 d# w6 | m K F3 g7 l5 s9 G5 i
! `, V Q8 V/ w# @1 q0 _, m# P- j22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:4 m+ d$ `/ v1 T- V4 g3 z8 w2 T5 Z4 d
试求:(1)该树的后序遍历序列。
4 ^# p+ |$ a4 q( N (2)画出该树的后序线索树。
' E: N0 d$ M" x/ {7 Y1 2 3 4 5 6 7 8 9 10 11
/ M& p/ X" } O8 j; \- RA C B E D ( t# T" y# Z* Y; f X( x- j+ [
7 i& X4 T9 V1 p& u S
7 W: I7 {; A8 x0 o* Q* i6 _3 z6 h, ^+ D$ X- k8 f9 D0 m$ g
# R/ j4 Y4 J$ X0 u4 g
$ e. [) l5 y U
1 V8 h6 w b# m: N" R; C0 D, r4 V1 m
* T2 N( r) e0 F) B- b( i# ~) U
2 O! L7 s% a: c. t( ~3 s! t" K: H, C1 W$ r
" Z/ a% F* O0 A' p# f: Y) H
+ j. d0 Y0 t7 V+ e
23.分析顺序查找算法的“监视哨”设置作用% y% v5 ?2 \: |# p* d/ i- V
& N* j% s. H) v; g" c3 x. X$ t) Y
W2 [$ t# K3 f: ?1 `8 b6 |3 Y' e" m/ i# k
* j! u4 g6 j+ L: H
( B: s, ^3 T2 a8 l( _& y+ \" L
) Y8 A, i0 |8 U; S, U) H0 v$ [
3 ~7 d: b( H& E, T
% C9 j% u7 ^2 E( G& }
) L( [7 B* ~. r24.对n个整数的序列进行直接选择排序。
6 G4 A5 {- k" O! P. f+ w0 U/ v (1)算法描述。
, t) J5 X0 [# X0 b (2)并给出实例(52 49 80 36 14 58 61 23 )的排序过程。
/ H3 t/ h+ t& E% J4 f6 t1 t# w& K" r
' a* r1 e* Y/ n5 D( F
! u" R+ H8 y% |5 w6 Z5 |& `, b8 C: ^
9 ^8 _- Y9 K4 j0 @; e* s8 v. R
2 ^' q9 c( @3 F
+ N" Z0 r. w) \/ ?3 M
% r9 t% S2 V/ {- q" \5 Q
s: Y; v3 y, [8 Y
/ `& R0 E7 I/ {- b) q# Y3 b& H1 Q6 u5 s3 A
5 v! p7 H; }5 @3 Z9 p6 ~+ q$ Z
* p6 L: \# u5 J
- t& Q8 {* Y! s5 {% b, ~5 Z. s
l, _, K8 n2 w- b; W25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。
$ Q: t& s& b8 e0 E }4 j
9 `+ o7 R2 ^- ?5 g% K' t" Z4 [0 }$ G! d7 ^' ^2 d# U& r' x- z
* w' P* z1 p! T7 y& \
/ v J! B7 j7 |2 }+ ]( a e
' u: ]8 n2 f0 z3 f" B/ S
* P3 ~; c; P7 t3 r Y/ _, M7 I( R! S9 W( a0 ]* u/ n
- s, A$ ^+ @# k5 A" c
6 X* v) h! b& K. [% ?2 v' c- n1 l- h
" D8 ~+ w7 i! y5 k4 j$ P* M u
C' b# Y1 K1 N) [: C
3 t7 `/ {+ ^' T; }* G, j, w8 f; k) T N
3 L: o5 G' W# n2 {& ]% j* T
8 ]/ u8 v o) Q Y7 J1 O" z
/ l! m2 M; Y) t
5 Q+ H+ d2 l6 ?5 [! W四、算法阅读题(本题10分)
6 Z# L3 b! H" V ^3 p' h3 E26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。
% P% t- | I( T. b* j- R void exchange_L( Linklist &L,int m ) {
& n9 a9 n+ Q& O8 a0 B. w0 @ // 本算法实现单链表中前m个结点和后n个结点的整体互换
3 x$ I1 o: m9 T: F# H' H if ( m && L->next ) { // 链表不空且3 s* E$ C8 {2 g% ~5 q
p = L->next; 0 `/ |2 @, \2 p* ?) M
(1); v/ a; L$ Y5 l
while( k< m && p ) { //(2)
2 T) Z7 ?4 i3 n2 u p = p->next; ++k;
/ T5 V$ d% g/ q, O" y4 u } // while
% X ^4 P) `7 n) d R/ H* h/ } if (p && (3)) { // n!=0 时才需要修改指针
6 y# p# e$ S$ [3 ^- q- J ha = L->next; // 以指针 ha 记a1结点的位置
" J; a: j" o$ x: h$ Y! L. y (4)= p->next; // 将 b1 结点链接在头结点之后' T3 I2 B4 L+ w9 t
p->next = NULL; // 设am的后继为空. R1 ]# H. i* a8 z/ P/ j( F# W( b+ J
q = L->next; // 令q 指向 b1结点 1 I0 ]2 i8 l, l; ?* G6 }
while (q->next)
, w" t8 ~% @$ L- b( g q = q->next; // 查找 bn 结点
9 k5 U3 \/ u4 ?2 K4 R9 [- J q->next = ha; // (5)- _" q/ l$ V5 j5 H0 }. Y
} // if(p)
6 B/ u" |; n) v# X5 T- z& | } // if(m)# W+ M9 A+ q+ Z; x# ^
} // exchange_L
9 h3 N1 Z% f; r* ]$ `# h* O% B0 ]6 C1 s: [9 F% ~& g0 [. ] {# g
(1)
! H: L1 u9 R' f1 {% Q/ V' D(2)
" M: C- d- l+ V( U(3)# q: q6 x0 B) m1 D4 B; q, p0 E1 G- _
(4)( \3 }5 f k6 o$ [/ f7 Z
(5)! ~2 t7 m1 h+ G Z
4 R2 ~& I$ F3 I7 H) `: q. z
7 K% ^" m+ w' k' y% m! f
* t& R! z# U; f$ C7 M2 o9 c
& M/ h9 { {) y0 y6 I! x0 f! H3 O) U1 ?1 a! Q
]7 j" @9 K5 k+ w$ f3 ~
7 R- k1 ~/ w+ {$ k五、算法阅读题(本题10分)7 s3 ?- I- h3 H: w2 ]
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。
% } T" @5 P; [; I1 r/ l7 yvoid Arrange(int A[],int n) {, A/ u7 R7 Q* g0 A
// n个整数存于数组A中6 P# y: ?: i* g& M+ B6 B
int i=0,j=n-1,x; // 数组下标从0开始- n* r4 v. }$ n: [
while(i<j){8 _: V* G& @: S/ S2 |
while(i<j && A[i]>0) i++; % t) S0 ~* E1 b1 v* [5 e) A* s- k
while(i<j && A[j]<0) j--; - B* G' M0 H1 a& l* Y- h5 n
if(i<j) { // 交换A[i] 与A[j]
# u2 j) k0 O4 a/ T$ l x=A[i]; A[i++]=A[j]; A[j--]=x; 4 t1 w: v5 M" M8 H( z
}// if
- r% G% v4 b7 S7 L* d; d }// while
9 q, F0 ~; a/ w% Z4 G: N }//Arrange
1 x: o, H/ ?' o4 }; f* D' A
b9 u$ u# x" B2 h- _/ o+ c(1)功能:& a# ~$ U6 H/ ?6 M& |$ Q% O) x
(2)指针i和j的作用:
) y# [/ r: q' j2 {) S2 z* R* ~4 @4 Q) Q% \. G
六、算法设计题(本题10分); u" k; t/ W& b8 j' {
28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。
8 m) C9 E2 {" n6 V" J8 `1 {7 V2 B+ q) ~$ U; m2 Y
* D3 {$ R+ X* s' B+ k" ?; j3 B( T) S3 i0 G: m
* I6 R2 [6 J) q. m* f* ~
, j( T, X1 s3 H- _& A
/ @* {0 L- h$ y' Z6 d2 c9 n7 |& G: v
2 M8 \5 `+ v" N7 I- p$ |" g5 N& A- D% q. c" Q+ f; L- C* B5 n
) u1 C0 F. J1 W
$ A* S8 U4 k; N
7 l3 \0 ~: K. \ G, Z" ^1 S9 r
$ Y( e7 t# v0 i6 {% t- B( @
# o% J8 B5 Q, Y& {) c/ q8 ], V
7 }6 g7 a; j* O& w: F- X
1 }' V5 M3 U$ `6 Z }% {5 l; X* Q9 B$ A, l: A- ~5 K8 i6 o% t, \& k
3 ^* p8 @: A" }6 Q2 y5 A3 v
, x% F- u9 q8 O) m. V1 s( k
七、算法设计题(本题10分)4 W s3 J' q+ ?5 h% ^9 Z3 `0 Q: c% K
29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。2 |0 B$ J( M7 n) G6 l3 n
! e+ Z; i& t0 ]1 F& [
- M W# ^; u+ D& m! U' N. A
& S% ]6 \+ _) |4 E8 g5 ]! w. x* k, d- p& L
! ~) w/ ^$ Y. D2 r9 C$ k3 D1 ^" x6 z( H4 C( s5 t& J
`4 }2 U7 a& }. Y% {
2 O% b5 x) r, V) x+ M6 g6 a% X. v
" w7 h" t7 w( C2 [7 n. `
. l: ^8 ~! }+ B3 U' V( K
* X/ N& ] `: X5 l( e# f: e' h
' B6 V- w! R) L" B0 N9 e1 D- G2 Y( P9 H5 T
# M$ L, T; V: [8 R
( y% `9 M6 o# ^# B% y( a
( P( G8 ~8 o8 q3 e8 f
* \5 g: `' W* E* r4 g2 B5 K1 ?, ^ b; n" B
/ `4 w$ c/ Y7 | t |
|