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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学（本部）]《数据结构》20春期末考核
试卷总分:100    得分:100
1 G2 j* v1 q5 ]* p) S6 i! [第1题,快速排序在下列哪种情况下最易发挥其长处()
A、被排序的数据中含有多个相同排序码
B、被排序的数据已基本有序
C、被排序的数据完全无序
) f( H9 ^* ?9 W) ?D、被排序的数据中的最大值和最小值相差悬殊
' y, p+ c3 ^7 ^: V" i7 y3 a9 U正确资料:

$ M3 @2 I$ a# p/ Y) ~
第2题,串是一种特殊的线性表，其特殊性体现在（）
# e/ M: ^4 J# k0 R5 S1 |  UA、可以顺序存储
B、数据元素是一个字符
C、可以链式存储
D、数据元素可以是多个字符
" b8 Y$ v( Q' a; ^3 E, A& Y( P5 u3 i正确资料:


第3题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A、1/2
4 S& `2 \7 c) a# x' EB、1
. \: V8 d: P, s8 ]8 H6 KC、2
1 N8 p5 Q1 l3 s6 f! ]: P- d: ~D、4
  w! f) Y+ u" }% G正确资料:

: [1 q& Q; i. ~: E6 E' g
第4题,堆的形状是一棵()
A、二叉排序树
B、满二叉树
8 r: _  H- [7 N- g8 _7 n' mC、完全二叉树
D、平衡二叉树
正确资料:


. w! v% k) D+ c& @" _6 d资料来源：谋学网（www.mouxue.com）,判定一个队列QU（最多元素为m0）为满队列的条件是（）
A、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
C、QU-front = = QU-rear
5 z) O; _4 T1 k" J2 i# tD、QU-front = = QU-rear+1
4 u' {/ V  |9 O' [6 ~正确资料:
9 z  ~1 k% a$ h) }- O

第6题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
A、i
B、n=i
C、n-i+1
/ T% g; J( N! h4 d3 S5 T5 {& C6 }, _D、不确定
正确资料:


9 E* D0 V; `" g! z( c& z第7题,单链表的存储密度（）
A、大于1
B、等于1
& t( y( ^0 [% p" R0 EC、小于1
. M, A) T! r/ xD、不能确定
正确资料:
7 g8 E, w8 v- L5 q0 {/ X6 W, ]! D4 N
7 K, C0 \/ ~/ L9 x& L/ k6 p* z; m% E
6 `( E7 X# L% F0 Q$ ~0 f第8题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
* w# E/ E" v1 Z$ j4 dA、0 2 4 3 1 6 5
- a# b4 Y/ N( T% |# @8 VB、0 1 3 5 6 4 2
C、0 1 2 3 4 6 5
+ @9 j* P( E' R  WD、0 1 2 3 4 5 6
正确资料:
9 [0 c9 K0 n9 a. \2 Y- l8 X

) n6 q1 m7 v$ H* O; T0 b- \第9题,链表是一种采用        存储结构存储的线性表
+ |0 W: \" y- G( j9 O* MA、顺序
B、链式
2 Y: @5 }  x: |1 Q: M  g+ YC、星式
D、网状
0 S5 T8 _9 e+ t. |1 X正确资料:
$ ~' Y7 x/ `& }7 `, o$ M, G
7 u0 D' a3 ?) w: \  ^0 s8 `. i4 ?
$ j' z& ]% p$ Y% o& y& Y8 A资料来源：谋学网（www.mouxue.com）,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
; l6 M; e) [6 o- y0 HA、20，70，30，50
7 j) k" B, A( n+ l% E3 yB、30，88，70，50
C、20，50
D、30，88，50
8 T5 {8 O2 V7 s4 E正确资料:
3 y, B4 w3 U& @  ^8 M
7 z5 U: x; B) S2 O9 ^3 F( g: l8 Z3 M
第11题,判定一个栈ST（最多元素为m0）为空的条件是（）
7 O/ S8 @5 H- @A、ST-top0
# @0 v' U, A8 Y. G9 `2 eB、ST-top=0
C、ST-topm0
D、ST-top=m0
正确资料:
- z% {$ Y! {9 V( h
9 C1 j0 U4 i$ \) z" c" |$ _2 Q
资料来源：谋学网（www.mouxue.com）,下列关键字序列中，()是堆
A、16,72,31,23,94,53
B、94,23,31,72,16,53
- w8 v) F1 g' Y. N$ lC、16,53,23,94，31,72
D、16,23,53,31,94,72
  T. c1 |, k4 r" z" R: [正确资料:


7 D/ c9 h+ g. `! y" X5 h第13题,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
A、79,46,56,38,40,84
3 |' L! N. m; ], [9 s, N2 g5 ZB、84,79,56,38,40,46
C、84,79,56,46,40,38
5 M' k! J3 `0 X* v5 OD、84,56,79,40,46,38
正确资料:
% j5 d2 p' O. |4 u9 |, J- B8 o0 H

5 F: D2 W  P2 r8 G' U9 {4 V第14题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
B、0 2 3 1
C、0 3 2 1
3 ^5 R. O# Z( V8 e1 P. Z4 LD、0 1 2 3
  O5 r# B3 q3 S4 s6 E4 W正确资料:

. ~# n% b  _8 L' t' Q* i6 Y
- D& y! H" E$ K2 V* t. J5 Z$ W资料来源：谋学网（www.mouxue.com）,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A、110
B、108
" L% }! R: M- G1 tC、100
D、120
正确资料:
/ j1 @3 q% W$ M6 p5 @- L2 I4 L
$ Y3 w" N1 V: E, B5 v
: o0 V' c8 N9 O9 d3 Z+ O第16题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
A、存储结构
B、逻辑结构
7 |5 T7 s, a2 [& W6 Q$ k! mC、顺序存储结构
D、链式存储结构
; w6 \) z/ e" _5 l( j: R正确资料:

2 ~+ L# W; D5 P$ @/ c  O- E
2 P) b1 ^; T2 U+ U4 Q6 P第17题,链表适用于()查找
# y0 V6 B5 {% o, d5 VA、顺序
/ {! p+ C6 f+ S5 t1 m) Y! M( {B、二分法
C、顺序，也能二分法
D、随机
正确资料:
' `, `! m( b$ M1 V' g
3 z0 x2 n+ _" v8 p' o2 v
第18题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
A、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
C、0 4 2 3 1 6 5
0 c7 r5 b, e) U+ q/ h+ u6 nD、0 3 6 1 5 4 2
正确资料:
! I0 v! i( }, Q

: }) t7 x; V' E9 l* A4 O第19题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
4 ~7 P) r$ i5 {! `/ WA、栈
+ q7 m; A+ N; x7 B: ~; m5 }$ AB、队列
+ b9 Y7 i- x7 e. b! FC、树
D、图
2 e' `/ f; h/ z正确资料:
! L' C# G+ |8 J$ O: i5 l" X
! x, B; ~4 P2 L6 i; {
资料来源：谋学网（www.mouxue.com）,设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A、n-1
B、n
: I) x1 p2 I3 M- e2 H# SC、n+1
D、n+2
正确资料:
/ V. v4 r1 Q1 ~$ o9 t! G
4 B- Z: C* m4 t% Z3 {  S: x4 y
$ p3 ]7 e0 v4 u% m7 O6 D第21题,折半搜索与二叉搜索树的时间性能()
" z6 V1 ?" l4 n, ~% iA、相同
+ ~3 y' F( R+ }( y  l# [& PB、完全不同
- x" O8 Q3 x( n- b- z+ CC、有时不相同
D、数量级都是O（log2n）
* f& Z  d" N/ P2 c; @+ k正确资料:

1 Q) {! T5 g. y! X% k/ U$ a
" j8 w4 {! {: J. s4 o: b第22题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
A、循环链表
+ u0 E  x1 v6 w0 a5 g+ {; J+ ~B、单链表
C、双向循环链表
D、双向链表
0 \/ N7 Q: h5 N! t! E7 m正确资料:

( P. M  M' l7 o
第23题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
/ a: ~& ^2 r& T0 kB、队列
2 r! b6 T8 `1 jC、树
8 l4 N( M1 n7 Q% Y/ ^4 c4 Z+ kD、图
正确资料:

" @; O: H  Q4 q, v( F/ @5 k
9 w" |" i+ A; k6 l, v% Q第24题,有8个结点的无向连通图最少有（）条边
A、5
4 y$ F* l3 G8 g* [' KB、6
C、7
& P' A# n( M! J4 rD、8
: D2 s8 W0 ?8 W. S1 ^  \; Q4 W正确资料:


资料来源：谋学网（www.mouxue.com）,链接存储的存储结构所占存储空间（）
2 h4 A0 o( _8 U6 J/ v% tA、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、只有一部分，存放结点值
C、只有一部分，存储表示结点间关系的指针
+ \9 }4 N! {3 m' }3 V7 v: q. PD、分两部分，一部分存放结点值，另一部分存放结点所占单元数
正确资料:
( @* c7 ?, K; _" e

第26题,栈和队列是一种非线性数据结构。
) T/ h5 T: J7 l" q4 I" j1 j5 [A、错误
: E7 V0 `# U6 }' q0 G, {B、正确
正确资料:


第27题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A、错误
B、正确
正确资料:


第28题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
A、错误
B、正确
7 U% X. o9 t& G# N  C正确资料:


0 f; R  U0 N/ @$ @1 D% w( R第29题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A、错误
B、正确
正确资料:
1 Z* j5 S- |: b9 @% Q; U

资料来源：谋学网（www.mouxue.com）,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
B、正确
( V  l* M  k; V' g正确资料:

4 o: ?* x" A7 v) T/ g5 L
8 I9 V& K* S& [9 a+ l( @# ]第31题,二叉树中每个结点的两棵子树是有序的。
A、错误
  n0 u4 o1 b+ W! SB、正确
. V/ b- H+ H4 Z正确资料:
: j+ A- p! b6 r1 H

第32题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
0 k' R9 w- {, h' \  t  XA、错误
. @2 J2 d1 M6 ^2 @B、正确
正确资料:
7 O6 m1 E9 `. ]( B; v4 O
* c5 A' s$ x: U5 w2 l5 s3 c9 c
( h/ s$ W; @* T& H9 J/ J+ t第33题,顺序存储方式只能用于存储线性结构。
A、错误
1 g  @& S2 C! ~( w! z  l; yB、正确
正确资料:
2 r$ _8 I: A: i2 u: e4 l

第34题,栈和链表是两种不同的数据结构。
A、错误
" N/ N& L; i# P' z6 R) }+ EB、正确
( @2 W% t) R4 F) h1 J正确资料:


3 s  k% e4 l! _) W$ {% f. v第35题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
% F( }# v$ l2 O( cA、错误
B、正确
1 [: w5 S1 G; h1 p正确资料:

7 b0 [: {; ]3 X& e/ n9 K' o
第36题,链表的物理存储结构具有同链表一样的顺序。
A、错误
B、正确
/ G0 z: B3 @; A1 M5 @9 k* \正确资料:
) H, l6 S( H" F& i* X5 q0 C3 f
! O: I! H- z$ u4 o( e1 Y% E
" P) }: d: F- e! q" x第37题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
B、正确
正确资料:


, h0 S  G/ H- M$ A8 g第38题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
A、错误
5 _1 m: B3 R0 \# }9 p! ?2 AB、正确
9 P% H0 b" Z" b正确资料:
* z$ f' ]- Z! h2 l6 f6 O
! n' f1 V5 `5 Q/ N! ?
$ n& O* j. A& j/ k, ~. O+ _第39题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
$ ?$ t5 E( }) n/ _# NA、错误
B、正确
3 _: N$ y( F9 L' J" \4 d) i正确资料:
# X  }9 A4 v5 r' Y

第40题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
2 }) D- p- r- a" J$ \* jB、正确
; ]7 k2 V6 _* }  ~+ Z正确资料:
& Q) L1 ^1 y* u7 I! j* J

; Q1 o" ~( p$ C/ I9 ?第41题,二叉树中每个结点的两棵子树的高度差等于1。
  }3 ~  y& x# C8 Q* gA、错误
B、正确
3 |( A* E8 M" J+ _% Z% U正确资料:

) V1 o8 f9 ]5 p  M' C. q
第42题,二叉树中每个结点有两棵非空子树或有两棵空子树。
0 P8 |/ |% a+ `: q: ?5 \  ]A、错误
* F6 c* z. G* M6 `) k: x4 IB、正确
正确资料:

% D* j# p7 Y, w1 [, Q: J/ I9 H
第43题,线性表在物理存储空间中也一定是连续的。
A、错误
B、正确
正确资料:


) X2 ~' ^, k# [3 ~7 `* g' L第44题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
A、错误
! T) I* ^9 v" j& h2 W; A* \* EB、正确
" D) ^; {: m/ u1 |/ L正确资料:


第45题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
4 |+ s: Y. F* ^8 jA、错误
B、正确
: e; i9 R1 L- |, X正确资料:
: ~; T, ~1 e7 V6 q* T

( s9 Z2 b# N" Z5 R) a# ^# ?第46题,设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
正确资料:
* p; |7 e  D1 J/ @3 v" p6 m2 M
$ l$ i" ?+ x0 _. {
第47题,设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
( r! F& p! X( w- d& a1 V% M正确资料:

- `1 D# G/ }( N% d5 M- B
0 y3 e) j0 \, p8 w2 Y第48题,设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
正确资料:

' Y4 c2 P1 [! j# p3 P# _, ~

9 C0 H$ I& R- E$ m4 c, y
$ D+ Z0 K$ R' i. M" {+ j
* u( ^) g' K5 t+ j0 n


9 z' c) _2 h9 w
( b5 }5 i5 {' v5 p, ?" ?
) H5 I- i- J+ N" L
! H. [: H- e  _; z/ |7 o2 E
6 }3 u0 C+ b) f2 o% v1 N

# R7 l9 m) x4 r; n

zuivlu57r

谋学网不错！

aa22222

顶顶，资料下载试试！

a253510464

谢谢，资料不错。明年继续