大学MOOC 数据结构(河南城建学院)1462665204 最新慕课完整章节测试答案
串、数组和广义表
串、数组和广义表 单元测验
1、单选题：
串下面关于串的的叙述中，（ ）是不正确的？
选项：
A: 串是字符的有限序列
B: 空串是由空格构成的串
C: 模式匹配是串的一种重要运算
D: 串既可以采用顺序存储，也可以采用链式存储
答案: 【 空串是由空格构成的串】
2、单选题：
串“ababaabab”的nextval为（ ）。
选项：
A: 010104101
B: 010102101
C: 010100011
D: 010101011
答案: 【 010104101 】
3、单选题：
串的长度是指（ ）。
选项：
A: 串中所含不同字母的个数
B: 串中所含字符的个数
C: 串中所含不同字符的个数
D: 串中所含非空格字符的个数
答案: 【 串中所含字符的个数】
4、单选题：
假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
选项：
A: 808
B: 818
C: 1010
D: 1020
答案: 【 818】
5、单选题：
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
选项：
A: 13
B: 32
C: 33
D: 40
答案: 【 40】
6、单选题：
二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
选项：
A: A[8,5]
B: A[3,10]
C: A[5,8]
D: A[0,9]
答案: 【 A[5,8]】
7、单选题：
数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
选项：
A: 55
B: 45
C: 36
D: 16
答案: 【 45】
8、单选题：
广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
选项：
A: (g)
B: (d)
C: c
D: d
答案: 【 d】
9、单选题：
设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。
选项：
A: 1和1
B: 1和3
C: 1和2
D: 2和3
答案: 【 1和2】
10、单选题：
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
选项：
A: 求子串
B: 联接
C: 匹配
D: 求串长
答案: 【 联接】
11、判断题：
从逻辑结构上看，n维数组的每个元素均属于n个向量。
选项：
A: 正确
B: 错误
答案: 【 正确】
12、判断题：
若一个广义表的表头为空表，则此广义表亦为空表。
选项：
A: 正确
B: 错误
答案: 【 错误】
13、判断题：
广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
选项：
A: 正确
B: 错误
答案: 【 错误】
14、判断题：
数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
选项：
A: 正确
B: 错误
答案: 【 错误】
15、判断题：
一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
选项：
A: 正确
B: 错误
答案: 【 错误】
16、填空题：
组成串的数据元素只能是（ ）
答案: 【 字符】
17、填空题：
INDEX（‘DATASTRUCTURE’， ‘STR’）=（ ）
答案: 【 5】
18、填空题：
两个串相等的充分必要条件是（ ）
答案: 【 两串的长度相等且两串中对应位置的字符也相等】
19、填空题：
设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为（ ）
答案: 【 O(m+n)】
20、填空题：
字符串“student”中长度为4的子串有（ ）个
答案: 【 4】
串的定义 随堂测验
1、单选题：
1.串与普通的线性表相比较，它的特殊性体现在（ ）
选项：
A: 顺序的存储结构
B: 链式存储结构
C: 数据元素是一个字符
D: 数据元素任意
答案: 【 数据元素是一个字符】
2、单选题：
2.空串和空格串（ ）。
选项：
A: 相同
B: 不相同
C: 可能相同
D: 无法确定
答案: 【 不相同】
3、单选题：
3.与线性表相比，串的操作的特点是（ ）
选项：
A: 算法的时间复杂度较高
B: 通常以串整体作为操作对象
C: 需要更多的辅助空间
D: 涉及移动的元素更多
答案: 【 通常以串整体作为操作对象】
4、单选题：
4.串下面关于串的的叙述中，（ ）是不正确的？
选项：
A: 串是字符的有限序列
B: 空串是由空格构成的串
C: 模式匹配是串的一种重要运算
D: 串既可以采用顺序存储，也可以采用链式存储
答案: 【 空串是由空格构成的串】
5、单选题：
5.下面的说法中，只有（ ）是正确的。
选项：
A: 字符串的长度是指串中包含的字母的个数
B: 字符串的长度是指串中包含的不同字符的个数
C: 若T包含在S中，则T一定是S的一个子串
D: 一个字符串不能说是其自身的一个子串
答案: 【 字符串的长度是指串中包含的不同字符的个数】
串的类型定义、存储结构及其运算 随堂测验
1、单选题：
1.设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（ ）。
选项：
A: 连接
B: 求子串
C: 模式匹配
D: 判断子串
答案: 【 模式匹配】
2、单选题：
3.设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ ）。
选项：
A: ‘ijing’
B: ‘jing&’
C: ‘ingNa’
D: ‘ing&N’
答案: 【 ‘jing&’】
3、单选题：
4.字符串采用结点大小为1的链表作为其存储结构，是指（ ）。
选项：
A: 链表的长度为1
B: 链表中只存放1个字符
C: 链表的每个链结点的数据域中不仅只存放了一个字符
D: 链表的每个链结点的数据域中只存放了一个字符
答案: 【 链表的每个链结点的数据域中只存放了一个字符】
4、判断题：
2.两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同 。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
5.KMP算法的最大特点是指示主串的指针不需要回溯。
选项：
A: 正确
B: 错误
答案: 【 正确】
广义表 随堂测验
1、单选题：
1.广义表((a,b,c,d))的表头是（ ）。
选项：
A: a
B: ( )
C: (a,b,c,d)
D: (b,c,d)
答案: 【 (a,b,c,d) 】
2、单选题：
2.设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。
选项：
A: 1和1
B: 1和3
C: 1和2
D: 2和3
答案: 【 1和2】
3、单选题：
4.对特殊矩阵采用压缩存储的目的主要是为了（ ）
选项：
A: 表达变得简单
B: 对矩阵元素的存取变得简单
C: 去掉矩阵中的多余元素
D: 减少不必要的存储空间
答案: 【 减少不必要的存储空间】
4、判断题：
3.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
选项：
A: 正确
B: 错误
答案: 【 错误】
5、填空题：
5.当广义表中的每个元素都是原子时，广义表便成了（ ）。
答案: 【 线性表】
数组 随堂测验
1、单选题：
1.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
选项：
A: 1175
B: 1180
C: 1205
D: 1210
答案: 【 1175】
2、单选题：
2.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
选项：
A: A[8,5]
B: A[3,10]
C: A[5,8]
D: A[0,9]
答案: 【 A[3,10]】
3、判断题：
3. 数组不能作为任何二叉树的存储结构。
选项：
A: 正确
B: 错误
答案: 【 错误】
4、判断题：
4.从逻辑结构上看，n维数组的每个元素均属于n个向量。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
5.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
选项：
A: 正确
B: 错误
答案: 【 错误】
图
图 单元测验
1、单选题：
n个结点的完全有向图含有边的数目（ ）。
选项：
A: n*n
B: n（n＋１）
C: n／2
D: n*（n－l）
答案: 【 n*（n－l）】
2、单选题：
用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。
选项：
A: 5
B: 6
C: 8
D: 9
答案: 【 5】
3、单选题：
下列哪一种图的邻接矩阵是对称矩阵？（ ）
选项：
A: 有向图
B: 无向图
C: AOV网
D: AOE网
答案: 【 无向图 】
4、单选题：
无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
选项：
A: a,b,e,c,d,f
B: a,c,f,e,b,d
C: a,e,b,c,f,d
D: a,e,d,f,c,b
答案: 【 a,e,d,f,c,b】
5、单选题：
关键路径是事件结点网络中（ ）。
选项：
A: 从源点到汇点的最长路径
B: 从源点到汇点的最短路径
C: 最长回路
D: 最短回路
答案: 【 从源点到汇点的最长路径】
6、单选题：
要连通具有n个顶点的有向图，至少需要（ ）条边。
选项：
A: n-1
B: n
C: n+1
D: 2n
答案: 【 n】
7、单选题：
图中有关路径的定义是（ ）。
选项：
A: 由顶点和相邻顶点序偶构成的边所形成的序列
B: 由不同顶点所形成的序列
C: 由不同边所形成的序列
D: 上述定义都不是
答案: 【 由顶点和相邻顶点序偶构成的边所形成的序列】
8、单选题：
下面结构中最适于表示稀疏无向图的是（ ）。
选项：
A: 邻接矩阵
B: 逆邻接表
C: 邻接多重表
D: 十字链表
答案: 【 邻接多重表】
9、单选题：
下面哪一方法可以判断出一个有向图是否有环（回路）：（ ）
选项：
A: 求最小生成树
B: 拓扑排序
C: 求最短路径
D: 求关键路径
答案: 【 拓扑排序】
10、单选题：
下列关于AOE网的叙述中，不正确的是（ ）。
选项：
A: 关键活动不按期完成就会影响整个工程的完成时间
B: 任何一个关键活动提前完成，那么整个工程将会提前完成
C: 所有的关键活动提前完成，那么整个工程将会提前完成
D: 某些关键活动提前完成，那么整个工程将会提前完成
答案: 【 任何一个关键活动提前完成，那么整个工程将会提前完成】
11、判断题：
用邻接矩阵表示图进行深度优先遍历时，通常是采用队列来实现算法的。
选项：
A: 正确
B: 错误
答案: 【 错误】
12、判断题：
n个顶点的连通图，至少有n-1条边。
选项：
A: 正确
B: 错误
答案: 【 正确】
13、判断题：
有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。
选项：
A: 正确
B: 错误
答案: 【 错误】
14、判断题：
若连通图G中的一条边e是所以边中权值最小的边，则图G必存在着一最小生成棵包含边e的最小生成树。
选项：
A: 正确
B: 错误
答案: 【 正确】
15、判断题：
任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。
选项：
A: 正确
B: 错误
答案: 【 错误】
16、填空题：
有向图G的强连通分量是指（ ）。
答案: 【 极大强连通子图】
17、填空题：
一个连通图的（ ）是一个极小连通子图
答案: 【 生成树】
18、填空题：
求图的最小生成树有两种算法，（ ）算法适合于求稀疏图的最小生成树。
答案: 【 kruskal（克鲁斯卡尔）】
19、填空题：
对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为（ ）。
答案: 【 2*e】
20、填空题：
G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。
答案: 【 9】
图的存储结构 随堂测验
1、单选题：
1.n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。
选项：
A: n
B: 2(n-1)
C: n/2
D: n*n
答案: 【 2(n-1) 】
2、单选题：
2.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ ）。
选项：
A: 将邻接矩阵的第i行删除
B: 将邻接矩阵的第i行元素全部置为0
C: 将邻接矩阵的第i列删除
D: 将邻接矩阵的第i列元素全部置为0
答案: 【 将邻接矩阵的第i行元素全部置为0】
3、单选题：
3.无向图的邻接矩阵是一个（ ）。
选项：
A: 对称矩阵
B: 零矩阵
C: 上三角矩阵
D: 对角矩阵
答案: 【 对称矩阵 】
4、判断题：
4.用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是求第j列的所有元素之和。
选项：
A: 正确
B: 错误
答案: 【 正确】
图的定义和基本术语 随堂测试
1、单选题：
1.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
选项：
A: 1/2
B: 1
C: 2
D: 4
答案: 【 2】
2、单选题：
2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
选项：
A: 1/2
B: 1
C: 2
D: 4
答案: 【 1】
3、单选题：
3.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1ÍV2,E1ÍE2则称（ ）。
选项：
A: G1是G2的子图
B: G2是G1的子图
C: G1是G2的连通分量
D: G2是G1的连通分量
答案: 【 G1是G2的子图】
4、判断题：
4.图的连通分量是无向图的极小连通子图。
选项：
A: 正确
B: 错误
答案: 【 错误】
5、填空题：
5.设无向图G中顶点数为n，则图G至少有（ ）条边。
答案: 【 0】
图的应用 随堂测验
1、单选题：
1.已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，则由该图产生的一种可能的拓扑序列为( )
选项：
A: a,b,c,d,e
B: a,b,d,e,b
C: a,c,b,e,d
D: a,c,d,b,e
答案: 【 a,b,c,d,e】
2、单选题：
2.下面（ ）算法适合构造一个稀疏图G的最小生成树。
选项：
A: Prim算法
B: Kruskal算法
C: Floyd算法
D: Dijkstra算法
答案: 【 Kruskal算法 】
3、判断题：
3.在n个结点的无向图中，若边数>n-1，则该图必是连通图。
选项：
A: 正确
B: 错误
答案: 【 错误】
4、判断题：
4.关键路径是事件结点网络中从源点到汇点的最长路径。
选项：
A: 正确
B: 错误
答案: 【 正确】
5、判断题：
5.在AOE网中一定只有一条关键路径。
选项：
A: 正确
B: 错误
答案: 【 错误】
图的类型定义 随堂测验
1、单选题：
1.设无向图的顶点个数为n，则该图最多有（ ）条边。
选项：
A: n-1
B: n(n-1)/2
C: n(n+1)/2
D: 0
答案: 【 n(n-1)/2】
2、判断题：
2.树中的结点和图中的顶点就是指数据结构中的数据元素。
选项：
A: 正确
B: 错误
答案: 【 正确】
3、判断题：
3.连通分量指的是有向图中的极大连通子图。
选项：
A: 正确
B: 错误
答案: 【 错误】
4、填空题：
4.G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
答案: 【 9】
5、填空题：
5.有n个顶点的有向图，至少需要量______条弧才能保证是连通的。
答案: 【 n-1】
图的遍历 随堂测验
1、单选题：
1.用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
选项：
A: 栈
B: 队列
C: 树
D: 堆
答案: 【 队列】
2、单选题：
2.深度优先遍历类似于二叉树的（ ）。
选项：
A: 先序遍历
B: 中序遍历
C: 后序遍历
D: 层次遍历
答案: 【 先序遍历】
3、单选题：
3.下列关于图遍历的说法不正确的是（ ）。
选项：
A: 连通图的深度优先搜索是一个递归过程
B: 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C: 非连通图不能用深度优先搜索法
D: 图的遍历要求每一顶点仅被访问一次
答案: 【 非连通图不能用深度优先搜索法】
4、判断题：
4.对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。
选项：
A: 正确
B: 错误
答案: 【 错误】
5、判断题：
5.广度遍历生成树描述了从起点到各顶点的最短路径。
选项：
A: 正确
B: 错误
答案: 【 错误】
排序
交换排序 随堂测验
1、单选题：
1.对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
选项：
A: 从小到大排列好的
B: 从大到小排列好的
C: 元素无序&nbs