资源描述：
《电子科技大学研究生算法设计与分析拟考题及答案评分细则(3)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、•、PleaseanswerTorFforeachofthefollowingstatementstoindicatewhetherthestatementistrueorfalse1.Theknapsackproblemcanbesolvedinpolynomialtimebyusingdynamicprogramming.2.SomeproblemsinNPcanbesolvedinpolynomialtime.(T)3.ToshowaproblemisNP-hard，wecanreducei
2、ttoawell-knownNP-Completeproblem.(F)4.Inanundirectedgraph，thevalueofthemaximumflowbetweentwoverticesisequivalenttothevalueoftheminimumcutbetweenthem.(T)5.2w=O((V^),og/,).二、Arrangethefollowingfunctionsinascendingasymptoticorderofgrowthrate:/i(Z7)=n,ogM
3、+5,00nlogn,/2(zt)=2,o8rt+log,ogf⑽=4^，人(n)=2"+n2,/s(n)=(2+logn)参考答案：f2,f3，fl，f4，f5三、Pleaseanswerthefollowingquestions:(a)Whatarethemainstepsofdesigningadynamicprogrammingalgorithm?参考答案：1.定义子问题；2根据子问题建立递归关系式；3用自底而上的方式求解(建立储存表)。(b)Whatarethemainstepsof
4、provingtheNP-Completenessofaproblem?参考答案：1.证明该问题属于NP;2.选一个已知的NPC问题B;3.将问题B归约到该问题上。四、TheTravelingsalesmanproblem(TSP)isdefinedasfollows:Givenagraph,thetaskistofindashortestpossibleroutethatvisitseachvertexexactlyonceandreturnstotheoriginvertex.Forthegr
5、aphshowninFig.1，(a)findasolutiontoTSP((therouteisstartingfromAandbacktoA);(b)findalongestdirectedcyclethatcontainsvertexA.参考答案：I(a)A-〉D-〉C-〉B-〉A35+12+30+20=97(b)A-〉C-〉B-〉D-〉A42+30+34+35=141五、DesignanalgorithmforthefollowingIntervalSchedulingproblem:Th
6、erearenjobseachofwhichhasastartingtimesandafinishingtimef.Twojobsarecompatibleiftheydon’toverlap.Thegoaloftheproblemistofindamaximumsetofmutuallycompatiblejobs.参考答案及评分标准：将所有工作(Interval)按其完成时间的先后进行排序；在排好序的序列中用弹性法则，以此选取最小完成时间且和前面已选工作不冲突的工作。六、Findaminimu
7、ms-tcutinthefollowinggraph(thenumberbesidetheedgeisthecapacityoftheedge).Youarerequiredtogivethecomputationstepsandshowthesizeofthecut.参考答案：35.宥两个解：｛S,4,3,8｝和｛S,1,2,3,4，5,6，7,8，9｝评分标准：说明计算该图从s到t的最大流给出第一个增广连后而任意两个增广连(最后答案35和这个cut七、Provethatifwecancheck
8、ifagraphhasapathoflengthkinpolynomialtimethenwecanalsofindapathoflengthkinpolynomialtime.参考答案及评分标准：依次从陶屮删除一条边，然后检查是杏还存在长度为k的路径，如果存在则直接删除，如果不存在则保留该边。如此卜*去，最后图只剩下k条边。以上思想正确给全分。八、AHamiltoniancycleinagraphisacyclethatcontainseachvertex.TheHamilton
