22秋学期（高起本1709-1803、全层次1809-2103）《数据结构》在线作业答卷

admin

22秋学期（高起本1709-1803、全层次1809-2103）《数据结构》在线作业-00003
' {6 P3 ^" G/ ^! w, h; p试卷总分:100  得分:100
一、单选题 (共 30 道试题,共 60 分)
1.对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
4 C' w* U  Z; x+ V/ j! C% a: x% IA.从小到大排列好的
B.从大到小排列好的
5 [+ i0 z% O+ j7 U* RC.元素无序
+ q- ]& ]$ N& J" V( N; ED.元素基本有序
资料:
5 `+ m6 q: ?* {; q3 `
$ ]% W, s- b- w. f7 P+ R+ \2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
) v. C6 R/ i+ F, yA.必须是连续的
. ~0 }/ i. D4 g$ LB.部分地址必须是连续的
C.一定是不连续的
' H; r. u5 Z6 g- I, `: CD.连续或不连续都可以
资料:

; ?# M4 P4 F4 k' ?, ^! G3.链表适用于()查找
A.顺序
B.二分法
C.顺序，也能二分法
D.随机
资料:
, ]2 F+ x$ @# O
% a/ c/ A- T$ [, z5 ]; Y. K# D4.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
5 g$ ^/ J, z7 a% ?A.栈
B.队列
+ U5 N# R0 }; C  G- i# j/ H0 IC.树
D.图
5 h, G) A" V' i* V5 b资料:
8 M: S3 U! E- z
& W0 Y8 [+ r  K8 k8 q- b) r$ Z+ i* I5.有8个结点的无向图最多有（）条边
A.14
* F& |/ g9 M6 M; u" R& r  G' o4 AB.28
C.56
5 n8 U( t+ o' ?! s, bD.112
% g0 I- K* p) r2 M资料:
, m. p' G$ q+ F( Y! g- o7 N
! H- w8 i  \7 u3 A; }* Z6.下列关键字序列中，()是堆
. |2 \' g1 h5 `6 d- S3 X% sA.16,72,31,23,94,53
7 {# ~5 A, Z( P3 ?* D0 s& V% zB.94,23,31,72,16,53
C.16,53,23,94，31,72
- W4 H# o6 B! K2 `D.16,23,53,31,94,72
( L: V" D. \- p$ t  I0 c资料:
( t# U0 a& H  C' H" {. B
# l0 g5 q0 p+ G$ s$ u7.判定一个栈ST（最多元素为m0）为空的条件是（）
A.ST->top<>0
B.ST->top=0
6 I2 k5 b+ ~( ?6 T) C9 Y# D% ~$ LC.ST->top<>m0
, ?1 H- T' N/ N3 t, xD.ST->top=m0
. A. Y4 G+ n% T7 `8 e! h/ z5 |, {资料:
7 Q# h! G4 j( `, N  e: b$ U6 }- b
" }- R# @& L- |8 m# k7 f) a8.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2
4 B0 ~) ^" j4 d9 j; }' RB.1
# G' |# Q* z  ]: qC.2
D.4
资料:

# [, \* T# D: {+ @, B) [9.快速排序在下列哪种情况下最易发挥其长处()
A.被排序的数据中含有多个相同排序码
# l6 U0 u0 h. f( nB.被排序的数据已基本有序
C.被排序的数据完全无序
D.被排序的数据中的最大值和最小值相差悬殊
2 S. i" w2 d5 o' _# L  @资料:
; J' z' L7 j1 D+ P  L2 D# c0 H
10.栈中元素的进出原则是（）
A.先进先出
9 ?' w' ?$ i* \* D  Q7 GB.后进先出
C.栈空则进
9 ~4 d+ u: ~5 O2 ?D.栈满则出
+ {8 r3 w  P/ j; Z1 T资料:

11.有8个结点的有向完全图有（）条边
A.14
B.28
C.56
. N& o, V7 Y$ _5 lD.112
3 r; j" \4 k1 g% I7 X资料:
/ `9 g: @; b7 h# t( m
12.堆是一种()排序。
" X! C9 j' F3 s. e5 vA.插入
) q* {+ U2 h# C* mB.选择
C.交换
+ M3 ~& F) ^1 p' m+ ~" ]5 }5 ^D.归并
资料:
% L% j7 L- N) z- Z" X/ k- P
13.堆的形状是一棵()
3 J! l/ I* G. ?& }3 {- Z2 wA.二叉排序树
7 s/ U$ r2 i; O% X8 a# ^, AB.满二叉树
) {5 d5 {3 f# ~. t9 DC.完全二叉树
D.平衡二叉树
4 Z% i; F, @3 R& g1 V资料:

: `9 O7 p/ ?. Y6 U14.引入二叉线索树的目的是（ ）
2 m( c/ h$ X+ ^; @/ m6 L! V* F5 ]A.加快查找结点的前驱或后继的速度
5 A9 `" K4 z/ x8 |( B9 m8 I- qB.为了能在二叉树中方便的进行插入与删除
* @8 V3 e. T8 m. a% {) d% fC.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
资料:
# }+ M4 {2 r  K. h$ i- t/ }( a
15.串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储
! \2 ]/ J/ k/ B, b7 Q; L8 jB.数据元素是一个字符
C.可以链式存储
D.数据元素可以是多个字符
4 b; a9 E' V# E4 o* ?. `: Q9 X, S* b资料:
0 X, C, Y6 O5 V3 S: ^  o; Z; L
8 h4 B: K' a2 J) }* U) q0 Q16.设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
! U4 x$ ]$ A' {% O4 u
9 I! o# r" A8 f- A4 @$ u' i2 E) d* p{图}
A.循环链表
B.单链表
C.双向循环链表
! F5 q7 V9 v" F2 _D.双向链表
资料:
& D& e7 V  V4 C8 R, v) z2 h
17.广度优先遍历类似于二叉树的()
A.先序遍历
B.中序遍历
C.后序遍历
/ i) _7 R( q; B1 aD.层次遍历
, D7 p+ y8 A+ U1 F4 C资料:

18.不含任何结点的空树（）
' p% G* ]- N# QA.是一棵树
, V0 }8 N. H* w& C$ U$ T8 I  lB.是一棵二叉树
C.是一棵树也是一棵二叉树
& e- I! D6 S6 E$ {! xD.既不是树也不是二叉树
+ P1 P( O5 W" u: y6 n7 B/ ]资料:
: `1 D6 F4 R4 R* y" O, h
) S8 V: c# ~/ z# q19.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
5 r4 Q: U, w; X* j* O- n5 P5 KA.n-1
8 g. J3 l. e8 A, S) c8 D, j( QB.n
7 E2 K: M- P. o) P) z/ k7 fC.n+1
D.n+2
资料:

# z8 x% N* O# a: w/ x3 b7 {2 C20.单链表的存储密度（）
A.大于1
' Q% P9 j5 J* ~' O$ r( S- c. KB.等于1
C.小于1
! {" U2 X6 t/ D( _; H& v$ dD.不能确定
资料:
8 j% X6 T) e& n. Q- c- }
' G( @- l% @5 b21.折半搜索与二叉搜索树的时间性能()
, w* r1 `9 A, }( u2 S! Y' R& \: |A.相同
3 {' ~* _$ ]6 KB.完全不同
C.有时不相同
D.数量级都是O（log2n）
+ ?0 `0 _2 y1 |5 X4 q5 R资料:

9 r) T  E9 U+ s0 G3 W22.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
A.O(n)
1 E: f1 r8 X1 Y6 \4 z, AB.O(n2)
C.O(nlog2n)
D.O(n3)
* o2 u4 Q; b" }- O7 n8 O- c资料:
  A3 K# J  f% n! j- |* C$ _, P
; b9 O! X6 @% a" h9 t23.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
" E+ T: F5 V0 n2 Z% pA.79,46,56,38,40,84
B.84,79,56,38,40,46
. F9 _; m6 a! P) Z( N! p) d! fC.84,79,56,46,40,38
3 |6 p& O9 z: n+ }% _  vD.84,56,79,40,46,38
& N' u$ d& m/ {& N& M- V资料:
2 m$ n5 s; q$ G7 }/ L+ B  [
24.链表是一种采用 存储结构存储的线性表
8 h) Z6 _0 p; ?( H8 HA.顺序
, A. O3 c% n4 t$ t  R+ P  z5 \B.链式
C.星式
D.网状
资料:
# a* Y  j9 Z& s, k
25.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.在第i个结点后插入一个新结点（1≤i≤n）
C.删除第i个结点（1≤i≤n）
+ [% D; R0 }; l9 l# \# p5 N$ ^D.将n个结点从小到大排序
资料:

  ]; [/ y; Q# D26.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A.110
B.108
C.100
4 l( Y5 O8 Q: ^1 W/ B6 wD.120
资料:
9 l1 T% \: }' ~* J6 l$ _4 g
. b4 ~# ]$ W  p: I4 W9 H* q27.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（）
A.BCDEF
" X4 K1 l8 t+ X0 `B.BCDEFG
C.BCPQRST
D.BCDEFEF
资料:

5 {: ?, y: A% h6 k1 K1 u28.对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
A.3
B.4
1 y! s) Y. c. v9 SC.5
D.6
资料:
5 P6 B  t- t6 E% n
29.具有n(n>0)个结点的完全二叉树的深度为（  ）
/ h( Q& _; h) ]7 GA.{图}
B.{图}
C.{图}
D.{图}
资料:
- P8 {) @9 J8 ^: |  G8 x
30.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
0 l% b, k8 E" N( ^6 q0 y
{图}
A.0 3 2 1
B.0 1 2 3
5 D  o0 r* K+ g8 YC.0 1 3 2
" f' M) `# Z# c. C" CD.0 3 1 2
5 p! \# s1 j5 g! b: o% b4 ?资料:
& j* Z5 M5 c8 x* y& t5 Y7 n
2 ?* a/ p: o2 F1 d5 W, X1 r二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
31.链表的每个结点中都恰好包含一个指针。
4 B% K) q- T% D  Q, t4 n7 T# S6 k资料:错误
) u" F3 C: O2 D* {; a
32.二叉树中每个结点的两棵子树的高度差等于1。
, B. Y: q; w- V, r2 `2 j$ t资料:错误
- ]  S- v$ h& U% Y& W& X0 k
33.链表的物理存储结构具有同链表一样的顺序。
资料:错误
9 ?$ Y% R4 T; G8 ^0 Y- c1 K
34.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。
$ G! n' V- ^% w资料:正确

35.具有12个结点的完全二叉树有5个度为2的结点。
资料:正确

36.在表结构中最常用的是线性表，栈和队列不太常用。
资料:错误

37.二叉树中每个结点的两棵子树是有序的。
资料:正确
8 V0 p! v8 y8 X1 d; D
0 {; i. x: G. a$ A) P5 J3 ^38.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
资料:正确
0 S' S: o8 I. ^; x* a/ I
0 {4 a3 V1 n, R) Z) Y) c39.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
资料:错误
1 |1 n  z% F7 y; L, J
40.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
7 n6 b! e" d' f( t资料:错误

! U! ]* H1 o- b# n( n41.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
资料:错误

42.线性表的逻辑顺序与存储顺序总是一致的。
资料:错误
! r8 \) e9 e. k! ]0 v& n
43.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
6 _2 Y$ r" @& |6 D! e资料:正确

0 g5 Q( {( [% a5 S, \. z44.栈和链表是两种不同的数据结构。
资料:错误
0 i* c# n( X4 y4 v
45.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
. d! R9 \  l) C4 w7 `资料:错误
% N% P7 Z% N- o6 @, _
46.栈和队列的存储方式既可是顺序方式，也可是链接方式。
2 `$ c" |1 X  W7 V/ J资料:正确

' W; y4 w% e6 O/ O, }* V1 m. U! E1 I47.栈和队列是一种非线性数据结构。
资料:错误

48.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
资料:错误
* n/ ]+ ^) V; |, I) g" r
49.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
资料:错误

5 j: p& P/ _6 o4 F# R# d9 n7 C7 x50.顺序存储方式只能用于存储线性结构。
资料:错误

! m$ t/ c5 I: D- u$ {" R/ o; |



2 c; C5 K; Z; \2 [
$ s, w0 W. y' {, d0 V
# t0 S! l4 H- X  W' {8 E- M
( z& K6 G5 ^* G  b

+ u  z8 a3 l2 S- Z
3 ?) W# L' T, N( n, l8 Y0 P. ]

0633代表

谋学网越办越好，加油！

心心向希

一直都在用谋学网，不错！

dadajj1

谋学网老师确实厉害！