算法导论英文课件考试相关.pptxVIP

AlgorithmsReview

2考试范围算法分析算法分析的基本方法主方法递归树展开…典型算法的计算时间算法设计典型算法设计策略的求解方法分治：分、治、合并的过程DP：目标函数与递推关系式贪心：贪心准则有哪些信誉好的足球投注网站：有哪些信誉好的足球投注网站过程、限界函数典型问题的求解思路与基本的计算过程

3题目类型判断题计算题概念题设计题

4判断题归并排序的最坏情况下的计算时间为O(nlgn)。数组{1234567}是一个小顶堆。计数排序（CountingSort）通过统计给定输入中小于等于i（1=i=k）的数的个数完成排序。若一个问题不满足最优子结构性质，仍可用贪心算法求得问题的最优解。TSP问题属于NP完全问题。

5计算题求解以下递归式：

6计算题计算串X=A,B,C,B,D,A,B与Y=B,D,C,A,B,A的最长公共子序列长度，并根据计算结果给出一个最长公共子序列。

7概念题回答以下关于动态规化策略的问题：试描述动态规划策略求解问题的一般方法。利用动态规划策略求解问题时，通常要求问题需要具备什么特征？动态规化用于求解装配线调度问题时，最优解值的定义形式、所使用的递推关系式及其含义是什么？贪心策略用于求解Huffman编码时，使用的贪心准则是什么？