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

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页华南理工大学

《算法设计与分析》2022-2023学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在图的存储结构中，邻接表适合存储什么样的图？A.稀疏图B.稠密图C.有向图D.无向图2、二分查找算法要求数据必须是（）A.有序的B.无序的C.平衡的D.以上都不是3、在算法分析中，大O记号表示的是？A.算法的精确运行时间B.算法的平均运行时间C.算法运行时间的上界D.算法运行时间的下界4、在有向无环图中，进行拓扑排序的时间复杂度是？A.O(1)B.O(n)C.O(nlogn)D.O(n²)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.O(n)B.O(nlogn)C.O(n²)D.O(logn)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分）阐述基数排序与其他基于比较的排序算法的区别。三、设计题（