山东大学软件学院算法设计与分析期末考试回忆版-Toy模板网

这篇具有很好参考价值的文章主要介绍了山东大学软件学院算法设计与分析期末考试回忆版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、考试时间

2021年12月13日上午10:10-12:10
本次考试是山东大学软件学院2019级软件工程专业大三上算法期末考试
本学期的算法课上课时间为2-7周，9-14周（实际上13周就结束了），第15周考试

考试范围：除了并查集和35章近似算法不考，其他在老师PPT上的内容都是考试范围

二、考试题目

本次算法考试一共有4道大题，每道大题中有多个小题

2.1 第一大题

（1）请解释RAM模型

详细说明见课件
山东大学软件学院算法设计与分析期末考试回忆版

（2）给定递推式：T(n)=T(3n/4) + nlogn，求T(n)的上界

（3）关于NP归约的问题（英文题）

解释“归约”的概念
证明顶点覆盖归约到集合覆盖

2.2 第二大题

（1）写出强连通算法的伪代码，证明正确性，分析时间复杂度

（2）在一个无向有权图G中，有一颗最小生成树T，在该图中，将一条边e的权值w增加，设计算法求新的最小生成树，阐述算法思想，写伪代码，证明该算法的正确性（本题为英文题）

2.3 第三大题

（1）动态规划：x的初值为1，每一步可对x进行+1或乘2的操作，求对一个大于0的整数n来说，x经过操作后等于n所需的最小步数。写出Bellman方程，伪代码

（2）分析Floyd算法的思想，写伪代码，分析时间复杂度和空间复杂度

2.4 第四大题

（1）合并砖块问题：假设有n堆砖，每堆砖都有对应的块数。需要将这n堆砖合并，只能合并两堆相邻的砖。合并的代价是这两堆砖砖数之和。设计动态规划算法，使合并代价最小，写算法思想，伪代码，分析时间复杂度

（2）求“最小代价”问题：对于一个有向图，每个点都有一个值wi，wi > 0，原点s到该点的代价为s到该点的wi之和。设计算法，求s到每个点的最小代价，写伪代码，分析时间复杂度，证明算法正确性

三、总结

总的来说，这次的算法考试还是有一定难度的，首先是题目量较大，很多题都要写思想，写伪代码，分析时间复杂度，证明等，比较复杂。但是这次的算法题中，有三道题都来自平时的作业，并且老师最后一节课还提到了RAM模型可能需要掌握。因此总的来说，在考试的时候需要安排好时间，并复习好老师布置的作业，将算法过程熟练掌握，重要的证明同样需要熟练掌握。

祝学弟学妹算法考试95+文章来源地址https://www.toymoban.com/news/detail-496629.html

到了这里，关于山东大学软件学院算法设计与分析期末考试回忆版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！