南京信息工程大学《算法设计与分析》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.O(1)B.O(n)C.O(logn)D.O(nlogn)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、在算法分析中，大O记号表示的是？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分）简述单调栈和单调队列的用途。三、设计题（本大题共2个小题，共2