奥鹏作业网数据结构-[中国石油大学(华东)]《数据结构》2021年秋季学期在线作业（三）
试卷总分:100 得分:100
第1题,假设主串的长度为m，模式串的长度为n，BF算法在一般和最坏情况下的时间复杂性分别为 （ ），所以还是一个常用算法。由于有回溯，所以主串输入后必须保存。
A、n+m n*m
B、n m
C、n*m n+m
D、m n
正确答案:
第2题,下面关于图的存储的叙述中正确的是（ ）。
A、用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
B、用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
C、用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关
D、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
正确答案:
第3题,一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（ ）。
A、edcba
B、decba
C、decab
D、abcde
正确答案:
第4题,关于逻辑结构和存储结构，正确的描述是（ ）。
A、线性数据结构必须采用链式存储结构
B、一种逻辑结构，可以用不同的存储结构来存储，反之亦然
C、一种逻辑结构，可以用不同的存储结构来存储，反之不然
D、一种存储结构只能表示一种逻辑结构
正确答案:
已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) = （ ）。
A、（a）
B、A
C、(b)
D、(A)
正确答案:
第6题,已知广义表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))))
正确答案:
第7题,题目和答案如下图所示：
A、A
B、B
C、C
D、D
正确答案:
第8题,算法分析的目的是（ ）。
A、找出数据结构的合理性
B、研究算法中的输入和输出的关系
C、分析算法的效率以求改进
D、分析算法的易懂性和文档性
正确答案:
奥鹏中石油答案请进：opzy.net或请联系微信：1095258436
第9题,某非空二叉树的先序和后序序列正好相反，则二叉树一定是（ ）的二叉树。
A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无右孩子
正确答案:
关键路径是事件结点网络中（ ）。
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长回路
D、最短回路
正确答案:
第11题,有六个元素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
正确答案:
已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）。
A、1.0
B、2.9
C、3.4
D、5.5
正确答案:
第13题,若在线性表中采用折半查找法查找元素，该线性表应该（ ）。
A、元素按值有序
B、采用顺序存储结构
C、元素按值有序，且采用顺序存储结构
D、元素按值有序，且采用链式存储结构
正确答案:
第14题,设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）。
A、G’为G 的子图
B、G’为G 的连通分量
C、G’为G的极小连通子图且V’=V
D、G’为G的一个无环子图
正确答案:
在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（ ）。
A、都不相同
B、完全相同
C、前序遍历和中序遍历相同，而与后序遍历不同
D、前序遍历和后序遍历相同，而与中序遍历不同
正确答案:
第16题,将一棵树转换成二叉树后，根结点没有左子树。
A、错误
B、正确
正确答案:
第17题,线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
A、错误
B、正确
正确答案:
第18题,有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。
A、错误
B、正确
正确答案:
第19题,二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
A、错误
B、正确
正确答案:
哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
A、错误
B、正确
正确答案:
