|
东 北 大 学 继 续 教 育 学 院6 D. X! Y$ P, q/ K1 W, a& c
- B5 C0 C; s ]# ~6 v( R
数据结构II X 试 卷(作业考核 线上2) B 卷
) o& J' e, j6 L3 {9 X3 @' I
; \% ?. d2 f( r6 U2 F- I学习中心: 院校学号: 姓名
: v0 E9 c0 {/ m! H$ A$ P& }$ K8 m: z' j: c- R
(共 8 页)
: \6 [! \6 m U. F& ^4 e总分 题号 一 二 三 四 五 六 七7 b4 N) e0 c# x+ e0 t
得分 # Q" t% j+ U- b! k1 U
/ u0 r/ U0 z) l9 ~3 f
一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
, @. b' ?* a/ h; b3 ][ ] 1.抽象数据类型的三个组成部分分别为4 e9 B1 X" ~! s W Q2 N( g& e
A.数据对象、数据关系和基本操作
[! z3 z7 g: p9 B3 E7 X2 {+ [/ U B.数据元素、逻辑结构和存储结构1 b( V! [- d# a6 w* o: d( n
C.数据项、数据元素和数据类型
, z$ W( G" q3 V9 d# \/ |' B0 F D.数据元素、数据结构和数据类型6 z+ R( l5 E( w" P
[ ] 2.下列各式中,按增长率由小至大的顺序正确排列的是7 t2 T0 }1 [ _9 H x' N4 Z. k
A. ,n!,2n ,n3/2 B.n3/2,2n,nlogn,2100
- r, M4 e6 F: e C.2n,log n,nlogn,n3/2 D.2100,logn, 2n, nn; s- c4 ~# \7 I+ g7 Q
[ ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
8 G) X9 C" r) p9 f9 H0 y x A. q->next=s->next;s->next=p; B. s->next=p;q->next=s->next;) ]6 ?, ?+ U+ D2 J$ Z
C. p->next=s->next;s->next=q; D. s->next=q;p->next=s->next;. Q4 d' {2 E& b( j5 L; J* T
[ ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为4 H) G7 U6 P) ?* K. p. P, P
A.374 B.5760 Z2 j& W3 I4 M
C.378 D.580
) H. l, W& W6 u- D: s# x[ ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为
6 r2 G0 |6 q2 P A.4 B.5
1 \# T% D2 K- N2 sC. 6 D. 7, O" w$ t9 o/ j+ m& b( o9 f
- K/ z8 R% B" M2 M% [* C
[ ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为! B: l$ u$ u/ w
A.5 B.6
@4 V! @4 A; n5 h8 T" f0 o5 ^ C.7 D.81 W- ~; M1 h5 f
[ ] 7.以下说法不正确的是) `4 L, `% w3 f @" r) F
A.无向图中的极大连通子图称为连通分量/ ]. H$ ?2 w$ `! G$ v) i6 m
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点! F& Y! \, o, n4 Z" C: D7 F
C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
, k1 D$ v$ ?" Z7 ]9 D$ C/ J D.有向图的遍历不可采用广度优先搜索+ g! J) S! ~+ C# f# Z2 B2 U) m& d
[ ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为7 P$ ^4 g) a. u8 J
A. n-1 B. n C. n+1 D. n+2
0 X/ q/ C! f2 M$ I- C[ ] 9.设置溢出区的文件是
- }4 ~$ e% O1 i: e A.索引非顺序文件 B.ISAM文件5 r4 Z/ G& k/ W0 a9 c' m
C.VSAM文件 D.顺序文件
8 D0 X( p& J; u# f/ p[ ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是; `4 l: M) T, z1 l% T! b. I7 ~7 D6 X
A.{25,36,48,72,23,40,79,82,16,35}
" O% k/ P/ U3 B1 {; I- ^9 `* f3 p- pB.{25,36,48,72,16,23,40,79,82,35}
2 W' f9 |9 D7 e; D' Q8 f( U$ iC.{25,36,48,72,16,23,35,40,79,82}$ }' ]8 K% z0 Q0 \9 A. r8 J; O8 f, H
D.{16,23,25,35,36,40,48,72,79,82}/ |0 _! Z" K. @; A- ^
二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)* K2 Q8 E- Y, P! {2 j. M4 r5 P
11.下面程序段中带下划线的语句的执行次数的数量级是( )。( u: e F: s% O& E6 B4 L+ ^" p$ [& o
i=1; WHILE(i<n) i=i*2;
- i7 N3 A! Y1 I% p12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是( )。
: q# B$ T, j. m! [13.无表头结点的链队列Q为空的条件是( )。3 e7 j0 x4 ^: \$ b4 ^" u0 c ~: B5 Y
14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为( )。
4 n5 U, A( H2 F6 x! [15.一棵含999个结点的完全二叉树的深度为( )。
{9 |; U* I; i( @ N1 J \) x16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在( )。
9 G, @/ S% b [4 l( Y* f17. 有向图G可拓扑排序的判别条件是( )。
: p' P% }4 W" j6 o c18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是( )。' t! i9 Z( i# R! k$ R5 }. M
19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为( )。
& J* E) ^1 I6 I8 S; j20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。 9 ?! E# Y+ l& e6 ?
三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)
3 {% ~8 \5 p9 y2 |8 Q7 l1 E1 N21.比较线性表和栈的基本操作的不同点。
- P/ b4 b; G. s; x' x& m$ Y M+ k" H7 n7 [ |
3 w* h1 h, ?# b
1 r$ ~" u- ?8 n; H* l0 ^
; J9 E, y) p# f+ ^; Y
- i9 u) J, I0 [8 ]2 j+ y+ ^' J0 r/ w7 B) b/ L) p. A- @' j2 ? {, R
0 j1 Z# q# _: ^# p* Y% W
9 I# L! J+ t* @, g3 P M( y' y
# Y2 u, I5 {0 R: E7 X# `
3 [$ r$ s1 M& I. `22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:3 B, C" q7 H6 \
试求:(1)该树的后序遍历序列。
2 A; c# }& e9 A/ U1 W; w3 z4 d n X (2)画出该树的后序线索树。7 ?% m5 Z, l8 \1 U! W3 ^; Y
1 2 3 4 5 6 7 8 9 10 11 # T+ e# j6 x9 |, q
A C B E D N- t1 Y# ~" V4 s) f0 B
. `) @+ h2 z" b1 h2 F) t" e/ z: Z- |
& C% k# @3 r1 e$ E+ r y. j7 o
. s) l; B e( }( v- P2 l2 N$ F2 Y$ r, d4 O. F% [* _; z- k; X0 [
8 y# T8 R. M; r: I: S
4 N8 o2 \! {5 w2 Y
2 h P. v1 A7 E) W2 g
$ D( {0 @3 c, F# Q* \: x! `
8 B3 L0 P- r6 \8 Z! c7 b4 X: d( ^: p
23.分析顺序查找算法的“监视哨”设置作用6 Q2 k- m5 O9 r L
/ [" s. @% f7 Z" b8 V" b7 Y* ~1 J9 [
) L4 c( Y2 x/ Z/ O
. h. Y; Y+ U0 n! J
' m L! J1 J3 M" q6 N* {' \- a
2 @- W: M, z+ Z5 \8 w8 f- G+ |% k- H# `
! ^3 _/ X3 f( ?8 i [- X" u% u0 C0 ]* b$ {/ A* v T, q! Y
7 P R- ]% S3 x. C; ^ E% m1 k4 y+ R- Q4 r: Y- y: P! [, E" u2 T
24.对n个整数的序列进行直接选择排序。
1 d) C! Y) c! `4 Q8 u (1)算法描述。
. i- a7 Q' [4 Q E (2)并给出实例(52 49 80 36 14 58 61 23 )的排序过程。
! h S0 K/ y0 x9 V/ a8 _
9 s# f! l, V6 Z- r- U" I
& G7 Z2 b: }/ @0 I. |& q7 j: k) {2 F8 M2 J/ x7 _
, _/ R- E5 X) }/ z! h6 l7 V5 I( o+ ^ ^! K7 W
8 H/ S6 x* s( O5 X8 H2 T1 L7 C; ^: G
* f8 s# K+ n6 S# l( l3 B
4 i' K4 W1 Y. N; F0 l; T( o0 m8 F {! U8 c' \0 e/ X7 {
% p+ H j8 o# D# R& @ c
4 ] [* M' }8 i4 _
; _8 F- L% j& \- x: s& S1 B( T
6 C1 n# i* Y0 T, c4 F) [ a* L- R; v- d
25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。5 T: a) M! R, D/ W) z
0 D# J5 \: N% F3 h+ q" f1 q( o
* |1 T3 r" O5 f! B1 I E) x4 Q3 f5 Z- f, j- n1 H
! U- ^( r$ y1 b- S' D3 `# S( F* \& I, H: v9 T9 `$ Z
, h6 T) p' M, {) g$ q) B) i
1 r( @ V, T, p2 D& `
* N6 j! B# n1 u9 _. o1 W! d3 T" W0 t8 p u- N3 ~5 |7 Q7 [$ z- ]/ _
/ h) \! i" X$ V5 c
4 j& h+ Y8 }9 B. |! s: k# [2 C _
1 ]7 `! i. C- s+ V% H! a, c# n$ E. T6 w, l$ Q
) m# F+ A2 D% Z, v( N) Q0 p4 a
0 v, E, g) m4 O) {1 ]
! t2 `+ E2 z) J& d" E# w, S. G
四、算法阅读题(本题10分)
2 Z. O3 t) s( O2 X' ~# c% c26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。* O3 r. B0 k) Q1 x- J2 _
void exchange_L( Linklist &L,int m ) {
0 D; H+ I) q0 I- g% @ // 本算法实现单链表中前m个结点和后n个结点的整体互换
7 }" T2 Z6 k7 K! W1 Y% S if ( m && L->next ) { // 链表不空且" c& l1 @2 k+ s2 ^
p = L->next;
2 C8 x6 B; I$ p# L (1)
: \! A3 W# ?' t! j3 S5 k6 }' G3 B. \ while( k< m && p ) { //(2)" S4 e9 `# S# I1 L1 Z
p = p->next; ++k;
4 g0 U( e) _ N( Z+ r. H } // while
! K: C4 J& I+ q: m) n if (p && (3)) { // n!=0 时才需要修改指针
3 [4 U1 C0 ~9 d! t& F ha = L->next; // 以指针 ha 记a1结点的位置 0 B/ x- r; l4 J$ c
(4)= p->next; // 将 b1 结点链接在头结点之后
, k8 B; z+ [0 B2 y5 l9 Q# R2 n p->next = NULL; // 设am的后继为空! ^7 x: [ D6 U2 o8 d
q = L->next; // 令q 指向 b1结点
3 \. b" b( Z' Y! R/ o/ D/ ? while (q->next)
/ m9 m; s4 E; T6 V" D3 p, P q = q->next; // 查找 bn 结点 0 H1 e5 | C( U8 q# v/ f" _
q->next = ha; // (5), X/ y* c. y1 q) M8 s7 s- a
} // if(p)
; ]7 |" m6 `' a9 ]/ L$ _6 d& ] } // if(m)/ g' F6 c* Z, P r8 m K
} // exchange_L 9 `# D& Q- w* a3 F! H
) _, d7 I' K! L& u$ ^+ W1 s: g s& B
(1)
, C9 E& d/ C0 V1 B* v(2); l. y/ t# P$ I6 i! R W
(3)% S, ]; q. N7 k
(4)
6 y8 |' e4 ]+ ^8 [; ?(5)( M& N! B% P, t% t
8 ^% @) W) L W1 z* @
, Q; Y1 _) u% P8 o( L9 f; _2 ~6 q6 P: A# D0 F7 q
) E3 \ o; J+ [; i$ z* h2 X; P3 H3 l5 K0 q
. F! J+ E, e! r9 C
) c+ \; k C- P6 x; W& g8 K五、算法阅读题(本题10分)) Z V# O* f% f) M5 ^
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。8 r0 ~: f r) j2 M( V- Z
void Arrange(int A[],int n) {" E/ x9 s% `1 O9 O+ o1 ~4 d. g
// n个整数存于数组A中8 n' N+ m) n) p% P0 r1 q1 E
int i=0,j=n-1,x; // 数组下标从0开始; k, P1 ~) L& E1 r6 G8 p
while(i<j){
$ R0 j1 y: ~% t- d1 @+ W while(i<j && A[i]>0) i++; 5 D, n; e( K" z
while(i<j && A[j]<0) j--; ( C2 K! }$ _9 x% b' n3 j
if(i<j) { // 交换A[i] 与A[j]7 X/ l# T0 C Y) C0 c$ M
x=A[i]; A[i++]=A[j]; A[j--]=x; 2 H( r# C( p, b
}// if
( F% s# n% D2 m }// while
; @ m& W w/ r# k& D }//Arrange9 k0 `5 h) N; |" |6 H2 M2 V
! L0 V2 q2 h% V* T8 L
(1)功能:
6 T4 L0 F9 d% N(2)指针i和j的作用:, X1 u! m. Y' c
' R6 ]& J+ @& w* P, l* p& D! I
六、算法设计题(本题10分)% q0 X) R, V9 w0 R
28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。. r- H, {7 \8 v- V) t" C/ g
7 ]+ ^- Q; O) H( |& v
9 V# U/ D8 I( R+ K) D
( p* x+ J3 {9 `! r, k; p/ A
5 b9 J; k# R# c8 B y4 p
- t" f7 Q" F5 m8 F* K' L
# x( Q" R' `" d0 j' L' h# @- Z! x& a' j( v. b( S
0 G2 J+ B. K/ h7 k% H$ m+ N) v/ A/ p5 J7 |: A: S! E$ B
5 e" ?1 _6 H# S9 ^
$ C. z; X5 X1 N$ s5 K' d: T/ T3 @
. J U: x" d8 F0 j
5 d% c+ t! ?* d" W
4 F7 A; P4 a6 F" s% F4 F+ t
7 }! F5 S: y7 Y1 J0 f, |! e. U8 [) |2 p( r
- D5 T$ j, j$ ?, S2 z5 }% s
1 n3 A; T+ f8 l9 y% e( s
七、算法设计题(本题10分)6 L3 M) e9 U4 i
29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。
3 k& X3 m) S! o2 \5 K: O$ c0 C! X3 y: X, l
6 }0 w+ c3 Y6 O5 e
2 `7 M7 t5 {" ]; H& i) t) D# j' n( t4 U% e; M
; {% t+ K1 U8 ~" L1 a
5 e% y* I8 a% R2 K: O( Y. W+ S8 o* g4 X3 h2 T
/ k7 _$ I# P" Q8 g: l, q2 d* c- Z, r
& B' n1 p# O9 i6 d5 B
3 h6 n) @% U$ [( h: d+ b9 F6 `( t
9 Y) d. S9 S7 C, [1 n
" b, z. I, w+ r( C
" K# C+ J2 G$ p- I! E6 ]/ a; U, W- r% P
6 i( e' B N/ X
% U8 o6 c A1 R' J# g4 L
7 O* s0 [4 t0 N4 m+ J2 f7 U, K; C" M8 Q# Z& B6 F
|
|