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

算法的定义及五大特性？ 算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。 算法的五大特性： ⑴ 输入：一个算法有零个或多个输入。 ⑵ 输出：一个算法有一个或多个输出。 ⑶ 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 最好最坏和平均情况。给定算法排序用大O记号。 如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。 最好情况：出现概率较大时分析 最差情况：实时系统 平均情况：已知输入数据是如何分布的，通常假设等概率分布 画出对三个数进行排序的判定树，并分析时间性能。 n!=O(nn),全排序叶子结点至少有n!个，n个排序有n!多种情况，每个叶子对应一种排序结果。 举例说明n个NP完全问题，解释一下，写出三种以上。 1．SAT问题（Boolean Satisfiability Problem） 2．最大团问题（Maximum Clique Problem） 3．图着色问题（Graph Coloring Problem） 4. 哈密顿回路问题（Hamiltonian Cycle Problem） 5．TSP问题（Traveling Salsman Problem） 6．顶点覆盖问题（Vertex Cover Problem） 7．最长路径问题（Longest Path Problem） 8．子集和问题（Sum of Subset Problem） 给定模式计算next值。KMP T＝“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)，得到最终表。 对于TSP问题采用最近邻点贪心策略，对于给定图的代价矩阵，写出求解TSP问题的过程。 最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市 写出由贪心法求解图着色的算法P22第七章 1．color[1]=1; //顶点1着颜色1