奥鹏作业网《数据结构》2020年春季学期在线作业（一）
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为（ ）。
A.i(i-l)/2+j
B.j(j-l)/2+i
C.j(j-l)/2+i-1
D.i(i-l)/2+j-1
2.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）。
A.5 4 3 6 1 2
B.4 5 3 1 2 6
C.3 4 6 5 2 1
D.2 3 4 1 5 6
3.关键路径是事件结点网络中（ ）。
A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
C.最长回路
D.最短回路
4.在数据结构中，从逻辑上可以把数据结构分成（ ）。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
5.树最适合用来表示（ ）。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
6.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) = （ ）。
A.（a）
B.A
C.(b)
D.(A)
7.下面关于线性表的叙述中，错误的是哪一个？（ ）。
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
8.题目和答案如下图所示：
{图}
A.A
B.B
C.C
D.D
9.采用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
10.n个顶点的有向完全图中含有有向边的数目最多为（ ）。
A.n-1
B.n
C.n(n-1)/2
D.n(n-1)
11.在有序表中使用折半查找法的平均时间是（ ）。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)
12.下列判断正确的是（ ）。
A.二叉树是树的特例。
B.具有n个结点的完全二叉树的深度为n/2。
C.Huffman树是带权路径长度最小的二叉树，树中权值越大的叶子结点距离根结点越远。
D.栈和队列都是限制存取点的线性结构。
13.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A.顺序表
B.单链表
C.双链表
D.单循环链表
14.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）。
A.O(n)
B.O(e)
C.O(n+e)
D.O(n2)
15.已知广义表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))))
16.设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）。
A.G’为G 的子图
B.G’为G 的连通分量
C.G’为G的极小连通子图且V’=V
D.G’为G的一个无环子图
17.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
A.(rear+1) % n = front
B.rear = front
C.rear+1 = front
D.(rear-l) % n = front
18.下面关于图的存储的叙述中正确的是（ ）。
A.用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
B.用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
C.用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
19.若串S=“software”,其子串数目是（ ）。
A.8
B.37
C.36
D.9
20.假设主串的长度为m，模式串的长度为n，BF算法在一般和最坏情况下的时间复杂性分别为 （ ），所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。
A.n+m n*m
B.n m
C.n*m n+m
D.m n
