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

admin

资料来源：谋学网（www.mouxue.com）-[南开大学]20春学期（1709、1803、1809、1903、1909、2003）《数据结构》在线作业
/ u  ]2 b9 J4 O8 n试卷总分:100    得分:100
2 U) i$ ^% [( R' G3 X8 a0 U1 g第1题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
A、必须是连续的
- \+ j+ l' i- d' V- l. F# QB、部分地址必须是连续的
C、一定是不连续的
D、连续或不连续都可以
正确资料


* M3 T  Y( b" f% ^- X; y第2题,一棵具有 n个结点的完全二叉树的树高度（深度）是（  ）
2 w) ]' _2 p1 H  l/ ?A、
B、
C、
# z( Z% x; N4 CD、
正确资料:

4 g) T3 C. B+ s8 o7 n: K
" s  h0 h. q9 V8 C( U: E第3题,一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
8 }% u( h- ^$ o& ]. K& g6 VA、110
4 e' e6 J! i- t; uB、108
C、100
8 N, \9 ]5 e+ V' y& eD、120
: l: Q7 D0 G0 c3 D; O) a正确资料:
" V: x* s( J+ J! n" Y

第4题,折半搜索与二叉搜索树的时间性能()
A、相同
9 k/ w% }) \1 P1 V1 p" zB、完全不同
C、有时不相同
D、数量级都是O（log2n）
正确资料:
' W2 S7 C* M, P8 t  |
" L" m, j* `- A8 K5 v. k: c" a# H3 a3 I
5 f2 U5 |7 W! b$ h+ Z  l资料来源：谋学网（www.mouxue.com）,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
3 x! f- D( j4 D& i7 ?A、3
/ D; N3 `, C- h- n2 {. S" T" |B、4
! [2 v. i/ o3 c9 rC、5
D、6
& H0 q/ D2 t  I; @  _% G1 Q. n# ~正确资料:


第6题,有8个结点的无向图最多有（）条边
, u) O$ D- e. ^+ ~, W  P7 yA、14
B、28
C、56
D、112
正确资料:
$ ~1 _) y* ~( M0 y0 U8 w+ G# K* e7 @- [
) N* r! p( ?: y3 U, }. z
' M8 {5 y4 B% N" |0 ]第7题,深度优先遍历类似于二叉树的()
9 {' m1 w9 y. mA、先序遍历
B、中序遍历
C、后序遍历
0 D8 b, F3 A$ x: h+ {# N* x( X# ID、层次遍历
正确资料:

1 p# L  c) g' z4 ?5 V4 T" G% ]& N
第8题,用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
+ w! h3 T, R$ x% w# A8 J) j2 BA、栈
9 W, e* `6 X$ N5 k6 R/ R* K! UB、队列
C、树
D、图
( s# n) C4 j0 e7 A: Q- r1 n  g1 z0 [; O正确资料:

& ]) U" U, `5 ?- A0 z' i
第9题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
+ u" T9 D2 O0 v3 Z8 y9 d/ nA、1/2
B、1
7 Z: t# f3 S5 H1 @: b; e4 a$ w8 \C、2
: G/ |' S! k1 r! @. C% WD、4
' m4 h3 V" L* V# u' Q7 H正确资料:


资料来源：谋学网（www.mouxue.com）,设串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
4 w  k  q$ Q, v: V1 ]+ {/ y4 C& ?5 PC、BCPQRST
' L4 k) D; |; _, i* e; vD、BCDEFEF
正确资料
5 K6 d. Q& P/ i1 P" c7 i4 X

9 X) C6 o$ D6 G( I5 X& k5 f: v第11题,数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为
! W& B; f  X/ z  I1 gA、r－f
B、（n＋f－r）% n
9 U( E6 p% @, v+ {C、n＋r－f
0 r! d: W6 X4 n. c+ [4 PD、（n＋r－f）% n
正确资料


资料来源：谋学网（www.mouxue.com）,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
; z9 c% `1 H" S2 C  OA、0 3 2 1
B、0 1 2 3
, z# z' d; o& o* ]9 hC、0 1 3 2
D、0 3 1 2
  k" y" w. k2 m" o8 M1 v5 e& Q正确资料:
9 u2 l& V; l. U: u: P

第13题,具有n(n0)个结点的完全二叉树的深度为（  ）
* a- U$ V% f$ {" C* K9 qA、
B、
C、
D、
正确资料:

3 r* R4 K) e+ B; {% d5 J% i
第14题,下述几种排序方法中，要求内存最大的是()
A、插入排序
B、快速排序
1 [- W4 {* e( ], ]& oC、归并排序
D、选择排序
0 j3 t/ i  V+ {8 U5 J8 r1 B' n( o正确资料:
1 |7 d, a# H3 v! M( Y5 I

资料来源：谋学网（www.mouxue.com）,设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
2 W1 Q% F9 @- I( WA、n-1
B、n
C、n+1
D、n+2
正确资料:

" a& w5 m( T1 j
第16题,链接存储的存储结构所占存储空间（）
6 \& Z  B* l  G+ @' x' B% GA、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
' @7 u* i$ z& }! HB、只有一部分，存放结点值
- j% l! \  \* K/ JC、只有一部分，存储表示结点间关系的指针
D、分两部分，一部分存放结点值，另一部分存放结点所占单元数
8 g2 |# f+ j, F2 b8 H5 o5 h3 O& D正确资料:
0 m4 c& H( V: j- c
. Y& e$ i) w2 |7 p" }
0 j4 o8 i: z6 M- j4 v! K/ ^第17题,链表是一种采用        存储结构存储的线性表
A、顺序
+ d! S8 v& N( `: C3 |4 Q- wB、链式
# Y) t2 T! T* u6 F4 j. _8 i0 j, V$ VC、星式
D、网状
; }. f& {0 ?  r% V$ `0 @: Z正确资料:
; h, B/ h8 i9 r& Q
  p: S( V9 i7 k, e' q) N7 Z5 g
第18题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
5 ?; }2 }1 w  p. M9 TA、存储结构
& V4 W! j0 G, aB、逻辑结构
C、顺序存储结构
D、链式存储结构
正确资料:
' |/ u4 n+ B( c( p

# W: g4 g7 k$ S, [" Y( |. ?4 Y第19题,任何一个无向连通图的最小生成树()
; @: J: i" d) _6 k- ]- H0 b. YA、只有一棵
B、一棵或多棵
C、一定有多棵
D、可能不存在
正确资料:
4 ~8 {- X7 K! q
* r( k, k' D2 z+ P
资料来源：谋学网（www.mouxue.com）,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
# R( D+ p6 J" u6 c( EA、O(n)
B、O(n2)
  R! C" Z$ {* _0 \1 FC、O(nlog2n)
" l( [7 N/ P. W/ |D、O(n3)
8 o7 b8 X+ y/ G  W' a3 e0 {正确资料:
3 L' Y) K$ n- A/ `7 g! l4 K0 H

: f8 S" M, r4 o# Q第21题,有8个结点的无向连通图最少有（）条边
- @3 J4 |7 x1 bA、5
B、6
C、7
D、8
% u' r6 D  X9 |/ b) u% R正确资料:
/ _- _$ a7 m4 y- V: Q

, z$ P/ L9 T5 z, j/ Q第22题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A、栈
! b5 T3 u( _+ a3 H( `& U7 ZB、队列
+ C4 B+ f! P2 X. f" }. q9 r! ZC、树
, d, }: `3 b, p" ID、图
正确资料:

7 `$ Y7 ]6 r  N- I2 K1 m1 ?, u
( g8 G  ~5 i9 F' r# f9 A第23题,单链表的存储密度（）
A、大于1
6 M0 a0 d) \6 ]B、等于1
C、小于1
D、不能确定
0 l3 q8 `4 x; Q# e: h9 d# s) `8 T正确资料:
  u1 b9 D. o( |' D1 ?

4 K- C  H! G- ?第24题,链表适用于()查找
A、顺序
B、二分法
3 v  R, N4 [4 x* LC、顺序，也能二分法
D、随机
正确资料:

! _% K! Q' I! [! W) i' ]
' i9 D$ O4 l/ V! }7 K5 ?  T* N资料来源：谋学网（www.mouxue.com）,在一个图中，所有顶点的度数之和等于图的边数的（）倍
$ k2 Y. U( n8 m  e- x5 q4 r- PA、1/2
% k% U( u' [3 m' l' P: AB、1
* c' K0 T0 D  ^C、2
D、4
  R+ P5 Q+ {( Q1 ^# Q正确资料:

; h& }) S$ Z, K8 H9 p
$ t$ Q  M) N7 Z第26题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A、连接
B、模式匹配
C、求子串
  Y) v; g0 z3 {1 Z2 }8 \D、求串长
正确资料:

5 ]5 E9 t% `8 ?! G5 W
第27题,堆的形状是一棵()
A、二叉排序树
- I4 H) U- Y1 b- o' j8 T2 w9 a  yB、满二叉树
C、完全二叉树
D、平衡二叉树
正确资料:

6 z- K, J) [' J; G+ {2 ?4 V
第28题,判定一个队列QU（最多元素为m0）为满队列的条件是（）
A、QU-rear － QU-front = = m0
B、QU-rear － QU-front －1= = m0
% [' I) }1 |4 W: L/ t; TC、QU-front = = QU-rear
D、QU-front = = QU-rear+1
" g1 d+ I3 i, ?. _" p正确资料:

" W5 B/ D% _7 e' H
) t1 v2 v0 N( t5 M+ p# k) s3 Z第29题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
( c8 w$ g/ E0 @" kA、希尔排序
/ o1 K8 P$ n  `! ^" q* o6 kB、归并排序
C、插入排序
D、选择排序
7 X' K: U" ^; |9 S7 z正确资料
% V+ M. Z$ c% f5 U9 F% F( R
$ r$ q* G- U& E$ ^9 N5 j8 T2 c9 @
资料来源：谋学网（www.mouxue.com）,排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
- G+ M( U/ A0 a. T- n" tA、希尔排序
' ]2 A2 ?" ?. p2 b* ?" AB、冒泡排序
C、插入排序
D、选择排序
7 h5 O8 j1 e5 @6 J4 n正确资料:


2 Y* e5 v; T1 L$ d第31题,在表结构中最常用的是线性表，栈和队列不太常用。
A、错误
. Z2 r) k5 Z. s+ k: l4 _8 xB、正确
3 f2 v7 z$ M8 o& m正确资料:
2 w/ x) J0 ]% |" q: Y' l* j  ]- g
1 `3 a$ `. X/ ]+ l* h$ h" T: B3 x( R
( b( o( \3 A0 f  p9 q. N第32题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
A、错误
% B% r6 R5 c/ {2 qB、正确
正确资料:
% X, U  `( L# W9 I
5 T. r3 m9 k$ V5 ?# N
第33题,若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。
A、错误
0 g; v; C  y8 J: I, r" i1 Y/ mB、正确
+ U. \$ R4 N( E, W. J+ Y8 U# \. Q正确资料:

5 S0 v5 W$ A9 N' V, L- M( S& K
' P1 s7 G8 d4 L) d第34题,二叉树中每个结点有两棵非空子树或有两棵空子树。
A、错误
, c% P/ A  G" }; ]B、正确
正确资料:


第35题,栈和队列是一种非线性数据结构。
A、错误
: W, V  f1 k+ J8 |1 S/ [B、正确
* ~! @- W; F  B$ n正确资料:


第36题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
" h, l7 T. U5 @1 t3 s& _A、错误
  C; O2 y. G# l. ~9 b8 u/ IB、正确
正确资料:
4 d& K# J% N" U% [1 l9 [

4 j# q% p6 h7 O! `. S, d& {4 ^# i' x第37题,线性表在物理存储空间中也一定是连续的。
A、错误
$ G" c7 ^- r6 ?/ v! n4 jB、正确
4 k/ H! p. p6 u& v! `% b; C正确资料:
6 i6 Z( N0 O9 E+ D  i  X8 Q& P3 b$ U
8 A" V  B( H, g6 y- x
第38题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
& I' N$ M+ F% c' F  DA、错误
4 J$ J* m, W9 X7 o2 z$ iB、正确
$ A  l2 k2 U. y9 a9 f% X/ ~正确资料:

) B; @. y) s+ W  }7 H9 a
第39题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
8 b. }7 v, G9 DA、错误
B、正确
正确资料:

0 z) ]$ @1 ^8 b6 G2 b
第40题,栈和链表是两种不同的数据结构。
# d/ C: s7 d& e+ k% e7 f7 }A、错误
B、正确
; q3 W1 i! y# b! h9 X9 z正确资料:
' B2 Z" ?6 ^8 h. s7 V5 I& n
+ B! _* K+ R# F
+ L4 ~1 ?9 }7 u% F第41题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
A、错误
B、正确
! I" v1 z  e/ b. @: Y正确资料:
& L* M" r( k  d* _6 H. ^- _$ Y
6 `1 K, Z6 J- P* F  N$ d) C
2 e1 s0 J6 J5 g第42题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
0 f% ^3 N" B) {B、正确
( f4 |- n+ M1 `7 _0 J' v' m& |# S0 {正确资料:
+ J. R5 M8 \9 u; |, L2 N
" B7 G* c+ F0 r7 m# {# f
+ o2 g' Y) p9 E$ Z第43题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
A、错误
B、正确
4 i6 y+ L' \2 I- R正确资料:
$ x3 ~4 z" r5 q% ^* p( N
. N+ Q/ o9 S, T
第44题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
4 d% m5 a/ \' R- A* s7 [A、错误
B、正确
正确资料:


3 C& S) |. A3 h( S第45题,链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
! V2 x1 q4 H! p" r, ^A、错误
B、正确
8 x2 q& Y' u9 H3 P# N) @正确资料:

) \2 v% n% S/ D- y8 Y6 ~. @
第46题,栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
4 D4 t3 {4 y% ], nA、错误
  i# ~) `7 s  r0 BB、正确
/ F. c9 h7 W1 N. Z- a2 D$ t正确资料:

- w2 ]$ O8 X0 o4 w
第47题,具有12个结点的完全二叉树有5个度为2的结点。
$ s2 |* X& U" B  q6 _A、错误
, a- H3 q/ y2 m- o) OB、正确
& H2 k  |, P7 ^# M4 y$ t, @0 L正确资料:


第48题,线性表的逻辑顺序与存储顺序总是一致的。
A、错误
( c7 d3 L6 w" F* EB、正确
# g. U7 L4 c2 o正确资料:
, o3 Z9 H/ A" _, e
; R. V# v# e' ]. z4 ^6 n
第49题,二叉树中每个结点的两棵子树是有序的。
5 o" n8 J7 K: Q, X. @A、错误
B、正确
正确资料:
3 m$ R# V* K5 ~! |. W, n: `

资料来源：谋学网（www.mouxue.com）,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
! y, ^0 t. s1 Q3 g) DA、错误
B、正确
正确资料:
4 e4 O) v( Z1 G% l5 Z, I$ Z
3 S. B7 v3 L. c1 E) J/ I: B: r


0 N: w/ x$ G5 K5 _4 Q- S" O% s

# }  T  h$ i& p

! w8 H" H/ p! V1 Z& ?) k! ]
# ^3 e# _9 A* ?, l; E( Z! O

$ V( f! [- |0 h7 b" }

5 T* F5 @1 E6 M; v0 @8 M

. z2 Z2 W( y) m- _( s( M+ ~( ]% b8 j* K
4 k9 l$ ^* w" S
; U* q; v2 E8 t* Q# ~6 s
1 A! ~- @; L8 r  L) R


% W1 l; F# U' f
0 B& |5 B, S# f1 C6 @& u

. B0 [& B) q  T' {9 S2 o6 W7 G; A