江大算法设计复习.docVIP

A、考试范围 一、基本题（20％） 排序、分治、动态规划、贪心、回溯和分枝限界；渐进性符号及定义，求解递推关系 二、简答解答（30％）：2题 三、算法设计（50％）：分治、动态规划、贪心、回溯，2题， B、第二部分例题： 1.考虑在序列 A[1..n]中找最大最小元的问题。一个分治算法描述如下： 如果n=2就直接求解；否则，将序列等分成两个子序列A[1..n/2]和 A[n/2+1..n],分别找出这两个子序列的最大最小元素，据此求出A[1..n] 的最大和最小元。请给出该算法计算时间T(n)的递归方程，并解方程来确 定算法的时间复杂度.假设n=2k(k为正整数) 2.简述基数排序的基本思想和算法时间复杂度； 考虑使用基数排序对下列8个数据进行排序，给出排序的中间过程和最终结果 2756，7352，3725，3762，5273，2375，5732，5627 3.快速排序是根据分治策略来设计的，其基本思想是什么？快速排序的最坏及平均情况的时间复杂度是多少？ 4.考虑用动态规划法求解矩阵的最优运算（即乘法次数最少）的次序， 其中 （1）设C[i,j]表示按照最优次序运算所需要的元素乘法次数。 请给出C[i,j]递推计算的表达式 （2）根据递推公式填写下表，包括C[i,j]的值及对应的最优计算次序的加括号方式 C[1,1]=0 M1 C[1,2]=120 M1 M2 C[1,3]=280 (M1 M2) M3 C[1,4]=258 M1 (M2 (M3 M4)) C[1,5]=333 (M1 (M2 (M3 M4 )))M5 C[2,2]=0 M2 C[2,3]=192 M2 M3 C[2,4]=168 M2 (M3 M4) C[2,5]=258 (M2 (M3 M4 ))M5 C[3,3]=0 M3 C[3,4]=96 M3 M4 C[3,5]=156 (M3 M4 )M5 C[4,4]=0 M4 C[4,5]=120 M4 M5 C[5,5=0 M5 C、第三部分例题 1.将正整数表示成一系列正整数之和，， 其中，。 正整数的这种表示称为正整数的的划分。正整数的的不同的划分个数称为正整数的的划分数，记作。试推导出的求解方法。 2.设个不同的整数按由小到大顺序存于中。 1). 若存在下标，，,证明：对，有 2). 若T中存在下标，，使得，设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间复杂性为 3．最长公共子序列（递增、递减、双向子序列） 4．背包问题、二维背包问题 5. 给定平面上n（）个点,要求把这些点连成一条折线，使得连成的折线长度最短。请用回溯法设计解决此问题的算法，并分析算法的时间复杂性。 使用排列树作为解空间树，用标准的排列树回溯算法。 P记录结点信息 p.i原结点序号 p.x结点横坐标 p.y结点纵坐标 bestP:记录最有顺序 len:记录从起始点到当前点距离； bestlen :已计算得到的最短距离 backtrack (int t) { if (tn) then 记录目前最优; bestP = P; bestlen = len; else for (int i=t;i=n;i++) { swap(P[t], P[i]); if i=1 then dist = 0; else dist = P(t)点与P(t-1)点之间的距离; len += dist; if (lenbestlen) backtrack(t+1); len -= dist; swap(x[t], x[i]); } } 主程序 对P, len初始化 对bestlen初始化（∞） backtrack (1); 输出bestP和bestlen 6、凸包问题（GRAHAM算法） 算法A 首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并 按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于 P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中 保存的点就是凸包了。 如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。和必定是凸多边形的两个顶点。 第二步：在上凸包点集s1中找到一个