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

久爱奥鹏网

一、单选题（共 25 道试题，共 50 分。）V 1.  一个算法应该是（ ）。
A. 程序
B. 问题求解步骤的描述
0 t. ]. _5 G  H4 u8 M- jC. 要满足五个基本特性
D. A和C.
( m* r# g6 a/ q% z9 b$ h1 c% e, B" o      满分：2  分
2.  下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
$ y1 O" a% ]4 p# lA. 堆排序
2 C* G+ E. N, N' bB. 冒泡排序
C. 快速排序
D. 插入排序
      满分：2  分
, T' j$ ]& z3 y' i3.  算法的时间复杂度是由（ ）决定的。
  K+ P& I& F: k0 S  I. i/ b/ SA. 问题的规模
/ W. _' J0 y6 QB. 待处理数据的初态
C. A和B
& Q9 j# [7 \4 @/ w( i) ?% t# ND. 变量个数
      满分：2  分
4.  在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A. O(n)
B. O(n＋e)
# O" o4 @/ E8 p+ {2 K5 xC. O(n*n)
D. O(n*n*n)
      满分：2  分
5.  线索二叉树是一种（ ）结构。
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性
      满分：2  分
; z! h0 l: ]" B0 [/ y, y/ o7 t6.  广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。
A. a
# G3 X" \5 D4 i: I+ P; hB. （）
C. （a,b,c,d）
D. （b,c,d）
      满分：2  分
7.  设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）
0 Y5 F% x, N/ e/ o& I# pA. 13
B. 33
C. 18
7 M" r2 e0 T% d9 Z, |* j4 OD. 40
      满分：2  分
8.  在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）
( z# T, d8 n! o/ |2 wA. O(n)
6 @8 d$ U6 u( d7 p% ]$ [3 xB. O(n＋e)
C. O(n*n)
D. O(n*n*n)
      满分：2  分
: B9 i; M8 W2 O$ B+ J9.  从逻辑上可以把数据结构分为（ ）两大类
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
      满分：2  分
; G5 T4 w1 q+ E2 |) G10.  字符串‘ababaabab’ 的nextval 为（ ）
  A8 u0 {; ]3 V5 h6 `0 CA. (0,1,0,1,04,1,0,1)
B. (0,1,0,1,0,2,1,0,1)
C. (0,1,0,1,0,0,0,1,1)
D. (0,1,0,1,0,1,0,1,1 )
$ q0 L5 d3 \- x  Z; ]      满分：2  分
11.  若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
$ z) F7 G+ m2 y5 LA. 3
" @4 B% P) u9 J# O) TB. 10
C. 15
5 f! e8 u8 E4 t7 U, ?' g7 V7 f9 YD. 25
      满分：2  分
  B( W/ w* ]6 O8 P7 q12.  一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）
A. 不确定
/ Q* o6 S8 j6 ~( I& `; c; _4 BB. n-i+1
* c" g$ g: T" E7 A/ MC. i
+ W. @8 f& j# w& q" JD. n-i
" k8 P4 G6 U- K      满分：2  分
13.  线性表是具有n个（ ）的有限序列。
A. 表元素
- d4 T: p( g( a5 j& fB. 字符
% p8 U8 F; I" T. E" q2 [0 p2 AC. 数据元素
D. 数据项
) N1 J) X" Y: f! p      满分：2  分
: g! t/ o0 Y% {3 Q5 |6 W" x# \14.  下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A. 堆排序
( }0 t9 m" r" @# r) hB. 冒泡排序
2 w& O: N7 i7 W3 n4 T1 gC. 快速排序
D. 插入排序
! r4 z( G! r" `& |2 I      满分：2  分
15.  关键路径是事件结点网络中（ ）
A. 从源点到汇点的最长路径
/ ^, y2 @6 e# _8 f: B0 kB. 从源点到汇点的最短路径
C. 最长回路
D. 最短回路
: ]7 G" A1 n( N( B( V      满分：2  分
16.  若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
: {  S1 i: Y/ Q* e+ @A. 前序
B. 中序
5 n: x# ?- v# |, x' VC. 后序
! M0 Z3 B5 N, x1 h! jD. 按层次
      满分：2  分
17.  对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
; O, B: j$ D( M, p9 Y, t' RC. 后进后出
D. 不分顺序
! A* g5 j0 J. c- T! y  w      满分：2  分
- i. t0 w& m5 v- W( x18.  有n个叶子的哈夫曼树的结点总数为（ ）。
A. 不确定
; G( p$ J: Y/ O5 v' @) _B. 2n
' i, K  ?( ?+ C* f( _# bC. 2n+1
D. 2n-1
      满分：2  分
19.  若串S=’software’,其子串的数目是（ ）。
A. 8
B. 37
C. 36
D. 9
      满分：2  分
20.  连续存储设计时，存储单元的地址（ ）
9 c' B, B; H+ z" A1 Y' Q& F" q# _, @A. 一定连续
6 ]6 @4 c  I" C: U9 vB. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
      满分：2  分
2 [8 A6 b. o: P/ Y  |0 e  E3 r7 ~! h* N21.  在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A. p->next=s;s->next=p->next;
0 n" f4 ~9 @3 d% v" j$ E1 lB. s->next=p->next;p->next=s;
( G$ s" m( H7 [; ^8 \C. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;
      满分：2  分
22.  连续存储设计时，存储单元的地址（ ）。
A. 一定连续
( h: a( ]" _: E. Z" @' ]B. 一定不连续
C. 不一定连续
/ G# P1 o/ q, Y8 f2 z# }D. 部分连续，部分不连续
+ u+ _) G( f& g( `9 c+ R, Y7 L0 t& v      满分：2  分
23.  用二分（对半）查找表的元素的速度比用顺序法( )
A. 必然快
- f6 e' n# v* I- Z* t; XB. 必然慢
0 M' M+ L; C: q6 ?! HC. 相等
& p1 c7 L$ r  m* UD. 不能确定
4 @( \- ^/ f4 @) ^' y) \      满分：2  分
$ T( m0 L$ n# m% w6 S/ `. i/ n24.  散列函数有一个共同的性质，即函数值应当以（ ）取其值域的每个值。
A. 最大概率
1 R2 M, ~, S# ]. Y  R* ~$ vB. 最小概率
9 a2 |( V" k# |6 D: B+ jC. 平均概率
D. 同等概率
      满分：2  分
' q* ~& e) l# b3 M# ?% p7 `0 C25.  一个递归算法必须包括（ ）。
A. 递归部分
; S* P* a6 t7 c" l% n4 b/ ]B. 终止条件和递归部分
8 W- T& L4 x. z5 q- z8 ^$ ~4 ]C. 迭代部分
D. 终止条件和迭代部分
( q; u0 K: K: k# }- J  w4 q$ h& e      满分：2  分

二、判断题（共 20 道试题，共 40 分。）V 1.  任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.
A. 错误
# M7 L5 X% O2 N" n$ z! l1 o+ FB. 正确
      满分：2  分
2.  任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ ）
& \$ m- y* v0 z. U% C6 t; h& B: cA. 错误
( R2 c" N8 W4 H6 TB. 正确
. S! c: ~* b3 h0 `( x9 j. x      满分：2  分
3.  当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素
3 J$ Z  c- J. v2 WA. 错误
" x1 G( r7 o' iB. 正确
      满分：2  分
' q# V% Y/ W& v4.  通常使用队列来处理函数或过程的调用。
5 K% s+ F3 \; R% ~- z! EA. 错误
6 b/ `1 Q" Q9 t) S/ w0 nB. 正确
2 i2 R) \% E3 z" i! t* N/ S+ s      满分：2  分
5.  对无序表用二分法查找比顺序查找快（ ）
& h3 C+ e; o, b, PA. 错误
B. 正确
      满分：2  分
6.  广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
A. 错误
B. 正确
; W; {! }. {9 K0 V      满分：2  分
" z$ W& c3 F4 X0 m7.  顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）
7 @# D$ F+ O( [  _9 B$ I# M  JA. 错误
B. 正确
: d0 \& S* \/ W  l' ^% S4 Y      满分：2  分
8.  数据元素是数据的最小单位。
7 V1 Z* t! X% V8 n7 AA. 错误
" i0 _5 t% U6 _9 l# AB. 正确
      满分：2  分
4 z2 s! w: E) Q5 C+ r- X9.  栈与队列是一种特殊操作的线性表（ ）
A. 错误
9 C: |# P" \5 v' jB. 正确
8 T; a6 Y# e  s" y+ n% y; X8 o) }" W      满分：2  分
& \5 u" p6 r( g/ \$ ~. K10.  就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
+ X, O# D! k5 qA. 错误
8 U5 r7 ]3 K' ^/ Z5 p$ P1 j+ hB. 正确
7 w9 J' o( o3 S- W* a+ p' @      满分：2  分
. B! }4 s4 C& Y, W( b9 K11.  消除递归不一定需要使用栈，此说法（ ）
/ ?* I) R2 c( uA. 错误
B. 正确
8 ?$ {  Z6 o5 s      满分：2  分
12.  广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（ ）
A. 错误
B. 正确
5 ?3 Z# `4 V6 g5 g      满分：2  分
4 @4 O  j, a2 j13.  对无序表用二分法查找比顺序查找快
A. 错误
B. 正确
      满分：2  分
14.  任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
: X) N6 c, S, g) A* }A. 错误
5 H/ A0 K& @- C" }B. 正确
      满分：2  分
15.  广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
+ s% U$ W' x  C* mA. 错误
B. 正确
      满分：2  分
/ h' u' R% N; w- |- {16.  线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）
) X; E! Z! U$ d) dA. 错误
B. 正确
$ B* N0 O! v, `& Q9 E6 ^% Z      满分：2  分
# w; J9 x( t( o1 }( `; |17.  排序算法中的比较次数与初始元素序列的排列无关。
A. 错误
B. 正确
      满分：2  分
18.  对任何数据结构链式存储结构一定优于顺序存储结构（ ）。
A. 错误
B. 正确
      满分：2  分
0 `" F) R0 Z6 ~& X1 Y" _19.  两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）
0 Q/ j6 m( E. gA. 错误
3 Y" f' B" ^/ _* X# ^* [B. 正确
- L( P, _) _! m; g% B1 ~. Q& g+ M      满分：2  分
' D; i# v1 u' E- Q& Z20.  线性表的特点是每个元素都有一个前驱和一个后继。
( c' w+ C/ d( O% @A. 错误
5 N2 k- n, S0 u0 N' h: ZB. 正确
: M# h: [5 L- r, a4 H9 L3 {) ]      满分：2  分

' e% q+ k6 j3 E, q三、多选题（共 5 道试题，共 10 分。）V 1.  下面关于哈希(Hash)查找的说法不正确的是（ ）
9 B& P' h$ U! y8 A1 E' B  iA. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
& m# i" D3 S% q8 \. Y2 ?B. 除留余数法是所有哈希函数中最好的
$ C  l( V+ K8 L( J% aC. 不存在特别好与坏的哈希函数，要视情况而定
$ x& c# I7 w; s* h, ND. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
+ B  @% G! K; L+ R4 t, ~: m( l      满分：2  分
. j( Q# q6 s; J1 @2.  在下列情况中，不能为二叉树的是（ ）
$ N  [$ |0 i9 x4 F" G% VA. 每个结点至多有两棵子树的树
& j3 S' o# C, d. HB. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
      满分：2  分
; n. R9 X$ q) N. r5 Y6 g% K) v3.  下面几个符号串编码集合中，是前缀编码的是（ ）
A. {0,10,110,1111}
9 z3 n* I6 U0 R/ yB. {11,10,001,101,0001}
+ v" g) Y- H# d+ M* P8 a8 hC. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc}
      满分：2  分
4.  下列关于m阶B-树的说法正确的是( )
A. 根结点至多有m棵子树
B. 所有叶子都在同一层次上
C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
+ {. J8 v1 _2 k2 ED. 根结点中的数据是有序的
" F  M" ?! Q" b6 _3 P      满分：2  分
5.  下列哪种图的邻接矩阵不是对称矩阵（ ）
; e6 @2 O: y* AA. 有向图
2 {: |* C& `! q4 SB. 无向图
8 @0 _7 H! A; u# oC. AOV网
+ b$ J, E) i2 k2 f& w" [D. AOE网
      满分：2  分

如果资料还未上传请加QQ：1306998094 谢谢