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

百分百晓林

福建师范大学
福师10秋学期《数据结构概论》在线作业一
* m- _# `' Q3 U5 F4 \单选题
1.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
( v* u6 A1 l/ J9 J" `- pB. O（1）
  \) P/ c8 B: f: [2 BC. O（n）
D. O（i-1）
资料：C
2.若串S=’software’,其子串的数目是（ ）
A. 8
B. 37
C. 36
D. 9
资料：B
3.从逻辑上可以把数据结构分为（ ）两大类
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
资料：B
4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
7 l2 w8 R; @; H: @- P! d: v6 M1 Z# ?C. O(n)
D. O(n2)
资料：C
5.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定
B. n-i+1
; C2 {/ W* O/ I, I: h/ J% xC. i
D. n-i
资料：B
6.算法的时间复杂度是由（ ）决定的。
: Z8 R0 b7 B, A: B- P1 r4 C( S3 ?A. 问题的规模
B. 待处理数据的初态
C. A和B
2 o/ q( c) p2 t7 k# {/ uD. 变量个数
  f- Q, M1 E3 @% z" l7.下面有关算法说法错误的是（ ）
6 H) _$ ^* {5 l8 fA. 算法最终必须由计算机程序实现
6 S5 K3 L- U4 }B. 为解决某问题的算法同为该问题编写的程序含义是相同的
" o4 U/ x- a9 JC. 算法的可行性是指指令不能有二义性
9 Q0 Z3 ]% Z, x  a# m0 A, yD. 以上几个都是错误的
8.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A. head==NULL
9 U2 b# [, X8 p- t5 V: VB. head→next==NULL
7 P, f6 F: T( ?- \+ xC. head→next==head
D. head!=NULL
9.链表不具有的特点是（ ）
& P- Z# W  ?* w5 A5 X& T/ FA. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
10.在一棵二叉树上第5层的结点数最多是（ ）
A. 8
8 i0 p7 }: @- P- J. D, OB. 16
/ m; n4 d! _1 @6 IC. 32
7 i1 U6 Y6 v3 ~9 T! o0 o' l' uD. 15
11.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
A. (rear+1) MOD n=front
B. rear=front
C. rear+1=front
. L5 G- Z6 [4 I5 O+ VD. (rear-l) MOD n=front
12.栈和队都是（ ）
( |- z/ ?1 Z8 \* `  s1 DA. 顺序存储的
2 a9 w! r+ P0 B1 ^B. 线性结构
C. 链式存储的
1 P: s- ~, {4 MD. 非线性结构
2 K0 I. w4 Q# U  _; }. y9 T  e# z* l13.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
14.算法的计算量的大小称为计算的（ ）
& Q+ z& q. h6 ^6 BA. 效率
B. 复杂性
C. 现实性
1 m7 a, _  M' C8 ]4 \D. 难度
$ P$ E! N& B( W7 N% F6 M% f: P1 _15.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
1 a; y, \% K+ y7 J  ^9 Y8 H. B! SA. p->next=s;s->next=p->next;
B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
/ c3 S8 T$ P! yD. p->next=s->next;p->next=s;
) R8 ^( ~& L. ]' x, _1 t16.连续存储设计时，存储单元的地址（ ）
% M0 H  a7 w, A8 r1 A$ U9 Z) P: A( ?A. 一定连续
( I6 }9 r0 w8 Z0 y+ |9 e4 XB. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
! `0 h7 c6 ^' X- r# y: t17.下面叙述正确的是（ ）
$ q: Q$ m0 j" |A. 算法的执行效率与数据的存储结构无关
B. 算法的空间复杂度是指算法程序中指令(或语句)的条数
! @5 y, x* o( GC. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
4 t6 }/ \, S7 E3 P9 d  R18.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
2 l: J' p; ^2 mA. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
: U/ |5 N6 j2 f8 o2 Y5 ?1 MD. 栈
19.一个算法应该是（ ）
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
6 b* u) v5 e8 p& MD. A和C.
20.栈在（ ）中应用。
" z: B, n- s8 ^4 b9 V( dA. 递归调用
8 h# y6 W4 z- p7 MB. 子程序调用
: a1 z) H1 m) gC. 表达式求值
D. A，Ｂ，Ｃ
21.对于栈操作数据的原则是（ ）
% b- u. w, n$ b1 JA. 先进先出
0 q% F1 j5 ]) P6 h% J8 v, jB. 后进先出
7 @7 w* U6 X, v- l7 f7 |4 xC. 后进后出
" }) r* ?4 u$ F) hD. 不分顺序
22.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
& ^# a- p6 [; g7 T2 EC. 匹配
D. 求串长
23.一个递归算法必须包括（ ）。
A. 递归部分
1 t' \. r1 q# HB. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
24.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
. \2 q) S( Q. a0 _7 G, \; G( jA. O(n) O(n)
2 D) T2 F% ^& a+ o3 d% w7 DB. O(n) O(1)
# a& |, W  a& x+ M3 a( l0 z( NC. O(1) O(n)
D. O(1) O(1)
" S1 C) D! E) ^9 S- N25.已知串S=‘aaab’,其Next数组值为（ ）
4 p) C* ~  [+ C. i" W6 zA. 0123
B. 1123
C. 1231
$ u: i, n1 W/ O' ?D. 1211
多选题
1.以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
B. 线性表
C. 二叉树
) K% U( c: W& U1 K$ _% A7 Y! SD. 栈
9 f8 t5 V! b, \( ]2.以下数据结构中（ ）不是线性结构
+ a8 X! h! L; g: R/ e2 GA. 广义表
5 k9 Z0 ^" }" O5 KB. 二叉树
9 Q( r( t, }' U8 ?8 lC. 稀疏矩阵
D. 串
3.下面关于串的的叙述中，正确的是（ ）
, J/ x2 f3 m* O& \* P2 [" eA. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
( g2 L9 m& x* q" ]: d1 z7 hD. 串既可以采用顺序存储，也可以采用链式存储
- |8 I- j- Q8 k4 N/ S4.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）
- t  }) r0 P$ N8 k% K- m+ u) P$ U0 HA. a，c，b，d
B. b, c，d，a
  F, R8 e' z& N6 U% d4 z  t2 }C. c, d，b, a
D. d, c，a，b
5.下面关于线性表的叙述中，正确的是（ ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
2 Y' u& K' C1 P. c! d, H6 N0 z- ^C. 线性表采用链接存储，不必占用一片连续的存储单元。
  p1 N6 y( r8 y! r/ `0 K7 OD. 线性表采用链接存储，便于插入和删除操作。
+ \9 |/ {) P6 I判断题
7 J, y1 i& C) N" k: q6 z) z" o1.通常使用队列来处理函数或过程的调用（ ）
& i& {) m! J2 y1 B: C$ l% M3 LA. 错误
B. 正确
2.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
# ^/ s( t, M) Y1 d4 f3 p$ B+ uA. 错误
" Y5 _8 p, F/ ?. ZB. 正确
$ i/ A) T3 J; d! p% q2 H3.栈与队列是一种特殊操作的线性表（ ）
4 s5 ~+ t2 A# j/ b" n- a2 Z0 yA. 错误
B. 正确
& K5 r# O3 L6 D4 D% K! q+ K4.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
, z$ A% `& C/ ?- x! e2 C2 n3 vA. 错误
2 a* j, }) T; l# s7 c3 s. r$ TB. 正确
$ O& n" ?1 V! s/ C8 m5.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
: H7 {+ e- h2 X+ Z/ cA. 错误
! H+ a. R0 @) rB. 正确
6.链表中的头结点仅起到标识的作用（ ）
" H. R1 x) t' h' ^0 ^( ZA. 错误
! P% j" q7 q- S% aB. 正确
: ~) q8 c" G6 G  o4 S9 L7.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
A. 错误
6 a( X+ A3 ~2 c& m% I  yB. 正确
8.循环链表不是线性表（ ）
" F3 u& ]; z! v5 B- AA. 错误
; Z3 A, ?1 M' m* K# j9 d* x8 yB. 正确
/ H2 e$ F9 Y5 Z5 T) ]9.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
A. 错误
B. 正确
9 ~1 u: j) t8 @0 s10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
A. 错误
B. 正确
- a$ {  v; T0 n/ k9 s- a11.顺序存储方式只能用于存储线性结构（ ）
A. 错误
B. 正确
/ H0 E5 Y' [. ^9 ^* g  Q12.顺序存储结构的主要缺点是不利于插入或删除操作（ ）
. f' |; d/ G) D! J# a+ B% AA. 错误
2 O0 F( F1 X$ k" WB. 正确
13.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
" b5 Q3 F: ~5 z* `A. 错误
) b3 D; u) e1 D) _, OB. 正确
14.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
& ?+ u; q/ y/ c0 ]0 ~- p+ }15.消除递归不一定需要使用栈，此说法（ ）
) l. c( s5 s4 \  Q4 m) w7 R3 lA. 错误
B. 正确
/ J& C) z+ s, k$ V' H( X! n7 z16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
A. 错误
" L! H5 x. `7 {) CB. 正确
17.线性表的特点是每个元素都有一个前驱和一个后继（ ）
! }! ^; d" V/ DA. 错误
B. 正确
18.循环队列也存在空间溢出问题（ ）
- U. Y( @9 F( q- ~A. 错误
B. 正确
19.栈和队列都是限制存取点的线性结构（ ）
( H% X( v7 s; k, k' aA. 错误
B. 正确
20.栈是实现过程和函数等子程序所必需的结构（ ）
: S2 P+ e. G, G8 H9 O9 z& Y) d! A" Z+ AA. 错误
1 h7 [0 o! C+ {1 d4 S" NB. 正确