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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

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

[复制链接]
发表于 2021-1-6 21:38:17 | 显示全部楼层 |阅读模式
谋学网
东 北 大 学 继 续 教 育 学 院8 M- z8 P4 D0 R+ r2 F. `

) E/ w) V/ R9 E3 \1 A 数据结构II X 试 卷(作业考核 线上2)  A  卷
8 Z- n; N! c# e! p
0 g& ~: q8 t# O$ V* N3 E( R; t学习中心:            院校学号:             姓名             . g$ |0 {/ N9 U3 Y' a) x
% ^1 i! k. z+ Z: r+ `. Y5 k& a+ x6 a
(共    6    页)         
& ]6 A+ s1 V$ O1 ~% B# q3 ~总分        号        一        二        三        四        五        六        七        八        九        十
& e: C+ w% v8 }# K/ C% S        得分                                                                               
3 I9 v# G# ^9 u一、单选题(共30题,每题2分)
& S* K' T' g. z9 k[ ]1.抽象数据类型的三个组成部分分别为
6 W  x: A: `/ ]% Q  O& X9 vA.数据对象、数据关系和基本操作1 B4 a7 o3 ?+ R4 V8 I5 r
      B.数据元素、逻辑结构和存储结构5 w4 T! K% L8 b+ Z7 ~  Y
      C.数据项、数据元素和数据类型( Z# E* L$ _& [; C/ E! K
      D.数据元素、数据结构和数据类型
/ M. M: m+ C$ N: }' a4 N! K[ ]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
: w/ \: D6 {+ K/ LA. 数据元素具有同一的特点
+ y" M, {4 i5 j/ k. g* v! D. |B. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致, {6 H. f8 W1 g0 ?$ S8 Y
C. 每个数据元素都一样
) i5 y) s# l$ _D. 仅需要数据元素包含的数据项的个数相同
4 S+ ]* X1 R4 r[ ]3.下列各式中,按增长率由小至大的顺序正确排列的是
: n" Z  f( f7 z& BA. ,n!,2n ,n3/2                    
* }8 O1 I) {: nB.n3/2,2n,nlogn,2100
; O& a+ C" j0 f, |, k, g# i      C.2n,log n,nlogn,n3/2                7 M! s- N# ^  w1 @0 t7 n; ?" `
D.2100,logn, 2n, nn
# A7 S- e7 u6 c& n[ ]4. 在下列哪种情况下,线性表应当采用链表表示为宜
0 v& ?/ z% s- V      A.经常需要随机地存取元素         
9 q: P) M/ Q3 n+ p4 r8 JB.经常需要进行插入和删除操作: j+ t% ]4 q/ O, l
      C.表中元素需要占据一片连续的存储空间    . N, @4 K  `; l- q( A
D.表中元素的个数不变
- {. L, Z4 ^. g9 s3 a$ d$ \% z, ?[ ]5.设指针p指向双链表的某一结点,则双链表结构的对称性是
  u% E+ b: C* TA. p->prior->next=p->next->next;       3 u; V- \6 a) f9 ^
B.  p->prior->prior=p->next->prior;
% d& |- N% O& T) @) ?9 XC. p->prior->next=p-> next->prior;     
5 t5 @1 R" G( `D.  p->next->next= p->prior->prior;
& Q% |& f$ `. `8 c+ E[ ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为7 Q+ W9 R* b) G- J* s4 ~
    A. s->next=q;p->next=s->next; 6 m; E- s2 c$ u: f% O
    B. s->next=p;q->next=s->next;
8 P+ r5 P  X! g! ^9 S+ u- l! A, i) TC. p->next=s->next;s->next=q;
9 e$ S4 q* x  X7 aD. q->next=s->next;s->next=p;
$ |; S' k$ b& x[ ]7. 栈和队列的共同特点是* k( z: P& ]9 I9 @6 L5 Q* j& h3 ~3 f
A.只允许在端点处插入和删除元素: S9 I5 X4 l6 j5 L" Q
B.都是先进后出   
7 i, z8 e" v7 N; tC.都是先进先出
* r! [1 E& y* g5 z  B: C: `. ?D.没有共同点
3 V5 s$ P/ `) z5 {1 X: l[ ]8. 对于链队列,在进行插入运算时.; q) s2 o2 }# S( q' X& v. B& \# f
      A. 仅修改头指针         
- P0 y" `. o, [5 |' m% ~7 gB. 头、尾指针都要修改+ H3 [. G+ n/ b" @5 r! ^% T" V
      C. 仅修改尾指针              ) o+ X8 r* N+ Z. z3 A5 U
D.头、尾指针可能都要修改
; _& O- q% [# }[ ]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为
. a& @2 m6 e% W4 @% x4 Q- m      A.4      B.5     C. 6     D. 77 w8 {1 H' a! T- H+ N' ?. @" k
[ ]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是6 D! a5 r6 G* r) r0 n4 H8 W
A.A,B,C,D               B.D,C,B,A   
& d2 l& [' `+ t6 |8 @7 MC. A,C,D,B               D. D,A,B,C
+ \# l0 u. j" q( I( b, o[ ]11.表达式a*(b+c)-d的后缀表达式是* p4 n# f" J7 a! a9 L/ {$ I
      A.abcd*+-    B.abc*+d-  C.abc+*d-   D.-+*abcd
; Q  y  i0 ~8 a/ f( q  `  M% ], i[ ]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是9 S2 k  e' i8 A) @' d0 b- U
A. 空或只有一个结点             B.高度等于其结点数
- F( S7 h7 m, p+ f( ~C. 任一结点无左孩子             D.任一结点无右孩子
2 D2 o/ }# x3 w* }, q, [[ ]13.下面的说法中正确的是0 a2 j$ R+ f3 ^8 T' o- d3 |5 l
    (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。: Z/ l' W. n5 e6 Q9 N
    (2)按二叉树定义,具有三个结点的二叉树共有6种。
9 H% Z9 B- M( o: _9 k$ rA.(1),(2)                       B.(1)    ( b1 q# |, h1 |/ I2 H2 k" _
C.(2)                            D.(1),(2)都错* K* Z/ D( ~: z8 K1 _
[ ]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。下面的& T- ]/ P' x  \2 l. t* h
说法正确的是7 q: b' c% H/ S7 y3 \4 F( z$ j( C4 H
      A.树的后序遍历与其对应的二叉树的先序遍历相同     
+ ~' ^# S4 e# u) @! \# TB.树的后序遍历与其对应的二叉树的中序遍历相同* O/ @- b3 K/ P& l4 x/ h/ ~
C.树的先序序遍历与其对应的二叉树的中序遍历相同      7 t9 k7 C4 w- A! `8 |% U0 H5 F. d1 C
D.以上都不对0 s+ p8 n8 E9 i$ Y# q
[ ]15.下列说法正确的是* n# M, p4 R. v3 y+ c5 V4 e7 N7 ^$ _
    (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索
/ A: n8 \. k% `8 R/ [8 X+ j* z    (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前
/ e8 k4 i! }2 S4 Y  E    (3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值
( {0 @2 m! s: L+ iA.(1)(2)(3)                     B.(1)(2)   
8 T% G: O: n; H1 b, o& H% f& G; ~C.(1)(3)                        D.都不对  M* A8 ^0 Y; e$ e4 a5 X7 l' D. E3 `
[ ]16. 二叉树的第k层的结点数最多为! q+ _2 q' ^# n5 d* Q# ^
      A.2k-1                          B.2K+1      
: t4 ~6 }& N5 i, CC.2K-1                           D. 2k-13 J  U0 s1 |& ?
[ ]17.以下说法不正确的是" B; ?' e  U8 [
     A.无向图中的极大连通子图称为连通分量
0 W7 W3 f- n, B6 e( M  y     B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点" W+ c8 Y8 A! F0 }
     C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点& x. q7 ~" W9 |  Z6 T6 N6 u
     D.有向图的遍历不可采用广度优先搜索
/ E" d: }; u5 f1 m9 N[ ]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中9 g  h7 O! R! t! m6 c
A. 第i行1的元素之和            B. 第i列1的元素之和6 m: f! ^" N7 K3 Q2 h
C. 第i行0的元素个数            D. 第i列非0的元素个数
6 F* i! u6 k% f7 w2 ?4 [$ V- F[ ]19. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至. e6 M2 l6 ]1 ]/ w- X" `& R
少应是
3 q+ P2 Q2 v& U9 VA.5              B.6              C.7             D.86 c( q9 A. m# X9 g
[ ]20..下图的邻接表中,从顶点V1 出发采用深度优先搜索法遍历该图,则可能的顶点序列是 3 l( x$ F$ v* H
  , T6 o7 x* |( @" A# l+ G
A. V1V2V3V4V5          B. V1V2V3V5V4
: F/ z7 g  f  G; SC. V1V4V3V5V2          D.V1V3V4V5V2 % w" ^5 g4 D# t8 G4 s
[ ]21.关键路径是事件结点网络中
& k6 h. _5 w  s+ z/ c( u      A.从源点到汇点的最长路径    B.从源点到汇点的最短路径+ E' p* S8 v0 R7 w% C
      C.最长的回路                D.最短的回路5 N4 I5 O5 q, q- ~
[ ]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是5 G8 y0 y$ q$ J
      A.8       B.3        C.5        D.9
! @# O, G2 s5 f% V4 @6 ~[ ]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是3 `# X! b1 p2 i: R+ h
A. LL型           B. LR型       C. RL型       D. RR型  H8 z$ l7 N' t! {+ v, t
[ ]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
; C; g5 a6 Y  q9 I* @# T) z: S1 H. T      A.插入排序                           B.选择排序    1 ^( t8 ^8 ~1 Q
C.快速排序                           D.堆排序& W! y: u' b: S" B4 H, K
[ ]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是
. |3 Y9 V9 s% i  i3 IA. 堆排序                              B. 冒泡排序   
3 p2 G) o+ `* O, p* ]0 `- Z1 z8 r1 WC. 直接选择排序                        D. 快速排序" h& Z8 B. y: Z3 s0 l+ ~/ y) m
[ ]26. 有一程序段:i=1;WHILE(i<n) i=i*2;其中带下划线语句的执行次数的数量级是  z' g  n, w. e
A. O(n)                                 B. O(log2n)   8 @# l3 y; c' Q% Z0 w6 T3 p7 C+ K" U
  C. O(nlog2n)                             D. O(n2)
, h4 B9 U' i" \; K4 o[ ]27.无头结点的链队列Q为空的条件是
. A' _9 S$ X% w2 s: B$ vA. Q->front->next==Q->real=NULL                             
2 U! |9 l, S/ @B. Q->front==Q->real<>NULL      
: V# f2 B" |+ ]* Q3 B- UC. Q->real==Q->front=NULL                              ; y, u( ]; n4 I# ?
D. Q->real->next==Q->front<>NULL
0 k6 t  e. I) B  `[ ]28. 有向图G可拓扑排序的判别条件是
0 _. [5 T8 ]4 v) \( YA. 不存在环                  B. 存在环        / F3 p: J6 S1 K
C. 存在入度为零的结点        D. 存在出度为零的结点   
: \1 ]' R: e4 W& O, ?[ ]29. 对n个记录的文件进行快速排序,所需要的辅助存储空间
3 a  {6 ?3 T/ {( s$ j; J- a      A. O(1)        B. O(n)      C. O(1og2n)       D. O(n2)
1 W# _" D& {6 e. O  O[ ]30. 下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
: v5 d  j% B. ?8 x& r8 \       A.插入排序                    B.选择排序     
  V) r( S  T. F# X6 uC.快速排序                    D.堆排序
7 _* v5 p8 Z7 T7 T8 ]二、综合题(共4题,每题10分)
$ [& M  I3 i5 T9 z& E: x31、阅读算法,在横线处填入语句或注释。8 c. V2 W& f8 w4 ?2 [* X
void exchange_L( Linklist &L,int m ) {
  G* k& S/ t4 `8 x' x# J // 带头结点的单链表中前m个结点和后n个结点的整体互换
: }+ L8 z7 r* {       if ( m && L->next ) { // 链表非空
/ h8 X  R3 @- T& P            p = L->next; , ~6 e. H8 h0 y7 k' k4 _4 g
            (1)// k取值
% q7 O* f; U9 ?- |6 }             while( k< m && p ) { //(2)6 T3 ~( O: o* U
           p = p->next; ++k;   N' Q, `9 T0 _( W1 `
       } // while
4 z+ u& D2 |# Y5 ]$ S6 k+ R2 F8 y             if (p && (3)) { // n!=0 时才需要修改指针
3 x/ c5 b  G9 c! \* f9 O3 @% @, T* t             ha = L->next;  //  以指针 ha 记a1结点的位置# l7 Q% k) `8 F/ U0 N
                 L->next= p->next; // 将 b1 结点链接在头结点后
* t2 x+ n/ R6 K5 S* Q0 s                 p->next =(4);  // 设am的后继
$ ^) l5 \4 x0 w$ r                 
, ^' L8 L# c! H, U6 ~( e3 b6 V9 e  q = L->next; // 令q 指向 b1结点
4 M, W. y! O1 k                 while (q->next) ! \# L7 u( ^5 f# S
                      q = q->next; // 查找 bn 结点 # N# @% \  ~+ i. H; Y% [$ j6 b
                 q->next =(5)//将第 a1 结点链接到 bn 结点之后
- o. @8 m$ ?" v5 u } // if(p)
) P$ Q; ?0 h8 _) n* U% h                              } // if(m)
* o) T! B2 }& y  ~                             } // exchange_L
4 o0 S' A' B9 B
- c, u6 R+ D2 N( z* N. M% `+ E4 a4 ^
8 r! c( a/ m1 h7 x' x5 F* ~. M3 A. d
, P4 C9 L3 _. c- Q

) `! G2 H5 \3 y  d# ^( ?4 a8 ]; \: m

/ B# B: _8 U  z- D4 j, L" `; r$ V
+ `) V5 z; ]  b; n  M9 s
( g+ A+ e% d9 N2 K% \
$ m) J8 i& R* J& v5 p, \
+ Z  W( R* L# n0 }32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1实现求值,并指出遍历的方式。/ M9 n( n& f3 h7 F5 ~

/ N3 N5 s3 n/ {; A& Z7 e3 {1 b4 @4 y* D; i+ T
+ V, c$ P) p2 g; B  s3 a* |  G
  {( F( c: `7 r
2 Y1 K6 }+ N# T& m, v. g

9 r" R+ B0 G, z4 w, }
& K6 e8 G5 v2 a8 T& O8 L. F
( p* i* q' B) `- }% A6 a+ Y& |2 N! d7 h+ W9 g- K

" v# O1 ?6 |* D) Y7 z$ ^; }' N, ~* J
' y( p8 a7 I4 x* F1 q
3 x& p4 I: c+ ?; O9 }5 j+ T- G1 u% {
5 Q9 f) C1 T9 Q- {$ R! M
, ^8 U0 |$ K) _7 [5 |  L
# n; E! `9 R6 `  m
33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。/ m: h4 Y/ M  F/ b
逆邻接表存储结构定义如下:7 d. ~' F5 y- T6 T
顶点结构                       表结点结构
& \- }' Z& [) N' L$ @9 w; [vexdata        firstin
) T# n) q6 D6 {7 E- u0 M, Y% vadjvex        nfo        firstarc' t* ^4 @2 ^* n( r

. C5 _" v8 o1 n4 j: N
( a; y3 F" H9 G6 w# X0 m  I  E/ O/ w# I8 j6 S

7 z7 [# S: {; Y9 v7 |
: \+ \, @2 t7 v( o/ {* [- Q) q" F. S! t% c( u

5 p0 j) i' b- [0 c* k
1 i% h; n1 |5 i- A' N9 |
3 N/ v# S+ c$ V# Z0 F0 H  C
' F# ]; X/ p# }8 T( d% g. ^1 B# b# n% P" O: C
; S  [+ l8 \6 t/ o' S! w
+ S9 a' p9 ~8 t- A' g

6 m) S1 a7 t0 [! _/ |$ v( B; p  _9 l) R3 n* W! W: I3 d2 ]

: q5 f/ S4 ?) z0 d34. 设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:H(key)=key%13。
' E3 x% u0 v2 z/ q试求:(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。
4 x( t9 F0 t! o; N$ I& S, w(2)计算等概率情况下,查找成功的平均查找长度。
; r7 _" |2 S4 Z
6 v* A5 u( E+ `1 W( z9 N1 r2 w9 t. N$ v
- f" p9 X# b) `2 K/ f

. R1 d% p9 p3 B# u3 X2 I- e. A
' N* v+ t( G/ j4 y: d+ B" z" N5 l7 P% a: y. W; e

# X0 Z0 k. ~1 @0 z, X- ?+ ^7 l/ t9 w5 D
( g3 l" E7 n2 ^

; B: q/ g- y; i3 g5 i7 L( T' ]: y0 s) |. [- z4 M" h

- q* u- i$ O& }5 ?) {+ `. w1 L/ F6 p6 z3 k9 L5 J2 |! H. C  A& ~
5 P4 Q& H3 b4 N7 {) `" x7 X# e
( n# Q2 _3 m9 t0 I( t

7 P: G+ Y4 x& R# C3 F! C( r) r
6 b8 V+ o7 B, c, E
: B% m, J! f- Y# o
) B- }# ~2 h9 b. Q6 k& n
4 \9 w* u( O0 U2 w

本帖子中包含更多资源

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

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

本版积分规则

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

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

GMT+8, 2025-2-21 03:12 , Processed in 0.089588 second(s), 20 queries .

Powered by Discuz! X3.5

Copyright © 2001-2025 Tencent Cloud.

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