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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

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

[复制链接]
发表于 2021-11-15 17:36:29 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院5 b$ u; @: u3 z3 E/ ~4 M* y

# |$ ^# a8 T# R$ G. K 数据结构II X 试 卷(作业考核 线上2)  A  卷
8 F9 m# Z! g) m% v. E0 O
3 R9 b  B/ \0 v+ E% _# o" H" w, R学习中心:            院校学号:             姓名            
) B/ f6 j7 e& A! m) l4 E& M
$ q  W" j, x% B7 c1 R+ I, L5 \3 v(共    6    页)         
0 F1 q7 n: \: ~2 d- s/ z总分        号        一        二        三        四        五        六        七        八        九        十
- m! |4 e: `3 y        得分                                                                               
. Q% t: b# w) _, q8 B  e一、单选题(共30题,每题2分)
6 `( e4 z& |! P6 U# A9 m, x[ ]1.抽象数据类型的三个组成部分分别为
5 p+ G5 r: ?; ?1 kA.数据对象、数据关系和基本操作
3 S- }7 g7 W, U+ C; v# Z      B.数据元素、逻辑结构和存储结构
: G. V( ^: a% o, y. S      C.数据项、数据元素和数据类型3 X) w. n. Z7 i9 a& p2 Q2 n$ H$ A7 ?
      D.数据元素、数据结构和数据类型& f5 r2 u8 g9 f1 _( s
[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
7 |. }; c' U) rA. 数据元素具有同一的特点
. e1 ^: B* q7 i7 {( I5 sB. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致8 X3 P/ a: o- S
C. 每个数据元素都一样- a! D$ `) P, \
D. 仅需要数据元素包含的数据项的个数相同
5 s) ^. N5 N/ _. d, e  v[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是
7 Y) l5 b6 z/ L& R. `# |9 mA. ,n!,2n ,n3/2                    
9 l, o) H* u! X! n+ bB.n3/2,2n,nlogn,2100* [. x2 H$ }9 c5 J5 u
      C.2n,log n,nlogn,n3/2               
4 d2 ~  L/ F) Z8 G( Y8 _+ B: HD.2100,logn, 2n, nn+ N$ m; a4 u8 j& W" A
[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜/ ]% r! O+ c  R# h# m- v: S
      A.经常需要随机地存取元素         / M. f% x: d" L% T" h+ Z
B.经常需要进行插入和删除操作9 n4 R  P) s. h! h8 |
      C.表中元素需要占据一片连续的存储空间   
1 x1 w8 J  J* r" n' r' ]D.表中元素的个数不变2 v6 r4 k  t* |2 E
[ ]5.设指针p指向双链表的某一结点,则双链表结构的对称性是
% t! N# j+ h9 h1 o9 RA. p->prior->next=p->next->next;       % {- c4 C* W9 g1 |( z6 X. k
B.  p->prior->prior=p->next->prior;0 x- U$ d- X' @1 s( }! K8 d3 n
C. p->prior->next=p-> next->prior;     
6 q! \" @+ Q" p& {2 zD.  p->next->next= p->prior->prior;
: y8 H# V7 }5 i- T/ s) q9 R[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为& C! M$ [+ z3 Z; k
    A. s->next=q;p->next=s->next; 6 ]$ R" @5 n$ o* ^5 _' r& k
    B. s->next=p;q->next=s->next;) F- s8 G: |6 b: \
C. p->next=s->next;s->next=q;
, a5 `5 _% t* DD. q->next=s->next;s->next=p;9 t4 k2 q+ S' A6 M
[ ]7. 栈和队列的共同特点是+ `; f% M& |: [, ^/ ?6 y9 _
A.只允许在端点处插入和删除元素
1 t6 f$ d" J+ N' X# s- FB.都是先进后出    ( w' ^8 a/ n6 H9 b! G3 q+ e
C.都是先进先出+ u! X- \0 C1 ]5 b6 f  B
D.没有共同点
6 W! ?3 T5 m  Z! _' c3 k[ ]8. 对于链队列,在进行插入运算时.. A' b3 j+ Y& @: [3 P( c  n
      A. 仅修改头指针          ! b+ y1 g/ E( q
B. 头、尾指针都要修改
+ s* N4 b6 g( y0 V      C. 仅修改尾指针              
% o8 ]- d: E% a9 q5 o0 ID.头、尾指针可能都要修改" x* Z) m. [0 U
[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为" n: v; X- s+ a
      A.4      B.5     C. 6     D. 74 B4 S4 ]" O5 o9 h) R" h
[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是% t$ j: m% r. O
A.A,B,C,D               B.D,C,B,A   ! W0 N& S2 [  {6 J( p1 ?
C. A,C,D,B               D. D,A,B,C  X' ]. @+ O9 u# T: }
[ ]11.表达式a*(b+c)-d的后缀表达式是/ l5 _+ Q. q$ y  A: z  s
      A.abcd*+-    B.abc*+d-  C.abc+*d-   D.-+*abcd
: i& _' D( T& y( m$ p[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是
& K+ q+ H6 Z: kA. 空或只有一个结点             B.高度等于其结点数
; A) U0 E1 @  a- BC. 任一结点无左孩子             D.任一结点无右孩子
, c7 X( J, h3 G  C" O[ ]13.下面的说法中正确的是( G' g$ E0 Y9 A* W- v: ~" Z
    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
7 z1 e3 g; i6 J) q  I    (2)按二叉树定义,具有三个结点的二叉树共有6种。
  S$ d. Y9 C: h4 Y( _+ L" i( WA.(1),(2)                       B.(1)   
( l+ j3 t0 ]# N6 a+ ^2 cC.(2)                            D.(1),(2)都错$ D1 a  \- D  s
[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的3 n) F* e( i' d! g8 Y
说法正确的是* }) q% F* u( X5 Z
      A.树的后序遍历与其对应的二叉树的先序遍历相同     ) i/ f; H7 r6 e# P$ ~
B.树的后序遍历与其对应的二叉树的中序遍历相同
! Y) W% [0 l( J/ ]9 RC.树的先序序遍历与其对应的二叉树的中序遍历相同      
+ J7 S& w" x: d! H) oD.以上都不对
& F- z6 k& o$ o8 z) i[ ]15.下列说法正确的是
$ [+ M7 L6 @/ W. q    (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索
6 Y" D3 Q  c# H  @2 w1 ?3 X/ ?    (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前
( O* \! x+ n7 G! p2 |    (3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值5 V' V! E3 o: k# r# q6 K
A.(1)(2)(3)                     B.(1)(2)   
; C3 K, e* s1 I7 ^1 M5 lC.(1)(3)                        D.都不对  b. A% f4 J. `
[ ]16. 二叉树的第k层的结点数最多为
; m( b5 p1 Z6 a9 }      A.2k-1                          B.2K+1      
9 y/ U$ b( S2 B  I' wC.2K-1                           D. 2k-14 B$ y  l7 V1 c. F
[ ]17.以下说法不正确的是& o6 c9 Q( y7 R" j5 X' k0 F3 j, O% G/ p
     A.无向图中的极大连通子图称为连通分量
" m8 B3 b, N. I) o0 c+ I, D0 I     B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点
' P. q" }! G/ Z* a: o  h  `% u     C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点' v: q5 f2 H5 \. A
     D.有向图的遍历不可采用广度优先搜索7 s8 @' }$ h9 y* U+ {" |
[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中4 X/ n+ R( R& c
A. 第i行1的元素之和            B. 第i列1的元素之和
! _8 O8 H* v, g) x- KC. 第i行0的元素个数            D. 第i列非0的元素个数" Z% A+ d/ Z8 Q. B- r
[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至4 f) I: X8 _' T; D
少应是2 i8 t9 r; ~" @& R
A.5              B.6              C.7             D.8& |: D- `, b7 @5 L
[ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是 ( L, ~8 @+ \2 H- X6 }# T# y5 y& \
  4 p" W7 h. @. K/ Y" ^: E) j( X
A. V1V2V3V4V5          B. V1V2V3V5V4
9 `# o7 t/ m* i2 T( c  l* ZC. V1V4V3V5V2          D.V1V3V4V5V2
5 T* E! F1 z$ b# s" e1 x& E( e[ ]21.关键路径是事件结点网络中' X- i$ [& b: Y+ O* }) s: i
      A.从源点到汇点的最长路径    B.从源点到汇点的最短路径
2 Z3 B* ^, n3 X+ N4 ~9 I      C.最长的回路                D.最短的回路
* f  }; J* {3 M; M& {- C[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是" L1 u+ L) P8 {; Z& `. X3 v8 r# g
      A.8       B.3        C.5        D.9
$ n  _  T. M6 X+ [% F; H[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是
* _. S6 q7 @: a  DA. LL型           B. LR型       C. RL型       D. RR型
/ V! [3 r, H" A( `' D8 ]& [* K4 o[ ]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
& T) M7 ^8 z* Z. M      A.插入排序                           B.选择排序   
: {9 b; x& k- z  O# kC.快速排序                           D.堆排序9 D9 k% @! h9 m% r9 B5 J
[ ]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是
& J  N8 D5 w: [0 y( ^+ Z. }A. 堆排序                              B. 冒泡排序   
0 F9 {. Y$ [) U4 T+ `, b3 Q5 q1 c2 V5 nC. 直接选择排序                        D. 快速排序8 [# b* n! M5 E% i, Y. j9 \: k" g' W
[ ]26. 有一程序段:i=1;WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是# p2 P& N* y! ^
A. O(n)                                 B. O(log2n)   
, p! F6 o2 A2 g- @+ g, S4 p  C. O(nlog2n)                             D. O(n2)
0 r" I5 w  X/ A. n% y7 e5 f[ ]27.无头结点的链队列Q为空的条件是
$ m. @% s4 A$ F$ UA. Q->front->next==Q->real=NULL                             
  i; u8 u& U, ]; m0 q7 `B. Q->front==Q->real<>NULL      
3 X* x" M5 ?% c8 E1 k" LC. Q->real==Q->front=NULL                              
- f) }: n% F' ^9 G0 |% sD. Q->real->next==Q->front<>NULL / b/ |6 Y5 V" b4 c( B
[ ]28. 有向图G可拓扑排序的判别条件是( \" k8 [9 C& j  ^5 Y4 T% M
A. 不存在环                  B. 存在环        
) m( o+ {/ i( s* t* T4 iC. 存在入度为零的结点        D. 存在出度为零的结点   
8 V" i/ G% p- J! V9 |; w[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间
! \2 u0 R/ ?+ j      A. O(1)        B. O(n)      C. O(1og2n)       D. O(n2)- i8 h( Y0 F* P0 _  y4 |
[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是* B; X5 @' H$ \0 ?
       A.插入排序                    B.选择排序     
+ r$ v' M6 q4 w6 E  v& FC.快速排序                    D.堆排序
( D+ B' C$ b! g8 \" C6 L0 {二、综合题(共4题,每题10分)+ V5 o6 I/ j! O0 V  q5 K
31、阅读算法,在横线处填入语句或注释。- [$ R8 w) A; V5 W& J4 v# {
void exchange_L( Linklist &L,int m ) {
5 O' i7 e! T" G // 带头结点的单链表中前m个结点和后n个结点的整体互换
& p4 L$ q+ i+ M# j" H9 x+ a* I       if ( m && L->next ) { // 链表非空
/ M/ a+ _+ l: v- k1 w            p = L->next; 0 I$ w+ O: z+ |5 [/ Y
            (1)// k取值8 G+ K( \! M- ~9 K0 Z4 F* h
             while( k< m && p ) { //(2)1 |0 y6 }+ ^& V7 z- x& p5 z
           p = p->next; ++k;
' S$ g& i; c/ r: N$ H  W: @       } // while + b$ G: M) J3 X" K# n+ {9 s" n
             if (p && (3)) { // n!=0 时才需要修改指针# M3 G& c$ a  n! @7 U1 K
             ha = L->next;  //  以指针 ha 记a1结点的位置/ d+ r( W' m1 D. p5 ?2 d" F
                 L->next= p->next; // 将 b1 结点链接在头结点后% b. K, l+ e% O8 D5 U3 G
                 p->next =(4);  // 设am的后继
* C- _& X, w& [/ \7 D' x                 . [2 ~8 E5 r1 f' l3 Q6 {
  q = L->next; // 令q 指向 b1结点
; W5 M# Q2 f' Q5 L, C) |                 while (q->next) " S2 c  o; l; g' n6 V; ]
                      q = q->next; // 查找 bn 结点
$ o9 _7 \  Q! _% I0 w$ p                 q->next =(5)//将第 a1 结点链接到 bn 结点之后% h/ O+ p2 ~$ D9 M" M0 P! h4 S0 I& U
} // if(p)
8 F' ^6 o9 r& g8 t; Z                              } // if(m)
5 D+ [7 \' P  _                             } // exchange_L
9 A4 T, S' r) L5 T/ s' S# x9 t0 f% [5 H" O( v, a5 @

" w0 l* M: D9 O. w2 f5 ^! |4 |: R2 B4 _9 ~$ u$ l+ K/ ^
: _/ `2 ]3 W% O& b7 z% n. D5 A
9 _/ K8 O! r5 k, p" i* _
) W' V/ Z( o# Z# u- _! K$ k2 ]/ P

" j& `, D, k6 p$ k& H( |) z9 R, K4 [8 y' \& P9 Y
2 r! R$ O! B# J& k3 C7 H; t0 u+ p

5 [5 }8 N$ g+ R; S0 C% R$ f& C7 Q/ p9 d
32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。% @% h6 v$ G1 Z0 K

7 s6 ?- U5 \, g# Z, ~* ^  V9 C- P
0 G5 q7 |/ t6 ~4 f1 T2 S; h7 j1 d0 P- b/ S, n. J4 U( X

  @& S  a; v6 W0 H0 H! G" p; y/ Y- w$ x. e0 P) S/ s( K, u* o

' V6 ]) l' g! m0 x( G# d* \* t9 c' d

- j6 q" M' k" |0 T+ S/ C$ e! c$ t

# m6 ^1 i) a( f; O5 K
- u. W; _$ v2 V7 m7 m9 _  P2 a/ I9 C: x$ Z
; j+ w3 E; h; J

$ D. Y$ |7 v9 x9 ]+ N' C* B5 Y
6 U# A  q4 b) p0 F( h! S' L
* B$ o( g; w7 a/ Y3 b" e; V3 {33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。/ y0 T1 o7 d0 k2 v/ l# d
逆邻接表存储结构定义如下:
0 d6 u" A- ^/ N3 E顶点结构                       表结点结构
* m. D3 R% m% X- q, c) yvexdata        firstin ! L9 F* n7 r# v7 v+ b5 b. Z# q1 E1 E
adjvex        nfo        firstarc
" q5 t8 G6 o2 G6 \
& j& {$ _' H, D. u
2 d/ T4 Q& ]" N# C: s1 Y
' U* I  E1 B/ a) u: y! q0 q# o
" e5 s' s& i/ H: B, y1 Y3 O) X9 L" w  T8 u8 U! h$ A
6 Q+ V0 N) _0 {# m8 L

# H+ N  {- I2 T5 p( ~
# u9 t, V& o! G7 M( N
5 A& n1 p8 Y1 O# Y8 x( K& w! _; K2 E8 P0 o3 Y4 e
, }4 b1 S% R! C  T! o! [% S
( F$ E9 Y) z. H

" x" n% P! [7 ]' g9 J
7 ]0 S4 d4 }( t
* _  W# |/ ?3 z  o( e5 c
9 u4 C4 V4 L4 x34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。
6 o* {! V4 G( l7 g* }, Q* `( a+ {试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。4 R' B8 K: C( l6 ~) e6 Y( m0 H' p. n
(2)计算等概率情况下,查找成功的平均查找长度。. w2 I# V6 L" `
, }& Q* x) g* s3 {6 f. D6 i

" N4 V5 ^) w# X; ^" L8 A! I0 x5 g/ B% e7 o  |3 a0 |2 V

/ L) O3 B0 _! |
% Q+ X& }. `6 @2 z2 C8 }: _; r6 E9 g! B! W* y

( D, c# l6 j% @$ a6 z" X7 v7 C( ~" [2 Z! @  c/ l
" L4 j2 Q2 B( F/ s6 G% ?. ~7 d( p
$ K- m( u( |$ s1 F" H

, u" F/ {* L8 Z3 |  H+ x: j2 n6 `
, B  C4 h- j0 Z, u+ C
* M( u& Z% q4 c, A
9 ?* w- q( }4 d$ |+ `% A  O
4 ?+ E7 K( L3 u# q# D* n" k  C; Y
2 Z  j# Z& z" ^9 M) y" F( ]

$ l# e( N- N2 q0 ]/ b7 C) d2 ^# [* {' n, X0 f
5 e& g9 y3 q7 Z3 l) B

本帖子中包含更多资源

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

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

本版积分规则

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

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

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

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

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