盐城师范学院《算法实现训练》2021-2022学年期末试卷

装订线装订线PAGE2第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.运行速度加快B.内存溢出C.结果更准确D.以上都不是7、以下哪个算法可以用于求解字符串的最长回文子串问题？A.贪心算法B.回溯法C.分治法D.动态规划法8、动态规划算法通常需要一个什么来存储子问题的解？A.数组B.链表C.栈D.队列9、在图的遍历中，深度优先搜索和广度优先搜索的主要区别是？A.遍历的顺序不同B.时间复杂度不同C.空间复杂度不同D.适用的图类型不同10、以下哪个算法常用于图的最短路径问题？（）A.Dijkstra算法B.Prim算法C.Kruskal算法D.Floyd算法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(n²)，如果输入规模扩大一倍，那么运行时间会变为原来的几倍？A.2倍B.4倍C.8倍D.16倍18、在二叉树中，度为0的节点称为？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