华南理工大学《算法设计与分析》2021-2022学年期末试卷

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

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、动态规划算法通常用于解决（）问题。A.最优解B.近似解C.随机解D.无解2、在二叉树中，度为0的节点称为？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.KMP算法B.冒泡排序C.快速排序D.插入排序8、在二叉树中，前序遍历的顺序是？A.根节点、左子树、右子树B.左子树、根节点、右子树C.左子树、右子树、根节点D.右子树、根节点、左子树9、以下哪种算法常用于解决旅行商问题？（）A.贪心算法B.动态规划C.回溯法D.模拟退火算法10、以下哪个算法可以用于解决0-1背包问题？A.贪心算法B.回溯法C.分治法D.动态规划法11、归并排序的合并操作的时间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)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.O(n^2)B.O(nlogn)C.O(logn)D.O(n)18、在图的深度优先搜索中，使用的辅助数据结构是（）A.栈B.队列C.优先队列D.哈希表19、在动态规划中，通过保存子问题的解来避免（）A.重复计算B.错误计算C.遗漏计算D.以上都是20、归并排序是一种稳定的排序算法，它的稳定性体现在？A.对于相等的元素，排序前后的相对位置不变B.排序的时间复杂度稳定C.排序的空间复杂度稳定D.对于不同的输入，排序结果一致二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述堆排序在数据排序稳定性方面的特点。2、（本题10分）举例说明常见的时间复杂度级别，如O(1)、O(n)、O(n^2)等。3、（本题10分）分析快速排序的空间复杂度优化方法。4、（本题10分）解释贪心算法在最小生成树问题中的应用（如Prim算法或Kruskal算法）。三、设计