黑龙江大学《算法与数据结构》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.重复计算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、以下哪个不是动态规划算法的优点？A.高效性B.准确性C.通用性D.简单性18、以下哪个算法可以用于求解图的单源最短路径问题？A.深度优先搜索B.广度优先搜索C.迪杰斯特拉算法D.克鲁斯卡尔算法19、以下哪个不是图的基本操作？A.插入顶点B.删除顶点C.查找顶点D.排序顶点20、在分治法中，合并子问题的解的时间复杂度通常为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）以最长不下降子序列问题为例，分析动态规划算法的解法。2、（本题10分）简述在计算机网络中使用的路由算法。3、（本题10分）简述在智能电网中的优化算法。4、（本题10分）解释如何根据性能测试结果进行进一步优