福师11春学期《数据结构概论》在线作业二

久爱奥鹏晓林

一、单选题（共 25 道试题，共 50 分。）V 1.  若串S=’software’,其子串的数目是（ ）
! N$ s/ |* j( \! O' OA. 8
  z. U$ A5 J9 E% p7 x! |$ {, PB. 37
% @9 H* }1 e* YC. 36
( O1 }% K* w4 Y; gD. 9
" e2 r# Z3 q( @& o* D1 p      满分：2  分
2.  在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）
A. p->next=s;s->next=p->next;
! [! ~7 v% {: M) Q: S9 }/ F, F5 kB. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
  s$ t; D" y) b% N4 eD. p->next=s->next;p->next=s;
7 C4 l# p7 D' A) t+ Y2 r$ S      满分：2  分
3.  链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
# {1 |( ]  b# }* N! g. {* w1 KB. 可随机访问任一元素
& H; f7 U! `( h3 a6 Y, qC. 不必事先估计存储空间
D. 所需空间与线性长度成正比
5 D2 U9 Y; c/ A0 q( F% a3 J      满分：2  分
4.  对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
9 v* D( }" f. o: O7 U( vA. 选择
B. 快速
C. 希尔
D. 冒泡
6 c9 t! P0 \( Y, z5 @$ V8 ?/ z      满分：2  分
9 w! s7 S8 b: x% t2 V# t, [0 ^5.  有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列（ ）
" [* w8 G: ?: Q, _& OA. 5 4 3 6 1 2
5 [* W1 d" A: d. C: y0 [, |  E% yB. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
      满分：2  分
6.  适用于折半查找的表的存储方式及元素排列要求为（ ）
A. 链接方式存储，元素无序
B. 链接方式存储，元素有序
C. 顺序方式存储，元素无序
D. 顺序方式存储，元素有序
  ^7 {$ i7 t- L7 |* P/ x      满分：2  分
7.  字符串‘ababaabab’ 的nextval 为（ ）
7 ?! X- q% f1 C+ ^+ i( e5 [" oA. (0,1,0,1,04,1,0,1)
B. (0,1,0,1,0,2,1,0,1)
8 |% y# @. e( W" y: ?/ SC. (0,1,0,1,0,0,0,1,1)
# f; Y* ?, B( AD. (0,1,0,1,0,1,0,1,1 )
      满分：2  分
8.  对于栈操作数据的原则是（ ）
A. 先进先出
: Y/ d' R( M  S2 B/ J7 X/ bB. 后进先出
C. 后进后出
D. 不分顺序
      满分：2  分
9.  下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;
A. O(2n)
4 l# ]: u0 s  `: X0 p7 AB. O(n)
1 i7 P6 _( b! @6 UC. O(n2)
; P4 Y+ y% d5 \3 w2 @: \6 qD. O(log2n)
      满分：2  分
1 o9 z$ N, }( X10.  散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A. 最大概率
B. 最小概率
8 c/ l* ?5 |. i: u. _, h7 M, x9 XC. 平均概率
D. 同等概率
; L3 G0 I, ^3 |! C6 }% \      满分：2  分
11.  在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
A. O(n)
, H6 w* Y2 r* L; r' BB. O(n＋e)
6 Z" i4 \: V! t, A2 r6 G: ?) ?C. O(n*n)
9 s7 t8 T- s/ z1 {4 E( v2 rD. O(n*n*n)
! }- b+ W" x  e" r% I      满分：2  分
0 E: B7 ^3 B* H; t) h' B  z  ^4 E12.  栈在（ ）中应用。
A. 递归调用
B. 子程序调用
C. 表达式求值
3 H# T1 W! k9 a& C7 u3 x4 LD. A，Ｂ，Ｃ
, Y6 g) t1 H7 n- b      满分：2  分
, l+ g* `6 T! w4 f# }13.  一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
2 Z; u) s- {' rC. DACEFBG
1 \& f% n8 y: f; m7 XD. ADCFEG
      满分：2  分
14.  从逻辑上可以把数据结构分为（ ）两大类
" P; \; h; s1 x. _4 aA. 动态结构、静态结构
* a7 T  A( E4 a. u& {B. 顺序结构、链式结构
, D+ `0 S0 j: |: I0 ZC. 线性结构、非线性结构
, F5 Y( f% v3 k" w4 J+ v7 e! nD. 初等结构、构造型结构
" b6 ^( X8 L1 G  i. ?7 M      满分：2  分
15.  若要求尽可能快地对序列进行稳定的排序，则应选（ ）
* o3 i  n& {! Q" rA. 快速排序
) w0 \' d% v! |8 |! RB. 归并排序
7 g" F% D& [, U0 Y/ BC. 冒泡排序
7 t! R6 i3 q0 Y- |" q4 zD. 堆
      满分：2  分
16.  已知串S=‘aaab’,其Next数组值为（ ）
A. 0123
4 [, [4 U$ y, r; A. D. hB. 1123
/ Y' n, f* ^& S4 V& S6 V% cC. 1231
& q1 _8 O6 J: fD. 1211
      满分：2  分
17.  树的后根遍历序列等同于该树对应的二叉树的（ ）
A. 先序序列
% P9 |7 y' i- P7 f8 Y* g5 d- mB. 中序序列
3 u# S6 ]4 [3 }/ @# T; UC. 后序序列
6 `! J- V( J; I4 X, E, I+ |D. 都不正确
8 x# T8 G. h$ W/ j      满分：2  分
+ y. u; l1 H' w( b4 P" ?6 x18.  设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
$ D  M" H9 G( q$ cA. m-n
0 F) Z& l9 k# K7 LB. m-n-1
C. n+1
2 y" z% Y6 @" w' R; c0 n- ND. 条件不足，无法确定
      满分：2  分
0 }! v7 ^8 G- h5 S+ @! g+ G9 r19.  设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1
B. n(n-1)/2
1 U7 i1 X4 W6 d6 W( E7 v) `7 e. fC. n(n+1)/2
: ~* ~7 U! i7 W" {2 Y" ZD. 0
" k2 _/ @! s. |& q9 s3 P) F4 f$ ]      满分：2  分
20.  具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
  x* \- E* q5 @; o, C6 x% Y2 e, d! XC. 10
7 h* Z2 Z1 p7 v2 YD. ll
      满分：2  分
5 X, }' a" S% B( E3 |' Q9 y21.  下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）
/ k% m0 b' o  q) S9 W; B: fA. 选择排序法
B. 插入排序法
7 J: i/ n+ D5 a9 L# }' u. T, g! hC. 快速排序法
D. 堆积排序法
      满分：2  分
22.  在一棵二叉树上第5层的结点数最多是（ ）
A. 8
, e7 Y; @7 r- N. b: t, ]B. 16
C. 32
5 i# E6 T( D* q1 v9 Y2 iD. 15
+ ]/ p+ k( L/ E9 j; T: i      满分：2  分
; v0 i# N) T. _+ [, o23.  设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
% _; k5 l6 O# |B. 联接
C. 匹配
D. 求串长
      满分：2  分
24.  若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
( j4 ]8 c+ a- q0 KC. O(n)
D. O(n2)
- j! }2 k& W2 e/ S6 i! M' Z      满分：2  分
4 F* Y- ^* K* A* u1 q9 |# F25.  从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
7 W5 c9 k! m! j" C3 N# c0 gA. 插入
B. 选择
C. 希尔
8 D$ Y5 |" j5 |D. 二路归并
      满分：2  分
二、判断题（共 20 道试题，共 40 分。）V 1.  消除递归不一定需要使用栈，此说法（ ）
A. 错误
9 B& r4 z* n6 I/ MB. 正确
      满分：2  分
2.  栈是实现过程和函数等子程序所必需的结构（ ）
A. 错误
3 \: @0 o8 m/ g' I6 _1 OB. 正确
% O5 J+ v: D7 A& _# x3 T      满分：2  分
7 J- _0 i( M' {3.  对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
/ u2 P- v0 p. y- |9 O% b: `B. 正确
      满分：2  分
4.  用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
A. 错误
! ]! C' f, F6 m! @8 wB. 正确
6 E8 {# ~3 r( W. J* k# o6 C; J      满分：2  分
2 V; c, H& j5 i9 K5.  任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
A. 错误
B. 正确
      满分：2  分
6.  完全二叉树一定存在度为1的结点（ ）
A. 错误
3 X7 \: D! h1 G( A1 z$ LB. 正确
+ O3 c- r2 @0 Z+ N' C      满分：2  分
& s/ G$ m: C7 o( d0 G& v7.  在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
A. 错误
, F$ U0 W% Y+ n5 K( r1 qB. 正确
      满分：2  分
5 b6 n+ ]! L3 R( W7 f/ b8.  采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的
  Z3 B, o% M! ?7 j) JA. 错误
B. 正确
      满分：2  分
; u" ?8 i4 ^: Q* W: |: w2 P9.  顺序存储结构的主要缺点是不利于插入或删除操作（ ）
2 T0 o' u" F" gA. 错误
' z; y- B- ]$ |# Q7 u) iB. 正确
$ B$ X* y) ^1 g$ w; J/ `      满分：2  分
10.  直接选择排序算法在最好情况下的时间复杂度为O（N）（ ）
A. 错误
  A; P) M; C3 i" Z8 m& p5 gB. 正确
8 A1 K7 v( z" K4 M& S3 W      满分：2  分
) y: F$ Y8 L+ u+ O( b* s+ B3 Z3 J11.  队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构（ ）。
$ d4 I* |" A8 h- Z+ v+ |! D$ z* FA. 错误
. Q3 V2 A# s' H4 sB. 正确
      满分：2  分
12.  一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
A. 错误
B. 正确
      满分：2  分
13.  排序算法中的比较次数与初始元素序列的排列无关（ ）
A. 错误
4 l2 j) ]: W2 X3 ~; C$ n$ iB. 正确
' D' \6 N9 U- t( L      满分：2  分
14.  用树的前序遍历和中序遍历可以导出树的后序遍历（ ）
A. 错误
$ Z0 N/ D$ A  _5 m, E3 qB. 正确
      满分：2  分
15.  健壮的算法不会因非法的输入数据而出现莫名其妙的状态（ ）。
% C) b) L% k$ oA. 错误
+ Y5 r/ o. t9 u7 N. V7 _B. 正确
      满分：2  分
* C( Q5 P5 s, ~5 t; G16.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
0 a6 S; h9 z1 z; ?3 E1 }* VA. 错误
B. 正确
/ t( Z' m5 `$ B* U$ G      满分：2  分
: A" s! B5 n: z; Z8 e1 |7 `- p9 k17.  当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（ ）。
A. 错误
3 g/ L2 {( h" w& H% R5 }7 k. oB. 正确
      满分：2  分
2 I: a2 G" H1 t18.  二叉树的遍历结果不是唯一的（ ）
4 K6 x8 s& O9 Y9 UA. 错误
- F3 O! ]2 l, M2 z, F8 V4 jB. 正确
5 C! c3 k# @8 e' s) P. G4 D      满分：2  分
19.  二维以上的数组其实是一种特殊的广义表（ ）
+ O% W" `' ]3 P* R# ^A. 错误
B. 正确
* F$ h9 S4 d. P, U6 c% t$ B      满分：2  分
20.  在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的（ ）
; C. @4 ?/ x1 i8 DA. 错误
4 _" |1 g- |, mB. 正确
" o# O7 ]4 G3 h. e' S5 W6 W3 ?4 f. E! Y      满分：2  分
, F; G* q& q+ E1.  以下数据结构中属于线性数据结构的有哪些（ ）
0 t1 d- Q. ~8 e+ H* s, OA. 队列
" D, w" H  h  f, k3 {5 j- l% @: ]B. 线性表
C. 二叉树
D. 栈
      满分：2  分
8 p; l* j  V8 c7 s& B( |2.  在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（ ）
5 D# X& C& u) X/ oA. G中有弧<Vi，Vj>
/ G, K" W- m5 N% c+ t. NB. G中有一条从Vi到Vj的路径
C. G中没有<Vi,Vj>
D. G中有一条从Vj到Vi的路径
      满分：2  分
3.  下面关于线性表的叙述中，正确的是（ ）
A. 线性表采用顺序存储，必须占用一片连续的存储单元。
B. 线性表采用顺序存储，便于进行插入和删除操作。
C. 线性表采用链接存储，不必占用一片连续的存储单元。
D. 线性表采用链接存储，便于插入和删除操作。
      满分：2  分
* T* E+ d' r( k) n4.  下面说法正确的是（ ）
7 \! `1 G. U: J) s0 M' d; WA. 广义表的表头总是一个广义表
! G- n7 d  a4 b1 t! aB. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
7 u" M" b" H$ M+ L/ f      满分：2  分
5.  下面关于串的的叙述中，正确的是（ ）
A. 串是字符的有限序列
B. 空串是由空格构成的串
) |4 R- R$ H5 M; `, W$ j. ~4 f3 H+ `C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
' E$ ]9 d+ L% t      满分：2  分