算法分析算法复习题（中英文）

本文格式为Word版，下载可任意编辑——算法分析算法复习题（中英文）of

indicesofXsuchthatforallj=1,2,...,k,wehavexij=zj.

LetX=1.F19.Forarrayoflengthn,allelementsinrangeA[?n/2?+1..n]areheaps.T20.Thetighterboundoftherunningtimetobuildamax-heapfromanunorderedarrayisn’tinlineartime.F

21.ThecalltoBuildHeap()takesO(n)time,Eachofthen-1callstoHeapify()takesO(lgn)time,ThusthetotaltimetakenbyHeapSort()=O(n)+(n-1)O(lgn)=O(n)+O(nlgn)=O(nlgn).T

22.QuickSortisadynamicprogrammingalgorithm.ThearrayA[p..r]ispartitionedintotwonon-emptysubarraysA[p..q]andA[q+1..r],AllelementsinA[p..q]arelessthanallelementsinA[q+1..r],thesubarraysarerecursivelysortedbycallstoquicksort.F

23.Assumethatwehaveaconnected,undirectedgraphG=(V,E)withaweightfunctionw:E→R,andwewishtofindaminimumspanningtreeforG.BothKruskalandPrimalgorithmsuseadynamicprogrammingapproachtotheproblem.F

24.Acut(S,V-S)ofanundirectedgraphG=(V,E)isapartitionofE.F25.Anedgeisalightedgecrossingacutifitsweightisthemaximumofanyedgecrossingthecut.F

26.Kruskal'salgorithmusesadisjoint-setdatastructuretomaintainseveraldisjointsetsofelements.T

27.Optimal-substructurepropertyisahallmarkoftheapplicabilityofbothdynamicprogramming.T

28.Dijkstra'salgorithmisadynamicprogrammingalgorithm.F

29.Floyd-Warshallalgorithm,whichfindsshortestpathsbetweenallpairsofvertices,isagreedyalgorithm.F

30.Givenaweighted,directedgraphG=(V,E)withweightfunctionw:E→R,letp=

ofmatrices,wherefori=1，2…，n,matrixAihasdimension

Pi-1?Pi,fullyparenthesizetheproductA1,A2,…,Aninawaythatminimizesthenumberofscalarmultiplication.WepickasoursubproblemstheproblemsofdeterminingtheminimumcostofaparenthesizationofAiAi+1Ajfor1≤i≤j≤n.Letm[i,j]betheminimumnumberofscalarmultiplicationsneededtocomputethematrixAi..j;forthefullproblem,thecostofacheapestwaytocomputeA1..nwouldthusbem[1,n].Canyoudefinem[i,j]recursively?Findanoptimalparenthesizationofamatrix-chainproductwhosesequenceofdimensionsis

十一Inthelongest-common-subsequence(LCS)problem,wearegiventwosequencesX=andY=andwishtofindamaximum-lengthcommonsubsequenceofXandY.PleasewriteitsrecursiveformulaanddetermineanLSCofSequenceS1=ACTGATCGandsequenceS2=CATGC.Pleasefillintheblanksinthetablebelow.

CATGCACTGATCG

十二Proof:AnycomparisonsortalgorithmrequiresΩ(nlgn)comparisonsintheworstcase.

Howmanyleavesdoesthetreehave?（叶节点的数目）

–Atleastn!(eachofthen!permutationsiftheinputappearsassomeleaf)?n!≤l（至少n!个，排列）–Atmost2hleaves（引理，至多2h个）?n!≤l≤2h?

h≥lg(n!)=?(nlgn)

十三Proof:Subpathsofshortestpathsareshortestpaths.

Givenaweighted,directedgraphG=(V,E)withweightfunctionw:E→R,letp=beashortestpathfromvertexv1tovertexvkand,foranyiandjsuchthat1≤i≤j≤k,letpij=bethesubpathofpfromvertexvitovertexvj.Then,pijisashortestpathfromvitovj.

十四Proof:TheworstcaserunningtimeofquicksortisΘ(n2)

十五ComputeshortestpathswithmatrixmultiplicationandtheFloyd-Warshallalgorithmforthefollowinggraph.

十六WritetheMAX-Heapify()proceduretoformanipulatingmax-heaps.AndanalyzetherunningtimeofMAX-Heapify().

三（10分)1CountingSort(A,B,k)2fori=1tok3C[i]=0;4forj=1ton5C[A[j]]+=1;6fori=2tok7C[i]=C[i]+C[i-1];8forj=ndownto19B[C[A[j]]]=A[j];10C[A[j]]-=1;四

算法描述3分

Thebest-caserunningtimeisT(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)=(c1+c2+c4+c5+c8)n-(c2+c4+c5+c8).Thisrunningtimecanbeexpressedasan+bforconstantsaandbthatdependonthestatementcostsci;itisthusalinearfunctionofn.

Thisworst-caserunningtimecanbeexpressedasan2+bn+cforconstantsa,b,andcthatagaindependonthestatementcostsci;itisthusaquadraticfunctionofn.分析2分

算法描述2分

Θ(1)ifn=1

T(n)=

2T(n/2)+Θ(n)ifn>1.

递归方程和求解3分五

7RAND-SELECT(A,p,r,i)(5分)ifp=rthenreturnA[p]

q←RAND-PARTITION(A,p,r)k←q–p+1

ifi=kthenreturnA[q]ifi

递归方程4分

CATGC000000A001111C011112T011222G011233A011233T011234C011234G

最长公共子序列长度为4AGTC求解过程6分

十二Fromtheprecedingdiscussion,itsufficestodeterminetheheightofadecisiontreeinwhicheachpermutationappearsasareachableleaf.Consideradecisiontreeofheighthwithlreachableleavescorrespondingtoacomparisonsortonnelements.

从前面探讨,它可以确定一个决策树的高度,每个排列显示为一个可到达的叶子。考虑一个决策树的高度h和l可及的叶子在n个元素对应于一种比较。

Becauseeachofthen!permutationsoftheinputappearsassomeleaf,

由于每个n!排列的输入出现一些叶子,

wehaven!≤l.

Sinceabinarytreeofheighthhasnomorethan2hleaves,由于一个二叉树的高度

h没有超过2h叶子

wehave（分析5分）n!≤l≤2h,

which,bytakin