|
东 北 大 学 继 续 教 育 学 院
/ P& ~4 g0 |. } z3 Y$ k x4 |+ d3 V0 Q W% x7 I
数据结构II X 试 卷(作业考核 线上2) B 卷
: c5 s/ z1 Z/ q: N [. h; ?( q
$ ~. K4 f! j" b& q7 ~4 A学习中心: 院校学号: 姓名
; @( d" y8 Y( t6 p: Q g1 m, l3 |. S2 O. m9 N* b7 L
(共 8 页)
: }1 k9 V3 c/ ]6 B8 Z( |总分 题号 一 二 三 四 五 六 七
2 c0 ^8 g( k7 V5 ` 得分
( Q) ]* s$ a3 ]) M+ T* O) d3 _# r3 @) ^' y- T/ ?$ b5 ?+ B: f0 [& ^! l% J
一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
* O+ _- C1 X3 R$ m0 W( X[ ] 1.抽象数据类型的三个组成部分分别为5 e" g, [/ F( x3 U" v
A.数据对象、数据关系和基本操作
1 W3 [6 f: |4 m% N$ ?6 { B.数据元素、逻辑结构和存储结构1 Z* Q. e2 i5 p: w+ k
C.数据项、数据元素和数据类型
; T2 s, d/ X, p8 H/ P5 R& x D.数据元素、数据结构和数据类型
* U8 P$ N& N3 U. {$ L[ ] 2.下列各式中,按增长率由小至大的顺序正确排列的是
1 |4 Y8 D1 }& ?) [" M' h6 w A. ,n!,2n ,n3/2 B.n3/2,2n,nlogn,2100
+ {( p7 J% b& V, I9 m7 v# @ C.2n,log n,nlogn,n3/2 D.2100,logn, 2n, nn1 e S T0 k: a/ Y1 M( r- ~
[ ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( p) v$ j! r* _$ V, x: ~. a
A. q->next=s->next;s->next=p; B. s->next=p;q->next=s->next;
! `. [, j& g; }1 h9 ]' F C. p->next=s->next;s->next=q; D. s->next=q;p->next=s->next;
0 I4 A& l0 i2 y8 T7 c7 L[ ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为7 k9 E; H w5 k4 n
A.374 B.5768 a2 `3 G8 ] N* c4 s1 F
C.378 D.580/ y5 ^$ i4 k$ _6 H0 V# _
[ ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为
, K. p2 n; w- e) _; v A.4 B.5 0 P+ o, ^4 `# L; p
C. 6 D. 7
, ?3 X3 X8 v& J# P M
) K1 D8 @' J6 `3 ]8 a2 ~9 s[ ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为
" m' B& c9 Y; e1 z) Y R; u. h& j A.5 B.6 / _8 P, q, N, C0 Y" P! D! D8 r) c
C.7 D.8
/ P2 u. U. E9 L[ ] 7.以下说法不正确的是9 m* ~/ ]7 g, l. A8 P( z1 W$ o* ?
A.无向图中的极大连通子图称为连通分量
6 {' T9 h" W1 k+ A* K$ s2 f B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点( y' V' a1 R9 c- t, q8 |3 C
C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点5 W& W/ s B) C+ m3 x
D.有向图的遍历不可采用广度优先搜索
$ ^+ E+ h5 n. N% e5 m2 }0 W4 S[ ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为) R8 F$ d8 {/ ^; Z, h. r( e" m0 M
A. n-1 B. n C. n+1 D. n+2
$ i$ n, i7 d! d& S6 F! e( T$ n. n[ ] 9.设置溢出区的文件是2 A' m. C/ M% U9 {$ G$ Z
A.索引非顺序文件 B.ISAM文件# [; g3 ]% `. E( M2 ~ s: B( E: w7 j
C.VSAM文件 D.顺序文件/ }1 T% S& e# c4 D, j0 {9 _$ L
[ ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( C, D0 {" K5 b9 S) Y
A.{25,36,48,72,23,40,79,82,16,35}
/ w; ?. Z. a; rB.{25,36,48,72,16,23,40,79,82,35}
) {, s N! u5 n* R+ Z+ `" y# IC.{25,36,48,72,16,23,35,40,79,82}
: ^$ c5 C: ?7 d5 `- z# D% z% FD.{16,23,25,35,36,40,48,72,79,82}
+ n; V7 m! B6 G二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)
" t9 S# Y; y: ~$ z. D11.下面程序段中带下划线的语句的执行次数的数量级是( )。5 l' }9 p3 J, K6 f4 b2 |
i=1; WHILE(i<n) i=i*2;
# h z4 b+ V* T0 V& n7 @12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是( )。) D; |7 m/ i) }
13.无表头结点的链队列Q为空的条件是( )。/ C/ v7 d) v; N3 V; `
14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为( )。$ }: a$ Z; P* G& Q3 p( D9 I
15.一棵含999个结点的完全二叉树的深度为( )。
6 n; D$ z+ k I' ]- J( q( u4 G& E: l$ N16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在( )。
. A$ W/ d. N9 |/ a: n m# t& F17. 有向图G可拓扑排序的判别条件是( )。+ |) z/ j8 _6 v5 V
18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是( )。
' M: z2 h' a9 L Z g4 u19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为( )。
3 \6 p+ r5 J/ s# b! E20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。 ; a$ W* j9 z. B
三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)
, Y' f& b5 _" R21.比较线性表和栈的基本操作的不同点。$ S! B/ H$ {& f7 x0 [+ \) r
' U) {& J) b1 Y, k( C- S0 j4 d
, M \/ j7 ?; f7 x/ P7 K. Y3 b* W* |( V2 U
# \( b( }4 ?3 j9 n' J
6 |' Y/ o) i5 Y% V5 d$ W- o3 u: V2 z7 [
; w2 e! s) l+ @8 Y: ]6 K/ `% W
Z* I/ j4 z- H% F6 F$ Z4 @/ d- C7 C) {: Y/ |9 {2 N- X
2 m x& o. i/ A. R
22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:- g+ R9 b3 [) n( ?6 ^ m; [
试求:(1)该树的后序遍历序列。
5 D: v0 L, e- \& o5 K* n (2)画出该树的后序线索树。
7 E5 D9 n' K: `8 S) {1 2 3 4 5 6 7 8 9 10 11 / t5 r p3 }* c& r! l
A C B E D
: K; N7 g3 T4 I# K3 t [& E
7 M; \$ }3 e% A# T/ K
5 [& @3 h0 O) D1 l' l# S6 |) h' A" g. \6 X8 G0 R* Q0 ^* m
* c+ |: L) n, C( v3 k/ \* o6 @* V8 l% L
$ r. B C2 L) [# i& X) e. s
: _. f& N: S3 O3 F% b
0 H! z/ w* N" [# e' a. C+ q; U$ I9 K6 b# C
' }" d0 j9 n. x- Y" s
4 l2 m; J; [3 n23.分析顺序查找算法的“监视哨”设置作用
: s6 [% x' p7 {) J" ]5 {6 {% E$ ]# m. m% Z! M
) K3 d% e9 B" C+ c) l$ @' ~2 n
9 [, S- @: D4 d- j+ F3 B0 Y
+ R2 X. a+ c) O+ i7 J/ ^6 l+ B) C2 N6 H) |, f ^1 L/ P( p
' F, G$ c0 o2 {! M
1 V6 U0 \# X c2 P0 F7 T" R( P- H6 x* X! I% a# T) ]
( B1 n3 T( U4 A2 {& c V" ?: D5 F9 c) w8 g3 i
24.对n个整数的序列进行直接选择排序。9 {9 M( s3 R& }8 A3 X% |
(1)算法描述。
& a0 R6 D' @1 c# _, x( i (2)并给出实例(52 49 80 36 14 58 61 23 )的排序过程。
/ l7 U# v' p' E0 _
$ v$ b9 ~# o" U2 s& t1 G4 n4 U' J) ~+ @- h' n x0 _
3 f: _2 T4 a: e8 o6 S
5 q& v9 h/ x; s
! h6 Z2 o% A9 Q# f3 s3 }% q5 s: n) G
& v0 ^, L& H$ g) m* x1 R
/ ~2 M. w: f: U. ~7 r; o0 k4 h
+ E* P7 F* g' _" S* n. D& H: [! h0 d: N* w5 Q" Z! @
: H o8 y0 ?) c/ x1 L. t0 f: M2 a; j- {* n$ P
4 v( C& ~, F; l+ U# e4 }0 u9 u
% C. v# Z6 g+ D* v( w# y1 T1 T M* k
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为根的深度优先生成树。3 m+ X- b. R" n' e! b7 L
' U; Q$ x0 Q8 B" ]
" J4 ^) D1 s' u9 d& z; ~' R4 C1 Z# [0 B. d
. j; b. }2 H0 N* C% O; f9 q% V8 C( x, s# h" p1 b
. W. t; y3 Z& } v" @( A
. X6 w3 h2 m9 L2 G1 @. A
; T3 ?7 y; g$ Y T+ r' t9 E* G, t' d0 e$ X, o
/ w' a# i- E6 {7 R4 U) \
; n1 p o( P# q% p# D
1 d7 N6 O8 J- P1 X/ [
3 p" K3 e/ d/ b* m/ @9 D X3 u! l2 \, [. E
/ _+ S* O( X' y* i% D- A/ V, w) u4 b1 i. p
8 [6 \- H) q$ K% u, g* r, I4 v四、算法阅读题(本题10分)8 N# C% M# h3 D: b
26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。
+ Z# Z. S3 Z9 D void exchange_L( Linklist &L,int m ) {
( }$ U: v/ K' Y# E. X$ b2 n' q // 本算法实现单链表中前m个结点和后n个结点的整体互换8 t T% J+ |, H& ?( J9 Q
if ( m && L->next ) { // 链表不空且
7 h6 o4 C. u8 h$ D- C p = L->next; 0 R* H+ f9 |$ B6 C
(1) t g( T$ N, W
while( k< m && p ) { //(2)3 [3 g# j$ d- |/ Q' L
p = p->next; ++k; 5 b8 V) \4 V* G7 p3 o
} // while
7 r2 O8 C7 i& n! e+ \) k* |0 [ if (p && (3)) { // n!=0 时才需要修改指针
, d2 W/ C4 N3 L0 M ha = L->next; // 以指针 ha 记a1结点的位置
/ K9 U% {4 s* ?& [9 y; W (4)= p->next; // 将 b1 结点链接在头结点之后
5 j9 `7 T; s& w( _$ \ p->next = NULL; // 设am的后继为空; h. W; z: j0 I2 ?5 B1 p
q = L->next; // 令q 指向 b1结点
: T/ H: |5 J V0 v while (q->next)
9 y' J/ I2 e5 s2 c) H+ S3 q( k8 C q = q->next; // 查找 bn 结点
$ G, ^' i2 ^9 F. w+ T q->next = ha; // (5) z( \1 R; c! ~" H9 I. d
} // if(p), J+ Z! b/ v$ y; ~" Q; Q* d
} // if(m)
* x" A+ z+ T7 W. e( G } // exchange_L : M9 _( X8 ^. y# `+ j5 L/ [/ I
* g# @0 P) U6 j8 J( M; z(1)/ F( b9 x# t7 {* z% L2 J
(2)- Q1 ^/ `. E* w
(3)
8 b$ e2 d9 V H j# L(4)
& |+ @1 v4 \& a(5)
8 P/ ~* f+ p; q$ n" ~ \3 B! e+ a, V+ I' z
: u5 S4 o8 ^+ }4 \& h# E- A$ Z4 y: Z7 ]. {: @# j; n
6 i+ e3 g: j2 l6 U' m8 ]4 {
9 C4 \+ q: L! m5 ^! e& k" @5 G% A8 W) _: x' ?/ ~
/ Z+ |4 K* ^ R; q) y9 H/ P五、算法阅读题(本题10分)
9 h/ |/ y2 {' W& ?' f6 f27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。
0 N7 y' ^5 R+ gvoid Arrange(int A[],int n) {
# s- ^3 O, p0 ^ // n个整数存于数组A中 N$ [& R# [# t0 p& z
int i=0,j=n-1,x; // 数组下标从0开始
7 B9 O0 e' X' r+ z/ ], F" U while(i<j){& T5 b1 c& j* O9 c' M0 B ?& C) \+ Q
while(i<j && A[i]>0) i++;
4 a1 ?: E4 L r while(i<j && A[j]<0) j--;
) P1 z2 r* f! }0 j if(i<j) { // 交换A[i] 与A[j]
% |2 T8 }1 O2 K- S( x x=A[i]; A[i++]=A[j]; A[j--]=x;
; J% T/ |8 ~2 N$ ]( C }// if
; B+ g/ h; m3 i# L. Y+ @ }// while6 z C" C z S8 c y
}//Arrange" {: J- r! W. v1 `5 m7 |4 H
4 O& K5 a/ P5 t3 m6 C
(1)功能:
, K) F2 u9 _+ i2 P- }1 P(2)指针i和j的作用:
3 i. I' C. Z. `/ K" V# v1 R& d, }' U: @
六、算法设计题(本题10分)
) x O0 [4 I; E, y28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。
0 h) M( P' q5 P2 e! O- r2 Z' G6 A: G4 S8 x% H& r
$ H. v+ W Y3 a! p+ A. |$ T
0 o# v/ C% {4 ]; c
# j& g% `6 O- E7 ^8 U1 t c$ V- B( t2 G. M* \% X" v
( X x2 y9 S, R
! `7 E& m- _& z- o
3 i: h# i& s6 J( y# `4 U( R$ Q' C8 {2 J+ J
% _4 E! S2 s; ^% @$ b- p
7 s! s3 v$ V3 l
/ M% D6 E/ ?; _6 ?- D/ F( d; |
) K0 w# z& ^! v- w9 ]% _# U/ O
% C$ _# r" C l2 N o+ I5 ?9 j; G& o" _3 r8 x- `" W0 |( W& U' q8 A# u
+ p7 t9 f8 {0 N' Q/ Q' B, W9 }* o8 p G" L. j
3 u$ N& o) `8 J8 t
七、算法设计题(本题10分)
0 q6 J6 {+ z8 o% R+ `/ Y, z' F29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。
9 d$ z) q8 G l) @4 O$ g' u
: ~$ Q2 D$ r5 W, e ~( d6 J1 W9 I' |% x6 |( I$ q
5 {$ j8 U$ K _+ E
# y- O: }* R* x
# b- }& B e8 V. m; h
( V# t) a1 C* ?9 \2 d6 n1 K2 H; H4 R- ~: ~0 Q/ Y, z
1 V# d$ C2 [7 K# ~: _
, y/ G) _2 Q: Q' s0 Y
7 q( U7 G- {! S, s, C; {: I% y
+ n, X9 v$ f6 p2 J, ]- k1 A3 c5 F4 c) S5 T4 @4 Q
2 d2 K+ C% Q5 G) g1 B4 \; \
; P4 z9 o0 y K! ~* z9 D
$ M7 _, l! e/ t/ T1 ~* Y
7 }# i8 J8 C. d5 r. o
# n. O3 u9 B( i% @! d; E2 d; o/ g4 y. R2 j
1 z# w6 n3 V$ v$ E |
|