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

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页东北林业大学《算法分析与设计》2025-2026学年第一学期期末试卷(B卷)注意事项:1.请考生在下列横线上填写姓名、学号和年级专业。2.请仔细阅读各种题目的回答要求，在规定的位置填写答案。3.不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4.考试时间120分钟专业学号姓名题号一二三四五六七八总分统分人复查人得分得分评分人一、单项选择题（每题1分，共20分）1.下列哪个算法的时间复杂度是O(nlogn)？A.快速排序B.冒泡排序C.选择排序D.插入排序2.在二叉搜索树中，查找一个元素的平均时间复杂度是多少？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)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.快速排序的平均时间复杂度是O(nlogn)。（）2.在二叉搜索树中，查找一个元素的平均时间复杂度是O(n)。（）3.贪心算法总是能得到最优解。（）4.栈是一种先进先出（FIFO）的数据结构。（）5.队列是一种先进后出（FILO）的数据结构。（）6.动态规划是一种贪心算法。（）7.回溯算法是一种分治算法。（）8.最小生成树是一种贪心算法。（）9.最长公共子序列是一种回溯算法。（）10.最短路径算法是一种贪心算法。（）四、名词解释（每题4分，共20分）1.算法复杂度2.分治算法3.贪心算法4.动态规划5.回溯算法五、简答题（每题6分，共18分）1.简述快速排序的原理。2.简述贪心算法的特点。3.简述动态规划的基本思想。六、案例分析题（