|
东 北 大 学 继 续 教 育 学 院5 b$ u; @: u3 z3 E/ ~4 M* y
# |$ ^# a8 T# R$ G. K 数据结构II X 试 卷(作业考核 线上2) A 卷
8 F9 m# Z! g) m% v. E0 O
3 R9 b B/ \0 v+ E% _# o" H" w, R学习中心: 院校学号: 姓名
) B/ f6 j7 e& A! m) l4 E& M
$ q W" j, x% B7 c1 R+ I, L5 \3 v(共 6 页)
0 F1 q7 n: \: ~2 d- s/ z总分 题号 一 二 三 四 五 六 七 八 九 十
- m! |4 e: `3 y 得分
. Q% t: b# w) _, q8 B e一、单选题(共30题,每题2分)
6 `( e4 z& |! P6 U# A9 m, x[ ]1.抽象数据类型的三个组成部分分别为
5 p+ G5 r: ?; ?1 kA.数据对象、数据关系和基本操作
3 S- }7 g7 W, U+ C; v# Z B.数据元素、逻辑结构和存储结构
: G. V( ^: a% o, y. S C.数据项、数据元素和数据类型3 X) w. n. Z7 i9 a& p2 Q2 n$ H$ A7 ?
D.数据元素、数据结构和数据类型& f5 r2 u8 g9 f1 _( s
[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
7 |. }; c' U) rA. 数据元素具有同一的特点
. e1 ^: B* q7 i7 {( I5 sB. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致8 X3 P/ a: o- S
C. 每个数据元素都一样- a! D$ `) P, \
D. 仅需要数据元素包含的数据项的个数相同
5 s) ^. N5 N/ _. d, e v[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是
7 Y) l5 b6 z/ L& R. `# |9 mA. ,n!,2n ,n3/2
9 l, o) H* u! X! n+ bB.n3/2,2n,nlogn,2100* [. x2 H$ }9 c5 J5 u
C.2n,log n,nlogn,n3/2
4 d2 ~ L/ F) Z8 G( Y8 _+ B: HD.2100,logn, 2n, nn+ N$ m; a4 u8 j& W" A
[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜/ ]% r! O+ c R# h# m- v: S
A.经常需要随机地存取元素 / M. f% x: d" L% T" h+ Z
B.经常需要进行插入和删除操作9 n4 R P) s. h! h8 |
C.表中元素需要占据一片连续的存储空间
1 x1 w8 J J* r" n' r' ]D.表中元素的个数不变2 v6 r4 k t* |2 E
[ ]5.设指针p指向双链表的某一结点,则双链表结构的对称性是
% t! N# j+ h9 h1 o9 RA. p->prior->next=p->next->next; % {- c4 C* W9 g1 |( z6 X. k
B. p->prior->prior=p->next->prior;0 x- U$ d- X' @1 s( }! K8 d3 n
C. p->prior->next=p-> next->prior;
6 q! \" @+ Q" p& {2 zD. p->next->next= p->prior->prior;
: y8 H# V7 }5 i- T/ s) q9 R[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为& C! M$ [+ z3 Z; k
A. s->next=q;p->next=s->next; 6 ]$ R" @5 n$ o* ^5 _' r& k
B. s->next=p;q->next=s->next;) F- s8 G: |6 b: \
C. p->next=s->next;s->next=q;
, a5 `5 _% t* DD. q->next=s->next;s->next=p;9 t4 k2 q+ S' A6 M
[ ]7. 栈和队列的共同特点是+ `; f% M& |: [, ^/ ?6 y9 _
A.只允许在端点处插入和删除元素
1 t6 f$ d" J+ N' X# s- FB.都是先进后出 ( w' ^8 a/ n6 H9 b! G3 q+ e
C.都是先进先出+ u! X- \0 C1 ]5 b6 f B
D.没有共同点
6 W! ?3 T5 m Z! _' c3 k[ ]8. 对于链队列,在进行插入运算时.. A' b3 j+ Y& @: [3 P( c n
A. 仅修改头指针 ! b+ y1 g/ E( q
B. 头、尾指针都要修改
+ s* N4 b6 g( y0 V C. 仅修改尾指针
% o8 ]- d: E% a9 q5 o0 ID.头、尾指针可能都要修改" x* Z) m. [0 U
[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为" n: v; X- s+ a
A.4 B.5 C. 6 D. 74 B4 S4 ]" O5 o9 h) R" h
[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是% t$ j: m% r. O
A.A,B,C,D B.D,C,B,A ! W0 N& S2 [ {6 J( p1 ?
C. A,C,D,B D. D,A,B,C X' ]. @+ O9 u# T: }
[ ]11.表达式a*(b+c)-d的后缀表达式是/ l5 _+ Q. q$ y A: z s
A.abcd*+- B.abc*+d- C.abc+*d- D.-+*abcd
: i& _' D( T& y( m$ p[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是
& K+ q+ H6 Z: kA. 空或只有一个结点 B.高度等于其结点数
; A) U0 E1 @ a- BC. 任一结点无左孩子 D.任一结点无右孩子
, c7 X( J, h3 G C" O[ ]13.下面的说法中正确的是( G' g$ E0 Y9 A* W- v: ~" Z
(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
7 z1 e3 g; i6 J) q I (2)按二叉树定义,具有三个结点的二叉树共有6种。
S$ d. Y9 C: h4 Y( _+ L" i( WA.(1),(2) B.(1)
( l+ j3 t0 ]# N6 a+ ^2 cC.(2) D.(1),(2)都错$ D1 a \- D s
[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的3 n) F* e( i' d! g8 Y
说法正确的是* }) q% F* u( X5 Z
A.树的后序遍历与其对应的二叉树的先序遍历相同 ) i/ f; H7 r6 e# P$ ~
B.树的后序遍历与其对应的二叉树的中序遍历相同
! Y) W% [0 l( J/ ]9 RC.树的先序序遍历与其对应的二叉树的中序遍历相同
+ J7 S& w" x: d! H) oD.以上都不对
& F- z6 k& o$ o8 z) i[ ]15.下列说法正确的是
$ [+ M7 L6 @/ W. q (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索
6 Y" D3 Q c# H @2 w1 ?3 X/ ? (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前
( O* \! x+ n7 G! p2 | (3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值5 V' V! E3 o: k# r# q6 K
A.(1)(2)(3) B.(1)(2)
; C3 K, e* s1 I7 ^1 M5 lC.(1)(3) D.都不对 b. A% f4 J. `
[ ]16. 二叉树的第k层的结点数最多为
; m( b5 p1 Z6 a9 } A.2k-1 B.2K+1
9 y/ U$ b( S2 B I' wC.2K-1 D. 2k-14 B$ y l7 V1 c. F
[ ]17.以下说法不正确的是& o6 c9 Q( y7 R" j5 X' k0 F3 j, O% G/ p
A.无向图中的极大连通子图称为连通分量
" m8 B3 b, N. I) o0 c+ I, D0 I B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
' P. q" }! G/ Z* a: o h `% u C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点' v: q5 f2 H5 \. A
D.有向图的遍历不可采用广度优先搜索7 s8 @' }$ h9 y* U+ {" |
[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中4 X/ n+ R( R& c
A. 第i行1的元素之和 B. 第i列1的元素之和
! _8 O8 H* v, g) x- KC. 第i行0的元素个数 D. 第i列非0的元素个数" Z% A+ d/ Z8 Q. B- r
[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至4 f) I: X8 _' T; D
少应是2 i8 t9 r; ~" @& R
A.5 B.6 C.7 D.8& |: D- `, b7 @5 L
[ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是 ( L, ~8 @+ \2 H- X6 }# T# y5 y& \
4 p" W7 h. @. K/ Y" ^: E) j( X
A. V1V2V3V4V5 B. V1V2V3V5V4
9 `# o7 t/ m* i2 T( c l* ZC. V1V4V3V5V2 D.V1V3V4V5V2
5 T* E! F1 z$ b# s" e1 x& E( e[ ]21.关键路径是事件结点网络中' X- i$ [& b: Y+ O* }) s: i
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
2 Z3 B* ^, n3 X+ N4 ~9 I C.最长的回路 D.最短的回路
* f }; J* {3 M; M& {- C[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是" L1 u+ L) P8 {; Z& `. X3 v8 r# g
A.8 B.3 C.5 D.9
$ n _ T. M6 X+ [% F; H[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是
* _. S6 q7 @: a DA. LL型 B. LR型 C. RL型 D. RR型
/ V! [3 r, H" A( `' D8 ]& [* K4 o[ ]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
& T) M7 ^8 z* Z. M A.插入排序 B.选择排序
: {9 b; x& k- z O# kC.快速排序 D.堆排序9 D9 k% @! h9 m% r9 B5 J
[ ]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是
& J N8 D5 w: [0 y( ^+ Z. }A. 堆排序 B. 冒泡排序
0 F9 {. Y$ [) U4 T+ `, b3 Q5 q1 c2 V5 nC. 直接选择排序 D. 快速排序8 [# b* n! M5 E% i, Y. j9 \: k" g' W
[ ]26. 有一程序段:i=1;WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是# p2 P& N* y! ^
A. O(n) B. O(log2n)
, p! F6 o2 A2 g- @+ g, S4 p C. O(nlog2n) D. O(n2)
0 r" I5 w X/ A. n% y7 e5 f[ ]27.无头结点的链队列Q为空的条件是
$ m. @% s4 A$ F$ UA. Q->front->next==Q->real=NULL
i; u8 u& U, ]; m0 q7 `B. Q->front==Q->real<>NULL
3 X* x" M5 ?% c8 E1 k" LC. Q->real==Q->front=NULL
- f) }: n% F' ^9 G0 |% sD. Q->real->next==Q->front<>NULL / b/ |6 Y5 V" b4 c( B
[ ]28. 有向图G可拓扑排序的判别条件是( \" k8 [9 C& j ^5 Y4 T% M
A. 不存在环 B. 存在环
) m( o+ {/ i( s* t* T4 iC. 存在入度为零的结点 D. 存在出度为零的结点
8 V" i/ G% p- J! V9 |; w[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间
! \2 u0 R/ ?+ j A. O(1) B. O(n) C. O(1og2n) D. O(n2)- i8 h( Y0 F* P0 _ y4 |
[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是* B; X5 @' H$ \0 ?
A.插入排序 B.选择排序
+ r$ v' M6 q4 w6 E v& FC.快速排序 D.堆排序
( D+ B' C$ b! g8 \" C6 L0 {二、综合题(共4题,每题10分)+ V5 o6 I/ j! O0 V q5 K
31、阅读算法,在横线处填入语句或注释。- [$ R8 w) A; V5 W& J4 v# {
void exchange_L( Linklist &L,int m ) {
5 O' i7 e! T" G // 带头结点的单链表中前m个结点和后n个结点的整体互换
& p4 L$ q+ i+ M# j" H9 x+ a* I if ( m && L->next ) { // 链表非空
/ M/ a+ _+ l: v- k1 w p = L->next; 0 I$ w+ O: z+ |5 [/ Y
(1)// k取值8 G+ K( \! M- ~9 K0 Z4 F* h
while( k< m && p ) { //(2)1 |0 y6 }+ ^& V7 z- x& p5 z
p = p->next; ++k;
' S$ g& i; c/ r: N$ H W: @ } // while + b$ G: M) J3 X" K# n+ {9 s" n
if (p && (3)) { // n!=0 时才需要修改指针# M3 G& c$ a n! @7 U1 K
ha = L->next; // 以指针 ha 记a1结点的位置/ d+ r( W' m1 D. p5 ?2 d" F
L->next= p->next; // 将 b1 结点链接在头结点后% b. K, l+ e% O8 D5 U3 G
p->next =(4); // 设am的后继
* C- _& X, w& [/ \7 D' x . [2 ~8 E5 r1 f' l3 Q6 {
q = L->next; // 令q 指向 b1结点
; W5 M# Q2 f' Q5 L, C) | while (q->next) " S2 c o; l; g' n6 V; ]
q = q->next; // 查找 bn 结点
$ o9 _7 \ Q! _% I0 w$ p q->next =(5)//将第 a1 结点链接到 bn 结点之后% h/ O+ p2 ~$ D9 M" M0 P! h4 S0 I& U
} // if(p)
8 F' ^6 o9 r& g8 t; Z } // if(m)
5 D+ [7 \' P _ } // exchange_L
9 A4 T, S' r) L5 T/ s' S# x9 t0 f% [5 H" O( v, a5 @
" w0 l* M: D9 O. w2 f5 ^! |4 |: R2 B4 _9 ~$ u$ l+ K/ ^
: _/ `2 ]3 W% O& b7 z% n. D5 A
9 _/ K8 O! r5 k, p" i* _
) W' V/ Z( o# Z# u- _! K$ k2 ]/ P
" j& `, D, k6 p$ k& H( |) z9 R, K4 [8 y' \& P9 Y
2 r! R$ O! B# J& k3 C7 H; t0 u+ p
5 [5 }8 N$ g+ R; S0 C% R$ f& C7 Q/ p9 d
32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。% @% h6 v$ G1 Z0 K
7 s6 ?- U5 \, g# Z, ~* ^ V9 C- P
0 G5 q7 |/ t6 ~4 f1 T2 S; h7 j1 d0 P- b/ S, n. J4 U( X
@& S a; v6 W0 H0 H! G" p; y/ Y- w$ x. e0 P) S/ s( K, u* o
' V6 ]) l' g! m0 x( G# d* \* t9 c' d
- j6 q" M' k" |0 T+ S/ C$ e! c$ t
# m6 ^1 i) a( f; O5 K
- u. W; _$ v2 V7 m7 m9 _ P2 a/ I9 C: x$ Z
; j+ w3 E; h; J
$ D. Y$ |7 v9 x9 ]+ N' C* B5 Y
6 U# A q4 b) p0 F( h! S' L
* B$ o( g; w7 a/ Y3 b" e; V3 {33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。/ y0 T1 o7 d0 k2 v/ l# d
逆邻接表存储结构定义如下:
0 d6 u" A- ^/ N3 E顶点结构 表结点结构
* m. D3 R% m% X- q, c) yvexdata firstin ! L9 F* n7 r# v7 v+ b5 b. Z# q1 E1 E
adjvex nfo firstarc
" q5 t8 G6 o2 G6 \
& j& {$ _' H, D. u
2 d/ T4 Q& ]" N# C: s1 Y
' U* I E1 B/ a) u: y! q0 q# o
" e5 s' s& i/ H: B, y1 Y3 O) X9 L" w T8 u8 U! h$ A
6 Q+ V0 N) _0 {# m8 L
# H+ N {- I2 T5 p( ~
# u9 t, V& o! G7 M( N
5 A& n1 p8 Y1 O# Y8 x( K& w! _; K2 E8 P0 o3 Y4 e
, }4 b1 S% R! C T! o! [% S
( F$ E9 Y) z. H
" x" n% P! [7 ]' g9 J
7 ]0 S4 d4 }( t
* _ W# |/ ?3 z o( e5 c
9 u4 C4 V4 L4 x34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。
6 o* {! V4 G( l7 g* }, Q* `( a+ {试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。4 R' B8 K: C( l6 ~) e6 Y( m0 H' p. n
(2)计算等概率情况下,查找成功的平均查找长度。. w2 I# V6 L" `
, }& Q* x) g* s3 {6 f. D6 i
" N4 V5 ^) w# X; ^" L8 A! I0 x5 g/ B% e7 o |3 a0 |2 V
/ L) O3 B0 _! |
% Q+ X& }. `6 @2 z2 C8 }: _; r6 E9 g! B! W* y
( D, c# l6 j% @$ a6 z" X7 v7 C( ~" [2 Z! @ c/ l
" L4 j2 Q2 B( F/ s6 G% ?. ~7 d( p
$ K- m( u( |$ s1 F" H
, u" F/ {* L8 Z3 | H+ x: j2 n6 `
, B C4 h- j0 Z, u+ C
* M( u& Z% q4 c, A
9 ?* w- q( }4 d$ |+ `% A O
4 ?+ E7 K( L3 u# q# D* n" k C; Y
2 Z j# Z& z" ^9 M) y" F( ]
$ l# e( N- N2 q0 ]/ b7 C) d2 ^# [* {' n, X0 f
5 e& g9 y3 q7 Z3 l) B
|
|