2023年8月1日发(作者：)

南邮《算法分析与设计A》2018-2019学年第⼀学期期末考试回忆2019.1.8 13:30-15:20 《算法分析与设计A》考试刚考完，回忆⼀下题⽬。先总结⼀下：感觉难度完全不是⾃⼰想象的那样，没时间检查，好多不确定不会做。主要还是⾃⼰复习的不好。⼀、选择题1. 算法的五个特性2. 动态规划法的特征3. 分⽀限界法的概念4. ⼀道背包问题求最⼤价值5. 克鲁斯卡尔算法，加⼊新结点之后，判断是否和原来的⽣成森林形成回路，其中⽣成森林⽤了什么数据结构。（同学说是并查集）⼆、填空题1. 第⼀个被证明的

NP完全问题 是什么？2. 回溯法的两个性质。3. 贪⼼法的关键。4. 求 f(n) 的下界。三、简答题1.

Prim算法 和

Kruskal算法 的异同点。2. 背包问题写出⾮启发式算法的S0~S3，并写出解。3. 关键路径：earliest[i] 和

latest[i] 的递推公式、填表格、判断关键活动、写出关键活动和关键路径。4. 图论相关问题，求最⼩费⽤，画出最终的设计图。（不知道是不是⽤

Prim算法 或者

Kruskal算法 ）5. ⼦集和数：先写出满⾜条件的⼦集，再画出空间状态树，最后写出解向量。四、证明题最长公共⼦序列问题Xm={x1,x2,…,xm}，Yn={y1,y2,…yn}，xm=yn。证明：若 Zk={z1,z2,…,zk} 是 Xm 和 Yn 的最长公共⼦序列，则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最长公共⼦序列。五、程序填空题1. ⼀般背包问题的程序填空。2. 最长公共⼦序列的程序填空。

2023年8月1日发(作者：)

南邮《算法分析与设计A》2018-2019学年第⼀学期期末考试回忆2019.1.8 13:30-15:20 《算法分析与设计A》考试刚考完，回忆⼀下题⽬。先总结⼀下：感觉难度完全不是⾃⼰想象的那样，没时间检查，好多不确定不会做。主要还是⾃⼰复习的不好。⼀、选择题1. 算法的五个特性2. 动态规划法的特征3. 分⽀限界法的概念4. ⼀道背包问题求最⼤价值5. 克鲁斯卡尔算法，加⼊新结点之后，判断是否和原来的⽣成森林形成回路，其中⽣成森林⽤了什么数据结构。（同学说是并查集）⼆、填空题1. 第⼀个被证明的

NP完全问题 是什么？2. 回溯法的两个性质。3. 贪⼼法的关键。4. 求 f(n) 的下界。三、简答题1.

Prim算法 和

Kruskal算法 的异同点。2. 背包问题写出⾮启发式算法的S0~S3，并写出解。3. 关键路径：earliest[i] 和

latest[i] 的递推公式、填表格、判断关键活动、写出关键活动和关键路径。4. 图论相关问题，求最⼩费⽤，画出最终的设计图。（不知道是不是⽤

Prim算法 或者

Kruskal算法 ）5. ⼦集和数：先写出满⾜条件的⼦集，再画出空间状态树，最后写出解向量。四、证明题最长公共⼦序列问题Xm={x1,x2,…,xm}，Yn={y1,y2,…yn}，xm=yn。证明：若 Zk={z1,z2,…,zk} 是 Xm 和 Yn 的最长公共⼦序列，则 zk=xm=yn 且 Zk-1 是 Xm-1 和 Yn-1 的最长公共⼦序列。五、程序填空题1. ⼀般背包问题的程序填空。2. 最长公共⼦序列的程序填空。