10湖北工业大学在职研究生《算法分析试题及答案》

湖北工业大学2014年在职攻读硕士学位课程考试（考查）试题考试（考查）科目算法分析与设计学位类别工程硕士说明：1.试题版面为标准A4，各题标题字号为黑体5号字，题干字号为标准宋体5号字2.答案必须写在答题纸上，写在试卷上无效。一、分治法有那几个步骤组成？（10分）二、给出贪婪法的设计方法描述。（10分）三、请画出四皇后问题的搜索树。（10分）四、请描述分支与限界法的基本思想。（10分）五、随机算法有哪些类型？（10分）六、给出如下算法，请分析时间复杂度。（10分）1.Typegame(Typegroup[],intn)2.{3.intj,i=n;4.while(i1){5.i=i/2;6.for(j=0;ji;j++)7.if(comp(group[j+i],group[j]);8.group[j]=group[j+i];9.}10.returngroup[0];11.}七、请画出5、8、4、9、3、6、7、2等数据采用快速排序算法的执行过程。（10分）八、请画出下图的克鲁斯卡尔算法执行过程。（10分）九、请给出搜索过程中可能生成的结点数的估计算法。（10分）解向量的第i个分量ix的取值范围为有限集iS；cons(node,x)判断结点node的儿子结点x是否满足约束条件，若满足为真，否则为假；表达式：}),(][|{xnodeconsiSxxT表示在结点node下满足约束条件的第i个分量ix的取值集合；sizeof(T)求取集合T的元素个数；choose(T)从集合T中随机地选取一个元素。估计回溯法在搜索过程中所生成的结点总数m。十、请给出求取整数因子的Pollard算法。（10分）输入：整数n输出：整数n的因子考试（考查）科目算法分析与设计一、分治法有那几个步骤组成？（10分）分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。二、给出贪婪法的设计方法描述。（10分）贪婪法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。贪婪法是一种不追求最优解，只希望得到较为满意解的方法，一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以不要回溯。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；三、请画出四皇后问题的搜索树。（10分）x1=1x1=4x1=2x1=3234134124123342423341413241412231312434232434131424121323121四、请描述分支与限界法的基本思想。（10分）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。其基本思想：在问题的边带权的解空间树中进行广度优先搜索，找一个回答结点使其对应路径的权最小（最大）。当搜索到达一个扩展结点时，一次性扩展它的所有儿子，将那些满足约束条件且最小耗费函=目标函数限界的儿子，插入活动结点表中，再从活动结点表中取下一结点同样扩展。直到找到所需的解或活动结点表为空为止。五、随机算法有哪些类型？（10分）8292419133565145403561250341816558606349535514162036322225302759575452484643413864624691123262831333739424447571012151721a)Sherwood算法：确定型算法在最坏情况下的时间复杂度与其在平均情况下的时间复杂度有较大差异；引入随机性来消除或减少问题好坏实例之间的这种差别；精髓不是避免算法的最坏情况发生，而是设法消除这种最坏情形行为与特定实例之间的关联性.b)LasVegas算法：对于找不到有效算法的某些问题，可使用LasVegas算法来求解，可能会很快找到问题的一个解；一旦得到问题的一个解，一定是正确的。但是，这种算法所作随机性决策可能导致找不到解；可通过多次调用同一LasVegas算法来增加得到问题解的概率。c)MonteCarlo算法：确定性算法还是随机算法都无法保证每次得到正确的解；MonteCarlo算法以高概率给出正确解通常无法判定一个具体解是否正确；可通过重复调用同一个MonteCarlo算法多次来提高获得正确解的概率。六、给出如下算法，请分析时间复杂度。（10分）1.Typegame(Typegroup[],intn)2.{3.intj,i=n;4.while(i1){5.i=i/2;6.for(j=0;ji;j++)7.if(comp(group[j+i],group[j]);8.group[j]=group[j+i];9.}10.returngroup[0];11.}七、请画出5、8、4、9、3、6、7、2等数据采用快速排序算法的执行过程。（10分）八、请画出下图的克鲁斯卡尔算法执行过程。（10分）九、请给出搜索过程中可能生成的结点数的估计算法。（10分）解向量的第i个分量ix的取值范围为有限集iS；cons(node,x)判断结点node的儿子结点x是否满足约束条件，若满足为真，否则为假；表达式：}),(][|{xnodeconsiSxxT表示在结点node下满足约束条件的第i个分量ix的取值集合；sizeof(T)求取集合T的元素个数；choose(T)从集合T中随机地选取一个元素。估计回溯法在搜索过程中所生成的结点总数m。IntEstimate(STypex){intk=0,m=1,r=1;do{SetType}),(][|{xnodeconsiSxxT;If(!sizeof(T))Returnm;R=r*sizeof(T);m=m+r;xi=choose(T);i++;}while(1);}十、请给出求取整数因子的Pollard算法。（10分）输入：整数n输出：整数n的因子(defunfactorial(n);;;阶乘(setfm1)(loopforifrom1tondo(setfm(*mi)))m)(defunexpmod(baseexpmodulo);;;幂取模(if(=exp0)1(if(evenpexp)(mod(expt(expmodbase(/exp2)modulo)2)modulo)(mod(*base(expmodbase(-exp1)modulo))modulo))))(defunpollard-p-1(nB);;;n是合数(let((k(factorialB))(d1));;;k=B!(loopwhile(or(=d1)(=dn))do(setfd(gcdn(-(expmod(+(random(-n3))2)kn)1))));;;d的计算d))