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

admin

22秋学期（高起本1709-1803、全层次1809-2103）《数据结构》在线作业-00003
6 Y. k  q0 R& R9 Z( f% r试卷总分:100  得分:100
4 |, j4 ^# y) s& W& m" @一、单选题 (共 30 道试题,共 60 分)
1.对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
. ]( n/ \% X! o6 B8 lA.从小到大排列好的
! E! u( x. Q. p: [3 l' }5 n5 UB.从大到小排列好的
C.元素无序
D.元素基本有序
资料:

2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
资料:
& S! }( y" A9 V9 q9 @" [
9 D' W$ O* L) H) Q$ \3.链表适用于()查找
A.顺序
B.二分法
7 O( ?" ?; t& ?- K' y6 SC.顺序，也能二分法
% k4 F1 F8 W) _7 \( W  LD.随机
资料:
  d7 S( ?3 y- P( g+ V2 M1 I
3 p4 x9 t& p- f1 u4.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A.栈
$ T  y/ A, U- r5 F1 eB.队列
C.树
$ K; X" i1 x" n9 m. k; F* bD.图
资料:

5.有8个结点的无向图最多有（）条边
. z( J* K  B) l% {; pA.14
3 p/ _* b1 E5 l1 h+ {& kB.28
% r8 [% T; l: ^. V1 UC.56
D.112
资料:
, ^* q8 V7 F* f5 O
! J1 L( T  i% `, |7 g8 M0 {) ]6.下列关键字序列中，()是堆
# D" B# d# m# O9 H7 G. bA.16,72,31,23,94,53
B.94,23,31,72,16,53
C.16,53,23,94，31,72
/ R% C5 l/ A6 F  f) p3 o  @D.16,23,53,31,94,72
资料:

7.判定一个栈ST（最多元素为m0）为空的条件是（）
A.ST->top<>0
+ G7 \! Z# G4 D4 H* V3 q( D  g1 ^0 xB.ST->top=0
0 F" f, h! \3 fC.ST->top<>m0
! {8 ?2 `5 {9 @D.ST->top=m0
  Z- M3 c" k! j! Q资料:

5 h0 N. _' T7 N" |; ^8.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2
6 F. y+ p' g7 A2 IB.1
; R5 w3 ^6 Y% D; CC.2
; j$ m/ a" N  r# O5 e+ K5 uD.4
资料:
$ A. g& N. x2 M2 L* W: B
) _$ o0 S* o& C9.快速排序在下列哪种情况下最易发挥其长处()
A.被排序的数据中含有多个相同排序码
; L6 M7 d( i# [+ eB.被排序的数据已基本有序
1 X2 ]: Z4 C3 Y3 S' D, j- r8 vC.被排序的数据完全无序
: f6 h' z( n& l4 I; M& B; SD.被排序的数据中的最大值和最小值相差悬殊
5 k  c. @& [9 I$ t资料:

10.栈中元素的进出原则是（）
A.先进先出
B.后进先出
C.栈空则进
! w* ^; L, h2 K0 C( H+ \. o" A' VD.栈满则出
资料:
( D' s7 N, S' l6 l
11.有8个结点的有向完全图有（）条边
# A! H3 Q5 }' f1 @1 TA.14
B.28
C.56
) z, m; {3 q4 e4 j7 P! {+ U+ ]D.112
$ o  b2 C, A. o8 G; o( R资料:
0 d& S' z% k5 P
12.堆是一种()排序。
. E1 i& }/ E$ W; P8 D/ o9 ]A.插入
0 g  C  U- E9 t+ a2 F7 q- E+ s! mB.选择
C.交换
: g/ K# ^( l5 @& ~2 GD.归并
% m8 v/ X7 n0 K. u' s! ~  B资料:
. c& }' k( P# }6 v; E7 P6 C" d
13.堆的形状是一棵()
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
资料:
7 |4 x9 _4 v7 }+ b3 M( b) l% Q
14.引入二叉线索树的目的是（ ）
A.加快查找结点的前驱或后继的速度
, H, U6 G  Y9 X9 FB.为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
* S/ E4 Q' P* p. F资料:

. [9 }. V" ~+ D8 g0 p15.串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储
$ j& R- s# L6 m  YB.数据元素是一个字符
) A- p/ E7 _2 U; H; w7 j; ?3 KC.可以链式存储
D.数据元素可以是多个字符
资料:

16.设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）

{图}
A.循环链表
B.单链表
( [2 U/ e9 Z  {7 z* SC.双向循环链表
% N# B( K& a1 |D.双向链表
9 E" c& W2 ^1 O5 l* T$ Y6 O2 Q资料:
4 d" t! r: ]* N+ H3 A/ L' j
; F( U  ^/ R9 O17.广度优先遍历类似于二叉树的()
A.先序遍历
' v, `, n+ u$ q- K* P- K( TB.中序遍历
+ Y1 Q8 y' P* h$ hC.后序遍历
3 e) j6 R0 A  y; r7 H2 M1 SD.层次遍历
资料:
( Q  [4 J& \9 }8 Q) E& N) I
18.不含任何结点的空树（）
A.是一棵树
" e4 g4 v& J2 J9 H( o7 ~' jB.是一棵二叉树
C.是一棵树也是一棵二叉树
D.既不是树也不是二叉树
. W+ F! \8 n4 J3 L2 H$ Y+ a资料:
  t  ]  G: M7 S
19.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
) ^5 s; \9 C  ~* D, sA.n-1
B.n
C.n+1
) |0 r1 [  H  ?D.n+2
  N- _! H  |0 S; j资料:

7 U0 ?2 Q4 |% q  B20.单链表的存储密度（）
) d6 f$ ], F) P. D, N% S+ B, \A.大于1
B.等于1
0 f3 M( |& u, F1 m7 [C.小于1
D.不能确定
: I1 d4 j0 C- v' \( c资料:
1 N; a" {% z% z1 p% K  B: }
% {" G. g4 [4 y' [, o: s' S21.折半搜索与二叉搜索树的时间性能()
& {& U1 d( F4 e+ GA.相同
B.完全不同
C.有时不相同
D.数量级都是O（log2n）
资料:
; M' _. ^3 J3 m7 R/ j3 N+ y4 A
; c0 [  T1 u' @22.对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
( l: v; }/ [! s- sA.O(n)
B.O(n2)
4 `* q" h" Z  k9 z6 N( |2 j- FC.O(nlog2n)
D.O(n3)
资料:

. I7 J8 L3 Q, c$ s, L. P23.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
2 H$ d8 y- E" U/ tA.79,46,56,38,40,84
) u9 N3 y% t4 x9 _2 L) O7 C4 Y. @B.84,79,56,38,40,46
C.84,79,56,46,40,38
D.84,56,79,40,46,38
资料:

% h8 R4 L" {# p/ o9 ~24.链表是一种采用 存储结构存储的线性表
" T6 q* X+ q: NA.顺序
B.链式
  T/ {& U+ I# d2 PC.星式
; K# p+ L: o- u& d& {# S3 rD.网状
资料:
# [- A; j% b! e& x9 m
7 P) F& t; @% H2 d$ C25.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.在第i个结点后插入一个新结点（1≤i≤n）
C.删除第i个结点（1≤i≤n）
D.将n个结点从小到大排序
. e- t0 d: W5 s, z0 ^4 X资料:

26.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A.110
+ Y/ M# g/ Y5 j+ H( a/ gB.108
C.100
( I: R) v1 }- r+ j1 I& ]D.120
  e5 K: p9 p0 a3 {5 q资料:
& g4 t# x; j$ |$ G
4 L! n- ]& [( N! g% i% d' 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
B.BCDEFG
C.BCPQRST
3 W, e# ~; W1 B; `# ]: BD.BCDEFEF
( ^6 Q5 H- [6 m( }/ Q; I5 P) w% h资料:
/ O; w5 y9 m1 Q% H: r6 A* [: z
28.对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
- m2 r9 S! h9 zA.3
$ w3 x( r, t5 w  ]5 G2 ~B.4
C.5
D.6
资料:

# I( X- s7 g9 n$ ^4 v2 G29.具有n(n>0)个结点的完全二叉树的深度为（  ）
A.{图}
B.{图}
C.{图}
D.{图}
. {  K! D, `5 R, @# S资料:
+ ?3 `9 `4 A/ {+ O, x6 s5 g. L7 i
) R3 U0 @4 Y8 `. P9 X+ W& x% |) y30.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
' I' V) {+ y/ ^( ?* {  M4 P
{图}
A.0 3 2 1
! S1 R7 z) U- sB.0 1 2 3
/ j" Z) y, i, o8 }0 Q9 a& ^C.0 1 3 2
  V2 e- R- {9 p% jD.0 3 1 2
资料:
1 X8 A# E, t# @4 n3 G
二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
2 o2 A9 N6 |" d: d( w31.链表的每个结点中都恰好包含一个指针。
6 F" m  B  u( b$ n资料:错误

32.二叉树中每个结点的两棵子树的高度差等于1。
资料:错误

33.链表的物理存储结构具有同链表一样的顺序。
0 s' }! M. V" Y  R资料:错误

34.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。
8 V3 N7 x- S* b$ g" `! x资料:正确

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

36.在表结构中最常用的是线性表，栈和队列不太常用。
资料:错误
  J' Y% X- b# k4 L2 M$ o
- a& |* w/ i9 L) v2 @5 A37.二叉树中每个结点的两棵子树是有序的。
资料:正确

38.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
7 S- Q- ^2 P! W+ b, V2 W资料:正确

! M' ?9 K7 v' r, L! ^, \39.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
9 \# n! s: Y9 V6 B$ D" I资料:错误
9 j4 W' o; A6 ]
( S7 G2 z  a" n) ?3 G' `40.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
资料:错误

41.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
( p8 P7 A- y0 S; y. B* N  ^  F资料:错误
& {! `; r+ p" p: U' ]. k2 Y
42.线性表的逻辑顺序与存储顺序总是一致的。
资料:错误
% G" u, F) L- w5 Y7 i& |( R/ D' C6 P
2 Y6 `3 u0 P4 l; D' T43.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
资料:正确
! \+ C# g1 D" j  j! D
44.栈和链表是两种不同的数据结构。
& R4 G6 m7 Y2 I% N资料:错误
% ]! {% J: m3 {/ ^5 k
45.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
5 f0 c% Q. V6 C资料:错误

46.栈和队列的存储方式既可是顺序方式，也可是链接方式。
4 }. b% J& Z7 c& J4 U) R资料:正确
) ^- F5 }: m" |
47.栈和队列是一种非线性数据结构。
/ Q" d6 g8 e* n% {资料:错误
$ I3 u9 |. b+ {& l# I8 G
48.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
- O8 T6 Z0 I6 T7 x- s; V7 l0 M资料:错误

49.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
0 E2 u* A% J$ H+ j资料:错误
0 Y1 N7 H! u" e8 O! u
3 e6 z: A5 X6 t50.顺序存储方式只能用于存储线性结构。
7 J/ q: S" P3 L& O! X; V资料:错误
, V' P  A/ F$ _2 @1 G5 l' h2 b

* b5 M3 z, V4 r8 }, A+ f
$ @9 h3 Q$ t$ z% M2 j" T9 N


4 b& N3 z+ b! |- k4 r; K

+ M  j3 ~9 W! M( k
' u  W, {  n) Z3 R6 [: o

0633代表

谋学网越办越好，加油！

心心向希

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

dadajj1

谋学网老师确实厉害！