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

admin

【奥鹏】-[南开大学]《数据结构》19秋期末考核
试卷总分:100    得分:100
第1题,有8个结点的无向连通图最少有（）条边
/ v' O- r$ K. U" }A、5
+ j4 U% G* Z9 d' ]1 }B、6
0 j% k4 g$ t) t. m6 C. P3 NC、7
3 D" p( z1 C4 sD、8
正确资料:
( O6 D- E( b  a

) }& U! i. u  T0 I第2题,链表是一种采用        存储结构存储的线性表
A、顺序
+ j( [7 |5 _  L5 ]# m, G3 `: V; }& sB、链式
C、星式
5 }2 |% B3 G8 ?7 WD、网状
正确资料:


第3题,栈中元素的进出原则是（）
5 p9 A7 s" X% \5 ~& }. e; M, r  TA、先进先出
1 B* |. e. R/ L8 c- m- qB、后进先出
C、栈空则进
/ @5 H4 l% R4 l; B; i$ K, Q& qD、栈满则出
  w- `" K8 h% r: F! s4 P1 }正确资料:
2 j1 h+ j1 [1 i# V% ?
) O: I3 Y2 `9 d; N/ G
1 g' w1 c0 \& U& q8 k/ s" J第4题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A、栈
  ^5 F; I$ E1 J, g! ^8 BB、队列
+ m4 [/ h; L& ~$ }; L( pC、树
+ d3 q8 l% e& ]2 ~# w2 TD、图
正确资料:
, [( l3 I- R* B; `) E
; H; O  @+ U( W* s( ^
第5题,链表适用于()查找
) n7 p/ R3 D) L) L5 k! `8 M4 lA、顺序
4 _9 W! l% v' p* YB、二分法
# y% M6 i/ a# z' uC、顺序，也能二分法
D、随机
正确资料:


第6题,把一棵树转换为二叉树后，这棵二叉树的形态是（）
0 R% v+ u0 w4 @! A1 l5 D0 F4 X% B( V4 ZA、唯一的
B、有多种
  b& s. ?$ u: L2 [$ WC、有多种，但根结点都没有左孩子
  J# F6 B. Q, i# ID、有多种，但根结点都没有右孩子
正确资料:


第7题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
A、8
B、63.5
0 h2 R7 V# D& D  j8 D$ DC、63
1 {. n$ X" f1 Y  c6 q! i- h* xD、7
正确资料:

2 g) L  Z9 o7 K- a' }, ]: \+ c
* o7 i" b( _8 d% X8 ?8 a第8题,引入二叉线索树的目的是（    ）
0 ?! }* V! B5 ]! nA、加快查找结点的前驱或后继的速度
B、为了能在二叉树中方便的进行插入与删除
3 d. Z& y( Z3 v( E' TC、为了能方便的找到双亲
D、使二叉树的遍历结果唯一
4 s* Y1 D, |' C2 [$ t2 w正确资料:
3 k8 w0 Y* L; e

第9题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
A、0 2 4 3 1 5 6
$ g2 F" o# o  h( o" E# j4 [, u* n5 HB、0 1 3 5 6 4 2
6 b' l! |. o7 y8 gC、0 4 2 3 1 6 5
6 [% q& p% h; K  r% L/ _D、0 1 3 4 2 5 6
正确资料:
  j& n. Q) L, L* x" K3 ?
' U$ `0 B. d; K* P
第10题,判定一个栈ST（最多元素为m0）为空的条件是（）
A、ST-top0
, N/ O' e8 t$ `( i. m! vB、ST-top=0
C、ST-topm0
) |) j$ Q, m, e6 J; fD、ST-top=m0
4 x& N+ ]6 o4 R  P" ]' h% O7 G+ f正确资料:


第11题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A、110
B、108
C、100
D、120
. h  Y7 t  c4 g4 T  o) B! l/ o正确资料:


第12题,广度优先遍历类似于二叉树的()
A、先序遍历
B、中序遍历
0 ]" Z; Y# ^1 r6 \" ^5 h) j+ tC、后序遍历
* ~& @5 s+ {$ \$ G0 p( O5 b5 KD、层次遍历
正确资料:
3 \* O! Z, X5 F* ~% E7 S9 ?! J  R7 I7 L

第13题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 6 5 1
! w3 g! ?( h% V# O+ zB、0 1 3 6 4 2 5
( L  r- y$ z$ X5 EC、0 4 2 3 1 5 6
) |0 I8 w/ J! D  `$ qD、0 1 3 4 2 5 6
5 _' j7 T8 B2 l' {1 J, w正确资料:
0 H9 w7 r0 K) a

2 `2 l6 L9 C) X( E# m2 u第14题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
A、循环链表
; Y' _$ l/ v$ vB、单链表
1 d8 }6 N! V# Z/ tC、双向循环链表
D、双向链表
- u" O1 _4 w: ~6 r. Y正确资料:

1 l$ A5 h1 @2 O* L/ _' b+ _
第15题,链接存储的存储结构所占存储空间（）
8 F. p% L2 H) a9 |# b; W2 Q+ HA、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
, Z0 X7 s* q' d; G8 g8 u0 m# tB、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针
  {0 s5 M( m/ d* T- S7 X7 \D、分两部分，一部分存放结点值，另一部分存放结点所占单元数
# Z; J, ^  M9 f  |4 q' R正确资料:


) O  l7 h5 J, d0 v) m% b第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))的结果串是（）
8 K/ A* p2 l' t' s' {. }A、BCDEF
B、BCDEFG
C、BCPQRST
D、BCDEFEF
0 {7 u$ _0 o( F9 y* c正确资料:
- q. p# k) m' Y) {
& Z; n; l& ]7 r. O
, X: g5 {' S& W7 B. F" k7 o9 ], D第17题,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
: j: i4 y4 ]9 M( |; v) h" J4 \6 GC、一定有多棵
. U/ O/ @9 l; o/ K& lD、可能不存在
6 @- K; r0 Q7 ~' V* T正确资料:


0 ?2 N# R) T$ h( A第18题,串是一种特殊的线性表，其特殊性体现在（）
. g$ C5 G1 S' c# OA、可以顺序存储
7 f8 A; y- n' kB、数据元素是一个字符
6 q0 j8 `3 n7 i# V/ Y9 a0 k8 q& EC、可以链式存储
7 w$ n, |; F& `) gD、数据元素可以是多个字符
$ k# w0 s1 M& T) B8 ^正确资料:


! k$ C: B" r- q& J5 b" V" `第19题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
7 d4 K+ i  o( w1 wA、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
# R3 T0 m9 F' U7 `% ?; \C、QU-front = = QU-rear
% k/ E5 i/ e) z8 [D、QU-front = = QU-rear+1
8 n4 \0 `; G. r- T4 u( S% ~正确资料:
- o+ F% o- o! H

1 Q$ w8 W! M9 i; _第20题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
- ~: R2 P2 k  S( J1 ~B、0 2 3 1
C、0 3 2 1
9 x' E) o' }8 @+ |D、0 1 2 3
正确资料:

7 b1 x7 Z3 W3 I  x
$ _/ s& e6 \6 _( ~: V5 z4 a$ s第21题,下列关键字序列中，()是堆
  U2 B2 a# s* H$ O" H: Q$ S) WA、16,72,31,23,94,53
B、94,23,31,72,16,53
; S2 v. q; _8 `+ W6 hC、16,53,23,94，31,72
; i# a5 E2 q0 m' ?" u0 _+ ^2 r( dD、16,23,53,31,94,72
正确资料:
/ Q* T' j# a9 Y" h: s5 V- a# d

4 t. {% C4 \" `, ]6 p# C第22题,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
A、20，70，30，50
" ]' c+ I/ p4 y* G; O6 P1 J8 kB、30，88，70，50
C、20，50
2 ^2 L. L4 S/ a' GD、30，88，50
正确资料:
( d! J  r# K; n+ w7 H4 U  i
0 i/ l9 u0 i6 F  o$ h+ @! c/ N- w: D
9 O6 [8 P2 h: H& v0 h! z1 N2 r第23题,深度优先遍历类似于二叉树的()
, Y4 K4 k4 Z7 {A、先序遍历
/ O, A7 v2 S* Z. I* eB、中序遍历
  j3 N7 u7 z& x5 k( G# m$ l( HC、后序遍历
D、层次遍历
# p' E' m7 q7 h) J& m7 L正确资料:


第24题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 1 6 5
, x% p$ n9 H9 J1 s4 xB、0 1 3 5 6 4 2
+ k, m! ^1 O. Z8 R* O& d( FC、0 1 2 3 4 6 5
D、0 1 2 3 4 5 6
: r$ U- K4 v  @- C8 y9 K0 V- x. Q正确资料:
# v# j( K: H/ n- z7 e1 A
. O7 L- E! {7 P' M
第25题,下述几种排序方法中，要求内存最大的是()
A、插入排序
# v9 P7 J" Z: K- u+ S" ?: MB、快速排序
C、归并排序
4 N# u5 e8 m2 [1 v( P. C5 WD、选择排序
1 s# n+ Q) i4 r  }5 a$ H+ x正确资料:
! l+ ?& L/ f  m/ v$ \9 Z

第26题,线性表在物理存储空间中也一定是连续的。
A、错误
7 z* M( e7 p+ G" {3 e+ RB、正确
, l4 B- f$ ^: |; s' l! T正确资料:

2 C& T' e* D2 |- V# ]5 b9 T* m/ {
" Z( A; e" R7 L2 G- i, a# y7 y3 e% U第27题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
& v3 {5 {: W5 J7 w/ vA、错误
B、正确
正确资料:
9 c! ~! x: |3 J# s- R

. ?: v- M8 K0 O+ _1 J! `第28题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
A、错误
B、正确
, A: ?+ `1 B" m- P正确资料:
& _/ ~5 ]; F. y3 A
# U' x5 c( f5 d3 G+ r) J# G" R
- g4 I$ {/ `! X9 F第29题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
0 b& X7 ]( [! @/ X: k: |3 v9 \: uB、正确
$ E$ W/ U# T( e7 E" j/ W5 G正确资料:


( n. ^$ ^! C0 t. N9 ], J第30题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
* I' j; o1 _( z- M) {8 u2 _" F3 l$ tA、错误
B、正确
' `1 X, o4 n" f9 |/ D正确资料:
% w" t/ m8 ^; r, V$ g; ]  t

第31题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
! K0 ~% }: q7 r2 E9 RA、错误
B、正确
' r9 {  I* ?: I4 ^, b正确资料:
; q. O5 _+ J7 G- l
- b  ?$ \: y4 y4 [
第32题,栈和链表是两种不同的数据结构。
- X/ G) h% H* Q4 Z+ _' W7 G! PA、错误
B、正确
4 o; u: D/ W7 @正确资料:
. ?6 U$ x. B8 M7 ~, W

第33题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
B、正确
, R+ {7 W4 \8 T# i& N正确资料:
2 z9 y* l' M6 f9 I
( y% b2 K: x0 ^* @9 f7 Y5 u4 `
第34题,具有12个结点的完全二叉树有5个度为2的结点。
A、错误
B、正确
正确资料:

& O) Z! ^" Q2 s5 `0 `5 M- l! k
" f' F  j; y/ _第35题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
B、正确
! j: [2 X. F& u" B* }# {; ]正确资料:
+ f8 {& G* W3 }6 ?. n; m8 ~

( Z1 o1 N1 y6 A+ [第36题,链表的物理存储结构具有同链表一样的顺序。
A、错误
9 q* s0 P' x8 U. B8 M. Z7 rB、正确
& u1 g. i% i% r* V, v( O5 Y正确资料:
5 K: x! U& @: r) W5 Z, y: V- f, ?
) [: M! G4 g7 k
5 t4 D: @. a$ E0 n3 w第37题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
8 f( T# G3 D. a% y6 \B、正确
正确资料:


. A( |! i8 S5 H0 A% X, z' ~第38题,二叉树中每个结点的两棵子树是有序的。
A、错误
B、正确
* r' M) I/ e- g正确资料:
0 P% {& L( T# y" z( C  ^$ X+ h
' t( ]0 {! g8 p- |/ p& ?
第39题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
# l- U$ L6 f8 I' b' L  YA、错误
B、正确
: z/ u: v7 E- M正确资料:


第40题,顺序存储方式只能用于存储线性结构。
A、错误
B、正确
正确资料:
. ^: ?3 n8 K2 t! t6 f  l

第41题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
7 w# m' r6 [7 M! h2 jA、错误
B、正确
9 x0 b9 ^& q# O正确资料:


第42题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
% O% ?9 b+ Z# M; Q0 H3 BA、错误
5 L. O! R0 u, vB、正确
3 A4 e' g3 U$ C% v; y+ W4 J正确资料:


第43题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
% ]. M; V8 p2 T: w4 h2 qA、错误
B、正确
正确资料:


, M7 ~. s/ W0 K" |! O6 [: j- U5 g第44题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
6 M& i6 m2 l7 |9 B# DA、错误
B、正确
3 c! r( h  Q7 F3 k% J% w正确资料:

& H+ B( G" f3 y9 ?; W( s  }5 g
- G1 k) Y8 U" o3 u! j' [1 x: C/ @第45题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
5 x9 E4 t3 k; V& W, H! _& w5 qA、错误
) d+ B' p4 x9 C# Q, JB、正确
8 y  w+ b' s  C1 Z6 S正确资料:
8 n% e0 Q  T4 [( M7 W5 |

第46题,设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
; A6 J. A7 ?9 i# G" w正确资料:


# K4 N: ?; g) b+ L* K: |第47题,设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
3 `; p$ O- C8 R& K% c* K  B$ V正确资料:


6 w. j+ S) M; F* v2 D" \第48题,设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
' ^5 Z4 Z6 W2 b9 J正确资料:



5 @( i7 n( m' G% x" G" q: r4 W
& O& b5 R* {$ A1 p/ a


& z$ c, O- P" j' U4 f1 z
8 W( d/ f9 f9 ~& P/ m: S* f
0 r7 n2 n) c7 l2 f  t
) Z) K& [, v% o( n
6 z" E, ^, o9 c4 |6 ~  D: r& u5 L

; }3 N8 _  t3 B5 c$ ]: T

爱征

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

42637124

学长介绍来的

eyyb4308

谋学网不错！