湖南工程学院《算法与数据结构》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.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克鲁斯卡尔算法二、简答题（本大题共4个小题，共40分)1、（本题10分）简述分治法的基本思想和应用场景。2、（本题10分）以不同路径问题为例，分析动态规划算法的应用。3、（本题10分）分析图着色问题的算法和复杂性。4、（本题10分）说明如何用回溯法解决迷宫问题。