雨课堂学堂在线学堂云《Combinatorics and Algorithms Design（清华）》单元测试考核答案

第1题Inthevideo,ProfessorMaintroducedabriefhistoryofmathematics,fromthebasicmathematicsinthe16thcenturythroughanalysis,whichinvolvesadvancedmathematicsandlinearalgebra,allthewaytosettheoryandthemathematicsoftoday.Thesebasicallycorrespondwiththemathematicsfromhighschool,universityandpostgraduateeducation.Sowhichofstageofmathematicsareyouat?(thisquestiondoesnotcounttowardsyourgrade)AbasicmathematicsBanalysismathematicsCmodernmathematicsDmanyyearssincelasthavingstudiedmathematicsEelse正确答案：E第1题AT-shirtwillbeprintedwithamagicsquareofsize3.Howmanydifferentprintsarepossible?A1B2C6D8SufferingParchmentRoll--Homework第1题Inthehistoryofcombinatorics,whosemanuscriptonstomachionswasrecordedonparchment,andhasrecentlybeensolvedbyscientistsusingmoderntechnology?AEulerBLeibnizCArchimedesDGaloisTalkingAboutCombinatorialMathematics--IsYourP第1题Accordingtothevideo,whichpicturesofthebellowingcanbesetasthepasswordofandroidphone?(multiplechoices)ABCDEF正确答案：ACFBrute-forceEnumarationORAbstractConversion--Homework第1题CombinatorialMathematicsisanusefulclass,pleasechoosethereasonyoulearnit:ApersonalinterestincombinatoricsBtoprepareforpre-postgraduateexamsCforthehighschoolexamsDarequiredcourseinuniversityEtoentercompetitionsininformaticsFasjobinterviewpreparationGwanttogetacertificateofTsinghuaUniversityHcuriousaboutaMOOCtaughtbyafemaleprofessorfromTsinghuaIelse正确答案：IHomework1第1题Thefigurebelowshowsapartial4X4matrix，istheresomewayoffillinguptherestoftheomittedentriestoproduceamagicsquareofsize4usingnumbers1-16？AnoByes第2题Whichnumberbelow,ifusedasthemagicsum,allowsustoconstructmagicsquaresofsize3,usingonlynon-repeatedpositiveintegers?A12B23C18D34E20CombinatorialtripofaPingpongball--Permutation第1题Pleaseinputthespecificnumericalvalues：C(n,0)=____P(n,0)=____C(4,5)=____CombinatorialtripofaPingpongball--VariousPer第1题EightDiagram(Bagua)contains____typesofdifferentarrangementways.Pleasecalculatetheexactnumber第2题Thecoefficientnumberofa2b2c2intheexpandedequationof(2a+b+c)6is____.PleasecalculatetheexactnumberCombinatorialtripofaPingpongball--DifferentK第1题Combinationnumberofputting5ballsinto4boxes：1)5differentballs,4differentboxes,thenumberofballsinsideaboxisnotlimited,allowsemptybox,andcontainstotal____differentsolutions.【Pleasecalculatetheexactnumber】2)5identicalballs,4differentboxes,allowsemptybox,andcontainstotal____differentsolutions.【Pleasecalculatetheexactnumber】CombinatorialtripofaPingpongball--Permutation第1题PleasecalculatehowmanydifferentsongsaretherewhichcanbemadefromthechangeringingintheTrinityChurch?(12bells,eachringonceandindifferentorders)Pleasecalculatetheexactnumber,youmayuseacalculator____Homework2第1题InaGoldenFraudcardgame(ApolularpokergameinChina),useadeckofcardswhichhavejokersremoved,intotalthereare4shapeswith52cards,playerscompetetheirwin/losebythe3cardsinthehands,therearedifferentcardpatternsintherules:Leopard:3identicalcards,forexampleAAAor222.ShunJin(Flush):Straightwithidenticalshape,suchasSpade456orHeart789.GoldenFlower:Identicalshape,non-straight.Forexample,Spade368andDiamond145.Straight:Straightwithdifferentshape,forexample,Spade5Heart6Diamond7.ThesmalleststraightisA23.AndthelargeststraightisQKA.Pair:2identicalcards,suchas223and334.Random:3cardswhichdonotfallunderanycardpattern.Special：235withdifferentshapes.（Duetothatdifferentareamaycontaindifferentcardrules,itisnotbeingconsideredunderthisquestion）Then,ifweconsidertheprobabilitiesforthosepatterns,howtoorderthem?:ALeopard<Flush<GoldenFlower<Straight<Pair<RandomBLeopard<Flush<Straight<GoldenFlower<Pair<RandomCFlush<Leopard<GoldenFlower<Straight<Pair<RandomDLeopard>Flush>GoldenFlower>Straight>Pair>RandomEFlush<Leopard<Straight<GoldenFlower<Pair<Random正确答案：EGeneratingFunction&CountingRules--Homework第1题InG(x)=a0+a1x+a2x2+..+anxn+⋯,generatingfunctionisconcernedof:AVariablexBTargetfunctionG(x)CCoefficientai第2题Thedefinitionofgeneratingfunctionisraisedby?ABernoulliBLaplaceCEulerGeneratingFunction--SimpleApplicationOfGenerat第1题Thereare3piecesof1gramweight,4piecesof2gramsweight,2piecesof4gramsweight,howmanydifferentwaystoweighthevalueof6-gram?____正确答案：:4FerrersDiagram--Homework第1题Thepartitionnumberofpositiveintegernbeingpartitionedintoseveralpositiveintegers,inwhichthelargestintegerisk,equalstothepartitionnumberofpositiveintegernbeingpartitionedintokpositiveintegers.ATrueBFalseHomework3第1题GiventherecurrencerelationofFibonaccisequenceisF(n)=F(n-1)+F(n-2),setG(n)=F(2n),thentherecurrencerelationofG(n)is：G(n)=___G(n-1)+___G(n-2)+____G(n-3)Pleasechoosethecoefficientvalue：A1,1,1B1,1,0C3,1,0D3,1,1E3,-1,0F3,-1,1正确答案：E第2题GivengeneratingfunctionG(x)=3+78x1−3x−54x2,findthecorrespondingsequence{an}A{an}=7∗(−9)n+4∗6nB{an}=7∗9n−4∗6nC{an}=7∗9n−4∗(−6)nD{an}=7∗(−9)n−4∗6nE{an}=7∗(−9)n+4∗(−6)nF{an}=7∗(−9)n−4∗(−6)n第3题Positiveintegernispartitionedintoseveralpositiveintegers(1,2,3，…).Ifrepetitionisnotallowedanddoesnotconsiderthepartitionordering,thenthepartitionnumberisequaledtowhichofthefollowings?AThesolutionnumberforputtingnidenticalballsintonidenticalboxes(allowemptybox)BThenumberofpartitionstopartitionpositiveintegernintoevennumbers(2,4,6，…)withoutconsiderationoforderingandtherepetitionisallowed.CThenumberofpartitionstopartitionpositiveintegernintooddnumbers(1,3,5，…)withoutconsiderationoforderingandtherepetitionisallowed.DThesolutionnumberofputtingnidenticalballsintondistinctboxes(allowemptybox)FibonacciSequence--Homework第1题Whichequationofthefollowingisincorrect?AF12+F22+...+Fn2=FnFn+1BF1+F2+F3+...+Fn=Fn+2−1CF1+F3+F5+...+F2n−1=F2n+1LinearHomogeneousRecurrenceRelation--Applicatio第1题F1002−F101F99=____noticethatF1=F2=1正确答案：:-1LinearHomogeneousRecurrenceRelation--Homework第1题Therecurrencerelationofsequence{an}isan−2an−1=4an−2−5an−3sothecharacteristicequationisAx3−2x2+4x−5=0Bx3−2x2−4x+5=0C5x3−4x2−2x+1=0D−5x3+4x2−2x+1=0HomeworkOfWeek4第1题Thegeneratingfunctionofsequence{an}is11−x+x2,soit'srecurrencerelation(whenn≥2)is:Aan−an−1−an−2=0Ban+an−1−an−2=0Can+an−1+an−2=0Dan−an−1+an−2=0第2题Givenan=an−12an−23,a0=1,a1=2,thentheexpressionofanisA23n+3(−1)n4B22n−1C23n+(−1)n2D23n−(−1)n4MagicalSequences--CatalanNumbers第1题Therearesixpeopleinalibraryqueuingup,threeofthemwanttoreturnthebook“InterviewingSkills”,and3ofthemwanttoborrowthesamebook.Ifatthebeginning,allthebooksof“InterviewingSkills”areoutofstockinthelibrary,howmanywayscanthesepeoplelineupsothatthosethreepeoplecouldborrowthebooks?____正确答案：:180ExponentialGeneratingFunctions--Homework第1题Whatistheexponentialgeneratingfunctionofthesequence{1,k,k2,k3,...}AexB11−xCekxD11−kxMagicalSequences--Derangements第1题Thereare5fathersandeachfatherhasakidwithhim(10peopleintotal).TheyaretakingpartinaTVshowcalled“Dad,wherearewegoing?”Inthisprogramthereisagamecalled"ExchangetheFather",afatherhastotakeakidwhoisnothisownchild.Sohowmanydifferentgroupscanbemadewiththisconstraintinmind?____正确答案：:44MagicalSequences--StirlingNumbers第1题HowmanywayscanyoudividefourpeopleABCandDintotwogroups?____正确答案：:7MagicalSequences--HomeworkofWeek5第1题Placendistinctballsinmidenticalboxeswherenoboxisempty.ThedifferentwaystodosoisknownastheStirlingnumbersofthesecondkindS(n,m).SowhatdoesS(n,n-1)equal?AC(n,1)BC(n,2)CC(n,3)DC(n,4)第2题Using5numbers1，2，3，4,5tofillin1x6grids,eachgridisfilledwithonedigit.Ifthereareoddnumberofgridsthathave1writtenonthem,andanevennumberofgridswith2,thenhowmanyarrangementstherefor1*6grids?____正确答案：:3906Inclusion-ExclusionPrincipleAndPigeonholePrinc第1题Given|A|=10,|B|=7,|A∪B|=10,then|A∩B|=____正确答案：:7Inclusion-ExclusionPrincipleAndPigeonholePrinc第1题Isthefollowingstatementtrueorfalse?Of3000people,atleast9shouldhavethesamebirthday?AtureBfalseInclusion-ExclusionPrincipleAndPigeonholePrinc第1题Thereisapositiveinteger,dividedby2theremainderis1;dividedyby3theremainderis2,what'stheminimumnumbercansatisfythecondition?____正确答案：:5Inclusion-ExclusionPrincipleAndPigeonholePrinc第1题x1+x2+x3+x4=20,1≤x1≤6,0≤x2≤7,4≤x3≤8,2≤x4≤6,calculatethenumberofintegralsolutions.____正确答案：:96第2题Oftheintegernumbersfrom1to10000,howmanyareneitherasquarenoracubeofaninteger？____正确答案：:9883Q:MajorityElement第1题Givenanarbitraryinputarray,thecandidatefoundbyMooreandBoyer'sincrementalalgorithmisforsurethemajorityelement.Q:AlgorithmComplexity第1题WemeasuretherunningtimeofalgorithmsusingRAMmodel.AlgorithmAandBbothhave

nbasicoperations,butamongthoseoperationsalgorithmAcontainsmorememoryaccesswhichistimeconsumingonmostcomputersintherealworld.ThereforeundertheRAMmodel,wecansaythatalgorithmAhaslongerrunningtimethanB.Q:AsymptoticAnalysis第1题If

f(n)=Ω(g(n))then

g(n)=O(f(n))HomeworkofWeek7第1题FindthemajorityelementinthearraybelowbyexploitingMooreandBoyer'sincrementalalgorithm.Whatisthevalueofcountwhenthealgorithmterminates?Inputarray:XYXXZYXZXXYA0B1C2第2题Wecanprove

f(n)=O(g(n))tobefalsebygivingaspecificpairof

(n,c)

suchthat

f(n)>cg(n).第3题Forthefunctions,

nkandcn,whatistheasymptoticrelationshipbetweenthesefunctions?Assumethat

k≥1and

c>1

areconstants.Ankis

O(cn)Bnk

is

Ω(cn)Cnk

is

Θ(cn)第4题Thestatement,"TherunningtimeofalgorithmAisatleastO(n2)",ismeaninglessbecauseAThephrase"atleast"ismeaninglesswhendiscussingtherunningtimeofanalgorithm.BThephrase"atleast"andthebig-Onotationtogetherleadtoacontradiction.COnlythe

Θnotationismeaningfulwhendiscussingtherunningtimeofanalgorithm.Q:LoopInvariant第1题Aloopinvariantis:AAsetofvariableswhosevalueswon'tchangealltheway.BApropositionwhichisalwaystrueabouttheproblem,regardlessofwhattheactualalgorithmis.CApropositionwhichiskepttrueatthebeginningofeveryiterationandalsoattheendoftheloop.Q:InsertionSort第1题Whatifwechangedtheloopinvariantofinsertionsortinto:"Atthestartofeachiteration,A[1..j-1]isinsortedorder"?AThenewloopinvariantwouldnotremaintrueforeachinteration.BThenewloopinvariantwouldnotprovethecorrectnessofthealgorithm.CThiswouldmakenodifference.Q:2-ColorDutchNationalFlagProblem第1题Considerthealgorithmshownintheslideswhichsolvesthe2-colorDNFproblem.Ifwewanttokeeptherelativeorderwithinelementsofthesamecolor,isthealgorithmabletosatisfythisrequirement?AOnlywithinredelements.BOnlywithinblueelements.CBothsatisfied.DBothunsatisfied.HomeworkofWeek8第1题Whatisthebest-caseandworst-caserunningtimeofinsertionsort?AΘ(n)and

Θ(n2)BΘ(n2)

and

Θ(n3)CBoth

Θ(n2)第2题Bubblesortisalsoapopularsortingalgorithm.Itworksbyrepeatedlyswappingadjacentelementsthatareoutoforder.BUBBLESORT(A)

fori=1toA.length-1forj=A.lengthdowntoi+1ifA[j]<A[j-1]

exchangeA[j]withA[j-1]Comparedasymptoticallytoinsertionsort,bubblesort:Ahasshorterworst-caserunningtime.Bhasthesameworst-caserunningtime.Chasshorterbest-caserunningtime.Dhaslongerbest-caserunningtime.正确答案：BD第3题Whichofthefollowingstatementsarecorrectaboutinsertionsort?Notes:1.Asortingalgorithmissaidtobestableiftwoobjectswithequalkeysappearinthesameorderinsortedoutputastheyappearintheinputarraytobesorted.2.Auxiliaryspaceofanalgorithmistheextramemoryitconsumesapartfromtheinputandtheoutput.AInsertionsortisstable.BInsertionsortisunstable.CInsertionsortrequires

O(n)auxiliaryspace.DInsertionsortrequires

O(1)auxiliaryspace.正确答案：AD第4题LetA[1..n]beanarrayof

ndistinctnumbers.If

i<jandA[i]>A[j],thenthepair

(i,j)iscalledaninversionofA.Whatistherelationshipbetweentherunningtimeofinsertionsortandthenumberofinversionsintheinputarray?ANotrelated.BTherunningtimeofinsertionsortisalinearfunctionofthenumberofinversions.

CTherunnningtimeofinsertionsortisaquadraticfunctionofthenumberofinversions.Q:MergeSort第1题Merge2sortedlistsofsize

mandn,respectively.Thenumberofcomparisonsneededintheworstcasebythemergeprocedurewillbe:Am+nBm+n−1Cmax(m,n)Dmin(m,n)Q:Select:Partition第1题WhatistheresultafterapplyingthePARTITIONproceduretothearraybelow?Inputarray:74289510A54279810B42579810C54278910Q:Select:LinearTime第1题Wehaveknownthattheworst-caserunningtimeofinsertionsortisΘ(n2).Insertionsortisappliedtoevery5-elementgroupatline2inLinear-timeSELECT.WhydowesaythatthislinecontributesrunningtimeofΘ(n)?ABecausehereweusethebest-caserunningtimeofinsertionsort,

Θ(n).BBecause5isaconstantsotherunningtimeofinsertionsortona5-elementgroupisconsideredtobeΘ(1).CTheslidesmakeanerrorhere.Q:SubstitutionMethod第1题UsethesubstitutionmethodtosolvetherecurrenceT(n)=2T(n/2)+n:Assumethat

T(k)≤cklgkforsomesuitablelarge

candk<n.Finishtheproofyourself.Whatcondition

cshouldmeetiftheproofistohold?Ac≥0Bc≥1Cc≤1Q:RecursionTreeMethod第1题ConsidertherecurrenceT(n)=T(n/3)+T(2n/3)+O(n).Whichofthefollowingisclosesttotheheightoftherecursiontree?AlgnBlog3nClog32nQ:TheMasterMethod第1题Solvetherecurrence

T(n)=7T(n/3)+n2usingthemastermethod.Whichofthefollowingiscorrect?AT(n)=Θ(nlog37)BT(n)=Θ(nlog37lgn)CT(n)=Θ(n2)DThemastermethoddoesn'tapplybecausetheregularityconditionisnotsatisfied.HomeworkofWeek9第1题WhatvaluedoesthePARTITIONproceduregivenintheslidereturnwhenallelementsinthearray

A[p..r]havethesamevalue?ApBrCfloor((p+r)/2)第2题Trytosolvetherecurrence

T(n)=3T(n/3)+nlgnwiththemastermethodandchoosethecorrectanswer.AT(n)=Θ(n)BT(n)=Θ(nlgn)CT(n)=Θ(nlgnlgn)DThemastermethoddoesnotapply.第3题Usingthemastermethod,wecanshowthatthesolutiontotherecurrence

T(n)=4T(n/2)+nisT(n)=Θ(n2).Wecanalsoproveitbysubstitutionmethod.Whichofthefollowingshouldbeaproperassumptiontoholdourproof?AT(n)≤cn2BT(n)≤cn2−dCT(n)≤cn2−n第4题UsearecursiontreetogiveanasymptoticallytightsolutiontotherecurrenceT(n)=T(n−a)+T(a)+cn,where

a≥1and

c>0areconstants.AΘ(n)BΘ(nlgn)CΘ(n2)DΘ(n2lgn)Q:IndicatorRandomVariable第1题Xand

Yarerandomvariables.Underwhatcircumstancesdoes

E[X+Y]=E[X]+E[Y]hold?AOnlywhen

Xand

Yareindependent.BOnlywhen

X

and

Yarecorrelated.CTheequationalwaysholds.Q:HiringProblem第1题InHIRE-ASSISTANT,assumingthatthecandidatesarepresentedinarandomorder,whatistheprobabilitythatyouhireexactlyonetime?Whatistheprobabilityyouhireexactly

ntimes?A1n!,

1n!B1n,

1nC1n,

1n!D1n!,

1nQ:RandomizedAlgorihtm第1题Arandomizedintegersortingalgorithmshouldbelongto:ALasVegasBMonteCarloQ:RandomizedSelect第1题WhatistheworstcaserunningtimeofRANDOMIZED-SELECT?Suchworstcaseisdeterminedby...?AO(n);thedistributionoftheinputBO(n2);thedistributionoftheinputCO(n);theoutputofrandom-numbergeneratorDO(n2);theoutputofrandom-numbergeneratorHomeworkofWeek10第1题Useindicatorrandomvariablestocomputetheexpectedvalueofthesumof

ndice.A6nB3.5nC3nDn第2题Useindicatorrandomvariablestosolvethefollowingproblem,whichisknownasthehat-checkproblem.Eachof

ncustomersgivesahattoahat-checkpersonatarestaurant.Thehat-checkpersongivesthehatsbacktothecustomersinarandomorder.Whatistheexpectednumberofcustomerswhogetbacktheirhat?A12B1C1nDn2第3题WhenRANDOMIZED-SELECTruns,howmanycallsaremadetotherandom-numbergeneratorRANDOMintheworstcase?Whataboutinthebestcase?AΘ(n);

Θ(1)BΘ(n2);

Θ(1)CΘ(n);

Θ(n)DΘ(n2);

第4题Howmanypeopleatleastmusttherebeinaroom,suchthattheprobabilitythatsomeonehasthesamebirthdayasyoudoisnotsmallerthan

12?A76B183C253D314Q:MaximumSubarray第1题WhatistherunningtimeofMaximum-Subarray(th