南开21春学期《数据结构》在线作业-1100分

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
试卷总分:100    得分:100
第1题,快速排序在下列哪种情况下最易发挥其长处()
- N7 X0 {! i5 \! L$ z2 X$ z# jA、被排序的数据中含有多个相同排序码
6 v$ d2 v: g: K+ X  R# g! ZB、被排序的数据已基本有序
C、被排序的数据完全无序
2 ?- A& J; D7 Q+ n/ N8 o0 gD、被排序的数据中的最大值和最小值相差悬殊
7 v( r: Q2 |  \6 y6 @正确资料:
5 C8 x; r9 f! Q+ }+ ~. f

% Y  a5 a* q; a  g8 n. Z第2题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
4 n4 k: E' y4 wA、0 2 4 3 1 6 5
% u- ^# I1 Z4 s! G/ o7 d3 g& IB、0 1 3 5 6 4 2
C、0 1 2 3 4 6 5
4 S' ^8 q5 n2 CD、0 1 2 3 4 5 6
正确资料:

. c& E- C" D  c, T6 o. P
第3题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
+ Y" g; q& o; HA、QU-rear － QU-front = = m0
4 i: D0 |% i, t& ~( EB、QU-rear － QU-front －1= = m0
C、QU-front = = QU-rear
D、QU-front = = QU-rear+1
3 e5 D, |# y5 i正确资料:


/ J: T+ N; n7 M) p1 Y- D0 ~第4题,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
4 y, U% {3 v" j# w: GA、0 3 2 1
# w3 A7 v& M2 k# j& T) l/ i; v( FB、0 1 2 3
C、0 1 3 2
D、0 3 1 2
正确资料:
  k! B4 w4 ?& r( Y2 H; c0 i8 ?

5 ^- A9 W/ n: B8 I资料来源：谋学网（www.mouxue.com）,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
: I& h% u0 P" dC、一定有多棵
1 D+ _5 r1 m9 F0 AD、可能不存在
! s! U/ ^5 }6 f0 f( P2 b正确资料:
9 J, X9 p- S3 \& P2 x7 y* m

第6题,链表是一种采用        存储结构存储的线性表
A、顺序
B、链式
( ?7 [5 R) a" I1 {C、星式
+ c$ ], z+ I7 D: Z  q9 _0 f! U8 R$ @D、网状
$ {! |" x: H( R9 ^正确资料:


第7题,不含任何结点的空树（）
2 l/ [' Y, F* U! H# H  D6 {A、是一棵树
+ m" l- i: W6 ^4 d' IB、是一棵二叉树
C、是一棵树也是一棵二叉树
2 c4 X9 K4 }9 c+ ^D、既不是树也不是二叉树
9 f& }# o5 n' F. B正确资料:


第8题,将5个不同的数据进行排序，至多需要比较()次
A、8
B、9
C、10
D、25
正确资料:


4 b9 V5 S$ Q" Q' K" x% |8 b( V第9题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
1 O; c; C7 F  z: C5 x- p5 K. O& {A、栈
B、队列
! R7 m5 C% i2 G' n" f$ mC、树
D、图
正确资料:


资料来源：谋学网（www.mouxue.com）,链表适用于()查找
  Y+ i; [' n9 G& c! s" m/ R, B. ~A、顺序
B、二分法
8 r4 f4 m9 ]/ ^" aC、顺序，也能二分法
+ p, W% a: `4 I! @. UD、随机
) U: I1 S# m, h* ?正确资料:

: r8 V0 N$ s) k) r( r
第11题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
# t  I2 S6 K* J4 ?! P) r, ~+ ~5 gA、1/2
! z% l! \. |' z1 v# X! d$ f; {- BB、1
C、2
9 a/ x* d8 r  g' V5 aD、4
正确资料:

2 u# x% E2 [- m! V$ X( |9 G* c
资料来源：谋学网（www.mouxue.com）,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
A、79,46,56,38,40,84
, _$ S  C  {  B: pB、84,79,56,38,40,46
C、84,79,56,46,40,38
& w5 j' P  a( bD、84,56,79,40,46,38
正确资料:

; u& y# N6 v) ]  `5 W
) _( \# M+ p/ L第13题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
A、循环链表
B、单链表
5 ^& {7 U+ K6 n/ GC、双向循环链表
D、双向链表
正确资料:

# o" e8 z: ?2 g2 I" g" I
第14题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
A、8
& l3 s7 a" C, i( l$ JB、63.5
( N$ O( o; n- W& h; {" u- y( sC、63
D、7
正确资料:


2 q/ B! p. S9 I; J# S+ _资料来源：谋学网（www.mouxue.com）,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
A、20，70，30，50
B、30，88，70，50
C、20，50
D、30，88，50
正确资料:

' I8 s. {3 J. w% H4 v3 J6 _
第16题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
A、希尔排序
8 o. l4 p) k+ i- WB、归并排序
* q1 u3 X! w' H: x9 E* A1 M1 tC、插入排序
/ W1 O7 l" p+ S/ g. ~" `( dD、选择排序
正确资料:
  f- B$ S& f  I. |* @

第17题,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
A、
B、
C、
D、
' S  a9 {; M$ Y+ R- ~正确资料:

9 Z3 ^! K0 T7 w- r+ A
第18题,有8个结点的无向连通图最少有（）条边
2 q6 o$ y- `0 D4 V! FA、5
6 v  k* R* X& c" W* p6 Q' DB、6
C、7
0 [; R# Q3 o( m* z4 X* {  B9 @3 sD、8
8 q; u/ _. J8 g( f正确资料:


# [7 M) E. D9 [! w- F5 H4 z( t第19题,已知图的邻接矩阵，根据算法思想，则从顶点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
D、0 3 6 1 5 4 2
7 T. l- D6 s; d8 |% J2 R/ l  Q! C正确资料:


资料来源：谋学网（www.mouxue.com）,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
# k! z, I. S9 {9 A/ cA、ＡＳＬ＝ｎ
B、ＡＳＬ＝（ｎ＋１）／２
C、
' o- P/ w1 w! X) c9 p5 {D、
正确资料:

8 [) _# c* G& n& t+ m
7 u. H" L  B/ Z) |$ ]6 V5 K第21题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
, e+ {9 a; Q4 N) r+ @: xA、0 2 4 3 6 5 1
4 W# K$ E1 }% {! v4 j; F, z0 WB、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
& ^+ I& V$ n3 |# m1 [D、0 1 3 4 2 5 6
正确资料:
: G& P) p8 d- u4 X' i
# s1 l  {  z' ?4 G& |8 N4 g: R
第22题,在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
: ^  l$ |* t; {8 u7 C" R% {* k7 aB、在第i个结点后插入一个新结点（1≤i≤n）
$ p9 G2 e# S1 N2 ^9 _4 Z( p  ~C、删除第i个结点（1≤i≤n）
D、将n个结点从小到大排序
正确资料:


6 u' S- f6 l& d3 q$ C, O第23题,设串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
) w- N9 ?1 A0 k' ?1 N  T' g/ ]B、BCDEFG
C、BCPQRST
D、BCDEFEF
正确资料:
0 m+ i- |. a* O+ }

7 g) a* n% O& d' _% o第24题,数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为
/ v3 }  z! X$ u; m  S$ iA、r－f
B、（n＋f－r）% n
C、n＋r－f
D、（n＋r－f）% n
9 R: U* @" u/ j1 _8 d; r" Z正确资料:
# J: h4 ^; g5 D

资料来源：谋学网（www.mouxue.com）,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
0 b! g! N' Z  }5 E" EA、3
7 U: F  _! w7 n' y  b6 A& j% kB、4
' M  u+ Z3 L" f7 b) XC、5
& d; b& X2 w2 B( s! yD、6
  o+ p* c2 o* O# e% w正确资料:


第26题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
; }1 n/ [( x0 b8 n' I+ AB、0 2 3 1
) E' M" E! m7 h1 m2 ]C、0 3 2 1
' Q! }8 Y, w. }# E$ s/ mD、0 1 2 3
# \* {* [! C" d$ D8 c正确资料:
1 A7 Y+ _$ @; y3 r& u

: E* J( a$ v) f: o3 D第27题,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
A、O(n)
. x2 X3 t! [9 QB、O(n2)
C、O(nlog2n)
D、O(n3)
( E: y) d( o* S  `正确资料:
% l( S1 @4 \' [( `$ ?
) [9 m/ ]& f- U2 o. n% V2 r+ X
第28题,对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
A、从小到大排列好的
) {6 t! m/ z, Y- LB、从大到小排列好的
/ c' _  J; [* ZC、元素无序
D、元素基本有序
, ]; V2 k# m" a0 i! L: t4 \! v正确资料:


: M0 m) h& ]8 f4 X第29题,已知图的邻接矩阵，根据算法，则从顶点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
2 @) ^4 P+ X! d5 i, O( r& H) ^D、0 1 3 4 2 5 6
. V) G2 y9 }( N9 S6 N. D! w正确资料:
! f" E- ?3 d1 S
$ A1 {. o0 @+ L/ B3 }
- X$ b; V$ B5 v/ v3 Q9 A  J资料来源：谋学网（www.mouxue.com）,折半搜索与二叉搜索树的时间性能()
5 i! D, V4 f: L; OA、相同
5 z9 [$ \' d$ D0 CB、完全不同
7 T/ h: X! ~+ ], vC、有时不相同
D、数量级都是O（log2n）
& E" M6 z# f* d6 T: J: e! r- V正确资料:
  H2 \4 W  P5 P6 T0 u6 f
4 @$ D9 J$ s, ~* U0 t; a
* ~/ d; c- P. }" K! }! U, N; X第31题,具有12个结点的完全二叉树有5个度为2的结点。
" u% O2 p2 n3 C! lA、错误
3 v* `; i. U7 c  kB、正确
正确资料:
+ @5 g8 e; a: j" ^! p* h% g

: R4 G& p/ z# F9 B+ V! o" D第32题,链表的每个结点中都恰好包含一个指针。
A、错误
B、正确
正确资料:
) o" ^$ G7 Y) ?8 i3 ~! F1 z

第33题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
4 l, v( T! N+ O4 e! l, YA、错误
6 s3 `. }( _0 ZB、正确
" o, z" p! K& c3 e. J5 D正确资料:
$ }! q9 p! Q1 q9 e0 l* v
# ~0 s0 ^/ C. O( I  l
第34题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
& T; [/ N6 b4 ^, Y+ N% c! oB、正确
正确资料:


2 t3 E7 @8 l& L" J第35题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
. q  _9 }6 e7 d/ T2 p0 pA、错误
B、正确
正确资料:

7 O; v) g5 a1 F) U7 S
第36题,栈和链表是两种不同的数据结构。
2 Y, }! u8 m+ k: S! `9 D" OA、错误
5 a" @) D' a3 z5 H* rB、正确
! u. X0 A- l/ z1 ?! L8 v正确资料:


5 |( u. c* ?9 ~% t7 n第37题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
0 p- v0 d7 r% ^1 M: H0 s9 o2 ZA、错误
( K: `# \8 {0 l0 G8 M; pB、正确
: f! Y5 S, A/ S2 J正确资料:

, K! C& k  l* X/ A5 A6 J& L
+ r. m$ g$ X$ p1 s( n5 P" g第38题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
A、错误
B、正确
正确资料:

1 @- C$ @3 A& m( B/ F7 M1 Y
第39题,栈和队列是一种非线性数据结构。
A、错误
B、正确
" d0 s) w  b% l/ a; \0 ]* D- c正确资料:


, I5 `7 b% g0 k8 w9 F6 p: F第40题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
/ t0 c2 t$ d5 ^0 X4 sB、正确
正确资料:


第41题,线性表在物理存储空间中也一定是连续的。
A、错误
B、正确
8 D# i! E$ O8 `6 @2 b1 u. j正确资料:
% q/ V, R" v3 B9 L. \

第42题,顺序存储方式只能用于存储线性结构。
9 j* ^# ?7 F% W1 ?A、错误
: W; A4 h$ {1 Z5 e( S! U) XB、正确
0 m/ c9 E# V/ z. f8 u正确资料:


第43题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
6 F- F- g6 s( A" W5 j% @2 YA、错误
9 |; D5 A' l' U; V7 h/ y% `B、正确
正确资料:
9 E1 q$ b- p4 `3 v# \. g! n! D
7 w/ P  h8 r& [) I7 [8 ~, ]
  w' n( B0 g$ S( [第44题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
$ \6 W" B/ b2 J. y, q) @/ [% v3 r# HA、错误
+ u4 ?+ t1 K& u  jB、正确
正确资料:
5 q( h, [3 ^2 N- G

% i. S' h  c! ^( _第45题,二叉树中每个结点的两棵子树的高度差等于1。
A、错误
B、正确
正确资料:
3 K4 w$ }% b4 [7 E& _# Q+ }" D. S
- C# s# U1 Z9 J9 g4 W0 l
第46题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
A、错误
/ U' C+ K) d. s% b; A8 GB、正确
% \+ ~! V4 Y/ v! t. @8 n! U正确资料:

5 e  b9 S4 |1 ^0 F% S% ?9 E
第47题,二叉树中每个结点的两棵子树是有序的。
( Z9 u# }$ Z5 c  B' @A、错误
B、正确
0 a% ~3 g+ F% o% C; Q4 `% u正确资料:


第48题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A、错误
% W+ L/ @* L% `: Z, y3 uB、正确
4 C" ?# p" ^- n! P' Y6 A. [正确资料:


7 Z. h' Q1 v' h) K  G第49题,二叉树中每个结点有两棵非空子树或有两棵空子树。
A、错误
B、正确
2 X7 s# B3 M9 j# z/ }4 t/ W/ M. @正确资料:
- K5 N8 L/ l  O" D" C

资料来源：谋学网（www.mouxue.com）,链表的物理存储结构具有同链表一样的顺序。
3 L- a, v5 ~2 X1 ~! q3 i) MA、错误
* e  x- `( s0 Q* a+ N, @& D+ x2 R* ZB、正确
( z: o: M3 |, v/ g6 t2 T正确资料:
6 L) B" Q% Z- L
% X8 x/ |3 h7 o. C6 v9 w5 W1 `5 N

- C/ \5 c! u0 U, W# P

& K* D! T* k, w9 U1 a/ o, u
+ [7 I6 n; D" G# `6 f
. P" y2 w0 x1 ?/ d# X% n
" \2 h* M3 u% W0 G2 Z% \$ E
1 w0 K; T& R# ?" q
- u( T$ d8 e: N+ W% F: E7 x* b' Z