|
东 北 大 学 继 续 教 育 学 院
7 K% J1 W( y: M; i9 I# j4 s0 @/ J8 G6 I$ x1 b: X5 ^
数据结构II X 试 卷(作业考核 线上2) B 卷
# m0 O1 o# t k2 ]# t: ~
' ^: n# ~9 f; Z$ y* n' Y. c5 D: U学习中心: 院校学号: 姓名
& `: v+ v$ y2 x; i+ Z+ Y* \0 v! V, {( { x' K& }
(共 8 页) ' ^5 g# v9 X0 \+ g
总分 题号 一 二 三 四 五 六 七! v' C( _3 N" O V, m9 L) \ W
得分 . T% ]- c$ B& J& p
7 ~) R6 _1 w4 U) T" g. ?# [一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
/ u7 s! m3 r" O! @$ n[ ] 1.抽象数据类型的三个组成部分分别为: C u# ^9 F! d( G; Z7 N. A3 m
A.数据对象、数据关系和基本操作
. I4 ]8 ]# {$ \& m: j n+ ~ B.数据元素、逻辑结构和存储结构
( ^% e+ X3 a5 r# s. z/ y% w C.数据项、数据元素和数据类型
( h8 F' v1 T' }3 F& y D.数据元素、数据结构和数据类型
0 X. R# ~; U( x# y[ ] 2.下列各式中,按增长率由小至大的顺序正确排列的是, }) a1 l, i( g' b
A. ,n!,2n ,n3/2 B.n3/2,2n,nlogn,21007 Y, G6 Z" A7 A& M5 z& ?
C.2n,log n,nlogn,n3/2 D.2100,logn, 2n, nn! H2 u" {1 W4 S. i1 o7 ~( i% M6 v h. Q
[ ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
2 E/ J* q8 T- r+ b- ` A. q->next=s->next;s->next=p; B. s->next=p;q->next=s->next;+ h; i- y) W$ y4 w( V
C. p->next=s->next;s->next=q; D. s->next=q;p->next=s->next;3 o8 i+ q. I0 C! f, E- h/ C
[ ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为) L1 D0 i9 e/ l6 D" C8 L5 k$ I
A.374 B.576: s+ E. E& ?- n2 y: u6 E
C.378 D.580
- b7 G r9 E9 Y# E3 e$ V/ i[ ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为9 D" l7 W* u+ N! h2 b/ T7 X/ ^ d
A.4 B.5
( c3 R" V( q! T* j* F( O3 m, s# S, UC. 6 D. 7; r( b7 z% g# l+ N6 n! G4 ~1 ~' M* c
! o* q1 t( I3 a/ U+ t. r- H5 Y5 y[ ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为8 P% R6 u( N) {/ }
A.5 B.6 ) m0 G) R) l/ E+ R
C.7 D.8
( h" U: \3 z& G% J" @+ K# C! I4 ~, }[ ] 7.以下说法不正确的是) K) ^0 x% D5 `0 i
A.无向图中的极大连通子图称为连通分量4 X6 Z, f. ~ ]" N8 g4 z6 N
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点9 e1 E( f4 n9 y! `0 d
C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
4 a- v8 @. U5 w) {0 \6 k; O+ f D.有向图的遍历不可采用广度优先搜索
6 q8 [9 |8 I( A5 e" w- `[ ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为
, ~7 Y, g: E- a# b" b2 M A. n-1 B. n C. n+1 D. n+2
. y" `! [( N( A# o Y, c' o2 z& A[ ] 9.设置溢出区的文件是
, G9 w" F/ m+ p- F0 Q A.索引非顺序文件 B.ISAM文件' j; m8 w8 C4 Z
C.VSAM文件 D.顺序文件
/ W( k& l; o, l[ ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是! M' N$ c% D. ^, Y+ U- v
A.{25,36,48,72,23,40,79,82,16,35}
+ Z) t: `* b- A; P( y$ ]B.{25,36,48,72,16,23,40,79,82,35}
! z+ t# Q4 \" Z( \4 k) B2 v" b' c XC.{25,36,48,72,16,23,35,40,79,82}
0 M' w$ a b9 w' SD.{16,23,25,35,36,40,48,72,79,82}
+ u8 ]' V" U3 x s8 ?0 }二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)7 Y$ H. U. Y+ [% r
11.下面程序段中带下划线的语句的执行次数的数量级是( )。) B) F1 M6 D% X* S
i=1; WHILE(i<n) i=i*2;7 H6 R1 L; _' u5 F8 u+ E. i
12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是( )。
4 |, s! u/ \4 n, a" Q2 p13.无表头结点的链队列Q为空的条件是( )。! |9 ]8 l/ z) u6 H ]( k
14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为( )。9 `% N* n8 i) J7 D- l
15.一棵含999个结点的完全二叉树的深度为( )。
( M' C+ e1 Z1 J* a: `16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在( )。
4 Z/ R, R9 {1 N& ]3 i7 i17. 有向图G可拓扑排序的判别条件是( )。
6 d, u/ W5 f& W6 O2 _0 Z, }18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是( )。
8 [+ Z' W& ?( P19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为( )。0 s% t$ }, t5 S9 S" x- e
20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。 & C/ ~1 |" @% X3 {0 J/ b
三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)
- c5 V0 B) v- `" [, b21.比较线性表和栈的基本操作的不同点。
; z" V0 F/ Q; F" t1 s" s6 w! ^
8 e+ L" Y. ?% i' ?2 t6 ~* s
" Y, H" x H! w2 b) U! g: V. ~# m- _6 Y. P! o. K
* A T# `/ }: ?, U
/ X+ c9 q5 Z; d! t2 b5 l2 U4 X
' p4 z& I; e+ J+ _% a$ d0 P+ Z# B/ ?; w( u
/ e9 f- z/ }9 ]8 f) ^& q# o* W
; F2 F8 _0 `. v! L' p* g: B# E$ x a d8 w, x6 Z- N. V! B
22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:' s; ~$ X( e0 u
试求:(1)该树的后序遍历序列。" J( A9 |& R% F/ H& Q
(2)画出该树的后序线索树。4 c1 n. ^. N7 E0 w, n
1 2 3 4 5 6 7 8 9 10 11 # e5 g" i6 E, |. A% W' N
A C B E D . [0 Y" ^- b% ^! i/ k7 |
' w* J5 _; b+ z, t, W
* u! _4 P, r+ k1 q) ~5 K ~1 @4 y
7 x* T( q) X- l$ [* R) ~ S$ X9 w( |6 x
* x* z: m) P* A7 @0 c
6 B, j, n$ Y4 N9 L( ^
" D! h) m4 H: z
& ]+ e6 |3 {% N# Y3 K1 k7 I' u
- Z+ E6 U: m% l$ }
3 v2 y5 y! F2 u23.分析顺序查找算法的“监视哨”设置作用# x( Z O+ m; H( `" g
: \/ g6 Y- Z, `/ Q, e. w* e4 ^5 a! K# x* c
+ s; ]8 \; ^; W- _7 W! c, K) z
) y) C" f" F# m& D" @* F6 A& `
b: } V k% h0 i/ D! R1 q$ l* Y, }. A
+ r f2 B. k2 t
2 A: E; F7 A4 q: y" T
, J" Y3 u# E+ H4 }5 M* v9 h( p" R
24.对n个整数的序列进行直接选择排序。1 _6 v( v( F0 l1 z# e7 F8 C4 H! d
(1)算法描述。6 U1 H: U5 d4 x, W( j6 s( X
(2)并给出实例(52 49 80 36 14 58 61 23 )的排序过程。4 [) Z8 g! C3 |- J; o
- J H/ Z7 D! y; D" u+ f8 w8 G' p
' \& w2 M3 d0 r: C% E+ j1 ~- K' r
9 R' H9 g; q7 f* d6 v9 G
0 |& E8 L9 j* \2 K2 u) v2 O/ T# z/ L1 }; R! d
( H: w( I! l2 D& e1 u: @
4 g& e" ]/ b! r5 F; L
# G% F$ A% B+ p: S G4 y& `5 z2 _, O/ R) p! U1 |$ S
$ u" z: e2 T7 G1 G3 @# O, _6 a
8 V+ i: D( ]( D+ Q3 r
5 c1 G8 e( R0 h3 J3 {% J; g; _0 D0 C' _+ {: B$ u- w" u
* k0 a' M: U% S& w8 @% T
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为根的深度优先生成树。
4 |2 u3 S: y! Q, `1 l
8 L0 I# P, \7 x, C: e
8 v; p3 _5 t* Y% l6 V9 d9 g; t3 c! b7 V: I2 K5 R: I
1 g% u3 ^$ J" M: A
# S' w# w" A; I8 h' j
& [, s' X8 n( H: o I
* M( l5 ~* I$ h& {5 \
5 n2 e- G" c: K, q6 }7 r0 [ @# v6 ^2 H- E" ]% m( U! C5 s$ z0 i
' T9 c) R) w! h9 z- w
+ v! h+ L; D' t {9 y- z! F/ P' _; l: ^" A7 d: ]+ g0 d
, Y" b% I6 p2 E6 O4 t
. Q, k0 u- I: ^0 q( Z5 t
4 I7 d3 S; d6 m4 v+ K
0 c% V/ n" e) ^5 A$ W
4 c, \2 ^4 c9 Y/ F) q" l四、算法阅读题(本题10分)4 e6 R% g- F. x0 K, l: \6 U; d B
26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。* }; G) D; b& `
void exchange_L( Linklist &L,int m ) {
* L- y; W1 T, |) k% r' K // 本算法实现单链表中前m个结点和后n个结点的整体互换
$ x/ k6 B: g- U. L/ V2 v if ( m && L->next ) { // 链表不空且: w+ |$ \) \: F4 _1 u
p = L->next;
9 d A, {9 l' X$ M$ E: ^ (1)# n! v& U! E! x4 S- A
while( k< m && p ) { //(2)8 ^ |, b0 i7 `1 a" M
p = p->next; ++k;
, E }, o4 v0 i. _7 l } // while
& U4 q& c/ h8 L' O if (p && (3)) { // n!=0 时才需要修改指针/ N) Q: @% k+ A+ z
ha = L->next; // 以指针 ha 记a1结点的位置
( E5 P8 s. d ^ V (4)= p->next; // 将 b1 结点链接在头结点之后
" ^4 R. S. \8 f9 \2 ` p->next = NULL; // 设am的后继为空0 L- l8 W& _8 q4 ?- M
q = L->next; // 令q 指向 b1结点 ( x, g" X* [$ f( u) A. `7 p
while (q->next) 7 f1 y% H: J" E h+ s" w
q = q->next; // 查找 bn 结点 ' U/ x# n4 A. w9 C
q->next = ha; // (5). ~3 y! w/ y! B/ ]5 E6 q+ W
} // if(p)
; E5 j; L0 l, Y% j3 m } // if(m)& U# c5 x3 {+ ]6 t
} // exchange_L
3 ^. p0 I0 r7 O- X: f" S" J
4 t8 \3 R! t1 h# L' k$ T B) s v: F: Z(1)
/ e1 G& }( P4 R3 ?. l' f# c(2)
3 M; I8 t) g% D: Y# v(3)
' Z1 d+ g+ G/ j( e+ Z/ i" v. r(4)$ m& Z, c% ]1 x3 o
(5)0 D9 \ c1 x6 H" q! a+ c6 T
6 p3 x$ I1 V" J; j7 |% i8 s4 Y/ o' Z' n* h1 s
% x6 ] r) m' c: I3 @" }% s6 E3 k
8 {0 j6 L3 B2 ?/ |' Z! N
0 c; f4 X/ R' y' }, o
0 w. y# t% `1 m" }8 j6 c2 P/ @7 i# O2 v1 }
五、算法阅读题(本题10分)& n! U- F( v7 ~: Z8 p% N+ w* u
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。
9 }8 G) {' i0 [4 P4 y& i7 S5 K. M/ mvoid Arrange(int A[],int n) {4 i( t+ v% W" c# ~5 v
// n个整数存于数组A中
) v- |2 n. x! `! F+ M int i=0,j=n-1,x; // 数组下标从0开始
# ]+ K) o U* c0 ?' e* A0 I while(i<j){! |: A5 f* u/ @# q0 Z& d {$ u
while(i<j && A[i]>0) i++;
9 e o3 v7 e9 B' I; l while(i<j && A[j]<0) j--;
* F, @' v0 @3 C2 \# i if(i<j) { // 交换A[i] 与A[j]
3 R, x( ^5 m! Q1 m- v( q x=A[i]; A[i++]=A[j]; A[j--]=x;
1 u" m( Z! J2 A1 {+ c, I' { }// if
( V6 `3 c8 J, m U' p$ i }// while
3 ]$ I: m$ r( t5 A9 H6 @3 A }//Arrange6 ]& T( Y6 V7 O# t# l) m
4 V# C7 F# \* z; @; M3 \1 w
(1)功能:1 \" A+ L" t$ ~+ \7 h* _
(2)指针i和j的作用:. T6 z1 g% y$ T- Z" G5 E. ]) j
! O5 J% d: U; N4 I) r
六、算法设计题(本题10分)
- e$ Q, V0 E2 T6 A28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。' O2 f; O/ z' _5 W# ^" D7 }
. s+ f1 g3 |$ {3 r8 E5 P7 C
) p& k2 W0 \, \( E- R* k- o
: a' m+ n7 I# \+ f3 G& d2 \$ o/ D7 S5 p9 n, Q- O# d, `( l
) c% ^; i4 V; Y( T8 ^: A& H
7 [. s! v& g1 v" m
5 D1 \2 p- \' d; P2 Y) J
P6 k, {6 \3 J6 n
' H+ v* h/ Z; v6 Z5 c( }
- E, l7 X+ j- r/ k8 P3 L5 S, `+ H1 T- v% v* R! d$ q& Z
$ j" B+ x. B2 b+ F* M9 D0 E/ g* I
) K9 i7 V. v' }7 H; H5 I7 H2 U! P" j* e, S. Q. p1 R
/ L- j) w- y' H4 o1 u% G. {. K, y; ?
- y. i! v- \1 v- w5 C8 I3 F; q3 o2 X2 p5 ]8 K: S8 G9 J
七、算法设计题(本题10分)
, ~8 ]" y+ k3 S+ j9 X7 o29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。
3 {1 j, }0 W, j; g6 R
7 K+ B. }+ ^, e7 \% q0 k2 v7 w! c
6 {0 M1 m: l/ m+ b( F' d a* d8 X
; b9 W$ F, b) J$ }5 H6 X" I/ y5 r7 C- R& l) C; R5 p
+ s$ x6 M+ O2 m& M9 j1 a! \
+ {! B1 H& L8 j' |0 c- {+ y2 b& R/ g+ B# z( l$ V6 d0 {
+ d+ p1 ]: g1 k. @
& D- e0 H& V2 e- v4 P1 v% C5 q$ M( o
. ?* H/ `: e9 `: J. y
/ ^1 f# @7 i$ p: s* G$ }, @* n: u6 b, X4 N, |" a
' A- d% Q4 L8 O+ R4 \$ f
0 W9 b& R' z* {
7 |7 N# N: {" E: o# `4 A S6 f( H' ]- M/ s
% |% y0 F# ]# x. C# C
" m$ v) `2 P2 [/ |; j9 G( K |
|