发布时间 : 星期六 文章算法分析与设计考试复习题及参考答案更新完毕开始阅读e2364bc56ad97f192279168884868762cbaebb4c
最优解。
4. 设计只求一个哈密顿环的回溯算法。
5．利用对称性设计算法，求n为偶数的皇后问题所有解。
参考答案
一、简要回答下列问题 ：
1. 确定性、可实现性、输入、输出、有穷性
2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，
如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。 8. 问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i 9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。 10. 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。 11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 12 最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 13 .T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n) 14 .二分检索算法的最多的比较次数为 log n 。 2 15．.最坏情况下快速排序退化成冒泡排序，需要比较n次。 16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。 18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终 位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。 20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。 21.哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。 22.当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。 23. 思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。 二、复杂性分析 1、 递归方程 T(n)?2(2T(n/4)?cn/2)?cn n?1?a T(n)???4T(n/4)?2cn?2T(n/2)?cnn?1 ??k 设n=2 ?2kT(1)?kcn解递归方程： ?an?cnlogn 2、 i←1 ;s←0 时间为：O(1) while i≤ n do 循环n次 循环体内所用时间为 O(1) 所以 总时间为: T(n)=O(1)+ nO(1)= O(n) 3、最多的查找次数是p-m+1次 4、F2（2，n,1,1）的时间复杂度为： T(n)=O(n-2); 因为i≤n时要递归调用F2，一共是n-2次 当n＝1时F1(n)的时间为 O(1) 当n>1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5、 xmax←A(1);j←1 时间为：O(1) for i←2 to n do 循环最多n-1次 所以 总时间为: T(n)=O(1)+ (n-1)O(1)= O(n) 6、log2n+1 三、算法理解 1、 Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ，D[5]=8 Cost(3,6)= C(6，8)+0=5, D[6]=8 Cost(3,5)= C(5，8)+0=4 D[7]=8 Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)} = min{1+ 5, 2+4}=6 D[4]=6 Cost(2,3)= min{C(3，6)+ Cost(3,6) } = min{4+5}=9 D[3]=5 Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)} = min{8+5, 4+6}=10 D[2]=7 Cost(1,1)= min{C(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)} = min{3+10, 5+9,2+6}= 8 D[1]=4 1→4→6→8 2、 写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=() 1、 48,12,61,3, 5,19,32,7 2、48,12 61,3 5,19 32,7 3、 48～61, 12～3 19～32，5～7 4、 61～32 3～5 5、 61 3 3、 给出5个数(3,6,9,1,7),M=12，用递归树描述sumofsub算法求和数=M的一个子集 的过程。 1，28，0 2，25，3 3，19，3 4，10，12 4、第一个分割元素为65 (1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 5、 65 2 75 80 85 55 50 70 3 7 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 55 70 75 80 85 65 50 2 48,12,61,3 5,19,32,7 48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61 6、 i←0 while i if G[k,i]=1 and X[k]= X[i] then return false i←i+1 repeat if i= k then return true 7、 K←1 X[1] ←1 , 返回 true X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true 找到一个解 （1，2，3，3） 8、 X[1]=1 X[2]=2 X[3]=3 X[4]=3 9、 调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题 调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题 调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题 调用第四层次 只有一个元素返回上一层 第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层 第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层 第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数 10、实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。 CU←25,X←0 W[1]< CU: x[1]←1; CU←CU-W[1]=13;