1IntroductionofAlgorithm1

/4

單選題

(1分)Thereare3mennamedBob,JackandDavid,and3womennamedAnna,GraceandAlice.Theirpreferencelistsareshowedasfollows.Whichisastablematchingamongthefollowingmatchings?ABob-Grace,Jack-Anna,David-AliceBBob-Grace,Jack-Alice,David-AnnaCBob-Alice,Jack-Grace,David-Anna

答案A2/4單選題(1分)Giventhesame3menand3womenasexercise1.WhichoneistheresultofGale-Shapleyalgorithm?Bob-Grace,Jack-Anna,David-AliceBob-Alice,Jack-Grace,David-AnnaBob-Anna,Jack-Grace,David-Alice答案C3/4單選題(1分)Gale-Shapleyalgorithmfinds______.aperfectmatchingwithoutstabilitypossibledifferentassignmentsamongallexecutionstheman-optimalassignmentwhichisastablematching答案C4/4單選題(1分)Giventhesame3menand3womenasexercise1.WhichofthefollowingmisrepresentationcanmakeGraceobtainbetterpartnerforherselfinthereturnedmatching?Gracelies"IpreferDavidtoJack"Gracelies"IpreferJacktoBob"Gracelies"IpreferDavidtoBob"答案A2BasicsofAlgorithmAnalysis1/4單選題(1分)is_____.答案C2/4單選題(1分)Forevery,_____.答案B3/4單選題(1分)and,then_____.答案B4/4單選題(1分)Therearenumbers.Thetaskistocompute,,where.Therunningtimeofthefollowingalgorithmis_____.答案C3Graph

1

/4

單選題

(1分)Thereisanundirectedgraph

G=(V,E)with

V={1,2,3,4}

and

E={(1,2),(1,3),(2,4),(3,4)}

.Whichoneistheadjacencymatrixofit?AABBCC

答案A2/4單選題(1分)AgraphGisbipartiteiff_____.itcontainsnoevenlengthcycleitcontainsnooddlengthcycleitcontainsnocycle答案B3/4單選題(1分)Thereisadirectedgraphwithnodesandedges.Canonedetermineifisstronglyconnectedintime?YesNoDependingonand答案A4/4單選題(1分)Howmanytopologicalorderingsdoesithaveinthefollowinggraph?A1B2C3答案C4GreedyAlgorithms

1

/5

填空題

(1分)Theminimumspanningtreeofthefollowinggraphshouldcost____

答案["40"]

2

/5

填空題

(1分)TheshortestpathfromnodeAtonodeBinthefollowinggraphshouldcost

____

答案["19"]

3

/5

判斷題

(1分)Decidewhetheryouthinkthefollowingstatementsaretrueorfalse.Let

G

beanarbitraryconnected,undirectedgraphwithadistinctcostoneveryedge.Suppose

e

isthecheapestedgein

G.

Then,thereisaminimumspanningtreeof

G

thatcontainstheedge

e.

答案√

4

/5

判斷題

(1分)Underthesameconditionasexercise3.Then,

thereisnotaminimumspanningtreeof

G

thatdoesn’tcontaintheedge

e.

答案√5DivideandConquer

1

/4

單選題

(1分)Analgorithmhasrunningtime

T(n),whichsatisfies

T(n)=4T(n/4)+O(n).So,itsrunningtimeis_____.AO(nlog?n)BO(n)CO(n2)DO(n2log?n)

答案A

2

/4

單選題

(1分)Analgorithmhasrunningtime

T(n),whichsatisfies

T(n)≤T(n/2)+c

and

T(2)≤c.Thenitsrunningtimeis_____.AO(nlog?n)BO(n)CO(1)DO(log?n)

答案D

3

/4

單選題

(1分)InMergesortalgorithm,wedividetheinputintothreepiecesofequalsize(replacetwopieces);solvethethreesubproblemsonthesepiecesseparatelybyrecursion;andthencombinethethreeresultsintoanoverallsolution,spendingonlylineartimefortheinitialdivisionandfinalrecombining.Then,therunningtimeoftheabovealgorithmis_____.AO(nlog2?3log?n)BO(n2log?n)CO(nlog2?3)DO(nlog?n)

答案D

4

/4

單選題

(1分)Therunningtimeofthefollowingalgorithmforintegermultiplicationis_____.AO(n)BO(nlog?n)CO(nlog?3)DO(n2)

答案D6DynamicProgramming

1

/4

填空題

(1分)Thereisastairswithaheightof10steps.Youcanclimbstairsonlybytwoorthreesteps.

Soyoucangoby

____

differentkindsofways.

答案["7"]

2

/4

填空題

(1分)Thereare6objectswithvalues1,5,10,15,22,25,30.Aknapsackhascapacityofvalue69.

Ifwefillknapsacksoastomaximizetotalvalue,wecangetmaximumtotalvalue

____.

答案["68"]

3

/4

填空題

(1分)Usingdynamicprogrammingtosolvethefollowingintegerlinearprogramming,theobjectivevalueis____.

答案["50"]

4

/4

填空題

(1分)Ifyouonlycangouporrightinthebelowgraph，thenstartingfrompointAandendingtopointBshouldhave

____

differentways.

答案["135"]7NetworkFlow1

/4

判斷題

(1分)Decidewhetheryouthinkthefollowingstatementistrueorfalse.

Let

G

beanarbitraryflownetwork,withasource

s,asink

t,andapositiveintegercapacity

ce

oneveryedge

e

.If

f

isamaximum

s?t

flowin

G

,then

f

saturateseveryedgeoutof

s

withflow(i.e.,foralledges

eoutof

s,wehavef(e)=ce).

答案×2

/4

判斷題

(1分)Decidewhetheryouthinkthefollowingstatementistrueorfalse.

Let

G

beanarbitraryflownetwork,withasource

s,asink

t,andapositiveintegercapacity

ce

oneveryedge

e.Let

(A,B)

beamimimum

s?t

cutwithrespecttothesecapacities

{ce:e∈E}.Nowsupposeweadd1toeverycapacity,then

(A,B)

isstillaminimum

s?t

cutwithrespecttothesenewcapacities

{1+ce:e∈E}.

答案×3

/4

判斷題

(1分)Decidewhetheryouthinkthefollowingstatementistrueorfalse.G

isaflownetworkwithamaximumflowwhichhasavalueof

v(f).Considertheflownetwork

G′

obtainedbyadding

1

tothecapacityofeveryedge.Thevalueofthemaximumflowin

G′

is

v(f)+1

.

答案×4

/4

填空題

(2分)Thebelowfigureshowsaflownetworkonwhichan

s?t

flowhasbeencomputed.Thecapacityofeachedgeappearsasalabelnexttotheedge,andthenumbersinboxesgivetheamountofflowsentoneachedge.(Edgeswithoutboxednumbershavenoflowbeingsentonthem.)

a)Thevalueofthisflowis

____.b)Thevalueofthemaximum

s?t

flowinthisgraphis

____.

答案["10"]2答案["11"]8NPandComputationalIntractability1/4判斷題(1分)Forproblem,analgorithmwithrunningtimealwaysfasterthantheonewithrunningtimeforallinstances.答案×2/4單選題(1分)Ifwewanttoproofproblemcanbesolvedinpolynomial-timeviaareductionfromproblem,whichofthefollowingstatementisNOTnecessary?Arbitraryinstancesofproblemcanbesolvedinpolynomial-time.Arbitraryinstancesofproblemcanbesolvedusingpolynomialnumberofcallstooraclethatsolvesproblem.Arbitraryinstancesofproblemcanbesolvedusingpolynomialnumberofcallstooraclethatsolvesproblem.答案B3/4單選題(1分)Ifwehaveamagicmachinethatcansolve3-SATprobleminunittime.WhichofthefollowingproblemcanNOTbesolveifweonlyusethismachinepolynomialtimes?(AssumeP≠NP)INDEPENDENT-SETVERTEX-COVERPRIMESHALTINGPROBLEM答案D4/4單選題(1分)Assumethateachofthefollowingsetsarenotequal.Whichoneisthebiggestset?PNPco-NPEXP答案D9ApproximationAlgorithms1/4判斷題(1分)Forproblem,a2-approximationalgorithmisalsoa3-approximationalgorithm.答案√2/4單選題(1分)Forproblem,nowwegeta3-approximationalgorithm.WhichofthefollowingstatementisTRUE?Thereisno-approximationalgorithmforforany.ProblemisNP-hard.Thealgorithmcangiveasolutionforanyinstanceofproblemwithinratio3oftrueoptimum.Problemcanbesolvedinpolynomialtime.答案C3/4單選題(1分)TheLPTrulegivesan-approximationalgorithmforloadbalancing.Whichofthefollowingfactorsisthebestfor.23/24/35/4答案C4/4判斷題(1分)Inknapsackproblem,iftheweightofeachitemisintegerandlessthanagivenconstant.Wecansolveitinpolynomialtime.答案√10LocalSearch1/4判斷題(1分)Alllocalsearchalgorithmscanstopinfinitesteps.答案×2/4單選題(1分)AssumetherearenodesinVERTEX-COVER.Thelocalsearchalgorithmgiveninthischaptercangiveasolutionwithinratio_____oftrueoptimumintheworst-case.23n-1n答案C3/4單選題(1分)Thesingle-flipneighborhoodalgorithmforMaximumCutwithnodesrunsatmost_____steps.答案D4/4判斷題(1分)Thebestresponsedynamicsalgorithmfork-agentmulticastroutingproblemalwaysfindsthebestNashequilibrium.答案×11RandomizedAlgorithms1/3單選題(1分)Thereare8statementsandwehavenoknowledgeaboutthem.Werandomlyguessthemtrueorfalse.Sothepossibilitythatwecorrectlyguess6statementis_____.1/2569/25637/25693/256答案C2/3判斷題(1分)Foranyinstanceof3-SAT,thereexistsatruthassignmentthatsatisfiesatleasta7/8fractionofallclauses.答案√3/3單選題(1分)GivenaMAX3-SATformulawithkclauses,weshowthattheexpectednumberofclausessatisfiedbyarandomassignmentis7k/8.Considerarandomassignmentforformula,theexpectednumberofclausessatisfiedis_____.7k/167k/87k/47k/2答案CExam1/11單選題(1分)Gale-Shapleyalgorithmfindsastablematchingin_____time.答案C2/11單選題(1分)is_____;is_____;is_____.答案A3/11單選題(1分)Abinarytreeisarootedtreeinwhicheachnodehasatmosttwochildren.Whatistherelationbetweenthenumberofnodeswithtwochildrenandthenumberofleaves(thenodeswithoutchildren)inabinarytree?答案C4/11單選題(1分)Supposewearegivenaninstanceoftheminmumspanningtreeproblemonagraph,withedgecoststhatareallpositiveanddistinct.Letbeaminimumspanningtreeforthisinstance.Nowsupposewereplaceeachedgecostbyitssquare,therebycreatinganewinstanceoftheproblemwiththesamegraphbutdifferentcosts.Decidewhetheryouthinkthefollowingstatementistrueorfalse.muststillbeaminimumspanningtreeforthisnewinstance.正確錯誤答案A5/11單選題(1分)Ifanalgorithmhasrunningtime,th