吉林大学《算法分析》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页吉林大学《算法分析》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种算法常用于解决背包问题？（）A.贪心算法B.动态规划C.回溯法D.分治法2、快速排序的递归终止条件是什么？A.子数组长度为0或1B.子数组长度为2C.子数组长度为3D.子数组长度为43、时间复杂度为O(n)的算法，其执行时间与输入规模n的关系是（）A.线性增长B.指数增长C.对数增长D.不变4、快速排序的枢轴元素选择对算法的性能有很大影响，以下哪种选择方式通常比较好？A.第一个元素B.最后一个元素C.中间元素D.随机元素5、在贪心算法中，得到的解可能是（）A.最优解B.近似最优解C.可行解D.以上都可能6、动态规划算法的核心是？A.递归B.贪心选择C.记忆化搜索D.分治7、以下哪个算法可以用于判断一个图是否为连通图？A.深度优先搜索B.广度优先搜索C.迪杰斯特拉算法D.普里姆算法8、递归算法的基本思想是（）A.自顶向下分解B.自底向上计算C.不断重复相同操作D.调用自身函数9、在图的遍历中，深度优先搜索和广度优先搜索的主要区别是？A.遍历的顺序不同B.时间复杂度不同C.空间复杂度不同D.适用的图类型不同10、在贪心算法中，一旦做出选择就（）A.可以更改B.不能更改C.视情况更改D.以上都不是11、快速排序在最好情况下的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)12、以下哪个数据结构常用于实现队列？（）A.数组B.链表C.栈D.树13、归并排序的空间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)14、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍15、空间复杂度主要考虑（）A.算法执行过程中占用的内存空间B.算法执行过程中占用的硬盘空间C.算法执行过程中占用的网络带宽D.以上都是16、以下哪个算法可以用于求解图的最小生成树问题？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克鲁斯卡尔算法17、以下哪个算法可以用于求解图的单源最短路径问题？A.深度优先搜索B.广度优先搜索C.迪杰斯特拉算法D.克鲁斯卡尔算法18、以下哪种算法常用于解决数独问题？（）A.贪心算法B.回溯法C.动态规划D.分治法19、算法分析的主要目的是（）A.评估算法的性能B.设计新算法C.比较不同算法D.以上都是20、以下哪种算法常用于解决旅行商问题？（）A.贪心算法B.动态规划C.回溯法D.模拟退火算法二、简答题（本大题共4个小题，共40分)1、（本题10分）解释插入排序在有序数据删除时的性能。2、（本题10分）分析快速排序的空间复杂度优化方法。3、（本题10分）简述并行计算中的任务分配和同步策略。4、（本题10分）以字符串匹配问题为例，说明动态规划算法的应用。三、设计题（