聊城大学《算法设计与分析》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页聊城大学《算法设计与分析》

2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在动态规划中，重叠子问题的性质是指（）A.子问题多次出现B.子问题相互独立C.子问题具有唯一性D.以上都不是2、以下哪个不是查找算法？（）A.顺序查找B.二分查找C.冒泡排序D.哈希查找3、快速排序算法在最坏情况下的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)4、以下哪种算法常用于解决皇后问题？（）A.贪心算法B.回溯法C.动态规划D.分治法5、以下哪个算法常用于图的最短路径问题？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法6、快速排序在最好情况下的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)7、在贪心算法中，每一步的选择都是（）A.全局最优B.局部最优C.随机的D.以上都不是8、以下哪种算法的时间复杂度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)9、算法的正确性是指（）A.对于任意输入都能得到正确结果B.对于大部分输入能得到正确结果C.对于特定输入能得到正确结果D.以上都不是10、以下哪个数据结构可以用于实现栈的功能？A.数组B.链表C.队列D.二叉树11、以下哪种排序算法在平均情况下性能最优？（）A.冒泡排序B.插入排序C.快速排序D.选择排序12、快速排序的平均时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)13、以下哪个不是图的存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.顺序表14、以下哪个排序算法在最坏情况下性能最优？（）A.冒泡排序B.插入排序C.归并排序D.堆排序15、在二叉树中，度为0的节点称为？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分）用动态规划算法解决最长公共子序列问题。三