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

百分百晓林

福建师范大学
, ?, @7 c* Q6 F福师10秋学期《数据结构概论》在线作业一
* Q0 x7 v2 ]1 f& K' [5 u! N& r单选题
3 i) _/ P* ~( }$ U1.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
) Z( I# O8 Z' d- E" a" l9 YB. O（1）
C. O（n）
: `1 i8 ?( V; `4 ^  SD. O（i-1）
1 g' s! ~/ D0 [资料：C
- a0 r1 s9 v, J. X& f/ c2.若串S=’software’,其子串的数目是（ ）
) i& ~3 `$ e. L  A! V% ZA. 8
B. 37
  J5 x4 k) o+ m$ TC. 36
D. 9
5 E1 T( _+ o& |5 F资料：B
' A. m8 V" o1 Z+ v( E3.从逻辑上可以把数据结构分为（ ）两大类
A. 动态结构、静态结构
" Z" h, ?% B5 JB. 顺序结构、链式结构
C. 线性结构、非线性结构
6 A8 S+ G- j, [' L/ h4 o+ HD. 初等结构、构造型结构
% b/ I+ @, ]" s& J- Q资料：B
2 J2 E7 Q' \9 x- x- Q" L# J9 W4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
* t# n  _0 O0 }B. O(1)
  t& Y2 E& ~: {9 Z1 O9 B/ n& WC. O(n)
D. O(n2)
' L6 ]) |' c' Q4 S* G* R资料：C
5.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定
B. n-i+1
C. i
D. n-i
资料：B
# f0 }; z( o- Z" f1 u3 R- Y7 P6.算法的时间复杂度是由（ ）决定的。
$ \: J# O5 U: F5 eA. 问题的规模
7 j$ ]3 q( ?! D: k. UB. 待处理数据的初态
5 `; f$ j" ~1 h4 n& ^4 @4 yC. A和B
D. 变量个数
7.下面有关算法说法错误的是（ ）
- k' e2 z: @9 D( TA. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
- R3 \; y5 c$ P; Z8 x3 f/ A. uC. 算法的可行性是指指令不能有二义性
7 f, N# v( m1 G$ r7 P; G& e2 DD. 以上几个都是错误的
8.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A. head==NULL
B. head→next==NULL
C. head→next==head
: }: u6 o, J) D, p4 sD. head!=NULL
9.链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
* `4 \5 l6 h; RC. 不必事先估计存储空间
; Z. c, n% ~3 B7 B* h+ g, P+ GD. 所需空间与线性长度成正比
! z( x+ R) {& F7 t9 ]  p10.在一棵二叉树上第5层的结点数最多是（ ）
A. 8
$ [# t! W& t8 X: A' k8 BB. 16
C. 32
D. 15
11.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
A. (rear+1) MOD n=front
2 Q" f2 [8 S, P3 r, B+ L/ UB. rear=front
C. rear+1=front
D. (rear-l) MOD n=front
0 s' F! x; Q& F! I. R% O12.栈和队都是（ ）
A. 顺序存储的
9 c7 p0 q/ L' v" AB. 线性结构
! Z( H$ i7 x" e, R4 {C. 链式存储的
( q  |* [' a" d5 C- BD. 非线性结构
13.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
2 j/ s5 K8 B4 ]! q# z! t. EB. push,push,push,pop,pop,pop
( u, I7 z3 |; |: |' AC. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
14.算法的计算量的大小称为计算的（ ）
A. 效率
/ N5 Z& s! E, e0 X; T9 h! WB. 复杂性
% e' j3 |( _# Z8 _C. 现实性
1 a( }8 p7 ]1 q$ |% H" [. QD. 难度
1 i: {/ y- q. v. O15.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
A. p->next=s;s->next=p->next;
) U& n2 M5 M9 g. Z5 Z2 O7 V3 ~6 a! f$ j5 aB. s->next=p->next;p->next=s;
' y3 H& [) \2 |9 R+ hC. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;
16.连续存储设计时，存储单元的地址（ ）
A. 一定连续
( V1 y0 L) Z) c0 E1 dB. 一定不连续
) o% b0 u. _  c/ d$ C0 lC. 不一定连续
. ~5 [' M# @' R4 Z& J3 G7 RD. 部分连续，部分不连续
; T4 }1 d' |' e, |$ B17.下面叙述正确的是（ ）
# u1 @: v4 v9 w2 k7 l2 pA. 算法的执行效率与数据的存储结构无关
4 p- T3 g. N. q  q! [. TB. 算法的空间复杂度是指算法程序中指令(或语句)的条数
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
3 h9 q( k+ L& M! ?: A9 W& }5 ?# l5 M18.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
  ^- L2 F- x( x- f1 `& HC. 线性表的链式存储结构
* R5 u" V* f; GD. 栈
19.一个算法应该是（ ）
  G7 u1 n: u6 H; r, aA. 程序
" z: z1 n' J6 f8 oB. 问题求解步骤的描述
# y+ B  h( V8 K) ?C. 要满足五个基本特性
2 {$ K& L9 t* JD. A和C.
6 S8 f  x: p0 z/ g. h: }20.栈在（ ）中应用。
A. 递归调用
7 g$ Q, W( i$ |6 N8 NB. 子程序调用
C. 表达式求值
. U/ O, K+ R3 FD. A，Ｂ，Ｃ
21.对于栈操作数据的原则是（ ）
* ^9 L8 m( ?9 P- e# jA. 先进先出
" T" a0 ?6 w1 ]) k& KB. 后进先出
: v  i( ]' [- j  L* iC. 后进后出
D. 不分顺序
22.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
( ]+ [6 b# I& p0 M) a$ X/ ]C. 匹配
( M0 l2 s; z; nD. 求串长
4 W7 k8 F, i0 o& A" V9 O23.一个递归算法必须包括（ ）。
9 m5 n6 u. X- qA. 递归部分
* m, G& E" u. d( i" eB. 终止条件和递归部分
  B  s+ b, [; O# R) p) `- p* c+ DC. 迭代部分
D. 终止条件和迭代部分
24.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
A. O(n) O(n)
5 R% S: t% B3 u( n- LB. O(n) O(1)
" {5 o, f* s8 ]+ s# CC. O(1) O(n)
D. O(1) O(1)
$ C- K8 m6 c) G0 B) ?! t25.已知串S=‘aaab’,其Next数组值为（ ）
A. 0123
B. 1123
C. 1231
D. 1211
/ j, F3 i, ^" b' T. j多选题
# L( P4 G- q. u/ \) \1.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
8 ?% O! V0 Z1 R& R% O0 fC. 二叉树
D. 栈
  A4 }8 w' n9 c! v/ L* L2.以下数据结构中（ ）不是线性结构
6 w% G/ a1 T; U8 F/ E- zA. 广义表
1 \( V. d6 R, N; Z# P: t& ]" Y. o& W& {* ^B. 二叉树
C. 稀疏矩阵
D. 串
/ K7 q$ c' G/ P: U/ u3.下面关于串的的叙述中，正确的是（ ）
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
, W) q7 }8 a" D4.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）
A. a，c，b，d
B. b, c，d，a
% D! \" c5 D$ y- @. q7 R9 Y7 SC. c, d，b, a
D. d, c，a，b
5.下面关于线性表的叙述中，正确的是（ ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
. s. I% |$ Q# O7 A' y3 ~7 oB. 线性表采用顺序存储，便于进行插入和删除操作。
5 [& M- H3 c  nC. 线性表采用链接存储，不必占用一片连续的存储单元。
) g2 J5 j$ d) B% _# t5 I; vD. 线性表采用链接存储，便于插入和删除操作。
判断题
1.通常使用队列来处理函数或过程的调用（ ）
2 V! w- {8 n. W  e* lA. 错误
2 W& N6 L" |6 N- oB. 正确
' `2 X6 F- y& E/ c. \2 R2.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
: E2 ^% X  e9 l6 S* L4 D5 o9 ^A. 错误
B. 正确
3.栈与队列是一种特殊操作的线性表（ ）
A. 错误
, k2 Z) D& \* k- Y8 i3 z% ]  bB. 正确
$ A/ y4 N7 `+ e1 {6 ~4.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
' T: i, |* N3 H& _- S) g9 mA. 错误
B. 正确
5.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
5 P: o% ?( Y/ ]  kA. 错误
4 B- Z6 @8 z8 \5 e7 m4 j" KB. 正确
- z1 M$ |' j5 h+ u8 k8 F6.链表中的头结点仅起到标识的作用（ ）
A. 错误
B. 正确
7.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
, H) u) r, v+ p) U; f1 x7 X3 QA. 错误
1 g8 M6 L8 ]" P3 ^( i1 l( d7 UB. 正确
7 ~/ f+ c/ Y+ ?0 p, t9 R$ t/ E& ^0 R8.循环链表不是线性表（ ）
A. 错误
4 G2 T' W/ t- O; y- O1 hB. 正确
9.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
* G, {3 A  l: A4 LA. 错误
/ B- H7 L' ?* Y; n$ U6 kB. 正确
10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
; u% l3 l# l" o; E' J! aA. 错误
' q- d4 ], D7 w0 z+ DB. 正确
11.顺序存储方式只能用于存储线性结构（ ）
A. 错误
B. 正确
12.顺序存储结构的主要缺点是不利于插入或删除操作（ ）
/ g" x: J9 O  ?7 ]9 }6 BA. 错误
B. 正确
+ I4 n9 \$ h- F* u4 p- h13.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
: H9 M% K" k+ d; z+ h  }' y5 l" B% NA. 错误
B. 正确
14.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
7 ?  c& T3 w0 b; D: @B. 正确
2 _. P2 |. H, \  b  L; \15.消除递归不一定需要使用栈，此说法（ ）
A. 错误
* @& @9 s5 j9 V8 Z: W1 x2 UB. 正确
16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
A. 错误
5 p: N0 }6 }( p0 EB. 正确
( t( V1 w: F8 S3 X! c5 d% k17.线性表的特点是每个元素都有一个前驱和一个后继（ ）
" b  t& |: d; g/ S1 mA. 错误
' {: l0 J$ n+ f( IB. 正确
18.循环队列也存在空间溢出问题（ ）
A. 错误
B. 正确
19.栈和队列都是限制存取点的线性结构（ ）
' v; k7 }) f, u* m6 B5 ZA. 错误
3 R+ a) P; x3 n! D, |B. 正确
& V; L* u# }3 v" K( N  K9 S" d20.栈是实现过程和函数等子程序所必需的结构（ ）
6 a- L, E/ y+ v' @. d, oA. 错误
B. 正确