20年06月考试题目回忆.txt

1 举例说明计算a^n时候，分治、减治、变治思想的异同。
2 举例说明BM，KMP，Sunday算法思路的异同。
3 举例说明01背包问题中贪心算法和动态规划算法的异同。
4 说明01背包问题使用分支限界中“界”的选择。
5 快速排序有哪些优化的空间？分析在SIMD-EREW，SIMD-CRCW，MIMD-TC上并行快排的思路。
6 最长单调递增子序列问题。x[1...n]序列上，满足a1<a2<a3...<am,其中m<=n,一定有x[a1]<x[a2]<x[a3]...<x[am]，则称{a1,a2,a3...am}为x的单调递增子序列。
（1）设计算法计算x[1...n]的最大单调子序列的m值。
输入：x[1...n]
输出：m
（2）设计算法计算当输入子序列的长度s时，输出能满足此长度子序列的数量num。
输入：s （需要进行条件判断，例如最大为m）
输出：num