大学MOOC 数据结构(沈阳理工大学)1457896174 最新慕课完整章节测试答案
图
图单元测试
1、单选题：
在图结构中，每个结点 。
选项：
A: 只有一个前驱和一个后继
B: 可以有多个前驱和多个后继
C: 只有一个前驱和多个后继
D: 无直接前趋
答案: 【 可以有多个前驱和多个后继】
2、单选题：
按结点之间的逻辑关系，属于非线形结构的是： 。
选项：
A: 网、树
B: 树、顺序结构
C: 网、链式结构
D: 树、循环链表
答案: 【 网、树】
3、单选题：
正确描述最小生成树的选项为 。
选项：
A: 由n个顶点和n-1条边构成的图。
B: 由n个顶点和权值和最小的n-1条边构成的图。
C: 由n个顶点和权值和最小的n-1条边构成的连通图。
D: 由n个顶点和n-1条边构成的连通图。
答案: 【 由n个顶点和权值和最小的n-1条边构成的连通图。】
4、单选题：
对关键路径描述正确的选项为 。
选项：
A: 从源点到汇点的最长路径
B: 从源点到汇点的最短路径
C: 关键路径只有一条
D: 关键点的最早发生时间和最迟发生时间可以不同
答案: 【 从源点到汇点的最长路径】
5、单选题：
下面是对深度遍历、广度遍历的描述，正确的选项为 。
选项：
A: 深度遍历是按层次遍历
B: 广度遍历是按层次遍历
C: 深度遍历的生产树高度比较小
D: 如果深度遍历算法可以生成一棵生成树，那么这个图应该是个连通图
答案: 【 广度遍历是按层次遍历】
6、填空题：
求最小生成树时，普利姆算法的思路为 。
答案: 【 通过两个顶点集合，在集合的顶点间，选取最小权值边，然后扩充进新顶点，直到顶点全部扩充进去。】
7、填空题：
求最小生成树时，克鲁斯卡尔算法的思想为 。
答案: 【 将图中的边从小到大排列，从第一条边加入开始，如果不形成环，则该边加入，直到所有边处理完成。】
8、填空题：
图的存储结构有四种，分别是 。
答案: 【 矩阵表示、邻接表表示、十字链表、多重邻接表】
9、填空题：
不仅可以表示有向图，也可以表示无向图的存储结构有 。
答案: 【 邻接矩阵、邻接表】
10、填空题：
已知无向图的邻接矩阵，求各个顶点的度的方法为 。
答案: 【 将邻接矩阵中各行的非零值相加的和】
11、填空题：
已知无向图的邻接表，求各个顶点的度的方法为 。
答案: 【 求各个顶点后链接的结点的个数】
12、填空题：
无向图G=(V,E),其中顶点和边的个数分别为n，e，如果用邻接表存储，表示边的链表（包括空链表）的个数为 。
答案: 【 n】
13、填空题：
拓扑排序时，第一个输出的结点为 。
答案: 【 入度为零的结点中的任意一个】
14、填空题：
如果拓扑排序不能输出图中所有的点，则说明此图 。
答案: 【 有环】
15、填空题：
描述生成树是由图中n个顶点和n-1条边构成的图，判断这种说法是否正确 。
答案: 【 错误】
排序
排序单元测试
1、单选题：
对序列（48、23、67、25、13、89、36、96）建立的大顶堆为 。
选项：
A: 48、23、67、25、13、89、36、96
B: 96,48,89,25,13,67,36,23
C: 96,89,48,25,13,67,36,23
D: 96,89,67,48,25,36,23,13
答案: 【 96,48,89,25,13,67,36,23】
2、单选题：
如果序列：37,28，16,45,78,5,96,30一趟排序后结果为：30,28,16,5,37,78,96,45，这种排序是 。
选项：
A: 一趟堆排序
B: 一趟快速排序
C: 一趟起泡排序
D: 一趟希尔排序
答案: 【 一趟快速排序】
3、单选题：
37,28，16,45,78,5,96,30，一趟排序后结果为28，37,16,45,78,5,96,30，这种排序是 。
选项：
A: 一趟简单插入排序
B: 一趟堆排序
C: 一趟加单交换排序
D: 一趟希尔排序
答案: 【 一趟简单插入排序】
4、单选题：
排序的时间效率与快速排序相似的排序有
选项：
A: 堆
B: shell
C: 简单插入排序
D: 简单交换排序
答案: 【 堆】
5、单选题：
对系列60、34、67、47、94、77、3、92、68建立初始堆时，调用重建堆的次数 。
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 4】
6、填空题：
按排序性质分，可以分为 。
答案: 【 选择、插入、交换、归并、基数】
7、填空题：
稳定排序是指相同关键字的记录在排序前后的相对位置 。
答案: 【 不改变】
8、填空题：
按稳定性划分，插入排序中稳定的有 。
答案: 【 简单插入、折半插入】
9、填空题：
排序中效率较高的算法有 。
答案: 【 快速、堆】
10、填空题：
shell排序是分组插入排序，组间、组内的操作为 。
答案: 【 缩短增量，组内插入排序】
11、填空题：
一个有序序列，如果用快速排序和起泡排序，那么排序的效率高的为 。
答案: 【 起泡排序】
12、填空题：
n个元素的堆序，建立初始堆的第一个点为 。
答案: 【 n/2】
13、填空题：
当序列有序时，快速排序就退化为 。
答案: 【 起泡排序】
14、填空题：
序列（48、23、67、25、13、89、36、96）快述排序时，对第一个关键字的一次划分为 。
答案: 【 36,23,13,25,48,89,67,96】
15、填空题：
对序列（48、23、67、25、13、89、36、96）进行shell排序时，d=4排序结果为 。
答案: 【 13,23,36,23,48,89,67,96】
数组
4-1测试
1、单选题：
已知二维数组A[-1 2，-2 3]，按行方式存储，若首地址为1000，且每个元素都占用2个存储单元，计算元素A（1，-1）存储地址。
选项：
A: 1020
B: 1024
C: 1026
D: 1028
答案: 【 1026】
2、单选题：
三维数组B[1..3、1..6、1..7]按行方式存储，计算元素B[1,2,3]存储在第几个位置上：
选项：
A: 8
B: 9
C: 10
D: 11
答案: 【 9】
数组测验
1、单选题：
三维数组A[1..4,1..5,1..6]压缩存储时，元素a333存储在所有元素排序中的第几个位置
选项：
A: 70
B: 75
C: 78
D: 80
答案: 【 75】
2、单选题：
对称矩阵压缩到一维数组S[k]（k≥1）中，存储时只存储下三角元素aij（i≥j），k和ij的对应关系为
选项：
A: k=i（i-1）/2+j
B: k=i（i-1）/2+j (i≥j)
C: k=i（i-1）/2+j (i≥j)k=j（j-1）/2+i (i<j)
D: k=j（j-1）/2+i (i<j)
答案: 【 k=i（i-1）/2+j (i≥j)k=j（j-1）/2+i (i<j)】
3、填空题：
二维数组A[1..m，1..n]以行为主序存储，数组首元素地址LOC(a11)，任意元素aij地址计算函数为： 。
答案: 【 LOC(ai j)=LOC(a11)＋[(i－1)×n＋(j－1)]×l】
4、填空题：
n阶对称矩阵压缩存储时，存储的元素个数为 。
答案: 【 n（n+1）/2】
测验
1、单选题：
n解对称方阵存储时，压缩存储为一维数组，存储元素个数为 。
选项：
A: n(1+2+...n)/2
B: （1+2+...+n）/2
C: n*n/2