|
东 北 大 学 继 续 教 育 学 院
$ b: m7 B6 {; D( [/ k j# k' N, {# \, U! k" o6 t- f |! [
数据结构II X 试 卷(作业考核 线上2) A 卷
p1 U7 |* m2 p$ I
2 D0 C' v$ \) L9 `, S: D学习中心: 院校学号: 姓名
: K0 y) Z$ R$ u$ H1 P5 |! ^
8 [7 i( N( B1 K6 |# g(共 6 页) 5 S) m& l" N/ f) ^# w, h1 g8 b% z
总分 题号 一 二 三 四 五 六 七 八 九 十
|" H/ Z9 p( G 得分 7 _% k2 W. n! G5 }
一、单选题(共30题,每题2分) a% x: n) f$ d
[ ]1.抽象数据类型的三个组成部分分别为& H5 t& B) `+ f- G, x
A.数据对象、数据关系和基本操作8 { S2 _8 v+ `2 ]- J! S
B.数据元素、逻辑结构和存储结构
4 `. _! B! r5 H7 J7 b C.数据项、数据元素和数据类型
5 X: m. \/ M% ]$ T& l5 T D.数据元素、数据结构和数据类型
% s! T. J5 f/ c[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
! P ~1 e( e/ S7 `1 t" WA. 数据元素具有同一的特点0 `4 ]) K% G3 C2 M# p0 C, ]
B. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致: |- B( b9 Z. X1 v$ S& l7 T
C. 每个数据元素都一样
- a( S0 F4 g9 ?* h4 y! r9 ? E* w, WD. 仅需要数据元素包含的数据项的个数相同
/ \# j$ q' A& z& x V W[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是- i! k# W" q4 q0 {
A. ,n!,2n ,n3/2
) D6 g' r o4 u o" fB.n3/2,2n,nlogn,2100: z# @) v) Z* k# Y& w# R$ B8 Z
C.2n,log n,nlogn,n3/2 ' B$ A8 Q7 ?1 l& b: }) |5 Z8 Q: [$ a
D.2100,logn, 2n, nn+ v# J/ z- R. F6 f( A \0 L
[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜
+ F4 m2 T f9 w/ K1 P A.经常需要随机地存取元素 % l; I( G0 V9 S9 E
B.经常需要进行插入和删除操作3 n! B" r( S% ?5 c& @/ _
C.表中元素需要占据一片连续的存储空间
# A& Y2 D9 S" U) G& d# O( T" n0 _D.表中元素的个数不变0 C9 {6 a- K- R
[ ]5.设指针p指向双链表的某一结点,则双链表结构的对称性是: R" ^9 f& h# |: Y6 x% V
A. p->prior->next=p->next->next;
% a3 n8 n+ \% r& a3 s1 \B. p->prior->prior=p->next->prior; r3 m8 l U# ~! O. \* k
C. p->prior->next=p-> next->prior; / S9 ~8 S0 T- D) P9 k
D. p->next->next= p->prior->prior;
9 P' V) _6 h: q3 {" m[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
& v1 t9 H4 |# ` A. s->next=q;p->next=s->next; , {: E+ j7 Z* a: ]8 o
B. s->next=p;q->next=s->next;
; P9 L" H0 {0 eC. p->next=s->next;s->next=q;! D, Z0 ]0 [9 ~. V g! F
D. q->next=s->next;s->next=p;2 i; N$ g+ `1 M7 u* W1 @) F1 J* o
[ ]7. 栈和队列的共同特点是. s6 g7 g, @( T$ J3 F
A.只允许在端点处插入和删除元素
; f% T+ [% b AB.都是先进后出 7 k* |' J: B* M! k; U
C.都是先进先出
9 j; Y) T% H6 O7 Y. o' T7 t4 UD.没有共同点 2 `2 Z9 F2 X1 z
[ ]8. 对于链队列,在进行插入运算时.; {+ @4 q- u( h7 |* K2 a! w7 {
A. 仅修改头指针 ! I1 U1 ] a1 v
B. 头、尾指针都要修改5 ~2 Q* Z, R" [8 N" c1 @" O& l
C. 仅修改尾指针 * P! x" i H/ \3 ]
D.头、尾指针可能都要修改
/ a6 c3 F8 H3 p9 G) w/ Z- L6 I[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为
/ p5 S7 O8 u4 T: B# W A.4 B.5 C. 6 D. 70 i; f! M; n, r1 J
[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是' X% ^' P5 b/ u" W
A.A,B,C,D B.D,C,B,A 4 Z( n; b0 m( X/ g: `' D o
C. A,C,D,B D. D,A,B,C' h, `1 l9 O: q0 e
[ ]11.表达式a*(b+c)-d的后缀表达式是9 R* C1 P: o% Z0 r8 f- a
A.abcd*+- B.abc*+d- C.abc+*d- D.-+*abcd! d" S9 Z' W# a4 U; e
[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是* a' @( s3 b' x& J/ U( w
A. 空或只有一个结点 B.高度等于其结点数
/ Q) l% d/ G. R% D9 ^) U/ uC. 任一结点无左孩子 D.任一结点无右孩子
9 q/ g- d1 q/ u) d9 w( e+ E[ ]13.下面的说法中正确的是
8 d- X$ A. g1 {! t9 o9 _% q' N9 p G (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。4 Z# O' B' ]5 l3 f) \& ?
(2)按二叉树定义,具有三个结点的二叉树共有6种。
: ]% N7 i W3 q: P- K/ l: MA.(1),(2) B.(1)
- l' n2 N i# l- ~* D& o( |! `C.(2) D.(1),(2)都错
7 A7 k/ }& ?+ r- Q+ L! b[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的
, g+ B% _4 F7 P4 B说法正确的是
2 a" a* N% r. f A.树的后序遍历与其对应的二叉树的先序遍历相同 1 I }$ @* y: l( ]7 A
B.树的后序遍历与其对应的二叉树的中序遍历相同: H q D# J0 e# u4 k5 _
C.树的先序序遍历与其对应的二叉树的中序遍历相同
$ X4 }! r- a( a* V8 FD.以上都不对
7 H' ^" `4 t+ o[ ]15.下列说法正确的是
' A1 p+ @2 {& L/ a! f& H+ B (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索" f. |- o- N2 Y7 u
(2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前" {- F7 }/ ?) K* d G
(3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值
+ u# n4 f( q7 O) s. GA.(1)(2)(3) B.(1)(2)
( L; S8 K: N* ]: o9 @& x; w1 k& i1 rC.(1)(3) D.都不对" v6 d" Z* n* f4 @* q4 o& p
[ ]16. 二叉树的第k层的结点数最多为, n+ L% Q/ T P# ^3 w- ]
A.2k-1 B.2K+1 5 r- O% p/ D1 [; ^
C.2K-1 D. 2k-1
/ N$ W& K; B5 a. E[ ]17.以下说法不正确的是0 O2 H8 R2 c( T0 c6 ]
A.无向图中的极大连通子图称为连通分量
8 [; u( K4 Y& n7 W" N! c/ {0 i! v" E B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
! K: @* C- _; R: \+ ^) | C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点$ i: M. A- I+ f) u1 l
D.有向图的遍历不可采用广度优先搜索0 ~9 d- v9 v2 o
[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中6 T( s i! Z6 o) Y% i' v5 G3 q
A. 第i行1的元素之和 B. 第i列1的元素之和
8 I7 S/ M' c2 p. ?0 J* \C. 第i行0的元素个数 D. 第i列非0的元素个数( @) j5 g3 @9 D) s! ]' ~5 U# [
[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至$ w( K+ _ i; L( W0 J
少应是. s' }2 o4 c7 e; N3 R
A.5 B.6 C.7 D.8
, \' Z. T* y# k$ l' y [ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是 . q* c2 B; a# {; }, N
1 G) n' T3 w; r. M% V
A. V1V2V3V4V5 B. V1V2V3V5V4
3 [: t; c" K* y5 `+ L( p# iC. V1V4V3V5V2 D.V1V3V4V5V2 2 O, i. @! u& U a
[ ]21.关键路径是事件结点网络中1 e# q ~% G! n
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
; T/ p$ M2 }3 G C.最长的回路 D.最短的回路
3 r$ c! e' r3 [+ M8 j+ W; i[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是+ O+ Q4 |5 y) f/ V% f( h
A.8 B.3 C.5 D.9
8 D8 A% F+ w! r. s, [/ t[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是
( O7 N/ F _" O z9 ?! ~# S6 S& x( FA. LL型 B. LR型 C. RL型 D. RR型
6 h; F0 S5 S; x# u: |[ ]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
3 }1 {6 O2 x/ X$ F0 {5 c A.插入排序 B.选择排序
" j8 j7 v3 A" ZC.快速排序 D.堆排序
( a( \+ y' W* e2 F8 s[ ]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是( M( H4 q+ z1 ~8 M
A. 堆排序 B. 冒泡排序 3 M7 c( y9 m1 c. ~- z6 L
C. 直接选择排序 D. 快速排序
; b, `4 o0 w# Y% M( h c[ ]26. 有一程序段:i=1;WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是
! O. p; B/ k$ E8 B: rA. O(n) B. O(log2n)
" l7 P; i" Z: z5 }6 d C. O(nlog2n) D. O(n2). e( X6 B( X5 n( i
[ ]27.无头结点的链队列Q为空的条件是
6 z& l7 T; X3 @$ EA. Q->front->next==Q->real=NULL
2 b* i$ L# ?" ]B. Q->front==Q->real<>NULL 7 Y1 r7 i, p% M/ H* D; K
C. Q->real==Q->front=NULL . O& ~$ j7 O3 _5 E1 A* _6 ^0 ~
D. Q->real->next==Q->front<>NULL
* ]5 k/ i# C/ T! x' m$ S( @1 h[ ]28. 有向图G可拓扑排序的判别条件是
( R" d: S/ S" I8 I8 H# _A. 不存在环 B. 存在环 # b* `1 o" d7 h
C. 存在入度为零的结点 D. 存在出度为零的结点
0 v+ R8 ]; q; I* K9 ? b# ]4 e[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间
$ F1 V9 _5 m& C c A. O(1) B. O(n) C. O(1og2n) D. O(n2)
1 h) W: i) n4 y5 x# O+ Q[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
1 `: _, F( _5 F C A.插入排序 B.选择排序
! ^6 O$ f! \8 j. D+ p$ K( j5 P) vC.快速排序 D.堆排序
' P, Y& ?0 x; h* }. [二、综合题(共4题,每题10分)% |: A) N: b7 L1 e. H
31、阅读算法,在横线处填入语句或注释。, z1 c2 n& l* {. Y6 a" [: b
void exchange_L( Linklist &L,int m ) {
/ a4 l) Z) \ G& \1 o // 带头结点的单链表中前m个结点和后n个结点的整体互换
$ I+ p" R4 e- c if ( m && L->next ) { // 链表非空. z& L1 D; w* N: \
p = L->next; 3 B3 ~' E- }3 k* @ k3 h& E
(1)// k取值! s3 s6 e3 h$ k r. `
while( k< m && p ) { //(2)% Y4 _5 q) w# l# w# h
p = p->next; ++k;
" \6 `* [6 \9 y/ L, X ], q5 l1 y8 z: { } // while 1 T1 t! M, r1 U
if (p && (3)) { // n!=0 时才需要修改指针- H1 Y5 k! e! r' w
ha = L->next; // 以指针 ha 记a1结点的位置
4 U: S, b' x8 R" b }' B, b9 O. _ L->next= p->next; // 将 b1 结点链接在头结点后1 Z5 ^9 B$ f: s
p->next =(4); // 设am的后继
) V0 T5 } h6 W5 q; h) d
) X( d+ d4 H( J& ?' k q = L->next; // 令q 指向 b1结点
0 r1 F$ K$ P+ x T0 a6 m while (q->next)
* ~! _0 o2 m3 J1 ]1 _( }, j, ]: A q = q->next; // 查找 bn 结点 # X: c# Y3 i, K1 o
q->next =(5)//将第 a1 结点链接到 bn 结点之后$ I! f7 ?* m- g- g- x
} // if(p)
; C3 m% C' {3 T- j } // if(m). I0 o' |0 j! l7 f: I
} // exchange_L 2 {, O, T" {! G
& u! e- j& _6 ?
1 V& Y* ^/ |6 j% J' r5 b$ @; l4 I
4 Q' M% h6 c1 y. z" @* d% m9 y
, o; L& w6 y: z2 ?8 j' i0 C& s! Q! v/ p: X. Q k
( J$ Y4 K7 z+ q$ a" p* C
6 H9 |% x4 f( j8 Q1 c$ l. N9 m3 I% q M0 U+ ^
" ~$ N4 j$ \7 M0 h8 I8 f* V9 U) p9 r- f
3 J6 x( v% ?% v, R& O$ w7 {0 M32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。! ]1 Y$ v9 H( ~. w$ G8 s
9 Q* Q3 T! r; ~6 i- A5 J+ m% R. v; D' ^1 ]) ?
, Q! j. `: D: l7 g) a+ P
- O' Q+ L2 D+ w, t; Y: p- H
- }1 s( l& `* s+ X, q0 ~! U/ _ `" g n0 M: R( z. H& Z
, F- ~# U. H' q6 b3 K- ?
9 a0 k, N8 G; S( O1 }: [+ X
3 y5 ^( P! ?/ w6 |, C+ s
% f8 l1 T( w6 g8 S
+ N8 W9 {7 h( L2 i6 Y
# ~8 J& U8 x; M2 {; }' L
" I. x4 o Z4 H$ R; A& e
. b" L, r$ P3 w$ |' t
6 _* T' a) e$ ^/ E" x5 f8 f
~% n j6 _+ i) `- O( G4 X/ g33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
+ i1 _1 c8 D+ b# N7 e/ R逆邻接表存储结构定义如下:
- c' e7 A$ K* e, d6 }顶点结构 表结点结构
& y) J2 |9 e8 p, F& G- ?) uvexdata firstin
7 U8 g4 ^9 z9 l9 u+ l6 badjvex nfo firstarc
. ]8 H; H" Q9 K0 t9 x- [. {" o8 `- j; j$ W: \4 _/ h7 Z C
' Y6 z: s) C! H# b- X* e
, Y4 _ W' U& Q" t* f7 A# k! w7 M' H/ k
, U; ^# k; O, Q3 }+ a% _5 \0 `) k# \9 Q
% E6 w) I: `& k$ ]5 q
4 h/ l& j- ^0 g+ R: Y# R# {2 o5 ^4 U: q" G% T( Y
: m, n9 G4 P$ d* R L; e/ L8 V
' j+ Q/ E t' y( s
- z8 y: [* T/ m: n; m( M! V2 n+ t, s
/ M* f! C0 n) u! z3 F+ O( q1 r$ I( F! w8 @
" x- y( \7 ]1 ^5 }4 I" _0 F34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。4 W1 `% S2 H4 k3 r9 H
试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。
Z1 [- }' g2 |( w- [) @(2)计算等概率情况下,查找成功的平均查找长度。
, I" I2 [& ?6 G4 }$ f3 [" n' a$ Z7 t& \
' z4 g! E5 T, ~! C. ` `$ \ Y
5 A0 D T- T" k1 Z6 ^ U( P$ F0 |5 D, Z$ ?
- k& t$ X, g: e8 ^; J
7 n+ u, u& K# V0 S; ?, v
; g( o/ o* J" E5 }5 D9 l! [
1 M1 Y. T9 @% Q0 u1 x7 N+ K3 ?7 W9 q4 g: P& ]
: J5 X }# u: j" v
4 |/ C7 C' H) L- K+ x* @) Q+ [0 G6 n9 d' `) o# h& e; A
8 Q- J7 h" A# b: G$ R9 [ s
& U' R! x3 V4 g- z
! E# Y C+ ]. E; Y+ B1 t
4 v# C1 z' X8 g- [1 ?
( l" F5 ]. @1 b* f
3 y# B( h2 Z$ h) ~/ P( }8 `7 @ x
7 F. O5 S. u }! o3 `
# f0 Y g; @" b% B3 K |
|