装订线重庆交通大学《算法设计实训》2023-2024 学年第一学期期末试卷院(系)_______ 班级_______ 学号_______ 姓名_______题号一二三四总分得分批阅人一、单选题（本大题共 15 个小题，每小题 1 分，共 15 分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在凸包问题的求解中，Graham 扫描算法是一种常用的算法。以下关于 Graham 扫描算法的描述，不正确的是：（ ）A. Graham 扫描算法通过选择一个起始点，按照极角顺序依次处理其他点，来构建凸包B. Graham 扫描算法的时间复杂度为 O(nlogn)，其中 n 是点的数量C. Graham 扫描算法在处理过程中需要对点进行排序和栈操作D. Graham 扫描算法得到的凸包一定是唯一的2、假设要在一个二叉搜索树中查找一个特定的值。如果二叉搜索树的结构不太平衡，可能会影响查找效率。为了提高查找效率，可以采取以下哪种措施？（ ）A. 对二叉搜索树进行中序遍历B. 重新构建一个平衡的二叉搜索树，如 AVL 树或红黑树C. 使用深度优先搜索算法D. 将二叉搜索树转换为链表3、以下哪个数据结构可以高效地进行插入和删除操作，并且可以快速地找到最小值？（ ）A. 数组B. 链表C. 栈D. 堆4、在字符串匹配算法中，KMP（Knuth-Morris-Pratt）算法是一种高效的算法。以下关于 KMP 算法的描述，错误的是：（ ）A. KMP 算法通过利用已经匹配的部分信息，避免了不必要的回溯，提高了匹配效率B. KMP 算法的核心是构建一个 next 数组，用于指导匹配过程中的移动C. KMP 算法在最坏情况下的时间复杂度为 O(m + n)，其中 m 是模式串的长度，n 是主串的长度D. KMP 算法的空间复杂度主要取决于模式串的长度，与主串的长度无关第 1 页，共 6 页装订线5、在最小生成树算法中，普里姆算法（Prim's Algorithm）和克鲁斯卡尔算法（Kruskal's Algorithm）是两种常见的算法。对于这两种算法，以下描述哪一项是不正确的？（ ）A. 普里姆算法从一个顶点开始逐步扩展生成树B. 克鲁斯卡尔算法按照边的权值从小到大选择边来构建生成树C. 这两种算法得到的最小生成树一定是相同的D. 普里姆算法适用于稠密图，克鲁斯卡尔算法适用于稀疏图6、在算法的实际应用场景中，以下关于算法在网络路由中的作用描述哪一项是不正确的？（ ）A. 用于计算最优的数据包传输路径B. 可以考虑网络带宽、延迟等因素C. 算法的选择对网络性能没有显著影响D. 能够适应网络拓扑结构的变化...
