湖南工程学院《算法设计与分析A》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页湖南工程学院

《算法设计与分析A》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪个不是动态规划算法的优点？A.高效性B.准确性C.通用性D.简单性2、以下哪种算法的时间复杂度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)3、在贪心算法中，一旦做出选择就（）A.可以更改B.不能更改C.视情况更改D.以上都不是4、在哈希表中，解决冲突的方法有哪些？A.线性探测法和二次探测法B.链地址法和开放定址法C.再哈希法和建立公共溢出区D.以上都是5、算法的稳定性对于（）操作较为重要。A.多次排序B.查找C.插入D.删除6、以下哪个算法可以用于解决0-1背包问题？A.贪心算法B.回溯法C.分治法D.动态规划法7、在二叉树中，中序遍历的顺序是？A.根节点、左子树、右子树B.左子树、根节点、右子树C.左子树、右子树、根节点D.右子树、根节点、左子树8、动态规划算法通常用于解决具有什么性质的问题？A.最优子结构性质和贪心选择性质B.最优子结构性质和重叠子问题性质C.贪心选择性质和重叠子问题性质D.随机性质和重叠子问题性质9、以下哪个排序算法是稳定的？A.快速排序B.堆排序C.希尔排序D.冒泡排序10、快速排序的平均时间复杂度是？A.O(n)B.O(nlogn)C.O(n²)D.O(logn)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、在二叉树中，度为0的节点称为？A.叶子节点B.根节点C.内部节点D.分支节点19、在有向无环图中，进行拓扑排序的时间复杂度是？A.O(1)B.O(n)C.O(nlogn)D.O(n²)20、以下哪个数据结构可以用于实现队列的功能？A.数组B.链表C.栈D.二叉树二、简答题（本大题共4个小题，共40分)1、（本题10分）解释后缀树和后缀数组的概念和应用。2、（本题10分）解释粒子群优化算法的概念和特点。3、（本题10分）阐述堆排序在大规模数据排序中的适用性。4、（本题10分）解释在电子商务中的推荐和定价算法。三、