南京信息工程大学《随机算法》2023-2024学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页南京信息工程大学

《随机算法》2023-2024学年期末试卷题号一二三总分得分一、单选题（本大题共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.容易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、在二叉树中，度为2的节点有10个，度为1的节点有8个，那么叶子节点有多少个？A.9B.10C.11D.1214、以下哪种排序算法对近乎有序的数组效果较好？（）A.快速排序B.插入排序C.冒泡排序D.选择排序15、以下哪个不是图的存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.顺序表16、以下哪个算法常用于图的最短路径问题？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法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分）分析冒泡排序在不同编程语言中的实现差异。三、