青岛大学《算法与数据结构》2021-2022学年期末试卷

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

《算法与数据结构》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种数据结构常用于实现栈？（）A.数组B.链表C.树D.图2、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍3、以下哪个算法可以用于解决0-1背包问题？A.贪心算法B.回溯法C.分治法D.动态规划法4、在分治法中，如果子问题的规模不相等，可能会（）A.影响算法效率B.提高算法效率C.不影响算法效率D.以上都不是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、在二叉树中，度为0的节点称为？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、在图的存储结构中，邻接表适合存储什么样的图？A.稀疏图B.稠密图C.有向图D.无向图17、在图的深度优先搜索中，使用的辅助数据结构是（）A.栈B.队列C.优先队列D.哈希表18、以下哪个数据结构常用于实现字典？（）A.哈希表B.二叉树C.链表D.栈19、在算法分析中，大O记号表示的是？A.算法的精确运行时间B.算法的平均运行时间C.算法运行时间的上界D.算法运行时间的下界20、在二叉搜索树中进行查找操作的平均时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释插入排序在有序和无序数据混合时的表现。2、（本题10分）简述贪心算法在网络带宽分配中的应用策略及不足。3、（本题10分）阐述归并排序在可扩展性方面的特点。4、（本题10分）简述在能源管理中的调度算法。三、设计