14春福师《数据结构概论》在线作业二辅导资料

谋学网

谋学网: www.mouxue.com 主要提供奥鹏辅导资料，奥鹏在线作业辅导资料，奥鹏离线作业辅导资料和奥鹏毕业论文以及其他各远程教育作业代写服务，致力打造中国最专业远程教育辅导社区。
3 n7 M6 B& {: k7 y' o
9 t! e+ N5 F6 S; J0 H一、单选题（共 25 道试题，共 50 分。）V 1.  从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
& e9 [/ U# F3 X/ xA. 插入
' Z( H- \& F1 D6 U% OB. 选择
C. 希尔
) V! X2 U# ?$ t: Z4 }! Q* SD. 二路归并
      满分：2  分
, [  [5 W! Z- F  B4 U- L0 F2.  线索二叉树是一种（ ）构。
6 s" M: t: i! X1 YA. 逻辑
- u8 m& d3 \$ h4 M+ r3 ]! BB. 逻辑和存储
1 Q  @3 t" p, A$ yC. 物理
D. 线性
      满分：2  分
3.  设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
' y; E5 u( ^; z0 ]A. 求子串
B. 联接
C. 匹配
D. 求串长
) Z) F% O9 F5 n      满分：2  分
4.  设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
- B$ c2 R  T. N* i. f6 MA. 1和1
7 H: N9 F; v4 c; E$ x0 kB. 1和3
C. 1和2
5 b) T, @, i+ z: \D. 2和3
& Q1 o2 C7 o  _2 O' `+ q6 I  h- N$ W      满分：2  分
5.  一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
. g) ^+ C. f! N7 q% Q' pB. ABCDEFG
( O3 j! |# g$ ]; I1 B, E( oC. DACEFBG
D. ADCFEG
% f. t: b( X, t5 K3 ], P      满分：2  分
6.  （ ）的遍历仍需要栈的支持.
- X/ V  p1 P' O: v7 KA. 前序线索树
B. 中序线索树
! `( m$ J* j7 ~. f* |C. 后序线索树
  Y! j# @5 C! }% n+ h' CD. 不确定
      满分：2  分
$ Y" `* d! P# [7.  对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
8 v6 o* I5 c8 }9 N% _- Q- vA. 选择
B. 快速
9 f  a& M% P2 K! R8 r  x" O! h; K* vC. 希尔
D. 冒泡
      满分：2  分
4 K) y8 G& I8 Q; {8.  算法的计算量的大小称为计算的（ ）。
A. 效率
/ a% e& X' C. R- _; U3 H) ?B. 复杂性
0 m+ v+ C) W/ K% d% i' Q6 d# xC. 现实性
! a( B* i6 c! @1 d% t6 y8 {D. 难度
      满分：2  分
2 Q% G& l' ?$ A" Z! Y9.  以下数据结构中（ ）是非线性数据结构
A. 树
& W  I: B; {. |2 `+ B# |/ V/ N5 d, JB. 字符串
2 B3 J% @! A0 v: {6 l2 \C. 队
D. 栈
      满分：2  分
10.  一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
+ j8 U- d7 r* J" RA. 不确定
B. n-i+1
/ ~; h4 s7 X0 o# xC. i
D. n-i
      满分：2  分
11.  下面叙述正确的是（ ）
A. 算法的执行效率与数据的存储结构无关
+ r1 A; u) Y( xB. 算法的空间复杂度是指算法程序中指令(或语句)的条数
C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止
D. 以上三种描述都不对
( [9 f8 t& \5 B8 G7 l# z0 d      满分：2  分
12.  在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A. O(n)
B. O(n＋e)
C. O(n*n)
9 H/ }8 _1 ]* R0 @3 D/ LD. O(n*n*n)
; ~+ {; ]- z. o$ D" c# @9 [      满分：2  分
4 O9 F& x) u: A7 P7 B; b7 P8 B1 e5 c13.  线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
" t  F# a8 n- i+ H4 M* Q1 V# O- u9 P; |B. O（1）
9 n% @7 l: d7 s1 r4 ]3 mC. O（n）
D. O（i-1）
5 |5 Z" S6 ?: Z9 c/ y      满分：2  分
14.  广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A)))))
6 ^4 @( z$ u% J, h7 @. `A. （a）
% L( j# l% y7 C( N! j3 K! _B. A
C. a
D.
, K6 Q8 n  E4 [2 ad
  u) T$ c5 k& V2 l
9 D9 H/ K2 }6 E0 Q      满分：2  分
' [7 T; s! X5 ?/ q15.  字符串‘ababaabab’ 的nextval 为（ ）
A. (0,1,0,1,04,1,0,1)
8 u6 y6 r8 W" Y/ k5 UB. (0,1,0,1,0,2,1,0,1)
C. (0,1,0,1,0,0,0,1,1)
% n+ V9 A1 U0 f, z# {0 aD. (0,1,0,1,0,1,0,1,1 )
      满分：2  分
16.  栈和队都是（ ）
9 L: z/ O' [# H/ K4 u$ cA. 顺序存储的
B. 线性结构
7 y  u. U- L' f& L- kC. 链式存储的
9 M. \: m% m7 j2 g+ R9 L0 k8 W% Q8 {D. 非线性结构
      满分：2  分
* M* V, z  C, Q0 _8 h17.  对于栈操作数据的原则是（ ）
# @6 k& B0 ~: A, kA. 先进先出
* w2 p/ i6 S- O2 ?; f  y% eB. 后进先出
C. 后进后出
! @( Y; F3 M* Q& q2 O) QD. 不分顺序
      满分：2  分
18.  算法的计算量的大小称为计算的（ ）
A. 效率
B. 复杂性
- N5 e2 t! Z4 n. oC. 现实性
D. 难度
9 d8 K  O# n( `, m      满分：2  分
19.  链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
& r1 n" B! b$ N8 P+ I6 r1 m; xC. 不必事先估计存储空间
6 w  j3 Y9 }/ R! S4 p3 T; zD. 所需空间与线性长度成正比
& K% t3 l" f. ^- X* n      满分：2  分
0 d0 g& g- |* K+ q9 o4 g20.  下面给出的四种排序法中（ ）排序法是不稳定性排序法。
A. 插入
* L  A' R9 D0 }6 n" s9 uB. 冒泡
1 [) p4 g+ O( D1 j- SC. 二路归并
D. 堆
9 {# F  _; P7 y) F" _* A8 {      满分：2  分
4 d- U3 ]6 z0 g' c" k21.  由3 个结点可以构造出多少种不同的二叉树（ ）
A. 2
& d' I8 a6 Y7 u( HB. 3
C. 4
: _7 E8 O$ S! Q) X  `D. 5
# ^3 m; B( h# h3 J+ l1 \& A      满分：2  分
- X1 {3 A7 |8 H9 p8 \) h2 _+ m22.  在下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;
A. O(2n)
' v+ a2 C0 D% Q8 X8 ?. H+ i3 nB. O(n)
% \$ [, G' c) x& q& T# BC. O(n2)
D. O(log2n)
      满分：2  分
23.  对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择
B. 快速
C. 希尔
6 e  A" z- |7 n1 a) }( u5 h, Z$ xD. 冒泡
      满分：2  分
7 e1 T+ Y! \# m; U1 Y8 e. C6 N2 Z24.  若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
A. 前序
B. 中序
7 o5 u6 t) _7 K8 F9 {% xC. 后序
D. 按层次
. L  O% i- |( G9 C, X& P2 R3 j      满分：2  分
. q! I9 h; E( G# a* Z25.  对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
* B1 I0 j7 F5 ~- C1 PA. O(n) O(n)
B. O(n) O(1)
% x" D5 e3 J* KC. O(1) O(n)
D. O(1) O(1)
      满分：2  分

" m) u0 Z2 c9 F2 }; G. O: l二、判断题（共 20 道试题，共 40 分。）V 1.  在顺序存储结构中，有时也存储数据结构中元素之间的关系。
$ I6 ~7 ^8 F! N! d4 u2 G4 t2 C' eA. 错误
0 m, {  ~1 L  y/ @4 k) G$ a$ v+ UB. 正确
      满分：2  分
2.  当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素（ ）
A. 错误
B. 正确
3 s$ q" e5 U& g  G      满分：2  分
3 _6 j; s( f/ u3.  在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
A. 错误
B. 正确
1 T5 M4 c/ P+ v' x" D/ W0 L% L      满分：2  分
4.  消除递归不一定需要使用栈，此说法
A. 错误
B. 正确
      满分：2  分
/ T( h6 g- e- o5 ?7 R" d5.  队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
/ [- w1 l  u2 d" ]' C) }A. 错误
B. 正确
      满分：2  分
6.  二维以上的数组其实是一种特殊的广义表（ ）
- q; w4 d( F+ P0 Q3 ^* WA. 错误
B. 正确
( k2 P8 P' f( @" ~. G3 r0 H      满分：2  分
( @) J& R7 r; u4 V  E! c7.  用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
A. 错误
B. 正确
      满分：2  分
8.  循环队列也存在空间溢出问题（ ）
A. 错误
* g* {* l- F% G: D8 [5 hB. 正确
      满分：2  分
9.  任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.
A. 错误
! Q3 T$ A2 ]  t. |2 I, H: P0 bB. 正确
8 R7 _& ^9 E9 Z$ q) u8 j" N      满分：2  分
10.  队列逻辑上是一个下端和上端既能增加又能减少的线性表（ ）。
A. 错误
: E% n4 k, G% oB. 正确
      满分：2  分
$ C. x' m% x# }! U- A11.  在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
A. 错误
$ A% G3 B7 n9 `- E7 b* pB. 正确
% x& |/ D  F" B5 S      满分：2  分
12.  线性表只能用顺序存储结构实现（ ）
A. 错误
  h0 }' w2 t6 U9 v6 z& j9 jB. 正确
: Q5 @1 c* b' t- j$ i0 J6 a      满分：2  分
9 i" y$ p$ W- l) n, D/ L13.  顺序存储结构的主要缺点是不利于插入或删除操作。
A. 错误
2 _+ z7 h! U& \$ I  s5 C+ |  [5 o9 QB. 正确
      满分：2  分
14.  顺序存储方式只能用于存储线性结构（ ）
/ ?$ t5 O% A. o$ i# l/ S% u, `# RA. 错误
# H- }  t9 r- ]# }- k, _$ BB. 正确
      满分：2  分
15.  任何一棵二叉树都可以不用栈实现前序线索树的前序遍历
2 c7 _8 ~: _& Z9 `( @6 P1 s! tA. 错误
B. 正确
/ ~  f" a+ r) A      满分：2  分
16.  一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
A. 错误
B. 正确
      满分：2  分
17.  折半查找法的查找速度一定比顺序查找法快（ ）
A. 错误
B. 正确
1 \5 S7 z. m- _3 Q3 @% J      满分：2  分
* T( ~1 a/ Y6 [  @18.  健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
A. 错误
B. 正确
/ X5 p$ H0 d5 A$ @( s      满分：2  分
* k4 F9 |, j  ~19.  链表中的头结点仅起到标识的作用。
A. 错误
B. 正确
      满分：2  分
20.  顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（ ）
A. 错误
B. 正确
      满分：2  分
- f& q- {% K( r$ i1 i. R. Z
2 P/ \. G% C; k2 _7 N9 U9 ~三、多选题（共 5 道试题，共 10 分。）V 1.  以下数据结构中属于线性数据结构的有哪些（ ）
A. 队列
% ?& y2 ]' ]7 e9 G* z, _B. 线性表
C. 二叉树
+ g4 c% r8 o5 CD. 栈
      满分：2  分
0 R. m+ l& D) O& C; U) z2.  有关二叉树下列说法不正确的是（ ）
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
8 ~0 |2 R2 R0 }8 h/ T& YC. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
      满分：2  分
9 C  _+ y7 E& h5 Y3.  下面关于哈希(Hash)查找的说法不正确的是( )
% X/ f% |7 O5 ~! bA. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
% P. H/ I) |" C# T9 \C. 不存在特别好与坏的哈希函数，要视情况而定
+ `0 _9 B, o' X* E" VD. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
! L' k5 B6 P0 Z3 @      满分：2  分
9 V9 y3 [# R) j) d9 u: D$ |4.  下面关于二分查找的叙述不正确的是 ( )
3 J, y2 \7 @  n1 Z& _A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
0 k" F& T# \$ F, nB. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
( I* U5 y- _# R! s& }- V% b% \& L      满分：2  分
5.  下列说法正确的是（ ）。
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 图的深度遍历不适用于有向图
0 f* u5 {( P& M9 J$ H/ `" gC. 遍历的基本算法有两种：深度遍历和广度遍历
D. 图的深度遍历是一个递归过程
/ B! g4 A% d" A# R  Y5 j0 j      满分：2  分
0 c! V9 ?3 O$ r) t9 [% y
谋学网: www.mouxue.com 主要提供奥鹏辅导资料，奥鹏在线作业辅导资料，奥鹏离线作业辅导资料和奥鹏毕业论文以及其他各远程教育作业代写服务，致力打造中国最专业远程教育辅导社区。