[南开大学]20春学期《数据结构》在线作业-2（资料100分）

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]20春学期（1709、1803、1809、1903、1909、2003）《数据结构》在线作业
: d6 W+ Z+ a% d9 k试卷总分:100    得分:100
6 E9 S5 x, Y+ p, t, K* w! Y9 T第1题,下述几种排序方法中，要求内存最大的是()
5 Z$ |$ F1 ^6 }  P% C3 s" g6 L3 |9 W  KA、插入排序
B、快速排序
3 `! w) |5 L, C5 i0 X2 [C、归并排序
D、选择排序
0 r! x( y1 L5 z( N正确资料:


3 [- {. X/ t. X4 |3 I7 B; G. C第2题,下列关键字序列中，()是堆
4 K+ p% l6 n' |6 k# [5 x" x4 Q4 uA、16,72,31,23,94,53
- i4 z0 i: z$ U5 Q5 [) c9 tB、94,23,31,72,16,53
( I9 o  a! V+ g$ c( u+ A7 ?C、16,53,23,94，31,72
D、16,23,53,31,94,72
# R$ m4 Z7 j% u  c7 o. q4 @正确资料


& ^4 |. K/ o2 r" h第3题,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
3 \9 w, w* @0 ZA、O(n)
5 {7 P4 ]0 p. r! }3 z% s! JB、O(n2)
' G! L6 \, P0 D3 k* a" LC、O(nlog2n)
8 |' N  ~, S, z* l! ~8 bD、O(n3)
正确资料:


5 u9 h& t8 Z' u第4题,已知图的邻接矩阵，根据算法，则从顶点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
6 i; b  E+ W9 K( D+ ?1 }+ ^D、0 1 3 4 2 5 6
3 t% m" E3 M* m2 h; k正确资料:


资料来源：谋学网（www.mouxue.com）,折半搜索与二叉搜索树的时间性能()
" ?( I" ^% b3 jA、相同
B、完全不同
C、有时不相同
% A8 \0 g6 h# fD、数量级都是O（log2n）
. j& r, T' r3 {4 |正确资料:


第6题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
* Y% J# R  f  S9 p1 l/ U7 w+ }+ FA、8
" C3 A8 E* V( M2 [B、63.5
7 c$ Z  C4 [3 K' YC、63
D、7
正确资料:
. M3 Y* C' b. t. o

第7题,单链表的存储密度（）
( f/ d0 h# g2 P" l! o1 NA、大于1
B、等于1
& b7 T" G) }" j0 {7 \C、小于1
6 E5 a9 }8 I5 k% T/ h; |3 B2 a- ND、不能确定
; V# F6 w7 R% \# {4 }正确资料:
6 z5 l8 S5 _9 V7 j& [' E* \

第8题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
/ ?' I6 G- F; F2 n: U, f* mA、栈
$ B6 L8 F! F4 W  V, YB、队列
4 Y0 ^0 P  R1 J7 Z) {C、树
& @+ W; k- z/ J7 o; LD、图
正确资料:


/ B- E/ I7 J6 v: `  f: \- I* A/ k第9题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）
A、i
9 I9 g- C$ o& c. H  Q9 h( \B、n=i
. C6 U# Q6 I! p7 p# oC、n-i+1
. P3 ], n3 z' ]! g/ l. G. c" E0 zD、不确定
正确资料:
2 v( b1 L' b8 b2 R; Y

资料来源：谋学网（www.mouxue.com）,已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()
  G- d0 V+ w1 cA、CBEFDA
( h0 V0 k  d5 V# s! s9 LB、FEDCBA
# Q4 j! d/ P' y9 M) t, NC、CBEDFA
D、不定
正确资料:

+ _+ |1 ~' c- A; H
) q# c0 `$ E! f: x6 o: V第11题,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
C、一定有多棵
$ C( r. M1 i7 L& c7 p. ^D、可能不存在
正确资料:


资料来源：谋学网（www.mouxue.com）,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）
A、0 1 3 2
B、0 2 3 1
0 H: ~/ @9 V' zC、0 3 2 1
D、0 1 2 3
正确资料
0 T8 P: u' b/ q% k0 o

第13题,在一个图中，所有顶点的度数之和等于图的边数的（）倍
5 ?6 k+ G5 {8 g* kA、1/2
B、1
C、2
D、4
" m# U( l* o! R9 u/ W3 V正确资料:
# `  ^! d8 s2 I- z
% G0 e. m$ l+ }, C% x
第14题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
A、0 2 4 3 1 5 6
& H. A  G. Y8 s/ R% GB、0 1 3 6 5 4 2
C、0 4 2 3 1 6 5
) A7 g! \0 h# ~3 G( @" S% gD、0 3 6 1 5 4 2
. }9 y$ r& W1 K: b" p8 i正确资料:
. X! r7 o$ P' y( k

资料来源：谋学网（www.mouxue.com）,设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A、n-1
B、n
3 Z2 @5 y8 V6 v* EC、n+1
6 j* d7 j+ `8 n1 MD、n+2
正确资料:


第16题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
, R) m' g0 B( q7 o+ vA、必须是连续的
B、部分地址必须是连续的
/ q& `* ~, ]* {" F  m  AC、一定是不连续的
  J) n8 M) {, v8 C  ?! H; ZD、连续或不连续都可以
正确资料
& m9 C" Z* M+ x/ E
. `! H7 u  O( J7 w' K
第17题,广度优先遍历类似于二叉树的()
A、先序遍历
/ J1 o3 Q. L# X% H+ B$ bB、中序遍历
( c# q" U( V( y, D( k0 cC、后序遍历
) |, y& C: d8 `! L: J" A0 BD、层次遍历
4 Z2 Q# u9 ~& [4 g" j! K正确资料

: c9 j/ j( u0 I5 A5 C& s' b
: |5 r' ~8 W1 k" L/ D第18题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
& u. ^' d( W  w4 J5 T) z7 a0 fA、栈
7 q9 H7 Z9 b' \( V2 c& V2 @B、队列
C、树
; B6 b0 X6 y. bD、图
正确资料:
" B$ E- [, z2 b" U- C% j

第19题,设串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
% r7 U; V, r, @9 ]4 {* j! b* wB、BCDEFG
C、BCPQRST
! M- d$ b" H. q+ g8 E6 T& Y' kD、BCDEFEF
" G7 Y- F2 A& {; e6 v! E正确资料
' B# L% d& x  B' _/ k& G
& E1 b# a" a3 K) S  U. T6 M  H4 a  q  l
资料来源：谋学网（www.mouxue.com）,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
$ N  B7 H4 q! A3 nA、连接
B、模式匹配
* ~6 N# q8 N* u" q) P! A! ZC、求子串
' e* B9 `* i( jD、求串长
正确资料:


第21题,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A、希尔排序
B、冒泡排序
C、插入排序
D、选择排序
  _' K+ [+ c1 t; x: H) J% x正确资料:

( \2 d8 H+ C4 f' o$ @$ U# j4 v8 J
. j* b3 ^; R2 C" i2 X7 @第22题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
7 P0 y) K. o+ |" Q7 k/ KA、1/2
$ n: D8 T, S2 D% R( g/ o% NB、1
' x0 Z( ]; }7 a* d& M  L- m( _C、2
D、4
正确资料:
+ K3 d1 Z) y. U/ _# x

第23题,判定一个栈ST（最多元素为m0）为空的条件是（）
+ A+ Y# {' \0 n; LA、ST-top0
B、ST-top=0
C、ST-topm0
D、ST-top=m0
4 u& w( c6 W2 y# D( i% _$ T5 A& G正确资料:
9 T5 p1 B8 B8 J3 Y

第24题,有8个结点的无向图最多有（）条边
A、14
$ n( i- O) C0 B: [, j% PB、28
C、56
6 Y) d  ~1 \6 DD、112
, ^4 a( z$ c$ a4 K2 m正确资料:


! T. e+ w, v, k9 Y资料来源：谋学网（www.mouxue.com）,已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（  ）
$ T# f- y1 n2 X& ~1 U& m7 DA、0 2 4 3 1 5 6
B、0 1 3 5 6 4 2
" Q) w2 i8 a( u, LC、0 4 2 3 1 6 5
3 s8 G: b5 x8 [  _- N1 J4 ^D、0 1 3 4 2 5 6
% _) B7 A1 ?8 [- b9 T正确资料
3 u, H8 n4 B  l

第26题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
A、希尔排序
0 ?( z& `: J8 {: w! e$ fB、归并排序
C、插入排序
D、选择排序
2 U  n  o8 }& P$ [  G/ q6 m8 r# R7 |正确资料
' t' ?! K6 }7 E1 X0 j6 }% s' M

! t- ?7 [: ^4 k! j: w第27题,串是一种特殊的线性表，其特殊性体现在（）
" H# H2 i$ g8 U$ Y- \; C* _8 MA、可以顺序存储
' C, q" O. x# hB、数据元素是一个字符
* i7 x% ?, C% I" M. [( m6 b. CC、可以链式存储
D、数据元素可以是多个字符
* Q1 D2 P) U9 U( F正确资料:


第28题,深度优先遍历类似于二叉树的()
$ A9 D- n$ _( u6 c9 P* x; x8 y4 kA、先序遍历
B、中序遍历
% d! u  U( u# T/ G' n  uC、后序遍历
D、层次遍历
正确资料:

$ G* }4 R) P; |7 n0 Y
8 m' Y8 h7 Q' K# t5 d第29题,对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
A、从小到大排列好的
+ g! s4 n6 O7 r% z$ E; p0 s9 RB、从大到小排列好的
C、元素无序
' J  X0 H+ a$ k- v8 o# |' s  YD、元素基本有序
# p  L; Y3 s5 l) _, ]% G+ d正确资料:
2 Y7 V1 }  U- d2 S: i* n

. U& h0 H: A1 l3 f: _) P# f8 Y. P- B资料来源：谋学网（www.mouxue.com）,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
9 A9 I! V% ~3 n) X4 s; [A、79,46,56,38,40,84
* O1 I7 q+ q2 K2 b5 _B、84,79,56,38,40,46
C、84,79,56,46,40,38
( k3 a# R$ U$ g0 F8 k1 y0 M  _D、84,56,79,40,46,38
" C4 B$ m% J, z2 d' g! Q正确资料:

, T1 J; E0 d9 _
第31题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
B、正确
( u/ m$ q! e# V正确资料:
% e; f$ ]( v0 M) t
) e8 C. `* x, d6 U! f' l/ r- `
, y9 A2 \4 T1 w: m$ v第32题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
( V* f/ |; ?1 d4 yA、错误
B、正确
正确资料:
! G4 J  L8 _7 E) g' f2 @/ ]1 C

  a$ t5 w  W8 d2 U9 l9 ]+ O+ x第33题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
B、正确
正确资料:

* e. ]: W9 h3 j" }  w+ y% G
* ~: D0 {; a( j9 T& `1 ^第34题,链表的物理存储结构具有同链表一样的顺序。
A、错误
9 F' K. {) j( E+ VB、正确
正确资料:


0 A) n2 a/ X$ Z: P! m9 @第35题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
  F6 d! u- }; ]# [A、错误
& Y$ D  B2 H- P2 I; mB、正确
$ b6 j3 ^: [  G3 p正确资料:

' \" E+ a  H+ X2 }
! l$ u; t0 g8 S* ~( G2 _第36题,二叉树中每个结点有两棵非空子树或有两棵空子树。
% o1 F  P" L3 R' s1 [% DA、错误
) g! z( M) P5 u6 LB、正确
7 N! f; w+ j2 n" S5 L正确资料:

+ b# h7 M1 t5 Z$ j6 a( o: V8 z+ ~
! C/ j9 |# M3 X  A9 v第37题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A、错误
/ r- e( c7 f& ]/ F2 K1 F9 ~# l2 sB、正确
( Y0 J/ I0 A! T6 p正确资料:
6 K/ \0 g( J5 g1 a( M% i# u

: Y- U0 P. i$ @1 N8 ]. r第38题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
) k( ~  y7 n# t. t! E  b" C- WA、错误
  b( w* H  a* t5 o; DB、正确
7 v+ f9 b. d* l( u) L* b正确资料:
7 ?  x6 f, a/ Q) I+ A

第39题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
A、错误
1 {/ E/ M" P) o2 S' ?1 W2 yB、正确
9 ^& r( Y2 y. W; }5 {! R正确资料:
5 Q8 ^. I, [* ?9 a9 K

5 ~1 ]6 a4 v/ G6 H$ n* M第40题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
& k2 Y8 X9 l3 _( x! Z+ ~; fA、错误
B、正确
正确资料:
9 J% k6 v# y' B3 s( v) p

第41题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
! R2 ~, k+ B$ N- V: d8 rA、错误
/ U! P2 N0 R- O9 y' [" tB、正确
正确资料:

& e- A0 D5 S; R2 i6 a, T4 m
第42题,二叉树中每个结点的两棵子树是有序的。
# o! {) S- A7 S& JA、错误
5 l' p: @( X& V) i8 D1 kB、正确
: W: ^$ K* P# A. \0 r# q$ G/ B% A! K正确资料:


0 C* a7 x4 Y: ~1 x9 S: E: F4 y' `  @3 S1 s第43题,若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。
A、错误
B、正确
正确资料:
8 A1 {' |- a7 }' w; o$ \
' z# ^- P7 d: v! y- w  d+ Q
+ [, k' l* w" F+ ~8 f4 I第44题,线性表在物理存储空间中也一定是连续的。
A、错误
  k2 E% S8 E3 d& mB、正确
正确资料:
9 I. `  R% j. p/ z2 t4 A

第45题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
) m* D6 D+ d7 E% N! KA、错误
( f" B& w+ X; k) v8 w( x$ T; h) _& @B、正确
, ^% O& V# ^- T正确资料:

: b5 g) n" |9 G$ y0 j
5 q1 ]2 }1 L8 a第46题,栈和链表是两种不同的数据结构。
3 H5 z0 {+ {# }5 HA、错误
; e0 l  D* e: e0 }9 eB、正确
$ ~, y# P6 B9 y9 t! I$ }4 k正确资料:
1 G* g! {  n8 d( u9 @; t7 W" L

第47题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
( Y. u( b" q5 Y% J, z! I; z, l) vA、错误
B、正确
正确资料:

5 V% B+ C  F: H- }# \! j2 r2 J: c' a
$ l' n8 M4 ~* S* B第48题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
A、错误
. F+ ~5 G, i( D  d5 M5 C4 |  r8 ]5 b5 iB、正确
正确资料:
1 c- p& L: E. M- _. O8 K

3 V! Z2 t$ |# X, n第49题,顺序存储方式只能用于存储线性结构。
0 b; O: M, o; |. VA、错误
6 f  R0 ~- P: P1 ^8 pB、正确
正确资料:

5 y6 }/ [7 k# Q; J/ j
) T$ j" ]5 F' J5 l: w+ y资料来源：谋学网（www.mouxue.com）,线性表的逻辑顺序与存储顺序总是一致的。
( @( b4 _/ a& P8 ]' Z- u" JA、错误
B、正确
. G5 u8 M$ s" o+ i' F3 F+ q正确资料:
! W( ]. `* \- W
+ u4 K1 f- t8 W; Q7 F& ~
+ O; C: S% @. O& l

6 l& B8 `1 m/ m! o+ p
$ o! B7 r- Z7 k! J1 D


4 Z4 X' [# W- D. S* j! n
' f, w3 J  D2 o- T$ V
" o& H6 t8 t3 U4 k$ ?
, \, Z. ]: {1 _* d7 ~
2 \  @  O4 i# F+ r/ _

) O: x( Q$ f* G$ \8 I$ P8 @
$ z* q% F* Q" [+ _/ `


0 ~- W# o; Z( W# Z. J



$ m& `0 d% A. f' o



3 m, v: ^" ~. P* p1 W) k& t