[南开大学]《数据结构》20春期末考核（参考资料）

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]《数据结构》20春期末考核
. p- I8 F7 A, V; x7 l/ }1 M$ ~; D  I试卷总分:100    得分:100
第1题,快速排序在下列哪种情况下最易发挥其长处()
A、被排序的数据中含有多个相同排序码
6 o3 S5 {: Q* I. m; _/ PB、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
正确资料:
/ `/ A/ K$ S4 n& x9 S4 C

第2题,串是一种特殊的线性表，其特殊性体现在（）
A、可以顺序存储
B、数据元素是一个字符
8 X$ C" ]: c) t6 R0 T+ _- X3 qC、可以链式存储
D、数据元素可以是多个字符
8 c2 W  Q( B( E0 ?正确资料:

, B& V8 |/ f# l) M( ^! v6 ?! }/ v5 H
1 T0 B9 p* x7 O% p$ C% F第3题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
5 t7 g5 k( M2 K6 |( n& |3 MA、1/2
) W. Z5 E; ~2 C: @1 O( N5 OB、1
C、2
D、4
正确资料:


第4题,堆的形状是一棵()
A、二叉排序树
B、满二叉树
+ V& P6 F7 g. W# b5 J! bC、完全二叉树
0 Y" H0 m. ?  p4 P0 U1 p4 C9 qD、平衡二叉树
正确资料:


9 x# I$ |3 R! A6 d- ^资料来源：谋学网（www.mouxue.com）,判定一个队列QU（最多元素为m0）为满队列的条件是（）
) s! Q/ w. _* Z9 I; KA、QU-rear － QU-front = = m0
, T/ k7 R9 U) R/ D4 ]6 `B、QU-rear － QU-front －1= = m0
C、QU-front = = QU-rear
D、QU-front = = QU-rear+1
正确资料:

. F: t4 W$ M; l) Q
! c9 H/ S& T, [4 J$ \5 `6 j3 s第6题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
- Y% g/ }: y1 t( b8 @A、i
3 W& Q/ Q0 V7 rB、n=i
- y/ G) A1 N6 A  k- K) qC、n-i+1
D、不确定
正确资料:

/ u1 ~5 Y1 }: v) k( b& x' l! z( C
  v3 Z: ~' O3 O3 U第7题,单链表的存储密度（）
- u4 p+ q' {6 y% S% qA、大于1
B、等于1
( d% F# E  ?3 S/ h5 _9 H) MC、小于1
7 V' ~1 _, f- q5 L; G$ hD、不能确定
正确资料:
( z- |; v6 L+ a+ O- n# u
' H' X; c5 a5 \' z
: M& `' E* o2 S- @" V, }( @& Y第8题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 1 6 5
B、0 1 3 5 6 4 2
7 U1 [7 s9 m5 k# z1 d* m/ aC、0 1 2 3 4 6 5
% L9 }# e3 R: O( h' |D、0 1 2 3 4 5 6
6 i& V' c' v) J. d  ]8 {, a正确资料:

) h2 O! [6 W$ u0 ]5 v
第9题,链表是一种采用        存储结构存储的线性表
( o1 `, R' @8 F' c- v# |/ @/ ?A、顺序
0 x% Z( j1 I. b7 J  n7 c: o4 GB、链式
+ b0 O1 ^5 {( o8 |C、星式
D、网状
7 n3 [( s1 k2 x+ u正确资料:
( I2 i% M. a, J( r

. c7 P- g- A8 V) C资料来源：谋学网（www.mouxue.com）,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
7 q: ^. j. S+ jA、20，70，30，50
B、30，88，70，50
5 ?  ]/ g+ X- x. RC、20，50
D、30，88，50
正确资料:

5 a) H6 D, m! U5 h" [
5 v8 ]6 e( u6 \第11题,判定一个栈ST（最多元素为m0）为空的条件是（）
A、ST-top0
! B0 S  q! K6 [1 U) L6 HB、ST-top=0
, Z& {2 T3 q8 e3 A, q! cC、ST-topm0
- t! i) d) B# C5 z+ uD、ST-top=m0
6 Q/ B& M* d* l* l/ T: r- z正确资料:
" A9 B# C6 D4 ?

( L7 G( M1 t  A  R( U5 `资料来源：谋学网（www.mouxue.com）,下列关键字序列中，()是堆
A、16,72,31,23,94,53
1 N6 X" Z  l7 z2 h, LB、94,23,31,72,16,53
C、16,53,23,94，31,72
" w3 R' F% W! x1 o, GD、16,23,53,31,94,72
7 L1 i$ S6 K9 U! Z正确资料:

+ ~( |2 f% J. [' F
第13题,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
& n, x$ X! |: b' Q: R7 `A、79,46,56,38,40,84
, R3 o; b* @, ]& }& ^+ Q" uB、84,79,56,38,40,46
C、84,79,56,46,40,38
/ [, _8 @. `' u) @" F- e; nD、84,56,79,40,46,38
正确资料:


5 v1 Q- c8 L) {& i第14题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
6 V: r8 n' t* a: u2 O) t: jA、0 1 3 2
$ a% l4 ^  S3 ^" @B、0 2 3 1
6 U8 S. f5 i# B6 XC、0 3 2 1
D、0 1 2 3
正确资料:


6 ~6 D' T" F! W. d) E' S资料来源：谋学网（www.mouxue.com）,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
/ U+ ~" {' _6 k7 h1 N" }( lA、110
B、108
C、100
7 S0 H& ~* y" I2 X: O, ]D、120
6 g* H6 @# s( J% `) T正确资料:
  ~5 M# ^4 E. n' H
/ S8 D5 O. p# _) O1 l$ |
) l! _- w& y' |- X. Z7 S$ x第16题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
A、存储结构
B、逻辑结构
C、顺序存储结构
D、链式存储结构
  w( M5 X% Z1 V0 a, t# {2 ^正确资料:

$ Y4 c7 z2 o4 B' h. c6 s+ h
第17题,链表适用于()查找
A、顺序
+ [4 o9 b  n1 n9 }B、二分法
C、顺序，也能二分法
; ]. Q% a4 x3 Z6 v: x; e; kD、随机
( z1 I4 W) z( e8 @* [0 x6 B$ S$ R" x正确资料:

4 x0 T( m) W, V6 Z; j
( J1 w5 F8 P" p) L) ^* O  M, ?第18题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
A、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
& m7 w: W8 R6 T0 T, d  |C、0 4 2 3 1 6 5
! z, l1 t* G4 G. T  k3 lD、0 3 6 1 5 4 2
$ h4 F7 f  j- J! e' j9 c3 I2 s正确资料:

  }+ i* t( y4 l6 l
: z+ i$ T$ s* P0 P) U第19题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A、栈
# k6 j) _% H  V9 NB、队列
( l7 z5 P) O$ r% |7 ZC、树
D、图
: T- h+ N4 R, l0 g+ D正确资料:


) d  ~4 A2 W+ B资料来源：谋学网（www.mouxue.com）,设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A、n-1
B、n
, K2 ?! Z7 |7 |2 hC、n+1
% C& A) M, R1 d% j7 ]4 PD、n+2
正确资料:

$ m$ z8 J# Z4 y2 K3 s/ ^+ Q* |4 k" o6 a
第21题,折半搜索与二叉搜索树的时间性能()
4 L9 c. X% E7 L4 T( OA、相同
0 ?" W3 u; n! Z  u, [2 eB、完全不同
" v( z$ {4 ]6 W8 c$ c- W* BC、有时不相同
/ X# B7 x2 v( m* L, d% nD、数量级都是O（log2n）
正确资料:
6 l; D* H, Y$ h% C  f6 `6 r

第22题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
! e# j  F& k+ h- U; Q3 }' W" SA、循环链表
B、单链表
C、双向循环链表
1 s; c8 p% |5 e# s! o5 A( ID、双向链表
! c; @) c  E2 H; d正确资料:

* T2 ~; O5 _* b% _  W; k
第23题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
# j% K* b: g3 C) p5 b& n9 C' g# eB、队列
C、树
D、图
正确资料:

/ p2 M7 \( s- M, s
6 X8 z7 \" S- e) O$ D2 N# s" L第24题,有8个结点的无向连通图最少有（）条边
7 l, ?2 L0 R+ [( Z4 oA、5
, ~2 b& ~% a, z3 X' \B、6
! _% y5 Z( {/ d* Q7 R  ?0 bC、7
D、8
正确资料:
5 T3 I4 Y) `/ P% P$ y! M
1 ~" }1 D- F& u6 G7 W0 F
资料来源：谋学网（www.mouxue.com）,链接存储的存储结构所占存储空间（）
7 }7 a( C4 c. Q5 XA、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针
D、分两部分，一部分存放结点值，另一部分存放结点所占单元数
; p6 _+ A( g* d0 O% f+ M正确资料:

4 B  P' }& a% r
第26题,栈和队列是一种非线性数据结构。
A、错误
B、正确
9 S5 [, z6 R: T8 t. U" {正确资料:

2 ]( u" n: g2 Z' m+ P* v6 i
* J3 P6 ^% M( ~* H& O8 w第27题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
% l- g. d( W2 ~5 d& m" e3 I/ m* gA、错误
B、正确
正确资料:
2 h; h  E; a6 @

7 Q! V/ z1 |: C: v# q( X1 r5 N第28题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
9 D5 z# y# W0 x3 `: ~A、错误
8 e0 V- H/ \! z! g  wB、正确
正确资料:
2 U! b- `* p  y: ?) e1 H4 \! J

第29题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
3 h  J: @8 W4 V2 R9 |. iA、错误
B、正确
# h* r& g' T  m正确资料:
3 ~; ?( O5 N  e; d1 I7 b7 u

资料来源：谋学网（www.mouxue.com）,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
9 s) Z4 E4 j6 b8 u8 d# q& O1 k2 VB、正确
; D& y" P  l5 h4 C  Q9 h正确资料:
' |/ P; Q( n0 _

第31题,二叉树中每个结点的两棵子树是有序的。
A、错误
B、正确
6 ~' P1 v5 d7 b* I- q0 z正确资料:


2 w9 ?  F/ n0 l. Z5 Y$ e/ w第32题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
B、正确
4 L8 d" T& ]9 E+ Y5 U1 Z. |1 [5 P正确资料:
4 T3 B2 ]2 D. |, ^1 v

6 V  P2 P. B/ V# Q* U; l第33题,顺序存储方式只能用于存储线性结构。
1 v) N) H. @( f# r8 }1 tA、错误
3 u" a2 m3 B( X9 c$ w" ^B、正确
1 W6 n5 q7 ?0 o/ ?# o4 G2 r正确资料:

, D6 t" q4 p6 Z, p0 _
' N: O! |2 O8 Q, `  L0 ~& h第34题,栈和链表是两种不同的数据结构。
A、错误
" q# x/ |  z9 m$ _5 BB、正确
4 I5 w9 Q& b+ _, d9 E5 U正确资料:
5 D4 \8 U1 u- t8 A' `% Z
& I1 V" ?7 R" n) ^( p
. U/ j5 @. ]% ?, M6 f7 p& c- a第35题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
) K; g3 V. Z/ }  b: j4 vA、错误
& |7 D5 X& o- p9 H( a. iB、正确
- }5 x+ I) ?9 h正确资料:
6 D4 X' U- F; b# A! o

1 f5 F9 Q- \* ?1 T3 J. O6 L4 G第36题,链表的物理存储结构具有同链表一样的顺序。
$ i. M! f3 r! i7 d8 u* j( rA、错误
B、正确
3 a; b4 o. \8 P9 ?5 _, S( Y正确资料:
5 Z! L: }9 {, s
9 c+ R- k7 S6 f% D: f( f
; w- b( |2 [" E) s0 I第37题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
( r) K( A! r+ A* [. b- pA、错误
B、正确
正确资料:

- ^0 ~/ I! I, K  k  E' r9 W
第38题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
A、错误
B、正确
* }+ z  U4 r. V0 V' q2 b正确资料:
! ^5 L8 }# ?3 y5 ?
9 Z, p9 c! A2 I9 t
第39题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
A、错误
B、正确
正确资料:

- S0 L' V# F  ?: H
" x% ~0 t' N# L& x第40题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
$ ~7 t. r) a5 uB、正确
3 {7 k; }1 v& z正确资料:
, \5 [% P- P3 V

第41题,二叉树中每个结点的两棵子树的高度差等于1。
8 w' i0 |9 E% k6 ?. tA、错误
B、正确
正确资料:

0 g) V7 L* D6 A
第42题,二叉树中每个结点有两棵非空子树或有两棵空子树。
A、错误
0 P# k! K5 d, ~6 k4 YB、正确
正确资料:
  X7 l3 Y, S: {" I% S
2 g! D4 t7 T7 I4 N
第43题,线性表在物理存储空间中也一定是连续的。
A、错误
B、正确
正确资料:

4 \! l! @. U7 q' \( \& N# [. n
: _, Y9 @8 Q) v9 ]6 q" W第44题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
+ L  v8 b& p! n) qA、错误
: t1 s; r0 c" MB、正确
7 q" K5 ?1 s% j  |7 N+ `正确资料:
7 z5 A$ T5 U$ |) r
8 K: C7 N4 A+ l! _6 H( Q8 l
第45题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
  i5 Z) O1 e% \& kA、错误
  v# c" G) |! t+ zB、正确
正确资料:


  ~' `1 d; Y" ^( y  d) ^第46题,设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
0 x3 Q8 r/ Z( V正确资料:

$ s3 t3 b* }1 Q0 q" h0 s
7 D6 V9 g' l, y# e! \$ D第47题,设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
正确资料:
& |, Z8 }5 I$ D& u2 T0 o

4 I" Z6 \' C; ~2 ~' ?6 O第48题,设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
正确资料:
; x( |1 g! H6 p/ ~: g( J2 o

' p8 R* M2 H& W7 B+ Y3 v


+ K$ L, C( X) b8 J& P1 p* n
: d, c( u% ]- ]1 f, i
6 C% C5 b, d( c' b
" H9 z1 \3 N. U( z0 ]

7 ]8 P2 ?- t! V. F. r3 E( T) e3 ^
/ A5 c  _% u8 |

) @3 Z% A: q& K* y+ D

erda2052

下载一份试试！

卢巳致

同学推荐的

louinu

同学推荐的