|
东 北 大 学 继 续 教 育 学 院
9 x8 [( ^9 ?* F) K9 s. W
2 y5 o+ t w0 W6 C: f0 B 数据结构II 试 卷(作业考核 线上) B 卷
8 h# j2 R5 X- s% P* _ }$ [5 a/ t1 A. J
学习中心: 院校学号: 姓名 1 U$ Y4 P" @& y* v+ Q0 x& D
5 U- L6 S; I8 V6 F9 e
(共 页) 6 R( V+ S* _/ R
总分
# L' l1 D/ G9 D4 T7 |" Q题号( ^3 l7 T7 n1 z2 p
一: D/ ~5 M1 ~4 H* P
二
d. Y# R* w: [( M9 e三
- P( W9 f& g5 \9 J+ g9 C- Q* I- c四
% f/ l; d4 C7 C2 L, U" F* E五( i8 i; Z( {# m' V
六
9 g. H, y9 e7 N七8 k; w( ]" _% B0 i& O
" U$ n( {# I4 v1 D& ~: ?! L得分
|9 g) n. `* g
9 c2 m0 X* k& R3 f4 Z' ?# `9 q7 G( u: R5 g0 f
3 z/ M- x3 L& r5 W3 o4 p" e
& `6 A" L' N* r% Y! E: R7 f9 L* E8 l7 j# J' O
! p4 i2 B" p6 k
2 D3 f( V' w! f: C# a+ a' D) f
$ S `+ ]8 R4 U* S
一、单选题(每小题2分,共10小题,20分)' v1 r4 A7 | p* Q/ F
[ ] 1.抽象数据类型的三个组成部分分别为
7 v1 S3 w8 ^5 J9 a# y0 R; a A.数据对象、数据关系和基本操作2 e3 R/ ?* o( x0 f$ {, d4 Z5 V. a
B.数据元素、逻辑结构和存储结构7 H7 E; n% k+ ^/ V; b1 @
C.数据项、数据元素和数据类型
- s8 ^9 _! [& X D.数据元素、数据结构和数据类型
- n4 k0 M7 N5 q8 I. p: Y[ ] 2.下列各式中,按增长率由小至大的顺序正确排列的是
) E3 p5 t. q, A, t: p; \; L+ Z% D& o A.,n!,2n ,n3/2 B.n3/2,2n,nlogn,21006 h' e* F% J3 s# q$ X
C.2n,log n,nlogn,n3/2 D.2100,logn, 2n, nn
" v+ K2 M. j2 }8 f# ?[ ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为! m Z% R ~+ y' t- E- R0 v
A. q->next=s->next;s->next=p; B. s->next=p;q->next=s->next;, @4 a5 q3 V% ~% q4 N5 ?
C. p->next=s->next;s->next=q; D. s->next=q;p->next=s->next;4 h9 c, W4 ]* y4 z9 o- C
[ ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为
$ Z0 M4 `" ^& n A.374 B.576
\/ C" |( m6 x# y$ R% f+ _ C.378 D.580
* B4 D2 i& Y2 n# v[ ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为' y- @5 _6 @2 L! ~' r! w
A.4 B.5
+ m% s/ `. N7 [/ d/ i8 }% Z C. 6 D. 7
" W, g. C7 Z; `. V/ s; M6 Y; S& Q( |% L& Y. c3 N3 n! X! L. r
. N( P4 C5 S8 I- K/ i[ ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为 M5 E7 t7 b* }; [, X4 C1 f
A.5 B.6
m/ S1 `* K6 } C.7 D.87 z8 {. [3 T0 F& `. h
[ ] 7.以下说法不正确的是
" C. V5 O' d& r( M- V6 \+ j& s5 _ A.无向图中的极大连通子图称为连通分量
4 F$ q8 B% H& F6 U3 b! i B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
; i# t& K: W, [" U0 P8 r2 B C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
' T$ ?" M. T8 ^; ? D.有向图的遍历不可采用广度优先搜索
+ F$ G. k1 u$ p: b9 `6 s[ ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为
* d5 G: \; F' Q, C5 d* ^1 i A. n-1 B. n
) [9 g/ G# N9 o) Q; v7 _# [. _ C. n+l D. n+2/ U6 c8 |9 O. n
[ ] 9.设置溢出区的文件是% ?' |5 A4 z( D" d6 I) W* X% `
A.索引非顺序文件 B.ISAM文件6 L' E# i0 U- n3 D, b+ J; ]" z( D
C.VSAM文件 D.顺序文件, l) Q/ A/ @0 L" ~- U
[ ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是: o1 P9 G0 Q) f: W
A.{25,36,48,72,23,40,79,82,16,35}
r, b3 A1 s# H B.{25,36,48,72,16,23,40,79,82,35}
; C( X' h* @: I1 Y( d7 w8 | C.{25,36,48,72,16,23,35,40,79,82}5 D* ^* i# X* Q5 B" W0 F$ P* B
D.{16,23,25,35,36,40,48,72,79,82}
" N8 ?" ?* W3 T+ j" ?; F二、谋学网(www.mouxue.com)(每小题1分,共10小题,10分)
: S' K R( ]+ C6 b1 q; F11.下面程序段中带下划线的语句的执行次数的数量级是( )。) w' b" K: A9 V5 W2 q4 l3 d
i=1; WHILE(i<n) i=i*2;
& m8 y! w. k x. n8 \12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是( )。
% M! d' K4 h2 `13.无表头结点的链队列Q为空的条件是( )。
/ J8 R+ y3 @7 N5 B9 G14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为( )。) x* k5 B% @ l& s" A2 n" M
15.一棵含999个结点的完全二叉树的深度为( )。+ u' r j& ^* G, M) l, g
16.在 AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在( )。
0 C) D: [7 _4 Q/ ?2 f ?2 B) w* ? p17. 有向图G可拓扑排序的判别条件是( )。9 X1 w0 @! \0 ?8 g. B' L/ J
18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是( )。) j; A' o. r, l) b
19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为( )。* b7 n3 b/ i7 s' T
20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。
. n1 ?" f% b Q2 a, t三、应用题(每小题6分,共5小题,30分)6 B6 l/ @' T5 {# o9 z
21.比较线性表和栈的基本操作的不同点。
$ ~ y0 t0 G8 t' P( K8 r: } w0 w6 d" K- r9 c: g
+ a/ H; J3 {2 G9 [8 ]/ Q4 u3 \
6 e% c8 r+ x& }9 g- {$ F; X' h! i
K ?& m* F+ _! D7 r
1 X# C2 |+ v$ H! i' U5 Z! |
+ K$ z% c# n9 |3 D# h
& W# Y) E: @* j5 Y. ~1 v
% }/ I2 Y" J8 x- Y
" D: }, d% b8 [$ Q" e: A0 ]+ }% t" ?0 I- n0 q, b! ^
22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:% ^4 g# O( O3 ?( P/ N
试求:(1)该树的后序遍历序列。
|$ H4 L7 h1 K- M2 a# x; u (2)画出该树的后序线索树。- }4 E# L) k2 Y% L9 P b5 Z0 \
1 2 3 4 5 6 7 8 9 10 11
; @0 o9 ? H/ C W5 T( T4 VA
& u ^4 Q7 q. y" R1 ?C
5 J8 k5 K9 z) N3 ^7 f0 UB
2 c+ b" U: P% T, j- I& J
2 Y5 g y$ `3 \
% ]& E0 G4 b* u( B9 ?3 EE+ d: W1 x H( b& Z b
D
+ B/ Q I! S6 v7 V# x
! L) |7 s/ g1 b; z9 l A7 V# R
8 f0 R `4 y: j! w3 l% Q/ V* ]
: A" v2 L* e% Y' [0 D2 z" h* k! a+ N% ^, M- S9 k4 u& @
1 p7 L' W! r9 ?, x6 Q
' R/ P& c# l0 z7 P* W2 b, d
. k) b) {) j+ e2 _: \; x
9 k2 p- R# M/ E- G) c! ~3 d8 s2 a& x( Q0 _
- J8 x' {( e. w8 h/ q- A
7 h3 \2 Z7 J" s) X( u& V+ h) \0 n( @) W
# g$ H5 U" r: R2 ]
. d/ J( T4 j9 f23.分析顺序查找算法的“监视哨”设置作用6 }# I' d% |+ v, s: T
- m" A& d8 {9 w, z. L' j M1 e7 s7 c
p' Q" g+ J" j3 S8 v/ r1 u' v, {/ u, Z5 ^- u, ?$ A4 I/ W: C8 z1 i
( f) ~8 {2 r, ^& l+ M( A$ ]6 H0 \# S/ k8 `" ?# J
! e" M7 g0 q! @6 G6 K M
0 ~% ]( y. e- I- g/ ^& j$ Y- F) ?24.对n个整数的序列进行直接选择排序。
/ r5 r2 ^. {" [1 l (1)算法描述。* s/ ~1 J* w4 V- g6 G
(2)并给出实例(52 49 80 36 14 58 61 23 )的排序过程。
, `' k4 }/ l) J& u- G0 D2 C) n: K0 f
1 B/ I/ ]7 i( f0 _9 P& Y% l
: j& r& }/ S( `5 \1 w) t# b$ @# ]( c- G. K; O4 X( ]
' P. Q6 v; x" K6 ]' n; _
' e& J! |% C+ |
6 Z4 a) z) c9 A3 \7 D* W' @, M
; F+ Y& @- y* m3 k9 F8 B7 K" m# U) c# }+ e* q1 U" s$ f0 v
" B, x2 Z9 D. `2 Q
0 W7 S$ _5 c7 h$ X' B6 ^5 v+ w0 T4 N2 f
) u9 a$ z6 L6 ~7 W/ x) m
4 q! H& ^! F9 N k$ `# t5 ?
8 E$ r- E4 { C8 \; |+ R. ^ f25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。6 d: y9 _" _* b- f, x
- u+ x' O; ]! Z
! \. a0 t$ ~. S
, a8 ?" e; n" w# q, t8 U
& ^* m4 X- a$ D" }# n# E8 C' A1 G& V; P
1 i6 @6 g6 n1 h+ P" T& s9 D) G/ z9 P, p4 @
1 `) H' q# b# C. _! u0 v6 v4 Z2 c8 `" X! e$ ?; e
# z% Y/ [* T! L) |
+ S n" O% H- k. I1 C/ z: D7 l& b: e' l
+ m. Q- J% x# Q, Y9 F, ^( c: G6 e, {/ b n3 M; v* u6 B0 ^
5 J* L% j0 ^: t$ |' S6 u, q7 O/ l
5 @8 j+ v, X6 w/ a% o+ k3 z. a
3 h/ W, `! K9 u( J5 O' Q四、算法阅读题(本题10分)
) s1 P1 A' i2 V+ ~( f; [: \26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。
! |" h2 e" T L ] void exchange_L( Linklist &L,int m ) { * e/ W) l& p/ J7 \+ H& J) C% h
// 本算法实现单链表中前m个结点和后n个结点的整体互换
! x: g" R0 j) B9 q. U' j' ?9 I% h if ( m && L->next ) { // 链表不空且4 s8 p; T. z& e
p = L->next; : d+ r7 u/ E, q: w& I
(1)
! Z5 {- ^1 p6 R5 K) r while( k< m && p ) { //(2)
- O3 I, m5 y7 j% q0 b% Y p = p->next; ++k; ' W: K* `# R( v, }
} // while 9 w& t; c" O, u8 B5 e+ z
if (p && (3)) { // n!=0 时才需要修改指针3 D R+ T. n5 x: |, K2 Z7 ?
ha = L->next; // 以指针 ha 记a1结点的位置
, h3 P+ \" `' A8 a (4)= p->next; // 将 b1 结点链接在头结点之后
) v$ D* d6 X1 b p->next = NULL; // 设am的后继为空
2 i K" w4 d% h9 s$ ]; ~; o q = L->next; // 令q 指向 b1结点 6 P' X$ y( k" ?
while (q->next)
( f( l# N G& n# K! k1 z' k q = q->next; // 查找 bn 结点
( E5 t- V* q% a9 S8 x2 s q->next = ha; // (5): C) z- L+ ^6 ?! M7 F
} // if(p)! V5 x( Y j# {8 l
} // if(m)
+ j+ v: `! q- s% A9 ^ } // exchange_L
/ D ~+ a/ c( ^; b% X. |! L- v& U, S( x3 t% ^# C
(1): h: |) j& M5 q5 ~
(2)* n+ C3 h d) Y
(3)
+ I% T8 _# O6 V. h O9 V5 [(4)! K+ ~# y M. h D' q. m" c- A
(5)1 U0 @4 ^; t$ K s) {+ a) _
$ [3 m! z: A: @7 l0 L7 e6 F2 `' a# ~3 N
9 t# \! g/ d* j* c3 p/ D* h; Z: y
3 X7 Q' W0 r' n, b
7 r1 y' e% F. D! S9 m
0 c1 H5 e$ S3 i3 E五、算法阅读题(本题10分). L8 @% u9 C" w$ F" n9 J
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。# E" c5 w% F: L- `+ I; W: l
void Arrange(int A[],int n) {7 g3 v" e0 c, w8 d4 N
// n个整数存于数组A中
; T; k( _& w" u4 K e0 ] int i=0,j=n-1,x; // 数组下标从0开始" e$ q- i# ]1 p+ m @# @& v! U3 |$ B
while(i<j){
: ^0 w9 Z. W$ F7 q7 | while(i<j && A>0) i++;
7 u: x: g @) | while(i<j && A[j]<0) j--; ) l$ T% D6 g% P* U0 g
if(i<j) { // 交换A 与A[j]7 r; p$ U: C' J6 `
x=A; A[i++]=A[j]; A[j--]=x;
8 g+ w& B0 h! A, i, j# [ I }// if; K0 Y3 t4 j. K* ?
}// while& E( \' O# B! U5 s5 f5 R* V% s. Z
}//Arrange
# }+ B Z7 s) n. b* S$ ]4 n, P! a& z; o2 l/ f8 F, z8 \% n8 \
(1)功能:
. ] P+ A8 u9 b(2)指针i和j的作用:+ o+ A0 j4 B& A4 X
. D% |8 w4 `% x1 m. a3 g
六、算法设计题(本题10分)
6 D5 t5 ?: H5 }( m% Q' P28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。: g9 }1 {" }# L# V# v8 G5 _7 u
$ \6 i- i6 k# d, Z! ?, Z: i: D
1 c. h1 q9 v: o4 a
/ V5 x' ` v" J, R" b$ k" D! D( |; O6 l- _2 Y
, K1 u7 O7 Y; O8 X* ]0 h. V& |0 |* ~: D6 S8 N2 A
y/ H1 I4 l& S1 R
: c0 c1 t8 g- t' c \6 N7 R) c$ D4 X# k% E( D6 K( ]5 f4 ~8 D* J# c
7 H* y& l: ^3 {0 U6 V
+ b) w# {, Y5 ]" A( N5 b) q# b# A4 C9 d q
6 l% I- M7 A! T: L& J
( @0 h* `2 F" x, i
) M- [) \$ y! d: u6 f
?6 A* L3 N" G5 Z) M8 _2 C: c
- E/ r, U6 r8 o' D ~1 i; D, e+ a; K5 s) j+ k; ~9 c
七、算法设计题(本题10分)
: T. Z; Y$ I7 ]9 f) e; Y: _29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。
* X6 l/ J3 L& _8 ^4 }3 T" w
* k& u4 ~+ r$ c! ~ C" b! |. ~: U' W) ?
m3 v$ J( {6 Y/ ]" U8 g2 w2 j8 M
9 Q, Q# w, L6 v. M+ o/ p
% O) {$ h/ d3 T5 t% v
4 B R( d8 Y( B; }* E
! t8 p1 Z" v1 V( Z; R8 d0 K! A6 {, o8 v1 b! Y; F: V
7 f% c$ _9 a* S6 s0 y x+ d4 g p% H) k2 R; R8 N& z. E, O
- e3 U2 E! @; L; W
$ y' h0 Z: I' m: n8 y9 I
9 R6 B, _, C8 ?# v
- e) r4 a& b5 Q8 ?1 P1 N5 j0 q; ?( A5 }0 Y
$ J( l7 ~1 s: |5 U2 L, N6 p3 {. g7 k- F* o9 ?9 b# x( r7 _% Q6 j4 H
* S: S$ T' Z) X
" [/ w) r8 \" a c/ {( W# ^
5 [- n% k3 N. K/ L% e1 d
/ p+ j' r" S+ E2 E# b* D: O
0 X' G# D& f' J4 |( P: \/ O; B: p( b* E+ F' M$ g
}( w7 L6 c+ X7 E2 @8 s8 T) {( O1
: G& b2 o$ B, d7 E- \8 W# S课程名称: 数据结构II
- A( @' A% h1 b; y/ ]. Y! F1 ^, t 5 u0 K/ U, n" d: @/ H8 P$ j
6 M8 }7 R$ e% j. x' v+ J& [* a
|
|