黄山学院《算法分析与设计》2023-2024学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页黄山学院《算法分析与设计》

2023-2024学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪个算法可以用于求解字符串的最长回文子串问题？A.贪心算法B.回溯法C.分治法D.动态规划法2、以下哪种算法常用于解决凸包问题？（）A.Graham扫描法B.Dijkstra算法C.Prim算法D.Kruskal算法3、在二叉搜索树中，插入一个新节点的时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)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.贪心选择性质B.最优子结构性质C.重叠子问题性质D.无后效性12、以下哪个算法常用于图的最短路径问题？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法13、在哈希表中，装填因子的取值范围是？A.0到1B.0到正无穷C.负无穷到正无穷D.1到正无穷14、算法的通用性是指（）A.适用于多种问题B.代码可复用C.易于理解D.以上都是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分）说明如何用分支限界法解决多目标优化问题。三、设计题（本大题共2