奥鹏作业网《数据结构》2020年春季学期在线作业（二）
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.在线性表的顺序存储结构中，逻辑上相邻的数据元素的物理位置（ ），在链式存储结构中，逻辑上相邻的数据元素的物理位置（ ）。
A.必相邻 必相邻
B.必相邻 不一定相邻
C.不一定相邻 必相邻
D.不一定相邻 不一定相邻
2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（ ）存储方式节省时间。
A.单链表
B.双链表
C.单循环链表
D.顺序表
3.已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中元素e的运算是（ ）。
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS))))
D.head(tail(tail(head(LS))))
4.设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）。
A.联接
B.求子串
C.字符定位
D.子串定位
5.下列说法正确的是 （ ）。
A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同
6.在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（ ）。
A.都不相同
B.完全相同
C.前序遍历和中序遍历相同，而与后序遍历不同
D.前序遍历和后序遍历相同，而与中序遍历不同
7.若串S=“software”,其子串数目是（ ）。
A.8
B.37
C.36
D.9
8.以下判断不正确的是（ ）。
A.顺序存储的线性表可随机存取。
B.同一线性表中的数据元素应具有相同的特性。
C.顺序存储方式的优点是存储密度大，插入、删除操效率高。
D.在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。
9.假设主串的长度为m，模式串的长度为n，KMP算法的时间复杂度为（ ）。
A.n+m
B.n*m
C.n
D.m
10.在顺序存储（空间大小为m）的循环队列q中，下列判满正确的是（ ）。
A.q.front % m = 0 ;
B.q.rear % m = 0 ;
C.q.front = q.rear ;
D.(q.front+1) % m = q.rear;
11.线性结构中的一个结点代表一个（ ）。
A.数据元素
B.数据项
C.数据
D.数据结构
12.设深度为K的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为（ ）。
A.K+1
B.2K
C.2K-1
D.2K+1
13.题目和答案如下图所示：
{图}
A.A
B.B
C.C
D.D
14.下列说法不正确的是（ ）。
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.图的深度遍历不适用于有向图
C.遍历的基本算法有两种：深度遍历和广度遍历
D.图的深度遍历是一个递归过程
15.进行二分查找要求查找表必须（ ）。
A.以顺序方式存储。
B.以链式方式存储。
C.以顺序方式存储且数据元素按关键字有序排列。
D.以链式方式存储且数据元素按关键字有序排列。
16.哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（ ）次探测。
A.k
B.k-1
C.k(k-1)/2
D.1+k(k-1)/2
17.下面关于完全二叉树的特点叙述不正确的是（ ）。
A.只有最后一层是不满的，不满层的结点首先出现在左边
B.至多只有最下面的两层结点的度小于2
C.左子树的高度不会小于右子树的高度，且左、右子树高度最大相差±1
D.叶子只能出现在最后两层上；
18.若在线性表中采用折半查找法查找元素，该线性表应该（ ）。
A.元素按值有序
B.采用顺序存储结构
C.元素按值有序，且采用顺序存储结构
D.元素按值有序，且采用链式存储结构
19.采用BF算法在主串a a b a a a c a a c b b b中查找子串a a a c a a c b的查找次数为（ ）。
A.13
B.14
C.15
D.16
20.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（ ）。
A.(c,d )
B.(d )
C.b
D.(b)
