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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]21春学期（1709、1803、1809、1903、1909、2003、2009、2103）《数据结构》在线作业
* J' ^( u' V1 P# t- g试卷总分:100    得分:100
第1题,快速排序在下列哪种情况下最易发挥其长处()
A、被排序的数据中含有多个相同排序码
0 A+ w2 D4 f* x7 NB、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
正确资料:
- V8 [9 Q$ t6 h# y) Z1 a
9 k2 Y5 Y1 ]# W/ ?$ `! J
第2题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A、0 2 4 3 1 6 5
B、0 1 3 5 6 4 2
* z5 m1 s4 i* e9 G2 u& oC、0 1 2 3 4 6 5
D、0 1 2 3 4 5 6
正确资料:


& x% R1 ~& `. a* ?: K: |2 k! j第3题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
# o& T, ~! [) j# P* M( zA、QU-rear － QU-front = = m0
, p( T, O2 u1 j3 |4 NB、QU-rear － QU-front －1= = m0
$ n% A+ J$ N# e2 dC、QU-front = = QU-rear
D、QU-front = = QU-rear+1
正确资料:
8 s. Y% v5 ]$ v0 f  i  F

第4题,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
A、0 3 2 1
, D# z7 J. A5 }( }. \9 Y8 nB、0 1 2 3
C、0 1 3 2
" t8 \& y( Q+ \D、0 3 1 2
正确资料:
# z2 `2 m" Y8 P
8 E3 A/ l, [! Y$ K
6 v* ]/ [& ?7 n4 a资料来源：谋学网（www.mouxue.com）,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
C、一定有多棵
& p+ f7 U" Z4 q* y0 y5 Z5 T7 ?D、可能不存在
正确资料:

4 _) R3 }3 n6 W: \* X0 B" Y
" |2 G* ~: G. O0 u4 u! Q) w第6题,链表是一种采用        存储结构存储的线性表
A、顺序
B、链式
C、星式
D、网状
* T; `0 N0 G* N, @0 H正确资料:
9 |5 v" o! e4 `+ h+ [

/ C: V! l" L( G! d6 k  W% C6 Y第7题,不含任何结点的空树（）
A、是一棵树
B、是一棵二叉树
2 P9 |4 ?9 Z- F% G( hC、是一棵树也是一棵二叉树
$ p/ K/ a5 P7 rD、既不是树也不是二叉树
正确资料:
' G- \( V9 L1 S7 x/ i
8 S& O% m$ o; d1 _. o0 r
第8题,将5个不同的数据进行排序，至多需要比较()次
% `- r1 }1 ~7 I% p3 x1 E! [A、8
B、9
  d: W4 u9 q0 Y% {C、10
& |" _0 C7 G( B$ a, y! S/ L6 u& Z/ ?) ID、25
正确资料:
  o; `1 W4 s+ [, q8 Y' C
) |$ n" Q5 D' M0 J& U. B, r# r/ Z7 t8 V
: L' J3 t# Q* J) k第9题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
B、队列
C、树
D、图
! z# d5 x  V1 C6 @/ U8 J正确资料:
: t& k' ~" K5 @4 {7 D8 W' c  |

资料来源：谋学网（www.mouxue.com）,链表适用于()查找
A、顺序
B、二分法
C、顺序，也能二分法
D、随机
+ T6 }4 J; l8 q5 d. w9 B+ `% ?* |; J正确资料:


第11题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
, n- }3 [# U7 \, D+ ^, `; YA、1/2
B、1
C、2
2 U6 \- v! G- j& H* L! ]D、4
" q4 W' {* `5 ]( O) u+ d正确资料:
3 E  v/ j  _0 }. ?9 S7 x1 s

资料来源：谋学网（www.mouxue.com）,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
& Q2 S- J$ d0 ^% Y. Q& C) }A、79,46,56,38,40,84
B、84,79,56,38,40,46
C、84,79,56,46,40,38
D、84,56,79,40,46,38
9 t8 q0 q" v- \6 g2 s/ h$ ~正确资料:

  M9 |' {8 n; ~: _: e
第13题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
/ _: ~/ Z1 o# F0 f2 q8 i2 N8 OA、循环链表
B、单链表
C、双向循环链表
0 [' {4 J3 N+ T7 N: ^9 z: x) O4 \D、双向链表
8 H- n) f7 k( `& ~* H+ N正确资料:
% K8 H7 E2 b7 V0 Y- Z
* S3 O3 E# E- @- z8 b5 `$ y
第14题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
A、8
/ T6 c; f) H, W( Y. h1 lB、63.5
/ r3 ?3 g- ~* T& mC、63
- O; p1 O& D$ U+ jD、7
' [5 _. T- Z4 u0 J+ P$ u. ?% U2 W  o正确资料:


资料来源：谋学网（www.mouxue.com）,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
. M- [1 }$ G6 P" E7 ^A、20，70，30，50
B、30，88，70，50
" ?! Z! p" f9 ?$ X' x: [C、20，50
D、30，88，50
正确资料:
+ |! y. s0 \8 g- G
$ X2 n  `) q+ ]; u' Z4 J9 t5 H. }
0 O9 {  V3 x! y0 \第16题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
" J$ _# G1 N, @3 w& zA、希尔排序
B、归并排序
C、插入排序
D、选择排序
正确资料:


第17题,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
A、
B、
; ?- K9 D6 I5 U, E) s7 OC、
D、
' ^# S; N  Y2 y; h" `正确资料:
/ S  u1 i' d7 i; S

第18题,有8个结点的无向连通图最少有（）条边
A、5
B、6
# s/ D$ D+ o3 W3 gC、7
" P# A( s9 D2 d+ F$ UD、8
0 y: y$ A1 Z7 s4 r正确资料:

. m# A$ a& L$ l. N
第19题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
1 a( L# z6 \. N2 i- T0 fA、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
! _  M) S" o9 x+ W7 g) |C、0 4 2 3 1 6 5
1 I7 S7 r" \7 ND、0 3 6 1 5 4 2
+ E8 x3 O1 X7 |% q正确资料:

% L$ \) Z; p6 I( f. A/ b/ c. I1 u
资料来源：谋学网（www.mouxue.com）,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
A、ＡＳＬ＝ｎ
2 c, K9 _; R" v. p: ^4 y/ ?# |7 DB、ＡＳＬ＝（ｎ＋１）／２
, X; @0 U  @" l0 I" pC、
" Y! h1 k, x4 Y& t% M1 yD、
1 K$ x( U7 C- R0 S/ E! M. g. Y正确资料:
" f) f# N3 s5 h; n7 X1 o

, D$ X0 O, O! G第21题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
( a) |6 B/ w9 {+ s3 H' F  ?A、0 2 4 3 6 5 1
) O( M5 C9 i, c& l; L% O# BB、0 1 3 6 4 2 5
C、0 4 2 3 1 5 6
D、0 1 3 4 2 5 6
正确资料:
2 @* s3 b) W& K5 v$ b. H( y" i
# i/ e$ m# j9 M* {8 z
, E3 A( B5 k* z; u; {) I. a第22题,在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
  i  w, R& `: R0 r' UA、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
7 L# X" P6 l: }" ~& ]* t2 jB、在第i个结点后插入一个新结点（1≤i≤n）
C、删除第i个结点（1≤i≤n）
$ ~) o! y% o. \0 O0 p, RD、将n个结点从小到大排序
正确资料:


+ B9 s/ K6 @# S# _) _第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
B、BCDEFG
C、BCPQRST
D、BCDEFEF
3 i: M; q& V2 [: H1 \' s  E- v0 O正确资料:
. l0 J- W) v* P
; I4 T: n/ ?  J, R2 T4 R4 f
' a! |2 t2 E5 s/ K! }8 B! @4 ]第24题,数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为
A、r－f
$ @% \3 I- M% U' {B、（n＋f－r）% n
C、n＋r－f
D、（n＋r－f）% n
5 s$ e2 U  e+ G# A, }- Z$ L正确资料:
9 G  ?- M, N9 x5 r
2 N- @2 v5 V/ G- m/ o: H
资料来源：谋学网（www.mouxue.com）,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
+ n" B! ]- n' d- C! iA、3
: J6 w, F. m" G4 q. E5 F9 OB、4
! D4 z/ m. U! T$ Q. IC、5
+ A$ V, m& ~4 n2 b+ T" dD、6
正确资料:
- v" n6 J! r8 \$ X$ |: ]( z. [
2 N+ S" Q' _0 V$ G% f- P& T, j( Q
第26题,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
B、0 2 3 1
/ _. q0 ~: w: {7 {- T! n7 H& y7 vC、0 3 2 1
D、0 1 2 3
正确资料:
2 m, w& y4 U# h1 ?7 o" f/ l

- Y8 q! O: v5 u% n0 p3 N第27题,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
& q5 H! v8 \" r& E" vA、O(n)
$ M/ x/ m* {6 D( vB、O(n2)
+ U7 Y/ d; ~0 fC、O(nlog2n)
D、O(n3)
7 [2 Y" F9 e1 G  n$ i' Y正确资料:
) ]/ I! ^) I4 o* g- r/ F5 g

第28题,对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
0 @6 l& d. u5 hA、从小到大排列好的
B、从大到小排列好的
7 ^, X$ H' `. `( AC、元素无序
; [; p2 P8 n4 \1 T# h. }) _D、元素基本有序
0 e% J$ @0 t5 g$ U正确资料:


第29题,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
- E( i8 r' D0 d0 c1 S% M+ rA、0 2 4 3 1 5 6
B、0 1 3 5 6 4 2
C、0 4 2 3 1 6 5
; v7 r+ c* O8 A  }+ D- DD、0 1 3 4 2 5 6
正确资料:


5 ~8 Q% J$ q- h资料来源：谋学网（www.mouxue.com）,折半搜索与二叉搜索树的时间性能()
A、相同
B、完全不同
  h& R  e* [0 K' o0 b, HC、有时不相同
: E& q* i7 S; Q5 t0 O' |D、数量级都是O（log2n）
' ?( {5 a8 z5 f9 J( P% D# V* c: x  s) \正确资料:

8 b8 B2 A, C) T. c0 K$ ?0 `
第31题,具有12个结点的完全二叉树有5个度为2的结点。
A、错误
B、正确
0 i7 @* t! _) [1 Z4 _8 X3 X正确资料:

  Q5 F: U# V* y/ K6 y
, z6 r3 |0 d, f; L第32题,链表的每个结点中都恰好包含一个指针。
A、错误
2 G2 @) l7 X% i% B6 NB、正确
正确资料:
. y+ H' i0 i. V8 B9 H

第33题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
  S! h% D* ]! sA、错误
B、正确
+ E- f# D2 N* A" C正确资料:


第34题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
! Q' B" Q2 S* O* _4 ]! JB、正确
! F% R% E2 B' n. ]. `. k6 Z) {正确资料:


第35题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
7 S+ }0 V; w5 ^; q' cA、错误
/ V9 d, q4 I, N4 l+ @( V4 gB、正确
正确资料:

  o- B. D7 l' E/ s; S3 Y
+ j9 o! I, d7 p: h第36题,栈和链表是两种不同的数据结构。
3 `' K- j8 P, S* o9 RA、错误
B、正确
% b( c; h: B1 I1 S, p( O: g' ~正确资料:
8 U! Q- Y; Q: G9 l
4 b% h; E' h; B2 ^( Z
第37题,线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
0 G, u! i! f9 L9 m) Q" ~# sA、错误
6 C3 I9 K$ v/ J* oB、正确
0 J  B0 }+ H2 z$ @8 H0 Z4 |正确资料:
8 H- Z' S1 W% K: R. I
- e* W' }9 Q' r( K. }. q5 ~2 u# J
; S5 x, ~6 Z' _2 U第38题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
7 I2 k1 A& `: j- C$ XA、错误
' P: ~) j: x) |5 T5 qB、正确
6 S, m8 G1 D# m$ g. l正确资料:


( V$ R( Z2 A6 B- Z. X4 I第39题,栈和队列是一种非线性数据结构。
2 T, z1 J* f; ?5 Z' R5 NA、错误
B、正确
5 ?3 e# D6 j: [& {* W! H正确资料:


- U, D3 P3 ?! I6 y! o第40题,线性表的逻辑顺序与存储顺序总是一致的。
- U: m- J7 {% [- n' h9 ]A、错误
B、正确
正确资料:
% g, A* t  X8 z& d

第41题,线性表在物理存储空间中也一定是连续的。
8 Q6 `8 L+ B1 Y( n  MA、错误
B、正确
2 m2 p5 i0 B" |, k1 A- Y; g/ Z5 f正确资料:

* q; Y0 X0 o( o, p2 p4 z) T3 F
第42题,顺序存储方式只能用于存储线性结构。
. o( J9 H! Z& O$ Y( bA、错误
  Z/ C0 J! f" U3 \B、正确
; @+ x2 H; b( g5 b, q正确资料:
  y- x- g9 B7 M1 X4 R9 G% T: g
# d9 Y- Q3 I! Q/ U; g+ ~  z3 A
第43题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
6 |/ J% A- U8 nA、错误
2 A. t" B! B0 X9 bB、正确
& s) O7 C9 q6 p正确资料:

! l0 o1 G# \8 D, T, h1 P
第44题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
$ e. G* Q0 A1 H; ]/ }: Z2 dA、错误
% R5 _& P$ O6 z+ V' Y& e' J/ WB、正确
正确资料:
/ a2 O4 F! H# Q4 [, \8 m0 N! W

3 V+ e1 a% t3 Y8 a第45题,二叉树中每个结点的两棵子树的高度差等于1。
2 Q5 _( `8 i. K% g7 b, ?# KA、错误
4 H% @% {2 @. v7 ~& V1 s) R. N4 B+ uB、正确
8 c! G* k% Y9 r$ z3 ~0 p( e正确资料:


$ X% u: ?# R( a; g8 D0 O/ ~第46题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
A、错误
/ B+ F7 K: g" tB、正确
正确资料:


第47题,二叉树中每个结点的两棵子树是有序的。
# k  w# j  k" m. b, Z2 J1 QA、错误
B、正确
正确资料:

' n! o, T% ?( O
' x8 ]! P  g3 Z3 S$ |第48题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
A、错误
B、正确
正确资料:
9 V+ A, H7 D! f  f% {3 y: i9 h- A+ b4 A

第49题,二叉树中每个结点有两棵非空子树或有两棵空子树。
5 v2 r. [$ K& a/ s5 y7 k% ^: nA、错误
B、正确
' ~1 x  M% A% c! a正确资料:
1 v( i* N& N2 y( L4 b( d  F

7 \# @4 @% m5 K+ }+ S( l- z资料来源：谋学网（www.mouxue.com）,链表的物理存储结构具有同链表一样的顺序。
A、错误
$ y+ G6 ]! y0 p& _& Z' tB、正确
& {* o# J8 X* F. D% ?正确资料:








* Z3 p4 K) P, p/ w
3 N/ _+ V+ E' d" J) h% G* s
  a, @0 v, G5 c4 o" A% H6 ^. q* b



5 |+ x4 \5 @" `& z. f