中国石油大学（华东）《数据结构》2021年秋季学期在线作业（三）

第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、分析算法的易懂性和文档性

正确答案:

第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、正确

正确答案: