type
status
date
slug
summary
tags
category
icon
password
一、概念题（英文题）
- 解释O Θ Ω 在函数的增长中的定义
- 解释多项式归约
- 解释P、NP、NPC问题
二、钢条切割问题，算法思想，伪代码，时间复杂度
三、证明子图同构问题是NPC问题（团问题归约到…）
四、给定一个整数序列。定义序列中的 “ inversion ” 如下：一个元素，它和位于其后位置的比它小的元素构成一个inversion。例如74386，inversion为74,73,76,43,86，其解值为5。求一个序列的inversion解值。（参考归并排序）给出思想、伪代码、复杂度（英文题）
五、n个团队，m个会议室，每个团队有A[i]个人，每个会议室容纳B[j]个人，使用贪心算法求如何能满足最多会议（一个会议室只能一个团队开会，团队不能分散开），算法思想，伪代码，时间复杂度，正确性证明
六、基础矩阵乘法求所有节点最短路径，算法思想，填矩阵，写最短路径
七、顶点覆盖问题的近似算法思想，伪代码、证明2近似算法（英文题）
感谢室友们帮忙回忆~
其他年份的：
山东大学软件学院算法设计与分析期末考试回忆版-CSDN博客 2021.12
教材课后题答案：（这版不错，非官方）
- 作者:Rainnn
- 链接:https://tangly1024.com/article/65546757-ee42-4c31-87cd-4ea25385b800
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。