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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

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

[复制链接]
发表于 2022-3-20 12:34:52 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院
6 v2 i4 x7 t6 r, t- u* W% m) T2 O2 ]! Z1 D0 n
  数据结构II X      试 卷(作业考核 线上2)  B 卷$ z! ~) S8 S0 X
* o2 n& v" Z: X$ z( l' V) _2 i& H
学习中心:            院校学号:             姓名            
2 y( D6 ^; X0 z9 J0 `
. s  N; e; x5 C(共   8   页)         
1 ^7 F  ^% Q- R/ l7 i- [  q) I; }总分        号        一        二        三        四        五        六        七; |. c# C; m3 t* v9 z0 r
        得分                                                        4 s8 B$ w2 u" W( T
, i% m% N1 u4 B2 h2 g- @  w
一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
2 X; V: s# e4 c[  ] 1.抽象数据类型的三个组成部分分别为
+ w, v4 z/ k% A( ?6 e5 ^( I     A.数据对象、数据关系和基本操作
6 L1 I$ r. I* x7 g     B.数据元素、逻辑结构和存储结构' D1 m: F; M6 L( v- A) f$ M
     C.数据项、数据元素和数据类型0 ^/ |5 B4 B1 K. r' T9 T
     D.数据元素、数据结构和数据类型
$ b0 Y# [8 @, c1 e' l[  ] 2.下列各式中,按增长率由小至大的顺序正确排列的是- I& `) V% n; t3 X# o" j) @# X/ V" r( H
     A. ,n!,2n ,n3/2                                        B.n3/2,2n,nlogn,2100
- a, Q3 x/ p+ @' L: C9 X     C.2n,log n,nlogn,n3/2                                   D.2100,logn, 2n, nn
, C8 P- T- G5 E[  ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
# ^6 N) _0 ^# S1 {( T) ]9 `. C     A. q->next=s->next;s->next=p;        B. s->next=p;q->next=s->next;" F  A3 u# h+ x; I7 c" n
     C. p->next=s->next;s->next=q;        D. s->next=q;p->next=s->next;
2 f7 T7 Y9 Z/ E# l3 Z& z2 x" x6 J[  ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为8 g# g0 Z# D9 s, f6 }/ A8 I2 t, b: S
A.374                                 B.576
0 D. q% a; s6 ~; g' y3 p- gC.378                                 D.580
2 l( {# A5 M- e- e! C' M; A" X[  ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为6 b7 i2 ?3 R: y* E
       A.4                                  B.5     
( L( E6 I) ?: u3 v9 MC. 6                                  D. 7
: |3 ~" Q+ a% T9 W5 W' [5 S1 |8 c4 v7 V/ m9 k5 ?! l7 y5 D
[  ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1  则T中的叶子数为
) K2 N# e2 K9 R  e3 T+ Q    A.5                                 B.6         . q* C- G( q: Q  {( f! b7 Y& {$ l
    C.7                                 D.8
: k. O7 V) B3 |# S, t' R[  ] 7.以下说法不正确的是2 w: ^. D4 q2 S, }& n. L$ V
    A.无向图中的极大连通子图称为连通分量
6 ]" r$ |) ]/ a. A# b, o' v    B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点- Z; `' q3 l1 ~& C5 h5 q
    C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点7 O, ]+ ~5 H1 v8 p! Z
    D.有向图的遍历不可采用广度优先搜索
  a2 x: t  g' W9 ?[  ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为% |% n- F' ]% z" W/ x
     A. n-1       B. n              C. n+1             D. n+2
( F' Z3 ~# q' P" v8 H. c: a: ][  ] 9.设置溢出区的文件是
, m/ G. b3 O1 m# w) y6 p     A.索引非顺序文件                           B.ISAM文件
# n4 K5 i6 Y1 E( R" T8 |! G     C.VSAM文件                                            D.顺序文件& e; l- y6 e+ t6 u% s! \& s+ Y8 \: T
[  ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是3 h, m* P0 d! R; d) v, g( p
A.{25,36,48,72,23,40,79,82,16,35}$ Z* c* `& W3 I! O
B.{25,36,48,72,16,23,40,79,82,35}5 [, Q2 A% i  f' v3 }9 M5 s
C.{25,36,48,72,16,23,35,40,79,82}: {7 K4 Y) Z+ Q/ j
D.{16,23,25,35,36,40,48,72,79,82}
: V7 w' e0 k0 [7 B二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)
' K- g: \) ^! p" |11.下面程序段中带下划线的语句的执行次数的数量级是(              )。
+ C9 N# g& J3 j' L+ \' H" vi=1; WHILE(i<n) i=i*2;/ ?* `7 i6 m  `, u# W
12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是(                          )。
& n- l$ s2 x8 J9 C* h) V% w# B13.无表头结点的链队列Q为空的条件是(                     )。! ?/ V  X7 u' c- w; ^
14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为(             )。
$ Q, o3 `6 q5 S7 K4 E2 J15.一棵含999个结点的完全二叉树的深度为(               )。9 h3 T: n8 Y! U' D) v0 c$ l
16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在(                 )。% x& x* `" T' W" {8 t8 B
17. 有向图G可拓扑排序的判别条件是(                          )。/ x# H6 }4 `0 M  i$ A4 l2 b
18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是(               )。
7 O. ]: C& B" y+ N19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为(              )。: J' h1 |2 F7 |0 P6 g
20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是(                    )。 9 B; k; {; ^9 U9 Q. r
三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)1 v" R) z: E) @% Z( B
21.比较线性表和栈的基本操作的不同点。
# G6 a$ x3 Y: Y, R8 K) b4 M1 E( U/ o3 Q4 l6 a  @) `

5 M& {7 ~- w5 h+ A2 t, t0 I# u# w- b6 Q- o- R
5 r2 n3 o) M$ i

* [' x* K/ C% w0 i4 c, z- i; _. W* ?8 x

  ^/ k6 c- v4 k8 s7 c& N
, M6 F$ v" @% ]# }4 S( t. f  L" L" \, f
5 E& O7 K' f$ e' e% N4 _+ e
22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:
9 e0 W% `4 |  H3 ?. f. R试求:(1)该树的后序遍历序列。  G8 m2 u$ x" o! ^' c) @* ^
     (2)画出该树的后序线索树。
$ T2 `8 k4 B; _) x- d* `+ D# h1    2   3   4    5   6   7    8   9  10   11      + M' A- {  J$ S# [: j
A        C        B                        E        D                               
7 r$ ^6 E' X+ H2 t8 s& J/ ~: L
5 v) J. g2 ^  Q
9 P& G( Q7 w6 F) x
2 F: P5 F$ Q7 t4 \/ w
( Q, p6 Z' j4 ^. ?( D5 u9 J& z2 U1 [
5 k1 N3 B  R$ ~( z' z* B5 f

# f  }6 b; w# Z' i/ o( g3 G& x* e  }, x
% Y  `# G4 y$ d, O
0 w( ]. `+ l. o

& n/ U! q- R! l! t8 n& i1 L23.分析顺序查找算法的“监视哨”设置作用- k! b6 C6 a% E* `+ b
5 r7 ?0 m0 n# U# w- L0 O

  h# p0 p/ Y3 @  @+ |$ v
: y9 P( A! Y  l) F+ j5 x
0 I' J( q, y3 x' U0 ^  ]
& e/ {$ V7 {. ]- L* ^3 Q& M) w# W, w- [  p: G2 J

; r: X2 P$ Z0 _( _. g: @2 m0 E3 M- ~$ }& _7 A: r
8 L4 X6 l5 Y! @) a; N- B( U1 G

. Q* ?9 Y) R, E  j5 N  c24.对n个整数的序列进行直接选择排序。
+ b& Z+ t' ]# V6 Q# @; N    (1)算法描述。9 h; C5 u* J. i! S$ J! M) f) }
    (2)并给出实例(52   49  80  36  14  58  61  23  )的排序过程。# Q6 c: A$ s" }$ g

2 c2 p1 R$ Y0 F5 x& S& R" ^) ]
& o) b6 H$ E1 ?$ l* X) z6 J+ }/ B
3 ^- [+ D. ~% l6 v* D) s5 n4 {; @$ p; Z$ Z# N. I
( L0 }  P- G, D9 I( O
" |; ~- a, ?8 d7 g% e

+ x9 ~$ C* Z; ~  V8 R  X8 L; L

  l$ b! n& {% M% o( D/ c
, X% B& j  u9 J! C' n6 N4 A) h& y" h4 ^. Y3 B! l4 N
9 `0 p5 x! ~; C0 W; e! u1 Y6 r

9 I8 r  {* V( N& j! l: a: v
" p6 j2 R5 ]0 M4 k* v, ]
" z- @0 m; Q: A$ P25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。
' F5 X! N6 b1 C$ j1 b
6 u& j7 L- h; ]7 a5 Y. ?7 D' u# A( N( N& E4 P! L
2 S: E- k! Q  Z; o1 M& n5 ?

& f& H' u( o: q1 v" Z7 t$ {8 t' k2 y9 v+ g0 A0 h
; w" f2 B' W7 w6 m
' \) X" ?6 b9 O" q/ D
2 @2 I+ h: S, d3 s7 J! O8 B
% ~- ?" q/ a7 J& h5 i

& d$ W9 I# b% X; z2 z
2 |. F7 S6 r4 j" }' Z. P% M: W# i* i
! c; Y, b$ I2 _# {( @9 q7 }# t4 R- I( a3 ^

9 x! U0 E" C6 l, Y9 {5 y! e
% j7 W1 {- N- p7 C) o- i/ s( R4 F( M3 b. p- k

! ?' X4 A* x1 k2 D/ X* C四、算法阅读题(本题10分)
# L- c" Z/ r  G0 F9 B! H26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。' F. u6 r9 d$ K, X8 C% ?
    void exchange_L( Linklist &L,int m ) {
3 ?6 I5 t+ T! I" o- v      // 本算法实现单链表中前m个结点和后n个结点的整体互换/ G# J" H, z* q1 X4 A
      if ( m && L->next ) { // 链表不空且8 h7 u  \6 Q1 m9 t" ^2 q. v
           p = L->next; ' Z6 b6 j7 o. ^) R# r9 T( {
            (1)2 a- Q2 `' e$ r' F  S; k' }
             while( k< m && p ) { //(2)
/ \7 a/ H4 V3 @+ X( y           p = p->next; ++k;
- ^3 U8 P# E1 g5 o         } // while % z/ w4 V( r9 g: ?& Z5 N9 i
             if (p && (3)) { // n!=0 时才需要修改指针
; R7 g# N" U- m) q) Q1 f- i             ha = L->next;  //  以指针 ha 记a1结点的位置  
/ p7 L# ~, G4 e) N5 n& r. I$ {; n                 (4)= p->next;  // 将 b1 结点链接在头结点之后+ ^4 |4 N% j, v1 A, _8 k# Z
                 p->next = NULL;  // 设am的后继为空
) u! ?9 Q/ a$ F! T- w                 q = L->next; // 令q 指向 b1结点
, ~' b: M+ S5 W5 k+ x# p7 Z: U3 e& z                 while (q->next) + X- g, o7 f7 @/ d# ^# w
                      q = q->next; // 查找 bn 结点 6 v3 L5 q2 r" r8 D1 q6 O: y& X
                 q->next = ha; // (5)
% j5 l) ~9 ?* E8 I0 s/ t8 E1 X: S             } // if(p)% s7 J( C2 S2 I, R5 V) G0 a
         } // if(m)
( w9 |/ g# ?7 ]    } // exchange_L   [  ], V0 a$ v$ L+ D- n% A) M

  _' r$ Q" I4 s# b6 y(1)
: _' _* Y& c) R2 \% O+ k" E+ g. |(2)7 o% D2 w- ?: n4 @
(3)
# Q3 M. K+ @  r- K, S3 R(4)3 p7 @: l! S3 R7 M1 U; P' _
(5)
: V! W% A+ _$ i9 F0 Q
  j+ v, v/ H- e: @7 R' M9 A% [* n% ?4 W1 g  n9 G- b( a4 a

, [  ]. s5 ~3 W' i( k) l$ b' N8 v

8 N! x& m8 G, Z) z9 t& B! t" k0 N+ ~: \& _" \! U! S1 {
# o7 k) z, j. S. w7 C+ _
五、算法阅读题(本题10分)
. |' q! G) X# q, U, `0 s9 [27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。: s2 m0 f& w7 z; _4 G& N
void Arrange(int A[],int n) {' ^  l7 r) Z+ C3 M. u, ?% s6 ~! T
  // n个整数存于数组A中
; U; o' e# x" n( B9 Y, i* s    int i=0,j=n-1,x;  // 数组下标从0开始  v% B4 l: ]# C5 Y
     while(i<j){
% x( e& h8 i& l/ l' Q      while(i<j && A[i]>0)  i++; * t! }* z9 ?( J; _& h9 z0 G3 i, d
     while(i<j && A[j]<0)  j--; - q+ J' `. q; o2 g* h
       if(i<j) { // 交换A[i] 与A[j]
) f- D/ I' y- Z) G& I           x=A[i]; A[i++]=A[j]; A[j--]=x;
- B+ z! O# o6 v! f: L2 }, k5 o       }// if
0 f( ]& X9 k& P6 a5 f  d3 R  }// while
' J. s5 {) K; s/ m     }//Arrange
2 O+ S" c1 w% D; z( W* F7 H. r7 @' W- ^0 r
(1)功能:
( {* v  n9 i% e6 g1 ]. ^(2)指针i和j的作用:) U& H# P! [: i  T# {

' s* q8 t0 P6 e' \六、算法设计题(本题10分)9 l) h9 j9 y- G; |# K5 m
28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。
* M3 U. z. p- n) [2 R# e6 s/ ~3 v/ n6 S& `* \+ ^2 u7 ]" k+ g
% Q& x6 E8 I; _7 V' K! V$ e. d

/ a. j6 v0 T& y( q0 z4 x
- W( g% @' F* K. ~( N
9 d; ]3 d  t! k$ \' W, W1 W5 S2 c4 I* C7 B# p* O- W2 Z$ c3 \
8 I2 f6 E2 Q+ ~. [$ _
+ L9 K9 _5 F; ]# V

0 I) d! _* h6 }7 Z  `2 Q
2 b" |: v* g4 m8 N" e2 |& S" S- y
. ?3 g8 G- g; K$ U* }5 S5 b( a( g% I$ [5 W9 T6 \8 B
; H9 _1 t% P: z7 B6 A# d+ l5 o
4 ~9 p1 W$ ]0 o% ]+ t! i& g! P
0 e! B, t; ]; }$ @

+ ^9 `. h5 ]! B6 f# ?9 H7 Z1 x/ [) I. ^: Q4 x

+ T9 g% e0 \. W/ c: K0 a七、算法设计题(本题10分)
$ g8 [. b3 w6 }1 F7 v- |29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。4 y: P% K: h: a: m4 I
- `+ l9 D# y% J. j/ j

2 a1 ~  X9 ?0 V( R( Z* q+ Q/ l9 g- t5 D
5 ~5 B* S; z* U& M  i0 j- g
) Q" G2 _- O: [' U  i" `
: b- N) Y0 U: P' k7 V! {
6 E8 G1 m6 o1 K, q
( h& a' T3 j& M- `8 N; `0 x  g
+ V/ u6 \+ c0 _

7 ~4 v4 R) D, R  x* [! ^
- m3 m& i: X* j$ u' k0 a8 J7 b& n& P0 Y( Y& X! M8 v

% C% D4 |5 Y' {: B/ A3 m; S  S9 `8 o
7 T) d' _0 ^5 p+ s( \1 M! i
6 o( p+ }5 E- M3 L( c! s+ B5 N& r/ E+ f

5 ]" |& N- D0 h1 n' Z+ x! _$ O  F
, Q( ~$ a; f) h  }$ \3 M8 y/ R, z
/ C8 m$ T' T- @2 x

本帖子中包含更多资源

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

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

本版积分规则

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

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

GMT+8, 2025-2-19 06:55 , Processed in 0.099782 second(s), 20 queries .

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

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