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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

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

[复制链接]
发表于 2021-11-15 17:36:29 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院
1 J7 x6 F" V( B/ W' W9 {! \4 ]
2 m$ N1 d, _. B; R& U8 p4 e- j+ c 数据结构II X 试 卷(作业考核 线上2)  A  卷  d* T) t' Y" X$ x; y
; R$ D, ]" a- T3 M
学习中心:            院校学号:             姓名             $ W- _  `  u7 B- {5 f: p

9 V8 e. J" K8 I. ?(共    6    页)          6 }  I7 k- t3 x" c
总分        号        一        二        三        四        五        六        七        八        九        十
$ M& f; t" h" h# \/ u        得分                                                                               
7 M' S5 G2 |4 B$ C一、单选题(共30题,每题2分)0 u6 |7 R; `1 n% a( D4 `
[ ]1.抽象数据类型的三个组成部分分别为+ j2 q) `' t: s4 j& b  t3 k( U
A.数据对象、数据关系和基本操作
6 V: g4 K$ {- J  C      B.数据元素、逻辑结构和存储结构3 }4 a( ^4 ~; l5 h
      C.数据项、数据元素和数据类型
7 d2 ^2 ]9 ?- _6 I      D.数据元素、数据结构和数据类型$ z! U# o9 c9 S, a( j: u
[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
( Z# ~+ P' l4 L" t6 r2 iA. 数据元素具有同一的特点2 {/ m% e7 k; N& w% ?6 {6 C+ T% p- _8 t
B. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致
9 T( o# m$ W3 H; P/ r3 ?; p  iC. 每个数据元素都一样
! j9 Y, K0 U; P8 RD. 仅需要数据元素包含的数据项的个数相同8 M* Q' K) D' v
[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是1 o: d" Q% v9 K6 F  X
A. ,n!,2n ,n3/2                    / Q9 b; O9 i9 D
B.n3/2,2n,nlogn,21005 _/ [* _! C' E5 Z' r6 U
      C.2n,log n,nlogn,n3/2                3 ?: z; i# D( K
D.2100,logn, 2n, nn
1 N# d" ^# r% a, Q4 q[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜
/ ^! R; G' @6 S: R      A.经常需要随机地存取元素         
1 X0 t" p$ |6 ~# Q1 z" g; ]  ~B.经常需要进行插入和删除操作
4 M/ _- y" q1 W+ v0 n( j      C.表中元素需要占据一片连续的存储空间    0 t! K- B7 L! v' B9 ~, T
D.表中元素的个数不变* k0 _( s5 {$ s, T! d8 m0 v
[ ]5.设指针p指向双链表的某一结点,则双链表结构的对称性是$ k! Z( C, ]# U) A8 O
A. p->prior->next=p->next->next;       " p+ t; @( m6 i! o. b
B.  p->prior->prior=p->next->prior;
( i' i# {# |- gC. p->prior->next=p-> next->prior;     
& f3 J1 `' B: }4 \; N* R3 g; b7 aD.  p->next->next= p->prior->prior;2 a- O8 y  Z7 ~
[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为, U3 c$ i5 z8 b
    A. s->next=q;p->next=s->next; 8 {" t& u' l. k" H" o5 t3 a
    B. s->next=p;q->next=s->next;
$ i% S- ~: ]$ t1 X. c* QC. p->next=s->next;s->next=q;) e4 k7 f7 t/ R4 O6 g* f: C
D. q->next=s->next;s->next=p;
% ?: F( w3 |" F[ ]7. 栈和队列的共同特点是% I) C% m8 ?9 |2 i
A.只允许在端点处插入和删除元素
; t9 r, h. D! s" f, e6 lB.都是先进后出   
. d. D7 k' {3 v3 p1 D( VC.都是先进先出& X+ Z8 U' Z. S) W
D.没有共同点
& e$ c' @" m+ [9 U6 k% r[ ]8. 对于链队列,在进行插入运算时.: l% V) M4 ?  p+ P
      A. 仅修改头指针         
8 p& B. m# I2 o4 N8 W4 GB. 头、尾指针都要修改9 L$ u, m' b7 o# N4 L" r
      C. 仅修改尾指针              
4 P: M- N. v- cD.头、尾指针可能都要修改4 Z; e" n- t! R0 A8 Z& }& \
[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为
0 m, d* y( ^$ {8 M      A.4      B.5     C. 6     D. 7% o% D+ f8 M; g/ L  W, W
[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是
( l9 X2 c+ ~& {- P; V& |1 b! a# b1 CA.A,B,C,D               B.D,C,B,A   
/ h- l7 d3 h1 eC. A,C,D,B               D. D,A,B,C
2 i! D% O5 z( L/ y- L2 Q0 M+ s& g7 C[ ]11.表达式a*(b+c)-d的后缀表达式是# b  a, @. R1 n) q9 j( G/ p+ w
      A.abcd*+-    B.abc*+d-  C.abc+*d-   D.-+*abcd
! x) _% }. c1 e+ M* e[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是
: v" P+ J1 F, V' x$ x( ~8 \/ ~A. 空或只有一个结点             B.高度等于其结点数 1 b' K" \- {1 |, j! {
C. 任一结点无左孩子             D.任一结点无右孩子
9 K8 h% k! W7 V5 G% ?[ ]13.下面的说法中正确的是
5 Y8 I/ }. h# K    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。# E9 l) u" Q3 j# q# D
    (2)按二叉树定义,具有三个结点的二叉树共有6种。6 ^' E% r% [6 N0 K$ u" P
A.(1),(2)                       B.(1)   
* x1 d/ X$ K) X& ?C.(2)                            D.(1),(2)都错
& Y1 p3 o. W5 m! J7 C% u# Q[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的
% Q; f2 C1 O' }) e+ L2 W# n2 C2 u说法正确的是
8 F3 _. e+ E4 H: G      A.树的后序遍历与其对应的二叉树的先序遍历相同     
3 Z  p4 Y  Y2 t- v+ B- D% LB.树的后序遍历与其对应的二叉树的中序遍历相同
( q* K/ G& ~3 F9 N0 v* h( B( C0 d+ dC.树的先序序遍历与其对应的二叉树的中序遍历相同      0 ^) j- ]# ?2 x- h
D.以上都不对
+ @. j; ~/ W; N[ ]15.下列说法正确的是
, L. v+ [  i5 ?2 A    (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索% m9 S" _3 D8 v' X+ h, T
    (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前0 L5 ?( O$ D# A( _8 q; ~# @: i
    (3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值
4 H# o) D& \) n" OA.(1)(2)(3)                     B.(1)(2)   ' S0 i- f) l2 }! S  E
C.(1)(3)                        D.都不对0 }7 T: F5 Q- C
[ ]16. 二叉树的第k层的结点数最多为
5 F: j5 ^0 f, u+ o7 N  o' y2 Z      A.2k-1                          B.2K+1      
+ c1 e  d# }* P( v% b, X( UC.2K-1                           D. 2k-1( ~' k; R3 v+ ?  r1 @, O
[ ]17.以下说法不正确的是
, B/ H, o: D; {" E; U- z     A.无向图中的极大连通子图称为连通分量
- u5 u+ o! I9 M) y& j; H     B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点% O* d$ `7 d9 l; Z1 S; E" Q9 Y/ d
     C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点; h$ j" ?( C$ t4 c1 `+ [6 E" Y  U9 `& V
     D.有向图的遍历不可采用广度优先搜索
7 f5 A# [1 N3 f[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中
6 d, I" Y- e& TA. 第i行1的元素之和            B. 第i列1的元素之和9 n, j0 S* Z7 E4 C4 o" m  i3 B( L- Q
C. 第i行0的元素个数            D. 第i列非0的元素个数3 V" A( U3 t9 A- h3 g# V* |
[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至
( o2 H' [7 u  j4 i0 C( j少应是2 R2 X9 K, G) R+ D
A.5              B.6              C.7             D.8
7 A. y1 B" a. o [ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是
9 u' U% ^" D' a/ l* @6 |) J  
2 ~9 X# h7 H/ B4 TA. V1V2V3V4V5          B. V1V2V3V5V4
3 ]7 W0 D4 `/ l& e1 s2 MC. V1V4V3V5V2          D.V1V3V4V5V2
: E: h% V: X! e5 d" |/ R( }[ ]21.关键路径是事件结点网络中
1 R% D  p% }1 E5 P* [" o9 }0 U5 j( ?      A.从源点到汇点的最长路径    B.从源点到汇点的最短路径5 G4 S! c1 \4 s( R& W$ y
      C.最长的回路                D.最短的回路
. R9 j! E# O" ^$ `# \[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是: X8 }/ g/ r+ t8 ^
      A.8       B.3        C.5        D.9
+ A! R8 u6 C" L2 V[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是
3 I$ I; |1 W& X- L1 L, gA. LL型           B. LR型       C. RL型       D. RR型
, n6 R6 [: C. k. ][ ]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是( R/ y0 l4 G+ W. ~
      A.插入排序                           B.选择排序    6 ^' {2 e; }1 `1 f
C.快速排序                           D.堆排序
+ _# b3 {: E" o9 d0 a% @$ A& M[ ]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是, F+ v5 U9 b5 W3 U( Z1 H
A. 堆排序                              B. 冒泡排序   
' |$ U$ `2 h3 Y& {9 l% ?) I) kC. 直接选择排序                        D. 快速排序
. L* m6 ]/ H' m[ ]26. 有一程序段:i=1;WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是5 S8 r/ B$ I* D. ^. U- [
A. O(n)                                 B. O(log2n)   3 L5 F6 u- `6 B
  C. O(nlog2n)                             D. O(n2)/ |% D# S/ }; c3 Y4 h
[ ]27.无头结点的链队列Q为空的条件是' c! h8 W8 Y: y( F) Z2 w* _1 t" O
A. Q->front->next==Q->real=NULL                             1 G# @# M( |* I! c$ g# v, [
B. Q->front==Q->real<>NULL      
0 i+ A* _- ?) O4 j  }7 j! gC. Q->real==Q->front=NULL                              ! s: p* C& [, j2 R" O
D. Q->real->next==Q->front<>NULL
  V& T6 P9 u& ?$ v- F[ ]28. 有向图G可拓扑排序的判别条件是
. h' i9 }/ e  \! H# v3 S7 ?8 O% aA. 不存在环                  B. 存在环        
& H9 j+ s9 t1 }C. 存在入度为零的结点        D. 存在出度为零的结点   5 c/ o5 R* \6 I( k( o; j. s
[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间! `! Y1 V. l: Y
      A. O(1)        B. O(n)      C. O(1og2n)       D. O(n2)1 |- v2 E" `' H) @" V# U* k
[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
2 x6 z# X: ~- k7 L       A.插入排序                    B.选择排序     
8 u! V# N+ u$ S8 I6 P9 x+ EC.快速排序                    D.堆排序
& B4 G; ]4 B1 \) S: Q二、综合题(共4题,每题10分)
' s9 s' O7 A( A4 A2 H3 L& s31、阅读算法,在横线处填入语句或注释。0 @4 J# x$ G& }+ O9 L
void exchange_L( Linklist &L,int m ) {
3 D# a" b$ U6 s: {: B% f // 带头结点的单链表中前m个结点和后n个结点的整体互换! ~4 F: I4 A* Z; Q
       if ( m && L->next ) { // 链表非空
' A3 d* ^. x8 j$ _3 T" O1 i: m            p = L->next; - d9 L" s7 c5 p9 g0 _# K. _
            (1)// k取值) i: h% O, e8 M; }
             while( k< m && p ) { //(2)" A( D, T% e2 f' J
           p = p->next; ++k; ) Z' T4 }# |3 j9 a6 B2 _' l
       } // while / @% U5 z$ u5 _7 N
             if (p && (3)) { // n!=0 时才需要修改指针( B9 w% w9 i- L+ I% F1 v
             ha = L->next;  //  以指针 ha 记a1结点的位置
6 N. D: B% U. b- ~4 Z2 \& z: n                 L->next= p->next; // 将 b1 结点链接在头结点后/ w. N' f# c# b( d
                 p->next =(4);  // 设am的后继  {; n+ [- Z' d5 ^# X% P
                 
9 Z& Y* U8 ^: g0 X  q = L->next; // 令q 指向 b1结点 , g) q- d6 Z& ?6 |( x* q: Z7 d
                 while (q->next)
  Z9 X. D8 s9 N& l" e5 n                      q = q->next; // 查找 bn 结点
8 _( G( V1 S5 f                 q->next =(5)//将第 a1 结点链接到 bn 结点之后
; F( O+ ?9 h6 v* N+ w. v& @ } // if(p)  l) T/ s# Y+ H, \0 A. }
                              } // if(m)
2 z' X* T2 G, G! V2 u8 \. U                             } // exchange_L # G9 g. l) F6 N0 `( T; g, ]+ f0 m

& q" D& x2 E0 ~6 D& v
0 D0 a, Y& W' z+ t- G$ s3 I1 K, w+ n# O

( X5 k5 F4 C5 J$ H* ~4 E* b3 T- i$ e9 e0 R5 Y4 ?
7 f2 S4 T  `8 O# B/ D' s
* K6 K, r" {( F! d2 N
$ J0 [2 W# ]4 T! @4 b+ E' p

9 G' V3 P3 R% f7 H1 t% g8 E$ r+ h3 i7 w0 M/ D7 U$ `0 a

# D; H( ^7 d6 a" z32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。- h7 ?0 e) L$ O, B6 J" ^! `
$ u9 t6 {1 ^$ j) d2 ?' d5 L' P4 @: e

0 t, @0 Y3 m# G9 f9 f, H1 z7 K, w* \& a3 A( B4 S6 J' @2 T. o
5 Z+ F" d- Z5 ]  p- V8 P
$ a% N% l% D0 `

6 S0 D! y& B$ \7 T9 r0 Z9 r8 I. x! t6 _+ a+ v
# I7 S! K" z& S5 m: W

) [, O; f  U# Z, `: [
5 ], J) Q& G: c6 s# f; i+ s
: J! Z4 `% r  L( r5 l  m, _$ ]7 Y! ^7 @8 z) \1 z
1 |1 ~3 z9 ]  h7 U4 N0 O$ }+ G

/ l4 X5 R# ?1 G, r1 _- n1 ^6 O, i. c1 W
& I! f1 L, A2 T: o4 R4 X: U9 h8 ]
33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。( x( t$ T8 `" g* p; V/ l4 e0 o5 f
逆邻接表存储结构定义如下:
& k4 I* r0 i/ C  f7 V顶点结构                       表结点结构8 T* Y2 U. K1 t/ c( q+ P8 [7 t
vexdata        firstin ! F; _8 l5 s) N% c
adjvex        nfo        firstarc: a* a/ t( N$ b

/ w7 p1 ~: x! V. N( q; u1 \) h/ V& b" Q
2 @3 `) e, c& @, h& e8 |$ d& v- P

& ]: ]. n5 S6 o$ h2 Z- Y( Z
% g. i, b3 M) T1 D$ ~5 R6 m* a6 e& y% o2 Z6 }

1 _  [, D2 w- e% U5 {
& G2 X) q! R0 |  s* x% a) C
. o, C: n2 z$ w- r  D
7 l6 i/ I% j  x& O) B: g4 r' q
; q8 C2 b) _. X8 O0 s  S2 p% W$ C. h3 D
# |8 `2 l; u! F* K' @# e2 ~( q( W
2 w6 c( t+ P0 D( D) s6 z

) Q) O2 i' S9 _& o8 I, }5 A: N/ J5 ]) \
34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。" |  ?7 `9 p4 p$ T0 @5 Z
试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。
& O8 B. `2 d) Z(2)计算等概率情况下,查找成功的平均查找长度。0 x$ L8 j8 U. S9 a9 u
0 l- ~+ Q4 d) }. t. [

/ A1 m4 ?, h% ~; C7 m( H, L( V6 ?. U8 H# R+ g

6 a+ E+ _  J/ h) Y" d& S, V  ]' f- p4 E# X, ^

+ o; [$ N! c3 o7 @& i# ]8 R) A3 k+ d* [' Z
/ o7 ]  e6 p, p1 O

. L2 d# E4 N/ i  K6 X% D: T4 \' a: d, t
8 m) M  ?" g$ Q+ }$ i1 \
$ i* k% J, R3 [, L- s( i" X

- @8 d/ v' I4 r# r# i
( ?2 `* r+ _9 S1 A" s) y  `' l$ X; A) f5 d# U" e* d7 x' w) F* ?1 a0 l! Q9 \
4 ^2 Z; C5 b1 J4 u& i) I/ R
" }: h- R6 m" i7 ~- ?$ ]

3 t- k, z2 K+ L! e
  e6 v4 v* O$ Z- h6 Q. g0 P
6 ~' g- g8 m+ }: r/ m

本帖子中包含更多资源

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

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

本版积分规则

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

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

GMT+8, 2025-2-19 07:08 , Processed in 0.114526 second(s), 20 queries .

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

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