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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

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

[复制链接]
发表于 2022-3-20 12:34:52 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院
7 K% J1 W( y: M; i9 I# j4 s0 @/ J8 G6 I$ x1 b: X5 ^
  数据结构II X      试 卷(作业考核 线上2)  B 卷
# m0 O1 o# t  k2 ]# t: ~
' ^: n# ~9 f; Z$ y* n' Y. c5 D: U学习中心:            院校学号:             姓名            
& `: v+ v$ y2 x; i+ Z+ Y* \0 v! V, {( {  x' K& }
(共   8   页)          ' ^5 g# v9 X0 \+ g
总分        号        一        二        三        四        五        六        七! v' C( _3 N" O  V, m9 L) \  W
        得分                                                        . T% ]- c$ B& J& p

7 ~) R6 _1 w4 U) T" g. ?# [一、单选题(更多资料下载:谋学网(www.mouxue.com)2分,共10小题,20分)
/ u7 s! m3 r" O! @$ n[  ] 1.抽象数据类型的三个组成部分分别为: C  u# ^9 F! d( G; Z7 N. A3 m
     A.数据对象、数据关系和基本操作
. I4 ]8 ]# {$ \& m: j  n+ ~     B.数据元素、逻辑结构和存储结构
( ^% e+ X3 a5 r# s. z/ y% w     C.数据项、数据元素和数据类型
( h8 F' v1 T' }3 F& y     D.数据元素、数据结构和数据类型
0 X. R# ~; U( x# y[  ] 2.下列各式中,按增长率由小至大的顺序正确排列的是, }) a1 l, i( g' b
     A. ,n!,2n ,n3/2                                        B.n3/2,2n,nlogn,21007 Y, G6 Z" A7 A& M5 z& ?
     C.2n,log n,nlogn,n3/2                                   D.2100,logn, 2n, nn! H2 u" {1 W4 S. i1 o7 ~( i% M6 v  h. Q
[  ] 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
2 E/ J* q8 T- r+ b- `     A. q->next=s->next;s->next=p;        B. s->next=p;q->next=s->next;+ h; i- y) W$ y4 w( V
     C. p->next=s->next;s->next=q;        D. s->next=q;p->next=s->next;3 o8 i+ q. I0 C! f, E- h/ C
[  ] 4.二维数组A[20][10]采用行优先的存储方法,若每个元素占2个存储单元,且第1个元素的首地址为200,则元素A[8][9]的存储地址为) L1 D0 i9 e/ l6 D" C8 L5 k$ I
A.374                                 B.576: s+ E. E& ?- n2 y: u6 E
C.378                                 D.580
- b7 G  r9 E9 Y# E3 e$ V/ i[  ] 5.设有一个顺序栈的入栈序列是a、b、c,则3个元素都出栈的可能不同排列个数为9 D" l7 W* u+ N! h2 b/ T7 X/ ^  d
       A.4                                  B.5     
( c3 R" V( q! T* j* F( O3 m, s# S, UC. 6                                  D. 7; r( b7 z% g# l+ N6 n! G4 ~1 ~' M* c

! o* q1 t( I3 a/ U+ t. r- H5 Y5 y[  ] 6. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1  则T中的叶子数为8 P% R6 u( N) {/ }
    A.5                                 B.6         ) m0 G) R) l/ E+ R
    C.7                                 D.8
( h" U: \3 z& G% J" @+ K# C! I4 ~, }[  ] 7.以下说法不正确的是) K) ^0 x% D5 `0 i
    A.无向图中的极大连通子图称为连通分量4 X6 Z, f. ~  ]" N8 g4 z6 N
    B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点9 e1 E( f4 n9 y! `0 d
    C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
4 a- v8 @. U5 w) {0 \6 k; O+ f    D.有向图的遍历不可采用广度优先搜索
6 q8 [9 |8 I( A5 e" w- `[  ] 8. 假设在构建散列表时,采用线性探测解决冲突。若连续插入的n个关键字都是同义词,则查找其中最后插入的关键字时,所需进行的比较次数为
, ~7 Y, g: E- a# b" b2 M     A. n-1       B. n              C. n+1             D. n+2
. y" `! [( N( A# o  Y, c' o2 z& A[  ] 9.设置溢出区的文件是
, G9 w" F/ m+ p- F0 Q     A.索引非顺序文件                           B.ISAM文件' j; m8 w8 C4 Z
     C.VSAM文件                                            D.顺序文件
/ W( k& l; o, l[  ] 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是! M' N$ c% D. ^, Y+ U- v
A.{25,36,48,72,23,40,79,82,16,35}
+ Z) t: `* b- A; P( y$ ]B.{25,36,48,72,16,23,40,79,82,35}
! z+ t# Q4 \" Z( \4 k) B2 v" b' c  XC.{25,36,48,72,16,23,35,40,79,82}
0 M' w$ a  b9 w' SD.{16,23,25,35,36,40,48,72,79,82}
+ u8 ]' V" U3 x  s8 ?0 }二、填空题(更多资料下载:谋学网(www.mouxue.com)1分,共10小题,10分)7 Y$ H. U. Y+ [% r
11.下面程序段中带下划线的语句的执行次数的数量级是(              )。) B) F1 M6 D% X* S
i=1; WHILE(i<n) i=i*2;7 H6 R1 L; _' u5 F8 u+ E. i
12.假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是(                          )。
4 |, s! u/ \4 n, a" Q2 p13.无表头结点的链队列Q为空的条件是(                     )。! |9 ]8 l/ z) u6 H  ]( k
14.设Q[0..N-1]为循环队列,其头、尾指针分别为P和R,则队Q中当前所含元素个数为(             )。9 `% N* n8 i) J7 D- l
15.一棵含999个结点的完全二叉树的深度为(               )。
( M' C+ e1 Z1 J* a: `16.在AOV网 中,存在环意味着某项活动以自己为先决条件;对程序的数据流图来说,它表明存在(                 )。
4 Z/ R, R9 {1 N& ]3 i7 i17. 有向图G可拓扑排序的判别条件是(                          )。
6 d, u/ W5 f& W6 O2 _0 Z, }18.如果结点A有 3个兄弟,而且B是A的双亲,则B的度是(               )。
8 [+ Z' W& ?( P19.应用回溯与分支限界法解决实际问题时,在搜索过程中利用判定函数,也称为(              )。0 s% t$ }, t5 S9 S" x- e
20. 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是(                    )。 & C/ ~1 |" @% X3 {0 J/ b
三、应用题(更多资料下载:谋学网(www.mouxue.com)6分,共5小题,30分)
- c5 V0 B) v- `" [, b21.比较线性表和栈的基本操作的不同点。
; z" V0 F/ Q; F" t1 s" s6 w! ^
8 e+ L" Y. ?% i' ?2 t6 ~* s
" Y, H" x  H! w2 b) U! g: V. ~# m- _6 Y. P! o. K
* A  T# `/ }: ?, U
/ X+ c9 q5 Z; d! t2 b5 l2 U4 X

' p4 z& I; e+ J+ _% a$ d0 P+ Z# B/ ?; w( u
/ e9 f- z/ }9 ]8 f) ^& q# o* W

; F2 F8 _0 `. v! L' p* g: B# E$ x  a  d8 w, x6 Z- N. V! B
22.有一个二叉树按层次顺序存放在一维数组中,如下图所示:' s; ~$ X( e0 u
试求:(1)该树的后序遍历序列。" J( A9 |& R% F/ H& Q
     (2)画出该树的后序线索树。4 c1 n. ^. N7 E0 w, n
1    2   3   4    5   6   7    8   9  10   11      # e5 g" i6 E, |. A% W' N
A        C        B                        E        D                                . [0 Y" ^- b% ^! i/ k7 |

' w* J5 _; b+ z, t, W
* u! _4 P, r+ k1 q) ~5 K  ~1 @4 y

7 x* T( q) X- l$ [* R) ~  S$ X9 w( |6 x

* x* z: m) P* A7 @0 c
6 B, j, n$ Y4 N9 L( ^
" D! h) m4 H: z
& ]+ e6 |3 {% N# Y3 K1 k7 I' u
- Z+ E6 U: m% l$ }
3 v2 y5 y! F2 u23.分析顺序查找算法的“监视哨”设置作用# x( Z  O+ m; H( `" g

: \/ g6 Y- Z, `/ Q, e. w* e4 ^5 a! K# x* c
+ s; ]8 \; ^; W- _7 W! c, K) z
) y) C" f" F# m& D" @* F6 A& `

  b: }  V  k% h0 i/ D! R1 q$ l* Y, }. A
+ r  f2 B. k2 t

2 A: E; F7 A4 q: y" T
, J" Y3 u# E+ H4 }5 M* v9 h( p" R
24.对n个整数的序列进行直接选择排序。1 _6 v( v( F0 l1 z# e7 F8 C4 H! d
    (1)算法描述。6 U1 H: U5 d4 x, W( j6 s( X
    (2)并给出实例(52   49  80  36  14  58  61  23  )的排序过程。4 [) Z8 g! C3 |- J; o

- J  H/ Z7 D! y; D" u+ f8 w8 G' p
' \& w2 M3 d0 r: C% E+ j1 ~- K' r
9 R' H9 g; q7 f* d6 v9 G

0 |& E8 L9 j* \2 K2 u) v2 O/ T# z/ L1 }; R! d
( H: w( I! l2 D& e1 u: @
4 g& e" ]/ b! r5 F; L

# G% F$ A% B+ p: S  G4 y& `5 z2 _, O/ R) p! U1 |$ S
$ u" z: e2 T7 G1 G3 @# O, _6 a
8 V+ i: D( ]( D+ Q3 r

5 c1 G8 e( R0 h3 J3 {% J; g; _0 D0 C' _+ {: B$ u- w" u
* k0 a' M: U% S& w8 @% T
25. 已知有一个10个顶点的连通图,顶点编号为1至10,其边的关系集合表示为{(1,2)(1,3),(1,8),(2,4),(3,9),(3,10),(5,7),(6,7),(7,8),(8,9)},试求:画出该连通图及以顶点1为根的深度优先生成树。
4 |2 u3 S: y! Q, `1 l
8 L0 I# P, \7 x, C: e
8 v; p3 _5 t* Y% l6 V9 d9 g; t3 c! b7 V: I2 K5 R: I
1 g% u3 ^$ J" M: A
# S' w# w" A; I8 h' j
& [, s' X8 n( H: o  I
* M( l5 ~* I$ h& {5 \

5 n2 e- G" c: K, q6 }7 r0 [  @# v6 ^2 H- E" ]% m( U! C5 s$ z0 i
' T9 c) R) w! h9 z- w

+ v! h+ L; D' t  {9 y- z! F/ P' _; l: ^" A7 d: ]+ g0 d
, Y" b% I6 p2 E6 O4 t

. Q, k0 u- I: ^0 q( Z5 t
4 I7 d3 S; d6 m4 v+ K
0 c% V/ n" e) ^5 A$ W
4 c, \2 ^4 c9 Y/ F) q" l四、算法阅读题(本题10分)4 e6 R% g- F. x0 K, l: \6 U; d  B
26.设计算法实现以链表作存储结构,将线性表中前m个元素和后n个元素进行整体互换,即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法,在横线处填入语句或注释。* }; G) D; b& `
    void exchange_L( Linklist &L,int m ) {
* L- y; W1 T, |) k% r' K      // 本算法实现单链表中前m个结点和后n个结点的整体互换
$ x/ k6 B: g- U. L/ V2 v      if ( m && L->next ) { // 链表不空且: w+ |$ \) \: F4 _1 u
           p = L->next;
9 d  A, {9 l' X$ M$ E: ^            (1)# n! v& U! E! x4 S- A
             while( k< m && p ) { //(2)8 ^  |, b0 i7 `1 a" M
           p = p->next; ++k;
, E  }, o4 v0 i. _7 l         } // while
& U4 q& c/ h8 L' O             if (p && (3)) { // n!=0 时才需要修改指针/ N) Q: @% k+ A+ z
             ha = L->next;  //  以指针 ha 记a1结点的位置  
( E5 P8 s. d  ^  V                 (4)= p->next;  // 将 b1 结点链接在头结点之后
" ^4 R. S. \8 f9 \2 `                 p->next = NULL;  // 设am的后继为空0 L- l8 W& _8 q4 ?- M
                 q = L->next; // 令q 指向 b1结点 ( x, g" X* [$ f( u) A. `7 p
                 while (q->next) 7 f1 y% H: J" E  h+ s" w
                      q = q->next; // 查找 bn 结点 ' U/ x# n4 A. w9 C
                 q->next = ha; // (5). ~3 y! w/ y! B/ ]5 E6 q+ W
             } // if(p)
; E5 j; L0 l, Y% j3 m         } // if(m)& U# c5 x3 {+ ]6 t
    } // exchange_L
3 ^. p0 I0 r7 O- X: f" S" J
4 t8 \3 R! t1 h# L' k$ T  B) s  v: F: Z(1)
/ e1 G& }( P4 R3 ?. l' f# c(2)
3 M; I8 t) g% D: Y# v(3)
' Z1 d+ g+ G/ j( e+ Z/ i" v. r(4)$ m& Z, c% ]1 x3 o
(5)0 D9 \  c1 x6 H" q! a+ c6 T

6 p3 x$ I1 V" J; j7 |% i8 s4 Y/ o' Z' n* h1 s
% x6 ]  r) m' c: I3 @" }% s6 E3 k

8 {0 j6 L3 B2 ?/ |' Z! N
0 c; f4 X/ R' y' }, o
0 w. y# t% `1 m" }8 j6 c2 P/ @7 i# O2 v1 }
五、算法阅读题(本题10分)& n! U- F( v7 ~: Z8 p% N+ w* u
27.设任意n个整数存放于数组A(1:n)中,阅读算法,指出功能及分析指针i和j的作用。
9 }8 G) {' i0 [4 P4 y& i7 S5 K. M/ mvoid Arrange(int A[],int n) {4 i( t+ v% W" c# ~5 v
  // n个整数存于数组A中
) v- |2 n. x! `! F+ M    int i=0,j=n-1,x;  // 数组下标从0开始
# ]+ K) o  U* c0 ?' e* A0 I     while(i<j){! |: A5 f* u/ @# q0 Z& d  {$ u
      while(i<j && A[i]>0)  i++;
9 e  o3 v7 e9 B' I; l     while(i<j && A[j]<0)  j--;
* F, @' v0 @3 C2 \# i       if(i<j) { // 交换A[i] 与A[j]
3 R, x( ^5 m! Q1 m- v( q           x=A[i]; A[i++]=A[j]; A[j--]=x;
1 u" m( Z! J2 A1 {+ c, I' {       }// if
( V6 `3 c8 J, m  U' p$ i  }// while
3 ]$ I: m$ r( t5 A9 H6 @3 A     }//Arrange6 ]& T( Y6 V7 O# t# l) m
4 V# C7 F# \* z; @; M3 \1 w
(1)功能:1 \" A+ L" t$ ~+ \7 h* _
(2)指针i和j的作用:. T6 z1 g% y$ T- Z" G5 E. ]) j
! O5 J% d: U; N4 I) r
六、算法设计题(本题10分)
- e$ Q, V0 E2 T6 A28.设计算法purge_Sq实现删除顺序表SqList中重复元素,指出其算法的时间复杂度。' O2 f; O/ z' _5 W# ^" D7 }

. s+ f1 g3 |$ {3 r8 E5 P7 C
) p& k2 W0 \, \( E- R* k- o
: a' m+ n7 I# \+ f3 G& d2 \$ o/ D7 S5 p9 n, Q- O# d, `( l

) c% ^; i4 V; Y( T8 ^: A& H
7 [. s! v& g1 v" m
5 D1 \2 p- \' d; P2 Y) J
  P6 k, {6 \3 J6 n
' H+ v* h/ Z; v6 Z5 c( }
- E, l7 X+ j- r/ k8 P3 L5 S, `+ H1 T- v% v* R! d$ q& Z
$ j" B+ x. B2 b+ F* M9 D0 E/ g* I

) K9 i7 V. v' }7 H; H5 I7 H2 U! P" j* e, S. Q. p1 R

/ L- j) w- y' H4 o1 u% G. {. K, y; ?

- y. i! v- \1 v- w5 C8 I3 F; q3 o2 X2 p5 ]8 K: S8 G9 J
七、算法设计题(本题10分)
, ~8 ]" y+ k3 S+ j9 X7 o29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法。
3 {1 j, }0 W, j; g6 R
7 K+ B. }+ ^, e7 \% q0 k2 v7 w! c
6 {0 M1 m: l/ m+ b( F' d  a* d8 X
; b9 W$ F, b) J$ }5 H6 X" I/ y5 r7 C- R& l) C; R5 p
+ s$ x6 M+ O2 m& M9 j1 a! \

+ {! B1 H& L8 j' |0 c- {+ y2 b& R/ g+ B# z( l$ V6 d0 {
+ d+ p1 ]: g1 k. @

& D- e0 H& V2 e- v4 P1 v% C5 q$ M( o
. ?* H/ `: e9 `: J. y

/ ^1 f# @7 i$ p: s* G$ }, @* n: u6 b, X4 N, |" a
' A- d% Q4 L8 O+ R4 \$ f

0 W9 b& R' z* {
7 |7 N# N: {" E: o# `4 A  S6 f( H' ]- M/ s

% |% y0 F# ]# x. C# C
" m$ v) `2 P2 [/ |; j9 G( K

本帖子中包含更多资源

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

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

本版积分规则

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

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

GMT+8, 2025-2-19 05:58 , Processed in 0.106834 second(s), 21 queries .

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

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