河北地质大学《算法设计与分析》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页河北地质大学

《算法设计与分析》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共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.O(1)B.O(n)C.O(nlogn)D.O(n²)7、时间复杂度为O(n)的算法，其执行时间与输入规模n的关系是（）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.O(1)B.O(logn)C.O(n)D.O(n²)16、以下哪个数据结构常用于实现图？（）A.数组B.链表C.邻接矩阵和邻接表D.栈17、在算法分析中，大O记号表示的是？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分）分析快速排序的递归深度及其对性能的影响。三、设计题（本大题