福师10秋学期《数据结构概论》在线作业一

百分百晓林

福建师范大学
" Z  j/ B$ t  t4 F  p; h. M福师10秋学期《数据结构概论》在线作业一
单选题
1.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
( m" C1 J% ]9 }& [; ]' F2 h2 p+ VA. O（i）
" a: |( ?, o- C" Z; s7 L. o% EB. O（1）
C. O（n）
D. O（i-1）
$ n7 J7 @8 \2 p9 F: i4 B5 X! v7 [资料：C
* k/ P$ U' Y/ ]% T! T2.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
  U6 t/ B+ l. z9 C4 WC. 36
- o& n4 G3 Z* h4 ]  A6 bD. 9
. H9 C9 A4 |+ U  I9 }; t2 a$ s资料：B
# l) g6 _% ^/ G. ]3.从逻辑上可以把数据结构分为（ ）两大类
# ^2 Z  f5 f) u7 Y1 HA. 动态结构、静态结构
% g; G' g2 V' ~' jB. 顺序结构、链式结构
$ g# N- h1 Q3 c' nC. 线性结构、非线性结构
D. 初等结构、构造型结构
. Z& u2 C+ ~' i: ?2 s! k资料：B
4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
% ^/ o/ {5 l5 Y7 F9 X& iB. O(1)
0 h' e2 [: ^3 ^. D0 m- GC. O(n)
# W$ a8 m4 s: O3 ^D. O(n2)
2 d9 @! g! \$ L8 p+ \资料：C
5.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
5 K5 o3 r0 j& Z0 Q- t! E6 eA. 不确定
* x* R, n7 N* k+ D( C0 g: wB. n-i+1
) J; U' H% I. L" H# }% ~C. i
) W2 }2 W, }2 Y- r7 H3 Z* _- iD. n-i
, A) r+ l  V- |. _) q; c资料：B
6 c) t7 ]9 Y" L$ r# }( N6.算法的时间复杂度是由（ ）决定的。
A. 问题的规模
2 f5 G% A4 l$ ^1 H9 x% k. GB. 待处理数据的初态
. r& |8 Y8 L) ^3 OC. A和B
$ z8 C5 A+ L8 }8 V/ q9 B( RD. 变量个数
' i- D* |& V& T: Q7.下面有关算法说法错误的是（ ）
, i+ B5 q& D$ D% QA. 算法最终必须由计算机程序实现
1 g. ?7 b& I/ m7 E/ [( k# |- IB. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
8.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
3 o, G+ E8 O5 i, I) v" U& ?' a8 M8 L# B* LA. head==NULL
$ J2 B' e" b- q( }: Z, O$ D: oB. head→next==NULL
C. head→next==head
* _1 q) k: {3 g5 Z$ z# ]; c5 sD. head!=NULL
6 S6 t) J) z4 z5 w$ L: x2 ?3 ^' [9.链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
5 e5 ?' X$ x+ WD. 所需空间与线性长度成正比
# S( B' h7 W, {, d1 U& V5 I4 m& H10.在一棵二叉树上第5层的结点数最多是（ ）
A. 8
3 G6 z  x+ n) H, ~B. 16
C. 32
. l% t- ~+ X5 b- c7 R; J. A/ yD. 15
  t+ Z. O0 d$ ]4 a( T9 \0 e11.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
A. (rear+1) MOD n=front
B. rear=front
" }7 U% M! I/ }3 z; s5 N( SC. rear+1=front
D. (rear-l) MOD n=front
6 W' H7 ~* `  i" l) V( z) ^( E12.栈和队都是（ ）
6 P$ Z2 n6 X  Q5 {& _8 X+ i6 m6 BA. 顺序存储的
6 P0 X7 A: q" o2 X* F1 oB. 线性结构
0 f/ A6 A% c" H; Z5 fC. 链式存储的
D. 非线性结构
13.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
+ \) Z8 ~% I4 \; R& H% ^B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
14.算法的计算量的大小称为计算的（ ）
A. 效率
! S2 }" j  C4 q* s( vB. 复杂性
2 N. Q3 v9 a/ a" DC. 现实性
( Z2 [" D4 G: q: j$ t7 Q/ A7 LD. 难度
8 f) k8 ~- l; P- _% G15.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
/ e' T& R; r* Q* \/ r, gA. p->next=s;s->next=p->next;
' W- k0 H) z$ @B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
% B; _2 N" U2 b! B  s) l  O+ @2 ED. p->next=s->next;p->next=s;
16.连续存储设计时，存储单元的地址（ ）
9 ~# b1 m9 ?9 H2 |A. 一定连续
B. 一定不连续
" i" r  r. m; N& gC. 不一定连续
! D8 _; ~5 Y0 Z% s5 |D. 部分连续，部分不连续
17.下面叙述正确的是（ ）
A. 算法的执行效率与数据的存储结构无关
* O) j8 o  m' L$ W6 mB. 算法的空间复杂度是指算法程序中指令(或语句)的条数
; a5 q) _* U: v5 c* aC. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
18.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
- \$ f* P2 g- y# wA. 线性表的顺序存储结构
# Y- K# e* R: j" t/ E0 L9 b5 dB. 队列
8 d5 @! }+ y+ P$ s, R" G; l( BC. 线性表的链式存储结构
5 ~/ n- f( D8 `5 x0 gD. 栈
19.一个算法应该是（ ）
& H: _3 \6 L9 ^2 K5 I. pA. 程序
0 E7 o3 W) s4 J* u% I3 ~: lB. 问题求解步骤的描述
C. 要满足五个基本特性
1 o( |, X8 U- w) H: ~7 d9 l; m/ eD. A和C.
20.栈在（ ）中应用。
A. 递归调用
2 _& v# K, h8 }' x+ B; x8 k: BB. 子程序调用
% b$ s; R4 \5 ^8 Y7 u& gC. 表达式求值
D. A，Ｂ，Ｃ
/ ?) W$ b2 t& d21.对于栈操作数据的原则是（ ）
A. 先进先出
) Z. S. y+ v3 L+ L' Y  ]B. 后进先出
C. 后进后出
4 t; q( v5 V3 H8 BD. 不分顺序
22.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
* ~& ?# c6 C6 e: w/ F3 NA. 求子串
B. 联接
8 T( \" n: D, _* x/ ]3 [6 bC. 匹配
1 ?  }, a- u/ R9 N6 H, xD. 求串长
. @8 I$ t& q9 {8 t4 x2 x23.一个递归算法必须包括（ ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
24.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
A. O(n) O(n)
: @/ o! b- W) S* f1 s: \0 HB. O(n) O(1)
C. O(1) O(n)
4 _2 v8 M3 [+ Z5 UD. O(1) O(1)
25.已知串S=‘aaab’,其Next数组值为（ ）
9 m/ ^: R% m( B4 k* A8 w" LA. 0123
  \/ c7 C1 @) W/ M+ Q) hB. 1123
C. 1231
D. 1211
多选题
4 y/ P+ S6 q6 w# g& p1.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
* g5 ?2 X5 s4 N" Z% gB. 线性表
4 M9 N9 u+ ?3 w5 G' u& g& EC. 二叉树
D. 栈
# U; P' P5 a2 i" T4 A6 L2.以下数据结构中（ ）不是线性结构
A. 广义表
* A! B, n: [$ T0 d- OB. 二叉树
9 o$ c2 b1 `, L; o9 r! O/ wC. 稀疏矩阵
D. 串
3.下面关于串的的叙述中，正确的是（ ）
: I9 p. F$ u( z! v  S- VA. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
5 a/ ]; R. V2 |3 D, SD. 串既可以采用顺序存储，也可以采用链式存储
! e. }1 H$ a! v4.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）
A. a，c，b，d
$ q8 L9 d2 P" a* s/ {B. b, c，d，a
0 R- n# V$ x3 x. uC. c, d，b, a
# X" I+ E/ C: g% _. m% lD. d, c，a，b
5 S' W5 _4 R4 H/ {/ W% u0 |: R) j) D5.下面关于线性表的叙述中，正确的是（ ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
+ Y5 x+ B! u$ }4 C% ]: FC. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作。
# ?* r& v7 P' [- E. E( e2 X4 W判断题
) u- e( |5 d* Z( k1.通常使用队列来处理函数或过程的调用（ ）
9 B% A$ d+ A& P- p3 xA. 错误
B. 正确
5 {8 ?+ }, d; f) D4 t+ z: m5 I2.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
* r' U" d2 g  p5 P' r9 Q3 D' ^A. 错误
B. 正确
( O5 h' u; _, W! P3.栈与队列是一种特殊操作的线性表（ ）
' c: @& e' K" K+ |2 F9 t- l' EA. 错误
2 O: i, a# N  t$ h4 fB. 正确
4.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
8 c7 Y' y: ^" v! q, DA. 错误
" i: |! r% ?, s" l$ i; {B. 正确
: g' U: n: v% U) t$ }' _: n5.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
A. 错误
B. 正确
2 D: d: B+ y. o+ L# \$ A, U+ `2 l! |6.链表中的头结点仅起到标识的作用（ ）
' f& P6 N' m8 U+ e$ o" ZA. 错误
B. 正确
7.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
# N0 I: a1 w0 D" T; `A. 错误
' B' f& Y2 {, A+ y( Q. C, C$ u4 yB. 正确
( ~; k, O# _# ^. c# C& @8.循环链表不是线性表（ ）
A. 错误
( Q5 ~+ \$ u+ x) g/ f: ~3 E, mB. 正确
9.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
A. 错误
B. 正确
9 y- V9 z* x; X10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
+ o' [8 E2 g! r6 jA. 错误
B. 正确
11.顺序存储方式只能用于存储线性结构（ ）
+ p/ p3 x* W/ v0 |8 w3 s- q( ?6 o6 sA. 错误
B. 正确
12.顺序存储结构的主要缺点是不利于插入或删除操作（ ）
A. 错误
, {7 J2 y& \( T0 lB. 正确
13.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
A. 错误
, a) ^+ @5 X& \; ]2 f6 PB. 正确
9 Z4 C1 c+ N# V3 B14.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
  M: Q: ?' @7 X9 D/ W6 K4 bA. 错误
. z/ D9 u$ i( J, f1 cB. 正确
15.消除递归不一定需要使用栈，此说法（ ）
0 X, K, q" L9 u, K2 y+ XA. 错误
1 V5 h( I$ {8 I2 YB. 正确
' s7 X. h$ `8 I2 f9 Q16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
& W5 h* {7 R$ T+ t9 a! E& @A. 错误
B. 正确
17.线性表的特点是每个元素都有一个前驱和一个后继（ ）
A. 错误
& L. j$ \6 c* p: P& N3 K  TB. 正确
18.循环队列也存在空间溢出问题（ ）
A. 错误
B. 正确
19.栈和队列都是限制存取点的线性结构（ ）
A. 错误
3 H8 k* o4 ]) c% V; RB. 正确
' y# f" t6 W+ v1 ]20.栈是实现过程和函数等子程序所必需的结构（ ）
* W, k8 z7 p% T6 J! {; ]- ~# v, JA. 错误
B. 正确