本文主要是介绍湖南大学-算法设计与分析-2023期末考试【原题】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
21:00刚刚结束的考试,凭着回忆把题目重现出来了,在复习的时候根本找不到往年的试卷,希望这张回忆的试卷能帮助到下一届的同学。知道题目基本上就能做出来了,但是不知道是真的做不出来,我就不给答案了,自己对着链接或者到书本上找找。
这场考试太不容易,题量太大了,没写完,寄了。这学期的课程考试都不太顺的样子。
教材用的这本书(第5版)
简答题(30分)
1.队列式分支限界,优先队列式分支限界区别在哪里?
2.动态规划和贪心算法的区别?
3.展开计算()
T(n)=4T(n/2)+O(n),n!=1
T(n)=1,n=1
答案:O(n^2)
4.回溯法框架填空(第5版,书P123页)
5.哪一种随机化算法可以解决线性时间选择问题?简要叙述解决思想。
算法实现题(40分)
第1题(10分) 装载问题(原题,书P125-127)
子树(1分)算法思想(2分)
剪枝算法(3分)最终完整(4分)
第2题(15分) 矩阵连乘问题(原题,书P49-50)
证明最优子结构性质(3分)
给出递推式(3分)
给出M矩阵(3分)给出S矩阵(3分)给出最终加括号的顺序(3分)
第3题(15分) Dijkstra算法
算法思想(3分)
证明贪心选择性质(6分)
跟着做一个案例(6分)
算法设计题(30分)
第1题 贪心算法:删数问题
(当时数据结构与算法分析的期末考试就是这道题,当时没做出来,这次又遇到了)(https://www.luogu.com.cn/problem/P1106)
第2题 分支限界法:最小权顶点覆盖
(书上原题,好像有改动,书上算法实现题6-2)
(这个好像有点问题https://blog.csdn.net/weixin_44755413/article/details/106504077)
第3题 动态规划:给两个字符串S和T,使用动态规划法判定S是否是T的字串
(个人想法:感觉是LCS最长公共子序列,对S和T做一遍最长公共子序列,然后看这个结果是不是S,如果是就说明是对的,否则就是错的)
这篇关于湖南大学-算法设计与分析-2023期末考试【原题】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!