淮北师范大学《算法设计与分析实验》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第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.对于任意输入都能得到正确结果B.对于大部分输入能得到正确结果C.对于特定输入能得到正确结果D.以上都不是11、归并排序的合并操作的时间复杂度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)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分）解释插入排序对近乎逆序数组的处理性能。三、设