南京工业大学《工程伦理：计算机》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页南京工业大学《工程伦理：计算机》2021-2022学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种算法的时间复杂度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)2、快速排序在最好情况下的时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)3、以下哪种算法常用于解决组合优化问题？（）A.贪心算法B.回溯法C.分治法D.动态规划4、动态规划算法通常需要一个什么来存储子问题的解？A.数组B.链表C.栈D.队列5、在动态规划中，优化子问题的解存储方式可以（）A.降低时间复杂度B.降低空间复杂度C.提高可读性D.以上都是6、一个算法的时间复杂度为O(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍7、以下哪种排序算法在平均情况下性能最优？（）A.冒泡排序B.插入排序C.快速排序D.选择排序8、归并排序的合并操作的时间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)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.子问题的选择顺序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分）分析希尔排序算法的特点和优势。三、设计题（本大题共2个小