南开19秋学期《数据结构》在线作业1(100分）

admin

【奥鹏】[南开大学]19秋学期（1709、1803、1809、1903、1909）《数据结构》在线作业
试卷总分:100    得分:100
& T' O9 l# w# X0 S$ S+ n第1题,设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
1 t2 a! ]2 F8 s  c( ]A、循环链表
7 @9 p: t  I6 I: N/ V8 z/ AB、单链表
C、双向循环链表
* L; {; W8 E5 uD、双向链表
4 }% y) ~7 \8 D3 k& \! u正确资料:
9 n, x7 q7 U' M2 g7 D2 y" F

第2题,对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
A、3
* w  r' V$ V+ c1 JB、4
C、5
D、6
正确资料:
" Z) X  |6 f. N% Z
1 ?6 C" q7 N- z. Z+ {
第3题,广度优先遍历类似于二叉树的()
A、先序遍历
7 N% M: n1 Y! }4 F1 aB、中序遍历
C、后序遍历
D、层次遍历
( Y' }# t, m  ]" V9 k正确资料:
  {! ^7 o  H2 K: q5 X
( x! \9 q+ a) b7 Q; V
第4题,折半搜索与二叉搜索树的时间性能()
A、相同
( Y6 Y2 H# J- M; ?+ aB、完全不同
C、有时不相同
D、数量级都是O（log2n）
9 Y& R5 ^5 c; e正确资料:
2 Z" i9 B/ j# C. l" C% @' q3 H" S

第5题,对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。()
A、从小到大排列好的
B、从大到小排列好的
C、元素无序
D、元素基本有序
正确资料:
+ k( M% i, \) B, n" k" q8 `

第6题,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A、1/2
B、1
; c- ?! `7 J& W3 VC、2
, P$ f3 ]: c( Y$ AD、4
正确资料:
8 h! E5 q# V& K. T

第7题,具有n(n0)个结点的完全二叉树的深度为（  ）
A、
; A( ~$ N, q4 ~2 CB、
  L$ M" Z/ [  o& a8 o: `5 o) }' BC、
D、
3 b) t" {8 S5 o9 [正确资料:
5 L3 I3 N; f, O/ O/ z5 X8 o$ A& x

7 s0 u( B: c* D0 I( v* D: T第8题,二叉树是非线性数据结构，所以（）
+ C& v5 [% T( C' R$ @1 {, LA、它不能用顺序存储结构存储
6 E; _7 h: s3 kB、它不能用链式存储结构存储
C、顺序存储结构和链式存储结构都能存储
D、顺序存储结构和链式存储结构都不能使用
, n7 i! `" o+ K正确资料:
3 O1 [, ?" ~+ ~: z: ?- l2 X/ o9 c, @

第9题,对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()
A、O(n)
B、O(n2)
8 j' K- Y8 b& KC、O(nlog2n)
9 x5 i! z+ M, Z4 n' P, DD、O(n3)
正确资料:
3 H7 c- p  s! f
  z2 w+ P2 W( ?+ Y
第10题,在表长为ｎ的链表中进行线性查找，它的平均查找长度为（  ）
A、ＡＳＬ＝ｎ
# s7 O3 \2 _# d: K3 }" ]( B8 kB、ＡＳＬ＝（ｎ＋１）／２
C、
D、
) ~" R7 @( S9 e0 W6 U正确资料:
" \& P- G$ D, X6 p
) l, d$ N1 E2 u4 [# O# W" g
第11题,向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素
. L) G/ l7 g2 ], t* Z2 }! eA、8
: u6 y% l& t2 L+ i, ~" A  LB、63.5
4 U, u4 H4 h5 a% CC、63
( W6 K$ y2 A: b: j0 u2 pD、7
# [( E6 N: N0 N( l正确资料:
# O% T* Z, x/ V4 r9 O- ~
% M' Z$ S; J$ o2 p4 a
) ?& i6 e" K5 x( Q2 g, C第12题,任何一个无向连通图的最小生成树()
A、只有一棵
B、一棵或多棵
* B7 T2 [  s, `, A4 AC、一定有多棵
) t- l; d$ }: _" b5 AD、可能不存在
正确资料:

: q! p1 C7 F# A
- V$ a/ G3 n: m3 w  ?, m1 b& Q; m第13题,在一个图中，所有顶点的度数之和等于图的边数的（）倍
. e7 a% X5 j- H% B" q3 `A、1/2
+ N& O  }1 ?% SB、1
C、2
+ V; a' a) W6 c! c: ]$ u) p1 |* TD、4
正确资料:

1 X# z! L* E5 e* L/ ^$ ]
第14题,下述几种排序方法中，要求内存最大的是()
A、插入排序
1 O/ H7 B) t' P" O7 W0 ?% DB、快速排序
C、归并排序
D、选择排序
% Y0 h/ {+ A; n2 h  L. C/ A正确资料:


# Q$ O( o! j' n* z8 u: Q; j% X第15题,若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）
' s& a, R! H6 \A、i
B、n=i
C、n-i+1
6 f# Z+ B7 r5 [; F6 BD、不确定
8 S' J) C* e4 c: ^& b& k. m正确资料:


3 y  F+ X; _) T第16题,设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A、连接
% p! x* j+ z4 eB、模式匹配
C、求子串
D、求串长
- x1 _+ j4 Y. [9 n* l1 h正确资料:


第17题,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）
/ l% ?" \3 Q8 l3 H& c% J, K& EA、0 2 4 3 1 5 6
B、0 1 3 6 5 4 2
! V" {. D2 ~0 N) d8 HC、0 4 2 3 1 6 5
D、0 3 6 1 5 4 2
. x- d- z, Q. S# v正确资料:


% E+ g) v1 X3 B: Z2 S第18题,若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()
A、79,46,56,38,40,84
B、84,79,56,38,40,46
C、84,79,56,46,40,38
3 c& B$ ~7 L7 xD、84,56,79,40,46,38
正确资料:

' B4 f, c9 w! V8 n6 u
6 b% s: n& l# m' j/ P8 [第19题,将5个不同的数据进行排序，至多需要比较()次
) a9 k/ S8 J- T* x" q9 EA、8
. u- W' i/ S5 V* q  ZB、9
! v3 s- ]6 m7 X2 Z* \, nC、10
$ M8 f5 M5 |' V+ WD、25
正确资料:
  v) {' F4 N6 k

第20题,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
A、0 3 2 1
  c$ v. m; I0 h- F4 e9 FB、0 1 2 3
C、0 1 3 2
" W: b$ e& X- m! s: Q& a) H, h5 CD、0 3 1 2
% s, S, i& M9 }2 c正确资料:


第21题,数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()
5 U# f7 z  t# L) mA、存储结构
B、逻辑结构
C、顺序存储结构
D、链式存储结构
+ ^: ~. N/ U3 W正确资料:
2 O7 }0 t' Y. }5 D

第22题,折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中()比较大小，查找结果是失败。
: X1 @, R% G5 S. _( QA、20，70，30，50
B、30，88，70，50
C、20，50
D、30，88，50
# J  j/ G8 u& l1 Y正确资料:
- d1 g2 ~& f0 R5 N: h4 ?/ ^+ h! H2 c

第23题,从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()
A、希尔排序
6 h$ S! g4 \' Q" m# a# cB、归并排序
$ M  z; n8 B# d# n2 J' DC、插入排序
- _8 H, Z. N$ n6 H/ h5 LD、选择排序
* }% Z* p+ {5 \$ m6 E1 p8 S0 k正确资料:


6 N: Y/ Q9 w5 P- I. e, l( i- ~第24题,设串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))的结果串是（）
& i- w' L# f5 @) W" v. FA、BCDEF
B、BCDEFG
C、BCPQRST
# u: a% ]" I# {+ |* }! ^+ [: Q+ X; iD、BCDEFEF
7 |1 g5 ]1 C% c. C7 S/ S正确资料:
2 V/ t/ W% R5 ]7 {9 T0 R7 V7 R! q

第25题,在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）
A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B、在第i个结点后插入一个新结点（1≤i≤n）
1 ^5 Q& w" a9 b$ W/ ]) o3 PC、删除第i个结点（1≤i≤n）
! E5 t* x' N) J3 kD、将n个结点从小到大排序
# b* t* i* J$ j( {正确资料:
6 f1 f, K/ S9 p- n/ G1 N& l

4 U5 r. @+ m' q: E7 _) c* ]" j; ^第26题,用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
- M: C0 ~" I# nA、栈
B、队列
C、树
  ]# c( q2 O  V- n7 X6 WD、图
  d; p% G+ ], \1 X. V3 G% I正确资料:
3 P$ b5 }8 T9 x

第27题,下列关键字序列中，()是堆
A、16,72,31,23,94,53
, s! M* `  o9 @% r3 iB、94,23,31,72,16,53
' b' y* f$ Q9 n% a" k" I1 LC、16,53,23,94，31,72
' I* H; \; |0 ~$ u9 k2 b1 aD、16,23,53,31,94,72
9 v; f4 g. r& w- u2 q4 r9 Q正确资料:
" ]2 T! _$ t1 {4 S6 A9 F1 u

3 l$ @5 E7 O& Q: u. ]第28题,线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
& V) ^, w' g/ N0 JA、必须是连续的
7 F( ^& n' t  x. TB、部分地址必须是连续的
9 A: [, l) `! }! w% c, h4 a8 G& z( dC、一定是不连续的
7 b1 f9 o0 a' rD、连续或不连续都可以
正确资料:


第29题,有8个结点的无向连通图最少有（）条边
0 P/ ^$ Z1 E+ t, n# M1 t6 LA、5
1 ~( t, K8 B3 o* p, `$ kB、6
C、7
D、8
正确资料:


第30题,已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
7 Q7 \( d6 r2 W9 z" s5 t8 M+ {A、0 2 4 3 6 5 1
B、0 1 3 6 4 2 5
' H$ f) l" Y/ z2 J+ Q8 y6 P2 L$ m6 oC、0 4 2 3 1 5 6
) ?- f$ K$ {3 |" WD、0 1 3 4 2 5 6
正确资料:

6 U9 e6 ]: X- t5 s6 g
9 e( T0 l0 z  g0 K第31题,栈和队列是一种非线性数据结构。
+ L- G3 S4 `% a9 J; B6 \& F9 PA、错误
B、正确
正确资料:
  q: E9 C& o7 b7 V) K6 y) o
7 i0 @( B) n7 b$ o- P, u
第32题,二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
* Z3 r+ ?* u8 EA、错误
7 ^2 @  T. Q3 l2 c4 FB、正确
正确资料:
& Y: C. q7 `" [9 X+ z& I0 ^

第33题,线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
' k3 f1 Q; p" kA、错误
4 T$ Z6 i/ G, p' V9 M, Z1 p" \1 RB、正确
- E% S/ S) M8 r正确资料:

1 ~6 T$ N3 d7 N
第34题,顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A、错误
B、正确
4 U* r8 }2 E; j- E正确资料:

9 f. Q1 j9 ~% h
第35题,栈和链表是两种不同的数据结构。
( }: W0 f/ I, `0 t3 V" D6 u" C8 FA、错误
B、正确
正确资料:
4 P& \; c7 g/ F/ Y9 W% j$ S5 j
1 l5 m1 w! N& j
6 M+ F. N+ X, U' f- I- f第36题,二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
A、错误
6 j/ r  n4 z$ o( ~) k; SB、正确
# J' r9 r& g( m1 h: @正确资料:
" d+ @5 L- m3 x$ K2 o- c6 U
' V( t/ A+ K! e! n3 Z
% K) n* ?% K0 ~9 a第37题,在表结构中最常用的是线性表，栈和队列不太常用。
7 d# b( d! ]% l7 t/ v4 HA、错误
/ S6 M; n2 M/ Q! ]: `3 RB、正确
正确资料:

* k% |, ~* _/ d0 c% v. k2 L
% l8 Z" _6 f9 L2 q7 j/ P第38题,对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表
A、错误
B、正确
正确资料:

" {. c9 u- T  n# M. F/ u
第39题,二叉树中所有结点个数是2k-1-1，其中k是树的深度。
' i% V% e/ Z9 k8 N" f; EA、错误
" w% K9 f" ]; \# [& \2 ZB、正确
正确资料:
1 x; J! G& |9 }9 R! @
" l) g! A6 h' Z% _. t9 J5 O+ c; V9 ~
- g! f% \! J  i% O4 ~第40题,顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
A、错误
B、正确
; H5 z7 I( x4 {: ]" s6 q正确资料:

7 u6 R$ }: B6 }5 r: H9 I
第41题,二叉树中每个结点的两棵子树是有序的。
A、错误
B、正确
) J) i- J; i3 f# m* f+ [2 P- m正确资料:
* k( W# l4 C4 N' N+ h1 r1 u

) v. @. B* N8 O/ A; m第42题,链表的每个结点中都恰好包含一个指针。
* o# q7 r# Z. c! m( {A、错误
8 T. |( m& k; d* |B、正确
正确资料:
: a% x& r5 c1 `

第43题,栈和队列的存储方式既可是顺序方式，也可是链接方式。
A、错误
B、正确
- w7 |& ^: z7 ?* `/ Y& W正确资料:
0 T2 }* \. K3 _+ ]0 d8 A

第44题,二叉树中每个结点有两棵非空子树或有两棵空子树。
7 l4 f) n5 I  k% D. pA、错误
0 I4 z1 l5 J1 U9 {# t# `/ k# \B、正确
正确资料:

8 q( L" q* R- X, e
第45题,两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
9 G2 x4 }) R6 PA、错误
, `  ]% ]) t2 n6 k) O6 _B、正确
正确资料:
$ ~+ X3 d. O0 x) A; C$ x4 @0 ~5 Z

第46题,对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
; ?# ]6 e& s5 l. q4 WA、错误
" ?+ A/ X  o+ Q3 ]B、正确
正确资料:
2 Y7 `4 R  |, @3 x, E
# ?  X, U  B! a2 p
, Z2 M7 R2 W  G/ k& z' }9 v3 T第47题,队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
A、错误
/ u0 d- \- n# ~& S. r6 EB、正确
7 ^& }( q" E# l6 o# ]  b8 C8 Y; w正确资料:


第48题,一个栈的输入序列是12345，则栈的输出序列不可能是12345。
% z% c2 o; f" ?A、错误
- x: G; _' N4 o6 A3 U. v1 S  bB、正确
正确资料:


第49题,二叉树中每个结点的两棵子树的高度差等于1。
A、错误
* H1 R' H2 N. ~4 G5 Y; {1 UB、正确
正确资料:
$ }1 Z. i7 c* M* Z7 a

% O: _6 Y0 {. z% }第50题,用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
5 U1 V8 X6 E, e  n9 W5 W- ?: |! nA、错误
B、正确
正确资料:
/ A* M4 C* l5 p8 b  f