[南开大学]《数据结构》19秋期末考核(资料参考）

admin

【奥鹏】-[南开大学]《数据结构》19秋期末考核
试卷总分:100    得分:100
第1题,有8个结点的无向连通图最少有（）条边
A、5
5 V+ r0 ~* y' W) [/ t* wB、6
* y0 f* i; n+ b& P+ J, Y4 \C、7
  h0 m* V1 L- x6 {& t) R1 O6 xD、8
5 G/ s2 k3 o; M$ U+ @7 X& Z正确资料:

: |9 `- m; C: X3 Q; V
第2题,链表是一种采用        存储结构存储的线性表
9 R% j- e' U/ q1 j/ I& ~4 \A、顺序
9 A4 S) ], C! Y0 ~$ R0 x( K0 f! Z2 RB、链式
C、星式
0 m: O3 c# M5 u3 L4 ~, ~& jD、网状
& L" x6 p+ n  R' `+ {* Y$ H正确资料:
: x- V! J& H- G: X) A0 Q1 Y. R

) C2 ^  y. Y* q第3题,栈中元素的进出原则是（）
A、先进先出
B、后进先出
C、栈空则进
6 O; B7 A; q$ d& u! X2 hD、栈满则出
正确资料:
" `, i% C- s" T! r& l! b4 a. Q
: C$ d  O. P1 j& i" ?
7 c; p; F+ @, x2 Q第4题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A、栈
B、队列
C、树
D、图
正确资料:


- \8 {  h, U8 L- I& i+ C; e* X0 n第5题,链表适用于()查找
. T" _2 _% {( {4 zA、顺序
B、二分法
' ^. d+ A- E' E( RC、顺序，也能二分法
D、随机
# X5 [* L* B- z. V6 p5 T正确资料:
& a# a0 V1 d3 M  b

第6题,把一棵树转换为二叉树后，这棵二叉树的形态是（）
# Z. {1 s9 P* f3 C1 {. J: OA、唯一的
  g  [: g6 {5 C! _B、有多种
" K- b4 m6 o* i! g& N, k' JC、有多种，但根结点都没有左孩子
/ A& \/ R; U# ~. ^D、有多种，但根结点都没有右孩子
正确资料:
2 u; X0 I5 S# j8 m
# e# }8 x7 g: J3 I4 ~" y& q* o' L* S
第7题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
9 c$ h' O3 W; v" [) Q0 PA、8
3 F. s+ w/ Q3 U- z3 A4 \B、63.5
C、63
- T# K) [% Q3 I$ DD、7
正确资料:


6 ]; M/ G  E; N& s9 l) F第8题,引入二叉线索树的目的是（    ）
A、加快查找结点的前驱或后继的速度
/ A( t# d2 v3 ]0 h# tB、为了能在二叉树中方便的进行插入与删除
# z3 E: |% e0 AC、为了能方便的找到双亲
  m6 F+ S- m- C7 _! QD、使二叉树的遍历结果唯一
正确资料:

  J# J9 T" A2 \8 D
第9题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
A、0 2 4 3 1 5 6
B、0 1 3 5 6 4 2
C、0 4 2 3 1 6 5
D、0 1 3 4 2 5 6
' _7 k' R6 w& q) {/ ?* A$ P. J% s! b正确资料:
, t# c3 O# M( ^0 C& a

: m6 _- B0 z: r( P; q2 I第10题,判定一个栈ST（最多元素为m0）为空的条件是（）
! f* b5 m- w. m  ^7 R, U" Z) T3 RA、ST-top0
# R' M/ q/ m7 e$ V2 S. vB、ST-top=0
C、ST-topm0
D、ST-top=m0
正确资料:


第11题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
3 M+ j8 X8 n7 [$ b& }A、110
B、108
C、100
/ r& Q9 Q/ L1 O9 \, xD、120
; o5 F$ C8 ^2 r0 n. t" _正确资料:
6 D" }% Y9 C& J% g6 Y+ m$ G) Z" m

第12题,广度优先遍历类似于二叉树的()
8 e& V0 y. z, N6 ]9 xA、先序遍历
B、中序遍历
% N/ V* F, m; L# w9 oC、后序遍历
$ d' u2 j$ f0 kD、层次遍历
正确资料:
3 |8 y/ t, d# }! A" t1 Q
; d) ^0 D8 X- o+ p! g
第13题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 6 5 1
B、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
1 M/ o( _( O2 H( iD、0 1 3 4 2 5 6
正确资料:

$ ~( ^, y- d2 ^- N- }9 s# q, ]
' U) L. @8 A8 _; c3 @第14题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
& r' ?  o  b0 z8 V8 ~6 M1 UA、循环链表
, l$ n/ S" }5 ]: a% H! k5 `& QB、单链表
6 w  @0 P" x, u- F4 a% Y2 j. LC、双向循环链表
D、双向链表
! ]- ]; h1 T& I% m  J正确资料:
8 p8 M  ]  x0 n/ z

* j0 T) w. }$ W# @0 b第15题,链接存储的存储结构所占存储空间（）
A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点值
$ _1 u! k( r* l! x/ x2 YC、只有一部分，存储表示结点间关系的指针
D、分两部分，一部分存放结点值，另一部分存放结点所占单元数
- T9 M5 P+ B% _3 `" I正确资料:
' a% k0 e" N5 t( O/ r) J! f0 H5 R

第16题,设串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))的结果串是（）
- W: O6 a/ p9 X3 K  nA、BCDEF
B、BCDEFG
1 C6 X# Q" T4 L; ?! v" P! f# vC、BCPQRST
  O5 d2 {8 ~+ |" q; y% L! w% qD、BCDEFEF
正确资料:


! ^: K# w" E2 v! z# @* k第17题,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
4 U" O$ K% |, C& P% c4 Y+ lC、一定有多棵
D、可能不存在
正确资料:

* T& f6 n( a0 g; D& o
第18题,串是一种特殊的线性表，其特殊性体现在（）
A、可以顺序存储
* [1 d* j" R! |' l8 bB、数据元素是一个字符
0 _7 `' @! q) i/ V1 ^C、可以链式存储
% [, m, m. O% w$ G# d+ SD、数据元素可以是多个字符
9 ]* s4 }. O. {6 t# D- @正确资料:


- n3 M- f' J3 F1 @5 I7 c第19题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
A、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
6 ~+ m  a8 I( y: r6 j' m  dC、QU-front = = QU-rear
D、QU-front = = QU-rear+1
; I0 z! M" W3 M0 f正确资料:
2 }3 R5 B- t3 b7 v1 m$ E0 C

  I6 f; e, G: `7 ]第20题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
: j- q. ~: Z, K3 N2 a3 [A、0 1 3 2
B、0 2 3 1
/ y- x$ p9 Y! z- g# |3 x: IC、0 3 2 1
D、0 1 2 3
* B7 J* y' U- y正确资料:

0 Q& h& ~2 _1 A( Q1 o
第21题,下列关键字序列中，()是堆
. B5 t3 }9 _9 Y3 bA、16,72,31,23,94,53
3 D" ~* |6 L- N+ ]+ CB、94,23,31,72,16,53
0 j% H- p; q, e/ @/ S6 K1 V+ y6 rC、16,53,23,94，31,72
! A+ y) F1 G" j" [6 c6 f3 lD、16,23,53,31,94,72
* o0 ]7 ]4 l; U5 D4 f4 n# m( z正确资料:

# K& O0 K# t8 l1 I% J/ f/ f
第22题,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
A、20，70，30，50
B、30，88，70，50
C、20，50
4 l: I7 ]" m9 eD、30，88，50
+ Z* f7 R4 g3 E正确资料:
/ D- x/ y4 L# ]9 ~* c
( |* I  U9 L& U# n6 j) J2 R' V
0 K. r$ }/ V' [# \1 w第23题,深度优先遍历类似于二叉树的()
  x9 w" M$ Y" t" q; m0 qA、先序遍历
& i( @/ ]& x9 P0 [3 d# a9 |. t) f" UB、中序遍历
7 V. l. @/ L7 m( i: q3 z* L/ N8 tC、后序遍历
D、层次遍历
+ J- _0 u. H1 y7 a6 Y/ y& a正确资料:
) T1 }& A) y2 I0 _2 B! g8 f; u
  R) }# Z0 L9 s
, I' N0 F, d, D" S! S; L第24题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 1 6 5
, Q0 f. Y& q5 C- Z( pB、0 1 3 5 6 4 2
: j/ E* G. C$ x5 nC、0 1 2 3 4 6 5
D、0 1 2 3 4 5 6
正确资料:


第25题,下述几种排序方法中，要求内存最大的是()
- R( O- `3 y3 y- P* R7 `A、插入排序
B、快速排序
C、归并排序
D、选择排序
正确资料:

/ t4 i) }% f! @
. V% s( u( h2 O4 T第26题,线性表在物理存储空间中也一定是连续的。
A、错误
B、正确
正确资料:
. k9 e( U3 @7 W7 R! k9 a0 e

第27题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
' v  g& _4 W* o, r+ eA、错误
B、正确
3 [) t* a+ V6 X! R9 v  v% q$ w! a正确资料:
4 e; [" p1 a- n7 U" ?, p4 S
* _0 [) E  x* |) L
/ C# {4 E6 F! q$ G( h* }8 W* C第28题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
, D% C$ R9 Q+ ~* }& d+ sA、错误
/ r9 l! |. c/ i8 \* F4 I( V+ m- E1 KB、正确
$ e! o/ \$ {2 j正确资料:


3 M6 o. n3 m/ h第29题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
B、正确
正确资料:
& t2 G& |5 N! ?
- Y0 p; x# J; B8 n
0 w& m5 @6 }( x3 b' B第30题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
  r0 n- e8 D* Y  ?A、错误
# e& l& M9 q& X8 KB、正确
$ I7 u; B9 E% p# a" q正确资料:
( W) M, Q' N; p0 N' O

% e" k8 e' V! J+ }+ t4 J第31题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
4 }$ ^% _  B( GA、错误
B、正确
- b. y1 t3 ]$ V) r/ \( R正确资料:


第32题,栈和链表是两种不同的数据结构。
# [) f( X1 X& q1 H$ {2 d, S( s2 oA、错误
B、正确
6 X- g2 i- T+ g( c$ z正确资料:


: o4 D1 e4 s' \% w第33题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
' r! d3 |" f' p) AB、正确
  w8 e" a! d' ?正确资料:

; ?0 ?. C+ M- R6 Q6 c
, `" G6 k- Y- N  F4 H第34题,具有12个结点的完全二叉树有5个度为2的结点。
A、错误
* |) T2 A! ?! ?. f, {& {9 q+ iB、正确
正确资料:
9 }4 b# z/ ?/ {& x" g/ z# l- V3 N2 m
6 p, G" m7 |; c: r) R6 i6 l2 D- J% |
第35题,线性表的逻辑顺序与存储顺序总是一致的。
% @  {& T) G* z/ G2 Y7 uA、错误
B、正确
7 g. V2 B( ~6 d* x$ m6 d9 r) P正确资料:
8 N7 l4 x$ b. {
9 }. |# G% t! k6 j' m, S
第36题,链表的物理存储结构具有同链表一样的顺序。
A、错误
/ r4 q, e$ o1 B/ A6 pB、正确
正确资料:
7 K4 Q- o/ E( o

' v$ A( R: j4 N第37题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
B、正确
0 I' V) w8 u7 x# A0 I正确资料:
* b; j7 p& B1 ?5 H( k
. ~  }/ b+ y% M- z2 _! v9 _' C, s
第38题,二叉树中每个结点的两棵子树是有序的。
A、错误
, A' ], ^8 m4 o4 b7 H( UB、正确
正确资料:


8 d# F3 x5 s, ]0 T0 H  p第39题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
1 t& ?. E( Z+ @  qA、错误
) t& t9 O* E: s# u$ E; BB、正确
正确资料:
! Y% K' H4 e4 V) A

9 Z6 [  f: }% }# F, w第40题,顺序存储方式只能用于存储线性结构。
A、错误
( t3 C6 y( ]9 D; c. c0 IB、正确
正确资料:
5 e1 p8 Q, E! f7 z% d

" Y. M( l% y. J3 S$ h5 B第41题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A、错误
B、正确
正确资料:
! V0 P. L3 @2 k
) O) G: q+ \# o0 L0 `
4 l0 {. |% ^' h) I- Q第42题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
( l4 d2 [9 M* N. l6 t# q( o, JA、错误
" Y% y* E2 j6 t4 R) H' K* O' PB、正确
正确资料:

0 u8 z( q6 p' ~
第43题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
B、正确
正确资料:


8 E8 ]' ]) o  v6 O1 ]  V第44题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
5 m, B& q1 [5 O4 p; [) A* ?9 j" bA、错误
B、正确
正确资料:
, _$ |$ d6 i% E2 y; D1 D2 z
/ f. @' u" M, I1 `* v6 ?
第45题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A、错误
* g+ E8 m( a5 ?$ H. u, JB、正确
# k+ r1 R; W: M  i& M- g' t- [正确资料:
1 i) v8 l0 c( M: E
3 G8 i5 F4 W1 p8 S  p
第46题,设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2 P" [) i' {0 c" {正确资料:


7 k; s- J  ?  p; }第47题,设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
正确资料:

! A- m7 P' B" j/ F$ r; y
7 Y( L+ s  N/ Q, d第48题,设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
正确资料:


5 z( ~( d+ m2 m, o5 \

* c7 [/ i6 n5 Q  J0 \8 `
- z; R% o1 M3 O+ @1 f






1 i, d$ e) T6 J( G8 a/ `
) j6 h* Y! V1 L6 G+ ~
/ W+ \4 f- z, L7 Y: P5 b: E6 h

爱征

资料不错哦，希望一直有这么好

42637124

学长介绍来的

eyyb4308

谋学网不错！