北京工业大学《算法设计》2022-2023学年期末试卷

装订线装订线PAGE2第1页，共3页北京工业大学《算法设计》

2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共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.算法执行过程中所需的最大存储空间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、以下哪个算法可以用于解决0-1背包问题？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分）比较Dijkstra算法和Floyd算法的适用情况。4、（本题10分）简述在数据库管理中用到的算法。三、设计题（本大题共2个小题，共2