湖南工商大学《算法导论》2022-2023学年期末试卷

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

《算法导论》2022-2023学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共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.O(n)B.O(nlogn)C.O(n²)D.O(logn)8、在图的遍历中，广度优先搜索使用的数据结构是（）A.栈B.队列C.链表D.树9、在哈希表中，当发生冲突时，可以采用哪种方法来解决？A.线性探测法B.二次探测法C.链地址法D.以上都是10、以下哪个不是动态规划算法的应用场景？A.资源分配问题B.背包问题C.图的遍历问题D.矩阵链乘法问题11、在二叉树中，度为2的节点有10个，度为1的节点有8个，那么叶子节点有多少个？A.9B.10C.11D.1212、在图的深度优先搜索中，使用的辅助数据结构是（）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.O(n)B.O(nlogn)C.O(n²)D.O(logn)19、以下哪个不是算法的评价指标？（）A.正确性B.可读性C.可扩展性D.代码长度20、以下哪个不是动态规划算法的关键步骤？A.确定状态B.确定状态转移方程C.初始化状态D.随机选择状态二、简答题（本大题共4个小题，共40分)1、（本题10分）解释在视频编码中的压缩算法。2、（本题10分）简述活动选择问题的算法思路和解决方法。3、（本题10分）简述网络流算法在实际中的应用。4、（本题10分）以石子合并问题为例，分析动态规划算法的应用。三、设计题（