算法分析与设计(西南科技大学)1465494465 中国大学MOOC答案2024版100分完整版

第一章 第一章 单元测试

1、 下面哪一个不是算法的特性？（）

答案: 及时性

2、 利用欧几里得算法计算12、8的最大公约数，只需要循环多少次？（）

答案: 2次

3、 下面为代码的描述，哪一个是错误的？（）

答案:=”” <span=””>for(i=0;i<n;i++)< span=””></n;i++)<></n;i++)>

4、 下面为代码的描述，哪一个是错误的？（）

答案: while b!=12

5、 对算法运行速度的效率分析主要是指（）

答案: 时间效率分析

第二章 第二章 单元测验

1、 算法分析中，算法运行时间的度量单位是：（）

答案: 基本操作被执行的次数

2、 下列对算法效率的描述错误的是：（）

答案: 平均效率是指输入为n时，算法在最坏情况的效率。

3、 1、 针对下面的算法，描述错误的是：（）算法 SequentiaSearch(A[0..n-1],K)i0while i算法的基本操作时循环最内层的加法。

4、 下面哪一个不是时间的渐进符号：（）

答案: Y

5、 下面那个断言是错误的：（）

答案:

6、 算法分析中，算法运行时间的度量单位是：

答案: 基本操作被执行的次数

7、 下列对算法效率的描述错误的是：

答案: 平均效率是指输入为n时，算法在最坏情况的效率。

8、 针对下面的算法，描述错误的是：（）算法 SequentiaSearch(A[0..n-1],K) i0 while i算法的基本操作时循环最内层的加法。

9、 下面哪一个不是时间的渐进符号：

答案: Y

10、 下面那个断言是错误的：

答案:

11、 考虑下面这个式子属于哪一种效率类型：

答案:

12、 以下式子属于哪一种效率类型。

答案:

第三章 第三章 单元测验

1、 采用蛮力法求解凸包问题的算法复杂度为：()

答案: O(n^3)

2、 用蛮力法思路求解旅行商问题的算法复杂度为：()

答案: O(n!)

3、 用蛮力法思路求解任务分配问题的算法复杂度为:()

答案: O(n!)

4、 以下关于蛮力法的描述中，正确的有()

答案: 较为通用，能解决一般领域的问题;
适用于小规模问题;
可作为产生其他有效算法的基础;
可作为其他有效算法的衡量标准

5、 以下关于深度优先查找的说法，正确的包括：()

答案: 数据结构采用栈;
采用邻接矩阵的效率为O(|V^2|)

6、 以下关于广度优先查找的说法，正确的包括：()

答案: 数据结构为队列;
采用邻接链表的效率为O(|V|+|E|)

7、 采用欧几里得距离和采用曼哈顿距离的最近对问题，算法的思路是一样的。()

答案: 错误

8、 判断对错：假设G是一个有n个顶点和m条边的图，它的所有DFS森林（对应于不同顶点开始的遍历）包含相同数量的树。

答案: 正确

9、 判断对错：假设G是一个有n个顶点和m条边的图，它的所有DFS森林包含相同数量的树向边和回边。()

答案: 正确

10、 判断对错：在DFS遍历和BFS遍历中，DFS遍历的方法总是比BFS遍历的方法更快的找到回路。()

答案: 错误

11、 采用蛮力法求解凸包问题的算法复杂度为：()

答案:

12、 用蛮力法思路求解任务分配问题的算法复杂度为:()

答案: O(n!)

13、 以下关于深度优先查找的说法，正确的包括：()

答案: 数据结构采用栈;
采用邻接矩阵的效率为O(||)

14、 以下关于广度优先查找的说法，正确的包括：()

答案: 数据结构为队列;
采用邻接链表的效率为O(|V|+|E|)

第四章 第四章 单元测试

1、 包含n个元素的生成排列共有多少个？()

答案: n!

2、 按照字典序生成的排列中，237654后面的是哪个？()

答案: 243567

3、 包含n个物品的背包问题中，所有物品集合的子集共有多少？()

答案: 2^n

4、 约瑟夫斯问题J(n,2)中，如果n为11，则结果为：()

答案: 7

5、 使用数组和链表分别实现一个列表，用折半查找方法进行数据查找，效率是基本相同的。()

答案: 错误

6、 从时间效率来看，使用俄式乘法计算n x m和m x n没有区别。

答案: 错误

7、 插值查找算法的效率是线性的。()

答案: 正确

8、 快速选择算法在最坏情况下的效率是线性的。()

答案: 错误

9、 包含n个元素的生成排列共有多少个？()

答案: n!

10、 包含n个物品的背包问题中，所有物品集合的子集共有多少？()

答案:

11、 基于DFS的拓扑排序算法的时间效率是怎样的？()

答案: 若采用邻接矩阵，效率为O(|);
若采用邻接链表，效率为O(|V|+|E|)