衡阳师范学院《算法与数据结构》2022-2023学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页衡阳师范学院《算法与数据结构》

2022-2023学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在分治法中，将问题分解成的子问题通常具有（）A.不同的规模B.相同的规模C.随机的规模D.以上都可能2、以下哪个算法可以用于求解最长递增子序列问题？A.贪心算法B.回溯法C.分治法D.动态规划法3、时间复杂度为O(logn)的算法通常比时间复杂度为O(n)的算法（）A.更慢B.更快C.一样快D.无法比较4、以下哪个不是贪心算法的基本要素？A.贪心选择性质B.最优子结构性质C.重叠子问题性质D.无后效性5、归并排序的合并操作的时间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、以下哪个不是图的基本操作？A.插入顶点B.删除顶点C.查找顶点D.排序顶点7、在贪心算法中，如果局部最优解不能导致全局最优解，该算法（）A.仍然有效B.无效C.可能有效D.以上都不是8、算法的最优性是指（）A.时间复杂度最低B.空间复杂度最低C.得到的解最优D.以上都是9、快速排序的空间复杂度主要取决于？A.递归调用的深度B.数据的规模C.枢轴元素的选择D.排序的稳定性10、以下哪种算法常用于构建最小生成树？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法11、快速排序的递归终止条件是什么？A.子数组长度为0或1B.子数组长度为2C.子数组长度为3D.子数组长度为412、以下哪个不是动态规划算法的关键步骤？（）A.定义状态B.找出状态转移方程C.确定初始状态D.进行贪心选择13、在有向无环图中，进行拓扑排序的时间复杂度是？A.O(1)B.O(n)C.O(nlogn)D.O(n²)14、在算法设计中，降低时间复杂度通常比降低空间复杂度更（）A.容易B.困难C.重要D.不重要15、以下哪个数据结构常用于实现队列？（）A.数组B.链表C.栈D.树16、空间复杂度为O(1)的算法意味着（）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个