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

 找回密码
 会员注册

微信登录,扫一扫

手机号码,快捷登录

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

《数据结构》20春期末考核(参考资料)南开大学 资料

[复制链接]
发表于 2020-9-3 15:25:49 | 显示全部楼层 |阅读模式
谋学网
《数据结构》20春期末考核-000014 ]  O/ x* R9 g! t
试卷总分:100  得分:70
1 h$ d( G8 B  B一、单选 (共 25 道试题,共 50 分)
; O& {$ b" w' U1.快速排序在下列哪种情况下最易发挥其长处()
) R; `' x) \. CA.被排序的数据中含有多个相同排序码
  ~+ N5 u) |5 XB.被排序的数据已基本有序
2 u5 U; V$ \( j. H9 _- P; L  JC.被排序的数据完全无序
% T- D- m; |# n$ g0 PD.被排序的数据中的最大值和最小值相差悬殊1 Y2 `1 X* J# r
正确资料:
/ l+ u. ~/ R, ]; O6 c5 L* O1 ?8 v; q3 f$ b, v* g
2.串是一种特殊的线性表,其特殊性体现在()
6 E6 g; s' @4 z- I1 _( D, ]$ |A.可以顺序存储
+ r4 ]) B5 r) ^# l  rB.数据元素是一个字符
& B  i! y  n3 e% ~5 r3 SC.可以链式存储
/ u3 \% h( ?0 o9 D* W# F% aD.数据元素可以是多个字符
5 ]- Q1 D4 s' t# I9 Z正确资料:, B+ H. \, Y' y) Y
$ ~) f) `" }5 H" R  U2 \
3.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。% w- Y; }1 j% B8 h8 i, U# |
A.1/2
$ c8 e) n+ K1 W4 v! j" JB.1* G$ B3 e" @: |/ Q& w8 D
C.2
& Q" S; y4 `$ M, d* M0 k' z5 g. L& \) V; yD.4/ z8 j2 ?6 ~7 H2 ~! g
正确资料:
# C) G9 o) X, z8 B4 W2 O; Q0 u; Z- _2 p1 i* f4 i3 n9 i( D/ e
4.堆的形状是一棵()
2 s) E+ K9 E9 z; g) Y! J4 tA.二叉排序树
" `' C$ F: t/ O' wB.满二叉树
8 ]. w; R, m6 I7 L+ v, p! ]$ EC.完全二叉树
* i9 i5 o" J  D( DD.平衡二叉树
- V5 E& ?! N  R& T! h4 J. G正确资料:
" @0 ]: Q5 ~2 ~+ \( `3 V9 p7 P& {2 p1 e6 y0 V; J# J! k
5.判定一个队列QU(最多元素为m0)为满队列的条件是()8 v; V  E8 g1 }; B. ]
A.QU->rear - QU->front = = m0  l1 C2 i% z# \+ G
B.QU->rear - QU->front -1= = m0
+ C/ B3 }8 y# N! q' SC.QU->front = = QU->rear: d2 R+ h* g0 `$ j! i: ^7 k% G" _6 c
D.QU->front = = QU->rear+1
/ \0 ~3 s+ C9 c) v3 O* m4 z5 T" x正确资料:: I7 M/ g' r, _6 A$ I) U5 ]
9 X) e5 S% ]: c
6.若已知一个栈的入栈序列是1,2,3,...,n,其输出序列为p1,p2,p3,...,pn,若p1=n,则pi为()
- u; [* u' @6 h  A% b  d2 \6 F& n* XA.i
# t9 W& h+ E$ y. j& rB.n=i- w. W0 ~1 F# F4 s* K9 i
C.n-i+1) V' u% |- d; c. Y# n% H
D.不确定
( D6 J: ~6 E$ B* W* D. Z正确资料:$ w, g3 g1 M& I7 R) O" R: `- S

- b! H4 `! S: z4 w* o+ w/ U7.单链表的存储密度()
4 ?8 Y) I$ N2 c$ k6 v. K$ OA.大于1
  o+ n5 c2 @' [7 ?1 w, \- ?8 YB.等于13 G: ~# Y1 \+ m) Y9 K
C.小于1# \: e7 K- t+ R1 u/ u9 k
D.不能确定
: ^- }8 H4 E4 x; f3 _正确资料:
' n5 ~: F$ ]* x2 R* z9 P
+ `* \* C: z5 h8.已知图的邻接矩阵,根据算法,则从顶点0出发,按广度优先遍历的结点序列是()0 |; b, \7 }% ~4 e5 Q  N9 y
3 ]4 u" q; O4 J& s2 z
{图}9 F6 B+ t8 F$ z& X2 i* N
A.0 2 4 3 1 6 5! D5 l; m% v9 P! [
B.0 1 3 5 6 4 2$ n% x1 q7 ~, [: T- G' e3 Y1 x- H! W
C.0 1 2 3 4 6 5; b8 b+ M3 T5 R8 ~. P; F
D.0 1 2 3 4 5 6
' m6 e3 ^1 N3 R; V6 a/ ~正确资料:
9 F8 M: K; D, e  k9 Q- Z1 t$ e( k/ M8 _) f  t! P
9.链表是一种采用 存储结构存储的线性表
2 k# i  A7 @; ^  }; k3 zA.顺序/ @' t7 N  s# B) \
B.链式
! u5 Y, a* S  mC.星式
" L" H$ q( m' Z3 rD.网状
/ r/ w2 v4 a% C; V正确资料:1 a$ q2 v# J% `+ W$ x6 f
; o: u) a& C, D- W* R* g0 q
10.折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中()比较大小,查找结果是失败。
4 A9 Q9 K/ f' X0 A$ C# `4 [; xA.20,70,30,50
' N7 y  R6 ~3 B3 b- CB.30,88,70,502 a7 C/ H1 E; _6 ]) C$ n  h" [% u
C.20,50
# k! z1 D! }9 L* ]) E; v2 r) yD.30,88,50
/ E% y2 n9 ?3 E$ I正确资料:
' @: w# [& K! w8 |0 Q+ u! y) ~+ y  w0 Z% u* ^% S( n. q" y6 x
11.判定一个栈ST(最多元素为m0)为空的条件是()1 u# \3 G6 O1 T- p' z
A.ST->top<>0  s4 z9 C, s6 t1 b/ |  V7 P
B.ST->top=09 h2 R6 ~8 Y. m
C.ST->top<>m0$ Y8 i4 b7 L+ B; ^4 U
D.ST->top=m0: K6 D2 o  H2 E
正确资料:  b6 H) Q* H6 Y2 F

9 n) c/ e1 o' U( w; T12.下列关键字序列中,()是堆
+ ^/ N; [" N+ s, xA.16,72,31,23,94,53: i9 K4 W( M, E. m
B.94,23,31,72,16,53
0 P" @) X! `4 O$ z, `C.16,53,23,94,31,72
# s7 k9 s  k7 z) S) Q; ED.16,23,53,31,94,72
  F  c, _; G/ K/ h/ T3 n, ~5 p5 N正确资料:# @3 q% U1 E3 P0 W8 ^' R
& E6 }$ V& \3 @  y1 S) `
13.若一组记录的排序码为(46, 79, 56, 38, 40, 84),则利用堆排序的方法建立的初始堆为()
7 \& H  l5 l0 s4 Q. v" uA.79,46,56,38,40,84
9 @% o7 N4 ~- Y. P1 ]1 D4 i0 w3 fB.84,79,56,38,40,46
7 D* a! l- u2 _' O3 W# {7 OC.84,79,56,46,40,38
1 z+ g, J- ]. g$ U3 l4 o8 ]D.84,56,79,40,46,386 u* n; B4 m( C8 `) X: B
正确资料:
; I5 c+ ^( O( y2 E. w; T
. c. u0 O8 I7 u- ^2 w3 a3 s& X14.已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是()
' A+ `9 E4 U* `2 w& R2 e% O9 H! P- m. W# {
{图}# k# y$ z" {+ k2 I2 n
A.0 1 3 2
# ?" L3 c* Q2 n% Y6 @; w# BB.0 2 3 1
4 g9 ]) a1 q  O! z0 ]# W" gC.0 3 2 1; T+ s: s/ Q' e) k5 G$ A, E
D.0 1 2 3
- Y! O0 B& }# o. O6 q正确资料:
3 k% k, C5 b9 A
4 L* E/ G4 Q! [15.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()
, o5 H# l* t7 h3 _; k# rA.110
! e( Q4 E2 |( ^! q5 i; p+ G$ yB.108
8 p5 X, ]( I- u1 q& ^/ H0 iC.100
  V3 M7 ~8 b  \; K- `6 [4 ND.120  \1 ^* u- g  o+ `  l% E2 i9 T" _
正确资料:
6 l* M, y# N/ M6 Y
$ w# `4 a* C% k. T- T8 t* ]3 o16.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为()
/ B* G/ u& s0 ]4 D/ T6 mA.存储结构: T  {  A3 [1 _
B.逻辑结构" n1 W+ B- d. _0 C  G5 P
C.顺序存储结构6 G! V1 l3 P" U, G
D.链式存储结构
1 V- P: b" @) {: l0 Q正确资料:. g* y+ f% U# t& l; `

: i  V* s1 z, o1 V6 y) Q17.链表适用于()查找. @. U( c1 k5 G# I5 S% J: O- A
A.顺序- ^* t1 a0 m( _0 ~
B.二分法9 E% S4 i6 r+ \( O. W9 k" [
C.顺序,也能二分法
# i; }: R0 R* W6 f+ i  TD.随机
5 X2 t) S! z& }/ t( y正确资料:
4 X. T: t0 C1 Y  _7 E; X& ?6 q0 o' `. ?5 Z% O3 Z
18.已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是( )% \+ E9 s; W5 U9 I" [9 I
{图}% Z2 d1 z4 `0 @; Y" T4 ~9 f! }
A.0 2 4 3 1 5 6! e& u' y+ P) P& ^' `, z
B.0 1 3 6 5 4 2
/ o4 ^+ T. m: y: Q6 OC.0 4 2 3 1 6 5! l( A- H9 O3 p1 ?  f
D.0 3 6 1 5 4 2
3 M9 i$ S3 R# d% H9 x2 b- p正确资料:/ e6 D0 g+ S: f( g( H) @6 A# Z
3 H9 f% M% T! z" P
19.用邻接表表示图进行深度优先遍历时,通常是采用()来实现算法的
+ w" a7 V( F  o% l. i$ ^+ Y# ~A.栈' Z9 w$ A: `' B0 L$ ~
B.队列
' t1 l* m/ }0 q0 b% J$ R; h% BC.树0 T1 u4 x( _8 z5 i
D.图0 Q1 G/ {# }6 @* \4 Q, w
正确资料:" V+ n9 ?6 S+ N1 o% f7 W
' F# j* Z" n! \& T" `8 V
20.设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有()个3 z2 o( v5 U4 {# r3 O# ]8 E
A.n-1: r( a6 V" T. g2 E& `
B.n2 h5 X; h- R# e/ a: ?% x+ c; s. }
C.n+1  ^, d/ k/ Y( ]7 q5 {, X0 q0 ]8 u
D.n+20 X$ a8 O8 @6 Q; Y+ [
正确资料:
! a. e  c+ j' Y4 I) _
4 v9 Z# E/ _% d/ x1 O9 ~. ~21.折半搜索与二叉搜索树的时间性能()
8 C0 S: M- `6 ]4 I5 o5 V5 q# eA.相同2 h  j" e6 J6 K* f- h; l/ o
B.完全不同
2 E  I# v2 D- X  {C.有时不相同
. j  b2 P" c7 |D.数量级都是O(log2n)
6 j2 j" E' I( x; L正确资料:3 Y- _; D+ W) W
1 [3 C- P0 h8 a/ s% a' K. Q
22.设a1、a2、a3为3个结点,整数P0,3,4代表地址,则如下的链式存储结构称为()
0 o: x1 C2 q: V$ t# s# i6 |  j
3 s4 |9 _2 l6 j+ i5 Q& L; A{图}
/ i: U2 s* u3 PA.循环链表
. ^9 `7 w' a' c7 p4 g+ u2 o2 EB.单链表0 A- Q/ _  m. |! K! i2 b5 t4 m% b
C.双向循环链表0 x" p% j1 l2 x+ e! G/ w5 [- I( _
D.双向链表
+ Q: v+ j) w6 k正确资料:3 \0 g  D8 U8 S$ q
6 S  V) O6 A( W% G8 ]" n* u/ s6 p4 |
23.用邻接表表示图进行广度优先遍历时,通常是采用()来实现算法的
; V3 h7 f& M; N' u* T$ fA.栈
: u; J. k8 v* RB.队列4 e, s6 ~" h0 R8 ^
C.树" K1 N$ e# x( G: b, e7 O
D.图2 |' n- h$ z: U: v1 y
正确资料:
% p) T9 C* @- M/ B2 }/ i7 F/ b
5 H2 i1 g  r9 A& a7 a" _5 i: m: m24.有8个结点的无向连通图最少有()条边1 x  q/ J- j" S! v
A.5
% G/ q  R( w. U  F# x9 BB.6. u8 Q- E3 C, e" y" c2 {9 Y
C.7( g# t1 J2 S# y( q# |0 a6 \$ f
D.86 i/ q# l% o, z+ Z6 P1 {
正确资料:
) ]+ S3 l( l/ W0 v
9 [4 _. C! t: n4 q25.链接存储的存储结构所占存储空间(). E% U! l: t: R) B+ M( w& M) I
A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
2 ^2 j2 m7 }1 ?5 s2 H0 |, b( vB.只有一部分,存放结点值% [* p+ y6 N% f
C.只有一部分,存储表示结点间关系的指针9 w1 E3 P) w  ~  q" r, r
D.分两部分,一部分存放结点值,另一部分存放结点所占单元数- X: e  e, ^' @, n( ^
正确资料:
' W$ D8 ?. }6 Z, C$ B5 i5 D# D$ {
0 D& H* r2 |. R, Y二、资料来源:谋学网(www.mouxue.com) (共 20 道试题,共 20 分)
) a2 k+ w+ V# ]/ `$ }6 P26.栈和队列是一种非线性数据结构。
( S8 |  @- T1 B, o资料:错误) ^4 M6 {+ F0 U

+ {; f! y+ |+ B. L0 u4 G" c1 F27.一个栈的输入序列是12345,则栈的输出序列不可能是12345。3 \* j& t0 X- E7 Z
资料:错误& J$ r& z/ p) u8 U" B/ V

/ [, e) G1 M7 B28.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。
7 E( Y4 B- _4 V) z$ S8 Q9 i资料:错误6 Q" g" S% ^& F# v7 W" A
" ]" w) A" n$ I7 J9 f
29.顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。7 t, h& ]* S4 G7 f6 z
资料:错误
6 O% \3 g, [9 d+ |: u5 p) E6 U9 u$ v4 i9 |; ?7 {3 |& N1 o% I
30.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。/ B* q$ O1 J# O) S( O
资料:错误
( s+ [5 F# D9 @; v$ G! w  v
! Z+ I9 s7 c* A+ U+ M31.二叉树中每个结点的两棵子树是有序的。
$ N  p# M: l, X1 o+ Z6 O资料:正确) `* C- h$ _, S, {' n

% z- j8 n; K  p* n$ p7 \" {32.栈和队列的存储方式既可是顺序方式,也可是链接方式。
% e! }) e$ I4 o1 F$ w资料:正确+ b9 ?* F! g. y% Z4 e+ q7 V

% A2 e, e2 z" x( [! Z5 n$ _% h33.顺序存储方式只能用于存储线性结构。
6 A9 F/ J4 b' L2 T+ M. G资料:错误7 P1 F7 b9 Q* _) ~" p* H
& j2 v4 z, ^% n. o! z9 ~) H
34.栈和链表是两种不同的数据结构。7 h' `! Z1 P! N
资料:错误$ d1 u- M% l4 Q5 T" ^
0 v! `/ \# o+ Y8 r+ {
35.队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。3 Z' w* F- p3 S8 K$ L/ |
资料:错误
  X5 @, a9 p/ S* _3 Q" q3 A" k* ]* P( J; R
36.链表的物理存储结构具有同链表一样的顺序。
* s) _% M- o# [) L4 Y) }' B资料:错误
/ A7 V0 O9 ?6 x' X2 B/ n% V$ t: q8 ^3 z- j: G5 B2 o5 B0 }
37.对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表
- d# z& x7 J0 i6 h$ h  _# R% z# u5 i资料:正确1 Y5 y0 C! z. ~' f

% `9 M% F, ~7 Y38.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。
9 g5 q$ t; m- @资料:正确
9 e' R+ x, J, j5 d. m
/ r2 k( A7 G0 @% T0 I' \" p1 w39.链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。
9 G. A/ f  B- v+ ]6 P8 T资料:错误/ L( j5 D' Z" Z- D
' U0 W& ]$ m8 ]9 x
40.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
$ m/ C* ?& N- }0 |6 K! H4 s资料:错误
) N% W1 N  \; N7 o( g$ Y
7 \- ?! Z: V1 q* R41.二叉树中每个结点的两棵子树的高度差等于1。: P  p' Z: ?9 D0 y4 r. S7 n9 Z8 P5 l
资料:错误) K  I% H6 S3 R. G

$ s5 ?" O( u3 }$ B* d9 }42.二叉树中每个结点有两棵非空子树或有两棵空子树。: A6 O0 |) [3 D8 O8 u9 @
资料:错误
+ W( F/ y9 b8 W8 [* a- I% G5 b; |5 p
# e0 F4 R7 J0 Y/ Z$ T+ B6 O6 ~43.线性表在物理存储空间中也一定是连续的。( p4 y; x; }  A0 r  }
资料:错误. }  `5 W0 O9 Q. Y, ?5 e

' b' _- d2 {4 Z) D7 U44.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i-1个结点。
% g4 i* t6 a: a4 @0 s8 K2 i+ @资料:错误* Y2 H7 `/ y! a$ O8 x; W& h3 v

7 ~( o9 v1 z( b8 Z7 \6 S% G45.二叉树中所有结点个数是2k-1-1,其中k是树的深度。
, h/ f. n# O9 a* l9 ^; E资料:错误
% G* V- [4 ~$ k1 ~+ |7 N+ b) U" r/ p1 `  s* s7 f$ S2 l' v' o
三、计算题 (共 3 道试题,共 30 分)
0 @2 U3 }$ ^& ?% g46.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
: N3 n) _) s' B: H4 a7 e+ N- p2 c6 @资料:&nbsp;(22,40,45,48,80,78),(40,45,48,80,22,78)<br><br>5 F  ~, K5 o+ ^# U# h+ G
4 w6 l. L# |4 \3 f7 Z" [% Y
47.设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。& Y9 I, G8 _, d) @
资料:链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA。<br><br>- W! q% u- ]/ F7 j

, K1 P+ o' \1 u- M48.设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为8,散列函数H(k)=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
) V/ I- `4 s) J/ N  Y9 |4 F" A资料:<img src="http://file.open.com.cn/ueditorupload/image/2020/03/13/6371972267653698224249520.png" title="结构答.png" alt="结构答.png">
- m9 p- A) L( [8 y5 I8 L: H+ C; x7 J8 p
0 d/ z  R% L" Y1 d  `. b. \; O
% l! V& n; M9 C) `, R3 q* @: R, ^

  |8 s- y, X, U% y( b9 ~$ z- b& R

9 v6 {( _% b  n
! l% H( |+ V, c# k; ~2 L9 o6 G: N/ o
- M+ S2 V- G& I7 {9 q2 \
& h, B  A0 c# m3 ?# {. R) c  `3 M
! g& c* s; P" |9 W& L+ m' W
( y/ Y% B  R) J9 y

本帖子中包含更多资源

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

×
奥鹏作业答案,奥鹏在线作业答案
发表于 2020-9-3 19:55:04 | 显示全部楼层
奥鹏作业答案,奥鹏在线作业答案
回复

使用道具 举报

发表于 2020-9-3 20:19:23 | 显示全部楼层
奥鹏作业答案,奥鹏在线作业答案
回复

使用道具 举报

发表于 2020-9-3 20:41:37 | 显示全部楼层
奥鹏作业答案,奥鹏在线作业答案
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

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

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

GMT+8, 2024-3-29 00:20 , Processed in 0.105166 second(s), 17 queries .

Powered by Discuz! X3.5

Copyright © 2001-2023 Tencent Cloud.

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