西南林业大学《算法分析与设计实验》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页西南林业大学

《算法分析与设计实验》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪种算法常用于解决凸包问题？（）A.Graham扫描法B.Dijkstra算法C.Prim算法D.Kruskal算法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.0到1B.0到正无穷C.负无穷到正无穷D.1到正无穷12、动态规划算法通常用于解决（）问题。A.最优解B.近似解C.随机解D.无解13、以下哪个不是贪心算法的局限性？A.不一定能得到全局最优解B.算法的时间复杂度较高C.对问题的性质有一定要求D.难以证明算法的正确性14、以下哪个数据结构可以高效地进行插入和删除操作，并且可以快速地找到最小值？A.数组B.链表C.栈D.堆15、以下哪个不是动态规划算法的应用场景？A.资源分配问题B.背包问题C.图的遍历问题D.矩阵链乘法问题16、在二叉树中，度为2的节点有10个，度为1的节点有8个，那么叶子节点有多少个？A.9B.10C.11D.1217、以下哪个数据结构常用于实现集合？（）A.数组B.链表C.哈希表D.树18、以下哪个不是算法的性能指标？A.正确性B.可读性C.可扩展性D.美观性19、时间复杂度为O(n)的算法，其执行时间与输入规模n的关系是（）A.线性增长B.指数增长C.对数增长D.不变20、以下哪个数据结构常用于实现图？（）A.数组B.链表C.邻接矩阵和邻接表D.栈二、简答题（本大题共4个小题，共40分)1、（本题10分）简述在交通运输中的流量预测和路线规划算法。2、（本题10分）解释在金融工程中使用的风险评估算法。3、（本题10分）分析在增强现实中的跟踪算法。4、（本题10分）分析希尔排序的分组策略对性能的影响。三、设计题（本大题共2个小题，共20分)1、（本