中北大学《算法设计与分析》2025-2026学年第一学期期末试卷(A卷)

说明：本试卷将作为样卷直接制版胶印，请命题教师在试题之间留足答题空间。（第1页共6页）制卷人签名：制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………中北大学《算法设计与分析》2025-2026学年第一学期期末试卷(A卷)适用年级专业考试方式闭卷考试时间120分钟学院专业班级学号姓名题号一二三四五六七八总分阅卷教师得分………………得分一、单项选择题（每题1分，共20分）1.在算法设计中，时间复杂度通常用哪个符号表示？A.O(n)B.Ω(n)C.Θ(n)D.∝(n)2.下列哪个算法的时间复杂度是O(nlogn)？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.数组元素是唯一的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.动态规划算法二、多项选择题（每题2分，共20分）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.最优子结构问题三、判断题（每题1分，共10分）1.算法的时间复杂度与空间复杂度是相互独立的。（）2.快速排序算法是稳定的排序算法。（）3.树是一种非线性数据结构。（）4.动态规划算法可以解决所有优化问题。（）5.贪心算法总是可以得到最优解。（）6.二分查找算法只能用于有序数组。（）7.链表是一种线性数据结构。（）8.最长公共子序列问题可以通过动态规划算法解决。（）9.最短路径问题可以通过贪心算法解决。（）10.树是一种非线性数据结构。（）四、名词解释（每题4分，共20分）1.时间复杂度2.空间复杂度3.数据结构4.排序算法5.查找算法五、简答题（每题6分，共18分）1.简述算法设计的基本原则。2.简述数据结构的基本类型。3.简述排序算法的基本思想。4.简述查找算法的基本思想。六、案例分析题（1题，满分12分）某公司需要从A地到B地运输一批货物，两地之间的距离为100公里。公司有3辆货车，每辆货车的载重分别为