赣南师范大学《算法设计与分析》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页赣南师范大学《算法设计与分析》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、算法的通用性是指（）A.适用于多种问题B.代码可复用C.易于理解D.以上都是2、空间复杂度主要考虑（）A.算法执行过程中占用的内存空间B.算法执行过程中占用的硬盘空间C.算法执行过程中占用的网络带宽D.以上都是3、在动态规划中，重叠子问题的性质是指（）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.O(1)B.O(logn)C.O(n)D.O(nlogn)10、时间复杂度为O(logn)的算法通常比时间复杂度为O(n)的算法（）A.更慢B.更快C.一样快D.无法比较11、以下哪个数据结构常用于查找操作？（）A.栈B.队列C.二叉搜索树D.链表12、以下哪种排序算法的平均时间复杂度为O(nlogn)？（）A.冒泡排序B.插入排序C.快速排序D.选择排序13、以下哪个数据结构常用于实现集合？（）A.数组B.链表C.哈希表D.树14、在回溯法中，当所有可能的选择都尝试过后，算法（）A.停止B.继续C.重新开始D.以上都不是15、快速排序的递归终止条件是什么？A.子数组长度为0或1B.子数组长度为2C.子数组长度为3D.子数组长度为416、以下哪个算法可以用于求解旅行商问题？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分）解释0-1背包问题为何不能用贪心算法得到最优解。2、（本题10分）解释选择排序在随机数据下的性能特点。3、（本题10分）简述近似算法的设计目标和评估方法。4、（本题10分）解释如何在推荐系统中运用算法。三、设计题（