MOOC 数据结构(沈阳理工大学)1463019161 最新慕课完整章节测试答案

图单元测试

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】

数组单元测验

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)，任意元素LOC（aij）地址计算方法为：              。‍
答案: 【 LOC(a11)＋((i－1)×n＋(j－1))×l】

4、填空题：
‎n阶对称矩阵压缩存储时，存储的元素个数为                     。‌
答案: 【 n*(n+1)/2】

随堂测验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】

随堂测验2

1、单选题：
‏n解对称方阵存储时，压缩存储为一维数组，存储元素个数为                  。‏
选项：
A: n(1+2+...n)/2
B: （1+2+...+n）/2
C: n*n/2
D: n/2
答案: 【 n(1+2+...n)/2】

2、填空题：
‍对称矩阵Am*n压缩存储在一维数组S[k](k≥1)中，下三角部分的数据aij（i≥j）存储在S中的位置为          ‏‍；上三角的数据aij（i<j）存储在S中的位置为            。‏
答案: 【 k=i (i-1) /2+j
k=j（j-1）/2+i】

3、填空题：
​下三角矩阵Am*n压缩存储在一维数组S[k](k≥1)中，数组元素aij（i≥j）存储在S中的位置为                       。‏
答案: 【 k=i (i-1) /2+j】

4、填空题：
‎稀疏矩阵存储时，通常用三元组表示法，三元分别指              。‏
答案: 【 行号、列号、非零元素的值】

查找表单元测试

1、单选题：
若n为静态查找表中结点的个数，则顺序查找一个结点的平均次数是     次。​
选项：
A: (n+1)/2
B:  n*n
C:  1
D: log2n
答案: 【 (n+1)/2】

2、单选题：
若通过输入结点关键字值建立二叉排序树，为使该树不至于太高，则关键字最好按      顺序排列。‎
选项：
A: 从小到大
B: 基本有序
C: 随机
D: 从大到小
答案: 【 随机】

3、单选题：
‍ 顺序查找和折半查找可以选择的存储结构，正确的选项为                 。‎
选项：
A: 它们只能是顺序存储结构
B: 它们只能是链式存储结构
C: 它们既可以选择顺序存储结构，也可以选择链式存储结构
D: 顺序查找两种存储结构都可以，折半查找只能采用顺序存储结构
答案: 【 顺序查找两种存储结构都可以，折半查找只能采用顺序存储结构】

4、单选题：
‎静态查找表和动态查找表的区别是                     。​
选项：
A: 静态查找表只进行查询检索操作
B: 动态查找表只进行插入和删除操作
C: 静态查找表中的数据元素关系是线性的
D: 动态查找表中的数据元素关系是树型的
答案: 【 静态查找表只进行查询检索操作】

5、单选题：
‏下列说法正确的选项为                      。‏
选项：
A: 二叉排序树中查找效率低的树一定不是平衡二叉树
B: 平衡二叉树是一种动态查找树
C: 同样n个结点，建立两种查找表。一种建立一棵二叉排序树；另一种建立一个顺序表。第一种的查找效率高于第二种。
D: n个结点建立的二叉排序树，高度一定小于n
答案: 【 二叉排序树中查找效率低的树一定不是平衡二叉树】

6、填空题：
‌关键字集合（60，70，50， 40，30， 55，58）按顺序输入构成一棵二叉排序树，该二叉排序树根结点的平衡因子为                  。‌
答案: 【 2】

7、填空题：
‎平衡二叉树是指，