|
|
福建师范大学. W8 E$ e/ \2 d7 N
福师10秋学期《数据结构概论》在线作业一
" b7 @0 | i7 {# A单选题3 C+ c" c0 N$ d# A) X. i$ l# {7 L& f$ _
1.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）3 y \2 V2 B& D4 \4 P6 _
A. O（i）9 B* s% h5 G2 d" o6 A/ R" |0 v. |: |2 A
B. O（1）
4 L/ ~2 l' Y7 \! {+ pC. O（n）0 {" s7 c4 k7 b0 u% X1 d. h
D. O（i-1）
) r* Y+ V) [9 u9 e: e+ q! @资料：C' T c6 Z$ K E9 O
2.若串S=’software’,其子串的数目是（ ）5 q/ e3 L4 W6 Y% V/ T
A. 8
& h7 |( n( V& F- d: y/ |4 QB. 37- h$ Q" L0 Y( @4 e: o- n
C. 36
+ B2 Y. J3 V4 A* {" w [4 }2 jD. 9
; i' b9 n/ I( ?/ J7 P6 E- |* N* X资料：B5 L6 K1 A; m: Z/ t$ c/ y4 M) _
3.从逻辑上可以把数据结构分为（ ）两大类 L! y7 @. L: Q( P4 i
A. 动态结构、静态结构
+ \& c; k( p, ?, z, H; W' f( IB. 顺序结构、链式结构
( p% W: M# c5 _- n% OC. 线性结构、非线性结构1 {6 e0 O7 n O# u, j3 O* r
D. 初等结构、构造型结构& u* I! X2 ]8 k
资料：B
9 N7 V1 Z P" C' B* o* I+ @+ G" H4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。- ?3 h b- S. w% O3 N ]7 o/ Y( n0 G
A. O(0)
4 q9 A: q6 P3 t4 o/ EB. O(1). V2 [: g1 i, q
C. O(n). }8 U2 V& E( }8 ^7 V
D. O(n2)
* ]' `* x5 g' X$ V2 c7 G0 v% ^# Y资料：C# t0 Q1 r- ?) i6 {- v5 v0 S8 X- f
5.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。: ~+ E2 u% _, Y/ j- v
A. 不确定8 A! f/ l7 b2 H# }
B. n-i+1" ^( v; t* z7 Z
C. i
/ |0 r2 K7 i7 ~7 W, h% f+ XD. n-i
9 K/ a o! n! D: C7 j资料：B
& ?8 P! I, ~8 W' D7 n+ _. J* J3 z( i6.算法的时间复杂度是由（ ）决定的。
, W7 p; _: x9 mA. 问题的规模
5 T! x0 }# m8 d, ~! C, ?" eB. 待处理数据的初态
" h9 c& i+ h9 J) J) D7 DC. A和B5 i: z6 X6 K! o( g5 @+ [* V* X
D. 变量个数7 ~9 f5 H% _( h9 ^4 s: ?
7.下面有关算法说法错误的是（ ）8 |* J- q& `; {! O5 C u( Q3 c
A. 算法最终必须由计算机程序实现
4 D9 J+ ~/ u* E3 y) FB. 为解决某问题的算法同为该问题编写的程序含义是相同的: `1 V" J8 q* D& e8 F+ t
C. 算法的可行性是指指令不能有二义性' Z4 Z6 h) o- \" k
D. 以上几个都是错误的
# c- z2 R3 r9 F0 ~+ K8.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
2 k- [- I, U, a# EA. head==NULL
- r% ~, G2 |1 N2 E4 m) V/ lB. head→next==NULL
7 s- H3 X7 P8 s+ C) g0 r& vC. head→next==head
5 e& k; q$ \. a! T& {D. head!=NULL7 Y2 r" s2 A+ T0 _$ w2 l
9.链表不具有的特点是（ ）
& K- T' M: v5 D9 E2 AA. 插入、删除不需要移动元素6 \' |' R5 F, F0 O5 N: c
B. 可随机访问任一元素
( q/ j; R- A0 f7 p! V9 x6 ^C. 不必事先估计存储空间% I. [! d* N, E' D
D. 所需空间与线性长度成正比
! {# j2 r! L2 \# g6 o" l10.在一棵二叉树上第5层的结点数最多是（ ）, u, w/ T: a/ W0 ]
A. 8# e' H) x) [. g
B. 16
8 F4 m V! g( d: RC. 32. c) b& b" r3 y$ h0 X6 J1 B, O
D. 15% E% R5 u* [+ b1 X4 ]
11.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）
2 q8 U4 B* Y4 w, m4 C9 F6 v& u4 ?A. (rear+1) MOD n=front! d8 \8 {) K- D( u) l0 F
B. rear=front4 b0 A2 O) i5 s8 N, s5 c% O
C. rear+1=front
' V" o7 d6 ]' S( b2 }( v4 aD. (rear-l) MOD n=front' O1 r$ w& C# G! |) ?( r
12.栈和队都是（ ）
% ?1 V7 H9 W6 {) z& MA. 顺序存储的
( D1 D. [9 E: Q& M: yB. 线性结构
0 f `! l& [! {+ q3 Z [) ?* BC. 链式存储的
9 b) p7 s( ?1 @) b# jD. 非线性结构( o9 s! E4 Q8 |% x% H# p, f
13.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
5 j0 R) w7 n8 C% h# H$ _# gA. push,pop,push,pop,push,pop
4 A) h( x/ ^/ m7 L9 h3 h+ eB. push,push,push,pop,pop,pop
6 g. ]+ K# L2 l+ kC. push,push,pop,pop,push,pop9 ^& B( X' g0 V5 C, }+ l; M
D. push,pop,push,push,pop,pop, C3 _4 ^# C( b/ P7 X) U' V
14.算法的计算量的大小称为计算的（ ）
( P' I$ z( p6 m8 t9 x4 g( AA. 效率2 }9 G) }1 c- ^$ `0 Z9 Z0 X( V
B. 复杂性/ t' H9 ?" @* A+ }
C. 现实性$ h) g0 W7 l' _% T1 J/ p
D. 难度) s- W1 _9 z7 o3 I( |
15.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
9 ?% u1 `$ [" z: X" V: iA. p->next=s;s->next=p->next;
* N0 |- P8 [/ ~1 Y, b1 X LB. s->next=p->next;p->next=s;+ ^0 T* f7 Y; \
C. p->next=s;p->next=s->next;
( N4 w7 I6 ?/ @; |/ z: J7 D" bD. p->next=s->next;p->next=s;8 i6 j' t: h! j( R; r- x1 E
16.连续存储设计时，存储单元的地址（ ）) a# E5 i" Q2 a; Z7 t
A. 一定连续) J; e Z) c# W) c; }) W
B. 一定不连续1 P9 p9 v+ r& y5 \
C. 不一定连续
* H. g1 g. N0 I0 ]5 E- s1 k2 @2 xD. 部分连续，部分不连续( F5 `! F0 R4 P' G* d' W
17.下面叙述正确的是（ ） x" W( w+ q: x) p- s
A. 算法的执行效率与数据的存储结构无关2 t/ I* j8 O8 N* R8 N
B. 算法的空间复杂度是指算法程序中指令(或语句)的条数
5 |( A2 h! v' K3 k4 ZC. 算法的有穷性是指算法必须能在执行有限个步骤之后终止1 p g9 }+ n+ ?* r# Q
D. 以上三种描述都不对# z* Q Y; V E
18.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。: N6 @' X4 q7 {9 y& ?# d& b6 a
A. 线性表的顺序存储结构- f- \, H% Y. c9 x+ x9 w, Y, Y
B. 队列
# Q' M7 T* _& q/ J7 BC. 线性表的链式存储结构- k, x/ D* H- f4 ?: v
D. 栈
) r/ b" d& Y5 ?$ |1 N19.一个算法应该是（ ）3 J' T$ L) Y( H; a+ i# b
A. 程序
4 x: B" f# M/ FB. 问题求解步骤的描述
# U9 J% Z( G. N8 ^: | MC. 要满足五个基本特性
9 ~$ ~7 @2 w; A% KD. A和C.
) {) o4 C8 u8 \! b20.栈在（ ）中应用。( ]8 Q' }4 g) U* P* z
A. 递归调用/ j2 L2 J6 [( c/ d T* U
B. 子程序调用
4 U8 k2 _/ a- I% [" P _C. 表达式求值
% Y% A; \ _7 y% o/ u* MD. A，Ｂ，Ｃ
6 B9 i/ d7 ^2 i! Z, U21.对于栈操作数据的原则是（ ）
, q% @8 `& ]: |4 L& J3 AA. 先进先出
! U3 _1 W0 Y) Z# s/ \0 @. pB. 后进先出
: i' n& _0 z0 W- M0 H9 O7 MC. 后进后出! Y4 }; `# G; `
D. 不分顺序: B( K# R) i# @8 i
22.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）) z9 @1 m9 ~& W# c' Y' W% B* m
A. 求子串3 _) @3 c0 }8 { ]% J3 E$ @
B. 联接; s2 Y9 _2 C/ M- R* P& J( y, c% w/ f/ A
C. 匹配
; H( d; \3 {+ QD. 求串长
' x: Y/ q4 _/ b7 q) W. _3 S23.一个递归算法必须包括（ ）。
1 t N/ ?8 ^$ v9 IA. 递归部分- e% K# ^* |0 \7 I$ m: z+ J. o {
B. 终止条件和递归部分
; ?) Q. D3 m9 T- O! qC. 迭代部分
+ W* I3 r4 [7 c8 ]" z1 tD. 终止条件和迭代部分) N3 G* n I) P+ B# f+ b1 w8 o
24.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）) [$ J& K9 W Y
A. O(n) O(n)5 C3 o$ @1 A/ w) B+ b- Z% A" Z
B. O(n) O(1)
1 J2 o0 L% C5 `. LC. O(1) O(n)+ |4 l$ \5 ^1 i* y; j3 W* L4 v
D. O(1) O(1)
2 d% C3 r3 I! K" m! h25.已知串S=‘aaab’,其Next数组值为（ ）$ T. w0 F8 i" b7 l
A. 0123
4 y! y q- ~# J4 @* B4 ~5 i$ XB. 1123( W6 n0 S. w7 q; u) d& x9 Q* u6 ]
C. 1231
# i: X$ S/ t5 ^D. 1211
' ^0 K1 c3 T: p# r/ K多选题
" t( o! S3 X' J G G7 U+ A1.以下数据结构中属于线性数据结构的有哪些（ ）
* G0 [7 f/ e* Q/ aA. 队列
# }' }* K, Z" p) z9 E3 Z. F- NB. 线性表& D* k7 N" G1 z4 S
C. 二叉树
+ N$ M: S& M+ V" v; f) [5 E, L( d& @D. 栈; [9 d3 f% q+ @; ]3 N( q: A
2.以下数据结构中（ ）不是线性结构
! J& k3 v+ `1 `1 oA. 广义表
9 @- V: g6 m4 F# lB. 二叉树, a/ q6 ~) t) ]9 o- ?" l; h
C. 稀疏矩阵) U% Y+ Q# m. _( c
D. 串
0 x9 X/ I5 V# y3.下面关于串的的叙述中，正确的是（ ）
7 @" k3 N# ?4 j( qA. 串是字符的有限序列
* `8 J$ o! x2 x& j" R0 K5 B8 LB. 空串是由空格构成的串
x9 m$ ~" n/ P; H! AC. 模式匹配是串的一种重要运算
3 D0 p4 U5 D/ J) E% z2 rD. 串既可以采用顺序存储，也可以采用链式存储" C$ s4 t8 h! y
4.某堆栈的输入序列为a, b，c ，d,下面的四个序列中，可能是它的输出序列的是（ ）( A( r0 X- S; s, F5 _9 l- F
A. a，c，b，d, {& e2 t/ c" C$ Z& {8 O$ z$ A, R& t
B. b, c，d，a* z3 ~& @5 r8 W& j
C. c, d，b, a
T2 C0 P, i7 I8 d' t; DD. d, c，a，b- T- t6 ^7 o8 U# R. A+ x0 ~
5.下面关于线性表的叙述中，正确的是（ ）
9 J, a; Y* ?& c9 SA. 线性表采用顺序存储，必须占用一片连续的存储单元。9 ^. }: C; G6 X' |, j4 D
B. 线性表采用顺序存储，便于进行插入和删除操作。
* o. B" f" R- C' WC. 线性表采用链接存储，不必占用一片连续的存储单元。
- p. ^1 {3 k! n' d% V v p5 HD. 线性表采用链接存储，便于插入和删除操作。
4 h0 u& [6 p( D* {" y: c+ c判断题
1 D( m/ z* w- u. ^1 ]1.通常使用队列来处理函数或过程的调用（ ）7 c" e% G, C F$ w' G/ t
A. 错误' `( O! f9 o) |: d$ P) {6 i. f
B. 正确7 I3 b; c. g' K9 R. ~; P
2.算法的优劣与算法描述语言无关，但与所用计算机有关（ ）
% R8 |2 B5 F, K5 e, CA. 错误5 K. z2 U0 t- x$ L9 \
B. 正确
" k9 |& u' Z3 S) Y' d. H3.栈与队列是一种特殊操作的线性表（ ）; ~9 v2 Q* R. b" i
A. 错误
9 n/ q( _7 x' X. qB. 正确
1 |0 S# v9 o" n& K* R4.队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。
- @& Z. g! }) L3 a4 RA. 错误. X6 m3 {% Z+ B! c+ R0 x- O
B. 正确
3 ]. @. G1 I, T# n$ P5.在顺序存储结构中，有时也存储数据结构中元素之间的关系（ ）
# [& @( ?1 L: J( E! PA. 错误( \7 J/ N/ Y5 G5 M6 `& G
B. 正确. p7 M( ?0 _; i6 X
6.链表中的头结点仅起到标识的作用（ ）
" ^3 p4 \' A1 ]A. 错误- x2 \5 @* W$ Z! k7 c& M
B. 正确
; b; J d L% T5 W, `7.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。. C, \( y' F7 r7 H/ c8 U
A. 错误
: C: c, m$ v; o0 L( OB. 正确$ N" v% d6 k% N" ]% M
8.循环链表不是线性表（ ）
; Y& H3 }% V; q4 e3 fA. 错误
& [! n. ~. g# B7 W6 t7 RB. 正确
6 S: Y* h: F0 r" B& r9.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
5 `+ I; \7 J* x7 ~4 u& Y* G' ?, WA. 错误
" C; h# N; Q0 v& [B. 正确
; ?7 G7 o/ D1 H8 M10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。/ J" Y. `7 X! R
A. 错误
; k# @4 P* w% a" D6 B4 }1 t) n; L5 f% iB. 正确6 \5 {9 ^7 b3 E/ i$ S
11.顺序存储方式只能用于存储线性结构（ ）
4 G0 ^" \2 m) ?A. 错误
3 W7 f0 I% o) N5 X P5 N1 T- t1 @B. 正确
/ J1 c9 m( ~$ h5 i12.顺序存储结构的主要缺点是不利于插入或删除操作（ ）
( z5 _+ Z+ U# Z2 X' ~0 ?A. 错误
' f: J. K' N- Z* D/ f; @B. 正确
1 |2 _$ O5 Z, h: a6 {" v: }13.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）" ?' p: |6 s7 e' c- @( z8 y, o
A. 错误1 Q! q/ H- B0 i+ S! C0 X0 l
B. 正确7 t; \0 s' ^! x4 W0 X+ x0 e
14.对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
0 Z# |# b( i Q! B% @1 k# rA. 错误
' l3 l: K+ R5 z0 Q& v ^3 kB. 正确6 w8 e( n) I/ V1 r+ O. @# Z
15.消除递归不一定需要使用栈，此说法（ ）4 e: b; M k$ ], l, M. D
A. 错误
& t* q1 G J+ fB. 正确# Y5 `, D8 s9 B9 ?) I
16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）6 x/ P+ l, Z4 ^0 ?+ @% q
A. 错误
- t6 O' q; @; X9 D1 G1 H3 bB. 正确2 X3 ~; f$ S P C0 W4 X2 p
17.线性表的特点是每个元素都有一个前驱和一个后继（ ）6 e% Y8 ]* I" x+ R8 F
A. 错误; Z& \1 }- C+ {' X2 a
B. 正确
8 Y7 q! x* k- b" v& l0 N" U: p18.循环队列也存在空间溢出问题（ ）
' r0 K+ C3 E3 Y& K' O# V& DA. 错误" m3 e% Y2 C4 A" ^! H9 u/ X6 {
B. 正确7 ~! b2 F4 T: I# N8 b$ o
19.栈和队列都是限制存取点的线性结构（ ）
8 R' c& S, w9 ?# a+ Q3 D% b: zA. 错误
5 n7 ~& }, q/ K- M+ UB. 正确' C2 Y: ?6 e* F4 e8 W2 e2 g
20.栈是实现过程和函数等子程序所必需的结构（ ）' A( |: I7 V! X3 x- X1 q
A. 错误
0 j9 J+ `3 Z0 P, O& jB. 正确 |
|
IP卡
狗仔卡
发表于 2011-2-12 11:05:54
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
