算法设计技巧与分析 期末总复习提要

Algorithms

DesignTechniquesandAnalysis

算法设计技巧与分析

期末总复习课考试题型各章复习提要

考试题型简答题(5小题，共20分)快速排序和归并排序两者中哪个的平均比较次数要多。

假定图用邻接矩阵表示，图的宽度优先遍历算法的时间复杂度是什么？如果图用邻接表来表示呢？

考试题型计算题(2小题，共10分)解下列递归方程：

f(n)=2f(n-1)+3f(n-2),n>2;f(0)=1,f(1)=0.使用记号

表示下列函数：

n3+

10nlog50n+100n

考试题型算法应用题(4小题，共50分)归纳技术、分治法：

考虑使用归并排序给序列{10,8,2,4,12,6}排序。请给出算法执行中各次划分、合并的结果。（可画图表示）动态规划：使用动态规划法来求解下列0/1背包问题的实例：n=5,W={2,1,2,3,3}，P={8,6,7,9,8}，M=6。给出主要步骤。

考试题型算法应用题(4小题，共50分)贪心法：

考虑用哈夫曼算法来找字符a,b,c,d,e,f的最优编码。这些字符出现在文件中的频数之比为8:3:5:4:11:7。试给出字符a,b,c,d,e,f的一种最优编码。要求给出主要步骤的结果。

考试题型算法应用题(4小题，共50分)设计一个回溯算法来求解k-着色问题：给定无向图G=<V,E>,要求使用k种颜色来给图中每个结点着色（每个结点使用k种颜色之一），使得没有两个相邻的结点颜色相同。

(a)

给出解向量形式，并画出当n=3,k=3时的搜索树。

(b)

给出剪枝操作。

(c)最坏情况下算法在搜索树上会访问到多少个结点？分析算法的时间复杂度。

考试题型算法设计与分析题(1小题，共10分)考虑在序列A[1..n]中找最大最小元素的问题。一个分治算法描述如下：如果n≤2就直接求解。否则，将序列等分成两个子序列A[1..n/2]和A[n/2+1..n]，分别找出这两子序列的最大最小元素x1,y1和x2,y2；然后据此可求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。试给出该算法计算时间T(n)满足的递归方程，并解方程来确定算法的时间复杂度。假定n=2k（k为正整数）。

考试题型

实验题目（1小题，共10分)[实验1]快速排序与归并排序平均运行时间之比较

——根据实验内容设计问答题[实验2]动态规划法的简单应用

——根据实验内容设计问答题[实验3]回溯法的应用

——根据实验内容设计问答题各章复习要点第一章算法分析的基本概念复习范围

1.1--1.14复习要点评价算法性能的几个标准正确性、易读性、健壮性、算法的时间和空间性能：高效率和低存储空间算法复杂度概念渐近记号

、

、

的含义P14最优算法的概念P20最好、最坏、平均时间(空间)复杂度P26分析复杂度的主要步骤，各步骤的要点（包括输入大小的确定P31、基本操作的选择P24等）相关习题类型

1.14---1.16各章复习要点

第二章

算法分析的数学基础复习范围2.7--2.8

复习要点简单求和公式P48定积分近似求和P50两个重要公式几个例子2.15~2.17简单递归方程的解法P52相关习题类型

2.16,2.17,2.18,2.19各章复习要点

第五章

归纳技术复习范围5.3,5.4,5.5,5.7复习要点各算法的基本思想能简单应用相关习题类型

5.7-5.9,5.17-5.18,5.33各章复习要点

第六章分治法复习范围6.1--6.4,6.6--6.7,6.8复习要点分治法的适用范围、基本思想各算法的基本思想、复杂度结论能简单应用相关习题类型

6.10,6.31,6.36,6.44各章复习要点

第七章动态规划法复习范围

7.2--7.6

复习要点动态规法法的适用范围、基本步骤各算法的基本思想能简单应用相关习题类型

7.5,7.9,7.15,7.21,7.32,7.33,7.34各章复习要点

第八章贪心法复习范围

8.1----8.5

复习要点贪心法的基本思想各算法的基本思想、复杂度结论

(Dijkstra、Prim算法的改进不作要求)

能简单应用

相关习题类型

8.10,8.13，8.23,8.24，8.31各章复习要点

第九章图的遍历复习范围9.1，9.2，9.4复习要点深度优先遍历和宽度优先遍历的基本思路、时空复杂度注意：应用中需要用到的边的几种类型相关习题类型9.1,9.2,9.6,9.19,9.20各章复习要