《数据结构》2020年春季学期在线作业（一）
试卷总分:100    得分: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
正确答案: