算法分析与设计复习题答案

算法的定义及五大特性？算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴输入：一个算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。最好最坏和平均情况。给定算法排序用大O记号。如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布画出对三个数进行排序的判定树，并分析时间性能。aa1<a2a1<a2<a3是是是否否否a1<a3a2<a3a2<a1<a3a2<a3a3<a2<a1a2<a3<a1a1<a3a3<a1<a2a1<a3<a2否否是是n!=O(nn),全排序叶子结点至少有n!个，n个排序有n!多种情况，每个叶子对应一种排序结果。举例说明n个NP完全问题，解释一下，写出三种以上。1．SAT问题（BooleanSatisfiabilityProblem）2．最大团问题（MaximumCliqueProblem）3．图着色问题（GraphColoringProblem）4.哈密顿回路问题（HamiltonianCycleProblem）5．TSP问题（TravelingSalsmanProblem）6．顶点覆盖问题（VertexCoverProblem）7．最长路径问题（LongestPathProblem）8．子集和问题（SumofSubsetProblem）给定模式计算next值。KMPT＝“abaababc”next的值，前面重叠子串有多少。j=1时，next[1]=0；j=2时，next[2]=1；j=3时，t1≠t2，next[3]=1；j=4时，t1＝t3，next[4]=2；j=5时，t2≠t4，令k=next[2]=1，t1＝t4，next[5]=k+1=2；j=6时，t2＝t5，next[6]=3；j=7时，t3＝t6，next[7]=4；j=8时，t4≠t7，k=next[4]=2，t2＝t7，next[8]=k+1=3。快速排序的分治策略。（1）划分：选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1…ri-1和ri+1…rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；（2）求解子问题：分别对划分后的每一个子序列递归处理；（3）合并：由于对子序列r1…ri-1和ri+1…rn的排序是就地进行的，所以合并不需要执行任何操作。简述最大子段和问题的分治策略。（1）划分：按照平衡子问题的原则，将序列(a1,a2,…,an)划分成长度相同的两个子序列(a1,…,a)和(a＋1,…,an)，则会出现以下三种情况：①a1,…,an的最大子段和＝a1,…,a的最大子段和；②a1,…,an的最大子段和＝a＋1,…,an的最大子段和；③a1,…,an的最大子段和＝，且（2）求解子问题：对于划分阶段的情况①和②可递归求解，情况③需要分别计算则s1+s2为情况③的最大子段和（3）合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。写出最优二叉查找树的动态规划函数对于P54的查找集合，写出二维表C、R的最终状态动态规划函数：C(i,i-1)=0(1≤i≤n+1)C(i,i)=pi(1≤i≤n)C(i,j)=min{C(i,k-1)+C(k+1,j)+}(1≤i≤j≤n,i≤k≤j)按对角线逐条计算每一个C(i,j)和R(i,j)，得到最终表。

01234100.10.41.11.72

00.20.81.43

00.41.04

00.35

0

012341

122332

2333

334

45

二维表C(b)二维表R最终表的状态d=1d=2d=3d=1d=2d=3对于TSP问题采用最近邻点贪心策略，对于给定图的代价矩阵，写出求解TSP问题的过程。最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市2525221543225221543232522154327363215432233215432(a)5城市的代价矩阵(b)城市1→城市4(c)城市4→城市3(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近邻点贪心策略求解TSP问题的过程C=∞33263∞73237∞25232∞36253∞232∞36253∞写出由贪心法求解图着色的算法P22第七章1．color[1]=1;//顶点1着颜色12．for(i=2;i<=n;i++)//其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++;//取下一个颜色4.2for(i=2;i<=n;i++)//用颜色k为尽量多的顶点着色4.2.1若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突，则color[i]=k;5．输出k;写出用回溯法求解哈密顿回路的算法1．将顶点数组x[n]初始化为0，标志数组visited[n]初始化为0；2．k=1;visited[1]=1;x[1]=1;从顶点1出发构造哈密顿回路；3．while(k>=1)3.1x[k]=x[k]+1，搜索下一个顶点;3.2若(n个顶点没有被穷举)执行下列操作3.2.1若(顶点x[k]不在哈密顿回路上&&(x[k-1],x[k])∈E)，转步骤3.3;3.2.2否则，x[k]=x[k]+1，搜索下一个顶点；3.3若数组x[n]已形成哈密顿路径，则输出数组x[n]，算法结束；3.4否则，3.4.1若数组x[n]构成哈密顿路径的部分解，则k=k+1，转步骤3；3.4.2否则，重置x[k]，k=k-1，取消顶点x[k]的访问标志，转步骤3；用回溯法求解4皇后问题的搜索过程。n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。QQQ××QQ×Q×××××QQQQ×Q××××QQ×××QQQQQQQ××Q(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)QQ×Q写出用动态规划法求解近似串匹配的算法P65.第6章，并分析时间复杂度。大O记号表示。intASM(charP[],charT[],intm,intn,intK){for(j=1;j<=n;j++)//初始化第0行D[0][j]=0;for(i=0;i<=m;i++)//初始化第0列D[i][0]=i;for(j=1;j<=n;j++)//根据递推式依次计算每一列{for(i=1;i<=m;i++){if(P[i]==T[j])D[i][j]=min(D[i-1][j-1