电子科技大学研究生算法设计与分析拟考题及答案评分细则

第1页共5页一、PleaseanswerTorFforeachofthefollowingstatementstoindicatewhetherthestatementistrueorfalse1.Analgorithmisaninstance,orconcreterepresentation,foracomputerprograminsomeprogramminglanguage.(F)2.ThefollowingproblemisaDecisionProblem:Whatisthevalueofabestpossiblesolution?(F)3.Thedynamicprogrammingmethodcannotsolveaprobleminpolynomialtime.(F)4.AssumethatthereisapolynomialreductionfromproblemAtoproblemB.IfwecanprovethatAisNP-hard,thenweknowthatBisNP-hard.(F)5.Ifonecangiveapolynomial-timealgorithmforaprobleminNP,thenalltheproblemsNPcanbesolvedinpolynomialtime.(F)6.Inanundirectedgraph,theminimumcutbetweenanytwoverticesaandbisunique.(F)7.Linearprogrammingcanbesolvedinpolynomialtime,butintegerlinearprogrammingcannotbesolvedinpolynomialtime.(T)8.Wecansolvethemaximumindependentsetprobleminagraphwithatmost100verticesinpolynomialtime.(T)结论9.Ifanalgorithmsolvesaproblemofsizenbydividingitintotwosubproblemsofsizen/2,recursivelysolvingeachsubproblems,andthencombinethesolutionsinlineartime.ThenthealgorithmrunsinO(nlogn)time.(T)10.NeuralComputation,FuzzyComputationandEvolutionComputingarethethreeresearchfieldsofComputationalIntelligence.(T)二、Giventhefollowingsevenfunctionsf1(n)=n5+10n4,f2(n)=n2+3n,f3(n)=2100001.5n,f4(n)=logn+(2logn)3,f5(n)=2n+n!+5en,f6(n)=3log(2n)+5logn,f7(n)=2nlogn+lognn.Pleaseanswerthequestions:第2页共5页(a)Givethetightasymptoticgrowthrate(asymptoticexpressionwith)toeachofthem;(7分)(b)Arrangetheminascendingorderofasymptoticgrowthrate。(3分)参考答案和评分标准：a)(1)n5+10n4=(n5)（1分，非最简表达式或写成O或不符合题意，不给分）(2)n2+3n=(3n)（1分，标准同上）(3)2100001.5n=(n0.75)（1分，标准同上）(4)logn+(2logn)3=((logn)3)（1分，标准同上）(5)2n+n!+5en=(n!)（1分，标准同上）(6)3log2n+5logn=(n)（1分，标准同上）(7)2nlogn+lognn.=(nn)（1分，标准同上）b)f4f3f6f1f2f5f7(3分，每个错误位置扣0.5分，扣完为止）三、Pleaseanswerthefollowingquestions:(a)。四、Intheintervalschedulingproblem,wearegivennjobseachofwhichhasastartingtimesandafinishingtimef,andthegoalistofindamaximumsetofmutuallycompatiblejobs(twojobsarecompatibleiftheydon’toverlap).Pleaseanswerthefollowingquestions:(a)Designagreedyalgorithmfortheintervalschedulingproblemandprovethecorrectnessofit.(b)Assumethatwearegiven8jobswithstartingtimeandfinishingtime(s,t)being(0,2),(1,3),(8,9),(3,7),(7,8),(2,4）,(6,9),(4,5).Useyouralgorithmtofindasolutiontothisinstance.参考答案及评分标准：a）将所有工作（jobs）按其完成时间的先后进行排序；第3页共5页在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。证明用反证法，假设贪心算法不是最优导出矛盾，课件中有证明。证明思路大体正确即可给全分。b)答案是(0,2),(2,4),(4,5),(7,8),(8,9).五、Findaminimums-tcutinthefollowingdirectedgraph(thenumberbesidetheedgeisthecapacityoftheedge).Youarerequiredtogivethecomputationstepsandshowthecutanditssize.（9分）Sv5v4v3v1v2T1045556106333234参考答案：18.Sv5v4v3v1v2T(9,10)(4,4)(3,5)(5,5)(4,5)(6,6)(9,10)(6,6)(3,3)(0,3)(3,3)(0,2)(0,3)(2,4)评分标准：说明计算该图从s到T的最大流（2分）第4页共5页给出第一个和增广路径（2分）后面任意两个增广路径（1分一个）最后答案18和这个cut（3分，任给一个cut即可，最后结果18错误则不给分）六、Provethatifwecancheckifagraphhasacliqueofsizekinpolynomialtimethenwecanalsofindacliqueofsizekinpolynomialtime(acliqueofagraphisacompletesubgraph).参考答案及评分标准：设检查算法为B，我们构造一个找到解的算法A，该算法多项式次调用B。（1分）算法A的步骤和思想：依次从图中删除一个点，再调用算法B来检查是否还存在大小为k的clique，如果存在则直接从图中删除这个点（2分）；如果不存在，则将这个点放入解集，同时将图中所有不和这个点相邻的点全删除，再删除这个点本身，在剩余的图中再检查是否存在大小为k-1的clique。（3分）以上思想正确给全分，其它正确解法也给全分。七、WeknowthatfindingalongestpathinagraphisNP-hard.PleaseshowthatfindingalongestpaththatpassingthroughagivenvertexisalsoNP-hard.(6分)参考答案及评分标准：将最长路径问题归约到通过某个点的最长路径问题。思想如下：对于每个最长路径问题G，我们对图G中每个点得到一个通过这个点的最长路径问题，总共得到n（n为G中点的个数）个问题，如果后一个问题存在多项式算法，则前一个问题也存在。以上思想正确给全分，否则最多给3分。八、Inasupermarket,therearendifferenttypesofgoodsforsale.Eachtypeofgoods第5页共5页hasapriceof0iwdollarsandavalueof0iv.Nowyouareaskedtobuysomegoodssuchthat:foreachtypeofgoods,atmost2piecesarebought,thetotalvalueofthegoodsisatleastVandthetotalmoneyusedisminium.Useadynamicprogrammingalgorithmtosolvetheaboveproblem.(a)Pleasedefineyoursubproblem;(b)Givetherecurrencerelationbasedonyoursubproblems;(c)SolvethefollowinginstanceshowedinTable1byusingthebottom-upmethod,whereV=10.Youarerequiredtogivethecomputationsteps(thetableusedtostorethesolutionstothesubporblems).GoodsPriceValue121232384423595Table1参考答案及评分标准：（a）定义OPT（i，v）为只能选择前i种物品且价值达到v的最小花销；（b）建立递归关系式：0ifv0(,)nosolutionifi0andv0min(1,),(1,),2(1,2)otherwiseiiiiOPTivOPTivwOPTivvwOPTivv其中第一条边界条件1分，第二条1分，第三条递归关系式3分。（c）画出存储的表格，用自底而上的方法求解算出最后正确答案本题若忽略了每种物品有两个，则总分的基数分为10分，然后根据各步骤是否正确再参照以上标准进行评分。若直接当成背包问题来说，基数分为5分。