奥鹏作业答案-谋学网-专业的奥鹏在线作业答案辅导网【官网】

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

VIP会员,3年作业免费下 !奥鹏作业,奥鹏毕业论文检测新手作业下载教程,充值问题没有找到答案,请在此处留言!
2022年5月最新全国统考资料投诉建议,加盟合作!点击这里给我发消息 点击这里给我发消息
奥鹏课程积分软件(2021年最新)
查看: 1045|回复: 0

[东北大学]22年3月考试《数据结构ⅡX》考核作业

[复制链接]
发表于 2022-3-20 12:34:52 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院
* p, Y6 F6 E* ^' n5 f$ K5 @2 t& m3 H$ j* [: Q. H. S
  数据结构II X      试 卷(作业考核 线上2)  B 卷
9 q3 e$ D4 j4 I% H
5 U4 c# ~4 t# d学习中心:            院校学号:             姓名            
6 ?: h, l; l% ], r1 q' ^: q! {4 J5 t3 z  _
(共   8   页)          + p2 J/ Q1 D4 i0 U$ d
总分        号        一        二        三        四        五        六        七
- {7 `" z% ]* e2 x        得分                                                       
' r  y. V- W7 ~2 f& R' R" K. U) Y; j$ @7 I5 l% Y
一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
& j5 X) P; I- E' @3 j( ?[  ] 1.抽象数据类型的三个组成部分分别为3 k6 R8 M9 a* P$ u& ?& [
     A.数据对象、数据关系和基本操作4 n' W& R' T4 d) V1 _
     B.数据元素、逻辑结构和存储结构
8 a3 Z2 e# y4 ^6 b" b     C.数据项、数据元素和数据类型
) `' J+ q: s+ L* {# J     D.数据元素、数据结构和数据类型# X  L  U4 r9 E* r; X+ T
[  ] 2.下列各式中,按增长率由小至大的顺序正确排列的是
) y# c) C5 q6 G6 G2 W0 v3 O. l" y     A. ,n!,2n ,n3/2                                        B.n3/2,2n,nlogn,21000 Z# v3 z: R  i+ g! N' @
     C.2n,log n,nlogn,n3/2                                   D.2100,logn, 2n, nn
3 B8 N! |0 t: S[  ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为9 \  i8 ~' s6 ]  X4 A; V
     A. q->next=s->next;s->next=p;        B. s->next=p;q->next=s->next;
0 H# x: a! A/ h0 X2 `     C. p->next=s->next;s->next=q;        D. s->next=q;p->next=s->next;3 G) m+ \. H& H/ c4 }
[  ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为: ^8 r7 W, K1 t% e
A.374                                 B.576" r  a. n  }3 o
C.378                                 D.580/ v) `% s) x' M
[  ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为
) P- X) ~; o. A       A.4                                  B.5     & H1 d3 i/ I( i
C. 6                                  D. 72 b# L9 Z% p* E% G: j( W" R
5 Q4 {7 `% \, H" L* z
[  ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1  则T中的叶子数为
3 a% m; m' c& i2 e    A.5                                 B.6         
& P$ a- x: Z- k- {    C.7                                 D.8. h. r" l8 q& G' u7 F- Z6 r" {
[  ] 7.以下说法不正确的是
' [% }8 d+ u- h8 i9 c    A.无向图中的极大连通子图称为连通分量: @8 O5 d1 H# z0 P- Q0 t/ Z
    B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点8 t! g$ C1 D* ?6 r- a1 u" E. k
    C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点7 }5 I+ K" ?, L6 I. y% R# v& n. D
    D.有向图的遍历不可采用广度优先搜索# k3 q  L3 k! b
[  ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为
- e8 c- N2 C8 ?     A. n-1       B. n              C. n+1             D. n+2& @# A( f# {- y7 ~
[  ] 9.设置溢出区的文件是8 J. n# w3 r* N  y, ]0 J  V1 `9 E
     A.索引非顺序文件                           B.ISAM文件3 T* ], |4 T  ^( v& k7 e
     C.VSAM文件                                            D.顺序文件
, w2 U. e/ K1 `, T( ~0 v[  ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
( R  g+ C, k1 B* U& hA.{25,36,48,72,23,40,79,82,16,35}
) Q3 x: e4 ?5 bB.{25,36,48,72,16,23,40,79,82,35}
6 Z% v9 D3 H& k6 y+ fC.{25,36,48,72,16,23,35,40,79,82}
+ \- y5 _) r+ f6 e+ \D.{16,23,25,35,36,40,48,72,79,82}4 ~6 h) p/ L9 l) ]! V  I% z
二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)8 l5 Y3 b& }5 u* p7 w& q
11.下面程序段中带下划线的语句的执行次数的数量级是(              )。
; b# r  e' S3 O' qi=1; WHILE(i<n) i=i*2;
9 F5 F4 I, i( M12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是(                          )。
6 n# r" F4 Q  w& t13.无表头结点的链队列Q为空的条件是(                     )。
/ X! G* @( n. D14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为(             )。' z! u  G# E& D. E; u- @3 @
15.一棵含999个结点的完全二叉树的深度为(               )。1 g+ F" p- I5 ^/ ~
16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在(                 )。* i6 @% X' {- W$ R; y. e
17. 有向图G可拓扑排序的判别条件是(                          )。2 ~& ^7 j% J/ u6 }/ P+ f
18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是(               )。4 ^! v% W: u+ m7 U3 v, l0 W% b
19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为(              )。
- k" j0 ~; D# d. V. J20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是(                    )。
  g1 n/ L. k5 u$ `三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)2 [  h9 _8 s& t% i4 T- @: N
21.比较线性表和栈的基本操作的不同点。
# }6 h: {. r1 K% B( }( R* ]( n2 x# L

& {9 ?9 y9 {% e% v2 Z4 b0 I5 P
" U7 X6 C  V) m' H& c5 |( t. y. \. Q% q2 J# A: w/ u
; T+ M7 B) _5 n; i7 i! k

5 Q- q& X1 b6 L& v  `
. L" F6 m, X5 A0 Q2 I8 @
. |, @, \3 d# w6 |  m  K  F3 g7 l5 s9 G5 i

! `, V  Q8 V/ w# @1 q0 _, m# P- j22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:4 m+ d$ `/ v1 T- V4 g3 z8 w2 T5 Z4 d
试求:(1)该树的后序遍历序列。
4 ^# p+ |$ a4 q( N     (2)画出该树的后序线索树。
' E: N0 d$ M" x/ {7 Y1    2   3   4    5   6   7    8   9  10   11      
/ M& p/ X" }  O8 j; \- RA        C        B                        E        D                                ( t# T" y# Z* Y; f  X( x- j+ [

7 i& X4 T9 V1 p& u  S
7 W: I7 {; A8 x0 o* Q* i6 _3 z6 h, ^+ D$ X- k8 f9 D0 m$ g
# R/ j4 Y4 J$ X0 u4 g

$ e. [) l5 y  U
1 V8 h6 w  b# m: N" R; C0 D, r4 V1 m
* T2 N( r) e0 F) B- b( i# ~) U
2 O! L7 s% a: c. t( ~3 s! t" K: H, C1 W$ r
" Z/ a% F* O0 A' p# f: Y) H
+ j. d0 Y0 t7 V+ e
23.分析顺序查找算法的“监视哨”设置作用% y% v5 ?2 \: |# p* d/ i- V

& N* j% s. H) v; g" c3 x. X$ t) Y

  W2 [$ t# K3 f: ?1 `8 b6 |3 Y' e" m/ i# k
* j! u4 g6 j+ L: H

( B: s, ^3 T2 a8 l( _& y+ \" L
) Y8 A, i0 |8 U; S, U) H0 v$ [
3 ~7 d: b( H& E, T
% C9 j% u7 ^2 E( G& }
) L( [7 B* ~. r24.对n个整数的序列进行直接选择排序。
6 G4 A5 {- k" O! P. f+ w0 U/ v    (1)算法描述。
, t) J5 X0 [# X0 b    (2)并给出实例(52   49  80  36  14  58  61  23  )的排序过程。
/ H3 t/ h+ t& E% J4 f6 t1 t# w& K" r
' a* r1 e* Y/ n5 D( F

! u" R+ H8 y% |5 w6 Z5 |& `, b8 C: ^
9 ^8 _- Y9 K4 j0 @; e* s8 v. R
2 ^' q9 c( @3 F
+ N" Z0 r. w) \/ ?3 M
% r9 t% S2 V/ {- q" \5 Q
  s: Y; v3 y, [8 Y

/ `& R0 E7 I/ {- b) q# Y3 b& H1 Q6 u5 s3 A

5 v! p7 H; }5 @3 Z9 p6 ~+ q$ Z
* p6 L: \# u5 J
- t& Q8 {* Y! s5 {% b, ~5 Z. s
  l, _, K8 n2 w- b; W25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。
$ Q: t& s& b8 e0 E  }4 j
9 `+ o7 R2 ^- ?5 g% K' t" Z4 [0 }$ G! d7 ^' ^2 d# U& r' x- z
* w' P* z1 p! T7 y& \
/ v  J! B7 j7 |2 }+ ]( a  e

' u: ]8 n2 f0 z3 f" B/ S
* P3 ~; c; P7 t3 r  Y/ _, M7 I( R! S9 W( a0 ]* u/ n
- s, A$ ^+ @# k5 A" c

6 X* v) h! b& K. [% ?2 v' c- n1 l- h
" D8 ~+ w7 i! y5 k4 j$ P* M  u
  C' b# Y1 K1 N) [: C
3 t7 `/ {+ ^' T; }* G, j, w8 f; k) T  N
3 L: o5 G' W# n2 {& ]% j* T

8 ]/ u8 v  o) Q  Y7 J1 O" z
/ l! m2 M; Y) t
5 Q+ H+ d2 l6 ?5 [! W四、算法阅读题(本题10分)
6 Z# L3 b! H" V  ^3 p' h3 E26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。
% P% t- |  I( T. b* j- R    void exchange_L( Linklist &L,int m ) {
& n9 a9 n+ Q& O8 a0 B. w0 @      // 本算法实现单链表中前m个结点和后n个结点的整体互换
3 x$ I1 o: m9 T: F# H' H      if ( m && L->next ) { // 链表不空且3 s* E$ C8 {2 g% ~5 q
           p = L->next; 0 `/ |2 @, \2 p* ?) M
            (1); v/ a; L$ Y5 l
             while( k< m && p ) { //(2)
2 T) Z7 ?4 i3 n2 u           p = p->next; ++k;
/ T5 V$ d% g/ q, O" y4 u         } // while
% X  ^4 P) `7 n) d  R/ H* h/ }             if (p && (3)) { // n!=0 时才需要修改指针
6 y# p# e$ S$ [3 ^- q- J             ha = L->next;  //  以指针 ha 记a1结点的位置  
" J; a: j" o$ x: h$ Y! L. y                 (4)= p->next;  // 将 b1 结点链接在头结点之后' T3 I2 B4 L+ w9 t
                 p->next = NULL;  // 设am的后继为空. R1 ]# H. i* a8 z/ P/ j( F# W( b+ J
                 q = L->next; // 令q 指向 b1结点 1 I0 ]2 i8 l, l; ?* G6 }
                 while (q->next)
, w" t8 ~% @$ L- b( g                      q = q->next; // 查找 bn 结点
9 k5 U3 \/ u4 ?2 K4 R9 [- J                 q->next = ha; // (5)- _" q/ l$ V5 j5 H0 }. Y
             } // if(p)
6 B/ u" |; n) v# X5 T- z& |         } // if(m)# W+ M9 A+ q+ Z; x# ^
    } // exchange_L
9 h3 N1 Z% f; r* ]$ `# h* O% B0 ]6 C1 s: [9 F% ~& g0 [. ]  {# g
(1)
! H: L1 u9 R' f1 {% Q/ V' D(2)
" M: C- d- l+ V( U(3)# q: q6 x0 B) m1 D4 B; q, p0 E1 G- _
(4)( \3 }5 f  k6 o$ [/ f7 Z
(5)! ~2 t7 m1 h+ G  Z
4 R2 ~& I$ F3 I7 H) `: q. z

7 K% ^" m+ w' k' y% m! f
* t& R! z# U; f$ C7 M2 o9 c
& M/ h9 {  {) y0 y6 I! x0 f! H3 O) U1 ?1 a! Q
  ]7 j" @9 K5 k+ w$ f3 ~

7 R- k1 ~/ w+ {$ k五、算法阅读题(本题10分)7 s3 ?- I- h3 H: w2 ]
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。
% }  T" @5 P; [; I1 r/ l7 yvoid Arrange(int A[],int n) {, A/ u7 R7 Q* g0 A
  // n个整数存于数组A中6 P# y: ?: i* g& M+ B6 B
    int i=0,j=n-1,x;  // 数组下标从0开始- n* r4 v. }$ n: [
     while(i<j){8 _: V* G& @: S/ S2 |
      while(i<j && A[i]>0)  i++; % t) S0 ~* E1 b1 v* [5 e) A* s- k
     while(i<j && A[j]<0)  j--; - B* G' M0 H1 a& l* Y- h5 n
       if(i<j) { // 交换A[i] 与A[j]
# u2 j) k0 O4 a/ T$ l           x=A[i]; A[i++]=A[j]; A[j--]=x; 4 t1 w: v5 M" M8 H( z
       }// if
- r% G% v4 b7 S7 L* d; d  }// while
9 q, F0 ~; a/ w% Z4 G: N     }//Arrange
1 x: o, H/ ?' o4 }; f* D' A
  b9 u$ u# x" B2 h- _/ o+ c(1)功能:& a# ~$ U6 H/ ?6 M& |$ Q% O) x
(2)指针i和j的作用:
) y# [/ r: q' j2 {) S2 z* R* ~4 @4 Q) Q% \. G
六、算法设计题(本题10分); u" k; t/ W& b8 j' {
28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。
8 m) C9 E2 {" n6 V" J8 `1 {7 V2 B+ q) ~$ U; m2 Y

* D3 {$ R+ X* s' B+ k" ?; j3 B( T) S3 i0 G: m
* I6 R2 [6 J) q. m* f* ~
, j( T, X1 s3 H- _& A

/ @* {0 L- h$ y' Z6 d2 c9 n7 |& G: v
2 M8 \5 `+ v" N7 I- p$ |" g5 N& A- D% q. c" Q+ f; L- C* B5 n
) u1 C0 F. J1 W
$ A* S8 U4 k; N
7 l3 \0 ~: K. \  G, Z" ^1 S9 r

$ Y( e7 t# v0 i6 {% t- B( @
# o% J8 B5 Q, Y& {) c/ q8 ], V
7 }6 g7 a; j* O& w: F- X
1 }' V5 M3 U$ `6 Z  }% {5 l; X* Q9 B$ A, l: A- ~5 K8 i6 o% t, \& k
3 ^* p8 @: A" }6 Q2 y5 A3 v
, x% F- u9 q8 O) m. V1 s( k
七、算法设计题(本题10分)4 W  s3 J' q+ ?5 h% ^9 Z3 `0 Q: c% K
29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。2 |0 B$ J( M7 n) G6 l3 n
! e+ Z; i& t0 ]1 F& [
- M  W# ^; u+ D& m! U' N. A

& S% ]6 \+ _) |4 E8 g5 ]! w. x* k, d- p& L

! ~) w/ ^$ Y. D2 r9 C$ k3 D1 ^" x6 z( H4 C( s5 t& J

  `4 }2 U7 a& }. Y% {
2 O% b5 x) r, V) x+ M6 g6 a% X. v
" w7 h" t7 w( C2 [7 n. `
. l: ^8 ~! }+ B3 U' V( K
* X/ N& ]  `: X5 l( e# f: e' h
' B6 V- w! R) L" B0 N9 e1 D- G2 Y( P9 H5 T
# M$ L, T; V: [8 R
( y% `9 M6 o# ^# B% y( a

( P( G8 ~8 o8 q3 e8 f
* \5 g: `' W* E* r4 g2 B5 K1 ?, ^  b; n" B

/ `4 w$ c/ Y7 |  t

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?会员注册

×
奥鹏作业答案,奥鹏在线作业答案
您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

 
 
客服一
客服二
客服三
客服四
点这里给我发消息
点这里给我发消息
谋学网奥鹏同学群2
微信客服扫一扫

QQ|关于我们|联系方式|网站特点|加入VIP|加盟合作|投诉建议|法律申明|Archiver|小黑屋|奥鹏作业答案-谋学网 ( 湘ICP备2021015247号 )

GMT+8, 2025-2-19 06:10 , Processed in 0.103729 second(s), 21 queries .

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

快速回复 返回顶部 返回列表