贺州学院《算法分析与设计基础实验语言》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页贺州学院《算法分析与设计基础实验语言》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在哈希表中，装填因子的取值范围是？A.0到1B.0到正无穷C.负无穷到正无穷D.1到正无穷2、以下哪个不是图的遍历算法？（）A.深度优先搜索B.广度优先搜索C.最短路径搜索D.拓扑排序3、以下哪个算法可以用于求解字符串的最长回文子串问题？A.贪心算法B.回溯法C.分治法D.动态规划法4、以下哪个不是查找算法？（）A.顺序查找B.二分查找C.冒泡排序D.哈希查找5、以下哪个算法可以用于解决0-1背包问题？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.KMP算法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分）说明如何用回溯法解决组合问题