|
|
东 北 大 学 继 续 教 育 学 院- J z3 |, p) O+ j q" c5 v
5 C7 V1 g1 I9 ~& I 数据结构II X 试 卷（作业考核 线上2） A 卷( [0 |3 {& |2 C# K+ D( j$ L
. `: F8 P! D2 ?3 B, i( b+ ~2 m
学习中心： 院校学号： 姓名 ; b* ]; v3 o# p* d9 C3 h/ i; g) a
& ]( C. P5 @3 E0 q
（共 6 页） 1 i3 z, Q$ ~* q1 Y7 }, Q+ [# O* b9 ^
总分 题号 一 二 三 四 五 六 七 八 九 十
5 K5 H z. p% ~% h; s 得分 , x8 L' }" k3 K! S5 b$ d6 N# \
一、单选题（共30题，每题2分）2 H* U" R/ G) [" g% L
[ ]1．抽象数据类型的三个组成部分分别为9 K; m M5 ^9 B& E3 S
A．数据对象、数据关系和基本操作3 h3 ^) e' V) |2 t- l5 f0 f5 r
B．数据元素、逻辑结构和存储结构0 V4 ?, [* X( b7 R+ {$ Z8 s
C．数据项、数据元素和数据类型! ^" W( k" Y T6 ]9 K$ o* b" n: o
D．数据元素、数据结构和数据类型
6 i; a- o( N* X' ?& c[ ]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为
, I+ g+ H0 A" a( Y5 cA. 数据元素具有同一的特点
& z7 A8 r* s3 f& v2 [B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
9 ?" B% Q7 T6 b8 yC. 每个数据元素都一样- {8 M# g4 R0 D% @' y" |4 o' A
D. 仅需要数据元素包含的数据项的个数相同6 Q; P# W" z9 S: {
[ ]3．下列各式中，按增长率由小至大的顺序正确排列的是
5 e% E# |4 `# R6 MA． ，n！，2n ，n3/2
! g9 ~. k/ P+ u4 nB．n3/2，2n，nlogn，2100% ?8 s, L, N+ W2 A
C．2n，log n，nlogn，n3/2
: L! N( K& X; D7 m, ED．2100，logn, 2n, nn
& m$ _4 ^+ O! |0 m8 V+ ~[ ]4. 在下列哪种情况下，线性表应当采用链表表示为宜
5 {% X2 x, Y0 h% k A.经常需要随机地存取元素 2 W9 @; E. v& b( p% A
B.经常需要进行插入和删除操作
( }* S; t, o+ t% q' y C.表中元素需要占据一片连续的存储空间
' ~9 E$ X, C$ gD.表中元素的个数不变8 m; `5 H' Y" _/ x7 S8 b4 w
[ ]5．设指针p指向双链表的某一结点，则双链表结构的对称性是# P+ C+ W9 O9 O' G0 _- W
A. p->prior->next=p->next->next;
! S" L4 O% K2 i4 t0 m+ iB. p->prior->prior=p->next->prior;
^* Z P* M, R/ v+ LC. p->prior->next=p-> next->prior; ) [# b1 Q' Z" N* x0 d8 d
D. p->next->next= p->prior->prior;* ?, z1 O \" Q/ D1 c8 {
[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为
3 O) r( w5 G7 ?( u5 U7 I9 r8 e A. s->next=q；p->next=s->next；
0 ?) }1 K" m! D3 R B. s->next=p；q->next=s->next；* @$ @% t5 J& K
C. p->next=s->next；s->next=q；
- w% e- L: K2 }4 \D. q->next=s->next；s->next=p；6 A+ U1 [/ w+ z
[ ]7. 栈和队列的共同特点是6 Q+ T5 r+ k2 y0 E; [# g5 X
A.只允许在端点处插入和删除元素
' Q0 }# d) @! ?. wB.都是先进后出
# ^( f# G; u2 }; @1 y/ C. iC.都是先进先出# F; ]7 ^! r M3 L! G
D.没有共同点 : o1 ?* G! t3 y) h4 U
[ ]8. 对于链队列，在进行插入运算时.1 ~7 Z; b2 R5 G8 C8 Z2 }
A. 仅修改头指针 , n8 ~; X0 b/ L8 c$ R! `1 N, Z
B. 头、尾指针都要修改5 g! G% o. S9 S
C. 仅修改尾指针 % k) B2 H) i4 v5 ~' X Z4 W' a
D.头、尾指针可能都要修改! v$ N% c8 l p! Q
[ ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为) E4 u! o+ M0 g# f
A．4 B．5 C. 6 D. 7
. Y5 F E( j( s[ ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是6 {& g- o$ D) f" Z9 Y* g
A．A，B，C，D B．D，C，B，A
0 D8 F- n8 x9 O- M8 C: VC. A，C，D，B D. D，A，B，C
( I' Q6 S' O+ ?( Z8 ?8 i[ ]11．表达式a*(b+c)-d的后缀表达式是9 O% s* b4 }+ X# Y
A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd. I& R9 G, r) Y' n' |
[ ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是$ ~, u. o: v6 \, L
A. 空或只有一个结点 B.高度等于其结点数
3 j; A% J9 T5 V( J/ y( BC. 任一结点无左孩子 D.任一结点无右孩子0 C( S$ a- ]% e6 P# C
[ ]13．下面的说法中正确的是4 s0 D5 c9 O$ R: e
(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
+ Z F$ z( S( k4 F/ A (2)按二叉树定义，具有三个结点的二叉树共有6种。
, d8 G' O+ C1 y! [1 _8 U) }! W% DA．(1)，(2) B．(1)
3 A% G1 ~, w$ v' |: E& K! h. }- [C．(2) D．(1)，(2)都错2 Q9 E& {+ Q: a* \; U
[ ]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的3 b' V( M, B- G7 x/ c/ L
说法正确的是9 C' B/ U1 @6 I6 D0 }4 B
A．树的后序遍历与其对应的二叉树的先序遍历相同 1 S. v- \6 Y9 p) u0 v7 ~! |
B．树的后序遍历与其对应的二叉树的中序遍历相同4 F0 `& F& [* Z: M0 T
C．树的先序序遍历与其对应的二叉树的中序遍历相同
7 I9 y$ ^4 u3 ? D B% g7 t/ U; [0 yD．以上都不对
. K: K9 b/ _2 ~4 }[ ]15．下列说法正确的是# x: I5 a0 R- W- U
(1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索
2 ~# Y. M2 ^2 m' B, I3 ] (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前
! ]. G$ n1 R/ W; T' \. }) q' a (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值% X# W; l7 t/ [2 w5 r0 Y( ?
A．(1)(2)(3) B．(1)(2)
3 {0 H6 h1 z% q$ t2 {. \C．(1)(3) D．都不对; x! p% } Y1 F6 d. h( E
[ ]16. 二叉树的第k层的结点数最多为
: u" z; X4 r) Y' b- o4 t+ d# U/ D A．2k-1 B.2K+1
2 W7 V" M2 i0 o& P+ yC.2K-1 D. 2k-1; T# }8 T+ w7 s: p! c9 d, Q
[ ]17．以下说法不正确的是
7 }' ?/ T& `" f A．无向图中的极大连通子图称为连通分量
+ \: |1 U* S) b3 w" _7 y+ d B．连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点6 L/ `" L. \5 b
C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
+ Y2 W; y$ u' g1 E7 [ D．有向图的遍历不可采用广度优先搜索* M; o& m3 y# \$ Y$ u. c, y
[ ]18．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
& c7 ^" a; {* z) Y, E6 HA. 第i行1的元素之和 B. 第i列1的元素之和
& o& m n; n. ]3 _; aC. 第i行0的元素个数 D. 第i列非0的元素个数
" T/ |* J% I' R0 D" G4 Y. H+ p[ ]19. 设有6个结点的无向图，该图确保是一个连通图的有效边条数至! D! k- k' g9 O) {- n: a
少应是* a7 {$ q* r6 L4 j
A.5 B.6 C.7 D.8
# O" a' r3 M S3 h9 i" V [ ]20．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是 " q7 x" n" I+ m( V8 S# J
: b; Z: x% K/ p4 `: Q# d( u$ U; QA. V1V2V3V4V5 B. V1V2V3V5V49 v0 Z- j7 h4 K
C. V1V4V3V5V2 D.V1V3V4V5V2 - N; o" U- z7 d% f5 u% A
[ ]21．关键路径是事件结点网络中
; X+ }3 x1 b' ^6 @+ | A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
: z* H+ [' K' k; o C．最长的回路 D．最短的回路
8 v# L- b: H, r7 {+ r[ ]22．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是$ v9 ^( \& ~- _8 v: t/ U
A．8 B．3 C．5 D．9
1 v, z7 c7 `" {, T* n, ^( l[ ]23．.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
7 B! |3 b3 K% c+ a1 {1 V$ cA. LL型 B. LR型 C. RL型 D. RR型6 E5 i" O/ b B
[ ]24．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是* n b1 T- t6 t$ B
A．插入排序 B．选择排序 & A5 S/ w$ u: ^! p( _* A
C．快速排序 D．堆排序
. ?8 O( w( {0 U0 w$ ?[ ]25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是
& j; e; Q ~3 BA. 堆排序 B. 冒泡排序 - l1 w5 k9 S8 R1 T l7 }
C. 直接选择排序 D. 快速排序7 k! H$ D; @9 n `
[ ]26. 有一程序段:i=1；WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是( Y$ T5 i0 J& F) n f
A. O(n) B. O(log2n) / \( o, Z3 W* b8 |/ a/ c6 Z
C. O(nlog2n) D. O(n2)! w4 t i1 V; J% W! w$ @3 P3 e' ^
[ ]27.无头结点的链队列Q为空的条件是4 S5 T1 h: a% F: R
A. Q->front->next==Q->real=NULL 1 v2 P! u- y; J# ]9 W
B. Q->front==Q->real<>NULL " ? b4 e6 H, ]; L7 H6 `
C. Q->real==Q->front=NULL 2 Q3 e- q X/ |( S
D. Q->real->next==Q->front<>NULL 9 L9 E9 H: W4 a- s5 i3 ^7 ?
[ ]28. 有向图G可拓扑排序的判别条件是
" k2 b# R' ]. w" M8 a' }A. 不存在环 B. 存在环 & j+ ^! \+ Q, D7 j
C. 存在入度为零的结点 D. 存在出度为零的结点
& I7 R: d9 H+ R; h3 I; n9 l& w[ ]29. 对n个记录的文件进行快速排序，所需要的辅助存储空间0 I4 F9 G8 {3 S. w# s6 U( {! o5 q
A. O（1） B. O（n） C. O（1og2n） D. O（n2）4 o6 s( I4 m( H! ?# `3 ^4 E
[ ]30. 下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是$ O0 h A2 ^ T: C9 N8 }: U6 i
A．插入排序 B．选择排序 # J& V: {& o9 D T0 L8 l4 Z
C．快速排序 D．堆排序7 c, f) ?" o. y* S' A' R
二、综合题（共4题，每题10分）! M+ L$ I2 o* [/ }
31、阅读算法，在横线处填入语句或注释。
- b a; F1 P( w8 l: cvoid exchange_L( Linklist &L，int m ) {
2 X, X# S) a( W // 带头结点的单链表中前m个结点和后n个结点的整体互换, e# t, F/ B. ]1 w f$ L
if ( m && L->next ) { // 链表非空/ }4 w1 T/ L- B' h; h+ K
p = L->next; 4 u, \3 H5 P3 c7 M* @, O; |+ Y
（1）// k取值) {/ r; }" B: K1 k0 k0 k# p6 n' S9 P
while( k< m && p ) { //（2）
; ] j+ c$ L- v/ y p = p->next; ++k; . ?$ N) m2 t! I; j5 ]" P
} // while 0 r" {1 K/ x. k2 A" a, H
if (p && （3）) { // n!=0 时才需要修改指针. Y. W" r8 V# L' g* @' [; D" k, Z; I( l
ha = L->next; // 以指针 ha 记a1结点的位置
6 K: @& g2 i `& a5 Y1 H L->next= p->next; // 将 b1 结点链接在头结点后5 L8 p/ H. Z# B, L
p->next =（4）; // 设am的后继
2 B: t% O2 O) p9 M # A5 L+ N- U6 e! Q2 ]+ p0 e4 j) a
q = L->next; // 令q 指向 b1结点
* s1 @# O8 s- X3 }( j3 d while (q->next) : C7 V3 G; l0 M! Y* j% U" I" |/ m
q = q->next; // 查找 bn 结点
4 {5 r3 x1 S' f5 R" l" x8 G q->next =（5）//将第 a1 结点链接到 bn 结点之后
+ f+ B( k! q" q7 ` } // if(p)
( i8 w& O) I, { } // if(m)
! {# t0 s' v3 ^ } // exchange_L
( B: V0 U7 U9 N! k5 s4 R) {7 C$ z% h; l! y9 V$ ^- @
* B' `* V; ^& B V4 q) J
3 Q+ e! N! C' k, l# k1 p1 ]2 J$ N
- ?& T4 M/ R# d |2 W' p5 I) ?& \. d+ C3 @1 M F
|9 C W5 q" ]5 Z: q* O6 M0 W2 O: f# _- j& M. x; r F2 h; o
7 [; y# T7 ]' q# Z* S! H- Q
6 l1 x' E2 H; Z+ s$ X# B& S5 a
R, S- t; [, L, R/ X5 S4 a- s% L32．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F1实现求值，并指出遍历的方式。
z7 _# E$ i l+ \! B6 i# m" h; |% E) Z1 n0 l2 H: A" }& d+ C
/ H# h+ k' _& a8 c( _+ A6 p
7 m# F E0 Y; N* [, F) Y& ^5 x
5 s% x# k8 W; {7 f# x. ]1 f
9 d# g5 `% G+ w) O8 _( j, [9 z$ U* B; v7 w' T
0 H) t& e% b- i) h- s, k9 u' Y0 T0 S( ~
1 u% C9 t3 p1 E/ K( Y6 Y$ |
6 t% j. T5 |' n) }! c
7 | k' N5 v% p1 U+ h/ U. g, j4 q/ {6 _' b' ^
: n1 k* I6 }& J# U( l& c3 [, R
& m/ m- s- @2 i* q- G. U- w6 z0 E( e8 K0 o8 K* M! f
9 s: z" |2 ?- `$ r% j' p2 X33．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
3 F! z# U! q+ f0 R! R4 l逆邻接表存储结构定义如下：, O' [& m! h. }+ J8 @+ j3 [# {$ w
顶点结构 表结点结构
( n0 G: W: `; P. K: {9 o! T+ c- }vexdata firstin 3 k4 `/ S( K) ?# X) }
adjvex nfo firstarc7 F; J$ W- Z! x/ D2 Q/ L# L+ l
4 T2 n+ O: z% O+ D' m4 h2 l* f+ [/ N9 ?! H* N! t
; o2 b. z& t4 Q5 T. c( f4 P2 M# g
/ L' ?3 n% L" P( ^1 L
2 E; @* z) ? F! l7 U. }) T" N+ z9 G
) m6 y# V$ ?; N, C1 _
& K4 b: L' N9 t3 R# r7 `9 ]0 p
7 P: f: \0 C. q4 ~- F8 A Z4 J9 b; Q& h/ N2 D2 R8 N
! b! ?3 v, O2 u3 ~+ ~( Q+ L
6 ]% V: h U# ^& V9 N. J! d# e" `7 S; T1 E; O9 S& Y) S
& A X% g# ^7 I7 e J
) n5 m" l% ~! ~; |# p& @1 I( k) W* u) B
' j2 J5 V; a' J
34. 设哈希表长为13，采用线性探测法解决冲突，哈希函数定义为：H(key)=key%13。2 |$ A# Y/ D2 ^+ p
试求：（1）填上依次插入关键字25，20，36，15，41，52，29，72，67后的哈希表。
& c5 d, C! J5 v" R（2）计算等概率情况下，查找成功的平均查找长度。( C, G* F* ?( B% L7 e
, x1 K7 I/ Y+ V9 ^+ n
" `6 N8 Y: g o- ?: }) y' J" z0 {9 n/ p
# k1 r* J. F- {% Y
' @0 o: z$ Y. v- `* g
7 a7 }5 Q& v( Z; N- H
' @; Q7 h. b z
- e U9 ~* J+ v. j
4 L* H- h3 A( l/ `0 V8 J5 w9 L( c0 h) C
. D* B2 k( U( ?; R- [( p9 l7 v$ g5 l
) y) w$ N, j; p4 K
$ U% _4 @7 V$ e7 w& G S$ V
% L1 s, h. N$ i
" b" N7 X# l/ h6 I Y1 h4 ~9 a7 o# \2 L& h! m; I$ y, T
* ^/ W% ^9 M2 S5 k2 g+ X
8 ^! O2 B# E, W& l' t& B& `6 V/ v' [, v1 l$ v' _2 p) @ b% ~ i
|
|
IP卡
狗仔卡
发表于 2021-6-8 10:47:10
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
