青岛科技大学《算法设计与分析》2023-2024学年期末试卷

装订线装订线PAGE2第1页，共3页青岛科技大学

《算法设计与分析》2023-2024学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共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.O(1)B.O(n)C.O(logn)D.O(nlogn)9、以下哪个数据结构可以用于实现集合的交集、并集和差集等操作？A.数组B.链表C.栈D.哈希表10、动态规划算法通常用于解决具有什么性质的问题？A.最优子结构性质和贪心选择性质B.最优子结构性质和重叠子问题性质C.贪心选择性质和重叠子问题性质D.随机性质和重叠子问题性质11、以下哪个数据结构可以用于实现图的深度优先搜索？A.数组B.链表C.栈D.队列12、以下哪种算法常用于解决装箱问题？（）A.贪心算法B.动态规划C.回溯法D.分治法13、在动态规划中，状态转移方程描述了（）A.不同状态之间的关系B.初始状态的计算方法C.最优解的计算方法D.以上都不是14、算法的最优性是指（）A.时间复杂度最低B.空间复杂度最低C.得到的解最优D.以上都是15、以下哪个不是贪心算法的局限性？A.不一定能得到全局最优解B.算法的时间复杂度较高C.对问题的性质有一定要求D.难以证明算法的正确性16、在动态规划中，重叠子问题的性质是指（）A.子问题多次出现B.子问题相互独立C.子问题具有唯一性D.以上都不是17、在算法分析中，大O记号表示的是？A.算法的精确运行时间B.算法的平均运行时间C.算法运行时间的上界D.算法运行时间的下界18、以下哪个不是动态规划算法的应用场景？A.资源分配问题B.背包问题C.图的遍历问题D.矩阵链乘法问题19、快速排序的平均时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)20、以下哪种算法常用于解决最大子数组问题？（）A.贪心算法B.动态规划C.回溯法D.分治法二、简答题（本大题共4个小题，共40分)1、（本题10分）解释在视频编码中的压缩算法。2、（本题10分）简述贪心算法在数据库查询优化中的应用思路。3、（本题10分）分析冒泡排序在数据基本有序时的效率提升。4、（本题10分）分析如何通过预处理提高算法效率。三、设计题（本大题共2个小题，共20分)1、（