誠信應考,考試作弊將帶來嚴重后果華南理工大學期末考試DATASTRUCTUREB試卷注意事項1考前請將密封線內(nèi)填寫清楚；所有答案請答題紙上；2考試形式閉卷；本試卷共十大題，滿分100分，考試時間120分鐘。1SELECTTHECORRECTCHOICE20SCORES,EACH2SCORES1ANALGORITHMMUSTBEORDOALLOFTHEFOLLOWINGEXCEPTBACORRECTBINFINITECNOAMBIGUOUSDCONCRETESTEPS2PICKTHEGROWTHRATETHATCORRESPONDSTOTHEMOSTEFFICIENTALGORITHMASNGETSLARGEDA4N3B2NCND30N2LOGN3IFADATAELEMENTREQUIRES8BYTESANDAPOINTERREQUIRES4BYTES,THENALINKEDLISTREPRESENTATIONWILLBEMORESPACEEFFICIENTTHANASTANDARDARRAYREPRESENTATIONWHENTHEFRACTIONOFNONNULLELEMENTSISLESSTHANABOUTBA1/4B2/3C3/5D3/44WHICHISTHEREALIZATIONOFADATATYPEASASOFTWARECOMPONENTAAANABSTRACTDATATYPEBAREALDATATYPECATYPEDADATASTRUCTURE5WEUSETHEPARENTPOINTERREPRESENTATIONFORGENERALTREESTOSOLVEBPROBLEMASHORTESTPATHSBGENERALTREETRAVERSALCEQUIVALENCECLASSESDEXACTMATCHQUERY6THEMOSTEFFECTIVEWAYTOREDUCETHETIMEREQUIREDBYADISKBASEDPROGRAMISTODAIMPROVETHEBASICOPERATIONSBREDUCEMAINMEMORYUSECELIMINATETHERECURSIVECALLSDMINIMIZETHENUMBEROFDISKACCESSES7INTHEHASHFUNCTION,COLLISIONREFERSTOBATWOELEMENTSHAVETHESAMESEQUENCENUMBERBDIFFERENTKEYSAREMAPPEDTOTHESAMEADDRESSOFHASHTABLECTWORECORDSHAVETHESAMEKEYDDATAELEMENTSARETOOMUCH8GIVENANARRAYASAMNSUPPOSEDTHATA00ISLOCATEDAT64410ANDA22ISSTOREDAT67610,ANDEVERYELEMENTOCCUPIESONESPACE“10”MEANSTHATTHENUMBERISPRESENTEDINDECIMALSTHENTHEELEMENTA3310ISATPOSITIONAA692B695C650D7089TREEINDEXINGMETHODSAREMEANTTOOVERCOMEWHATDEFICIENCYINHASHINGDAINABILITYTOHANDLERANGEQUERIESBINABILITYTOMAXIMUMQUERIES_姓名學號學院專業(yè)座位號密封線內(nèi)不答題密封線線CINABILITYTOHANDLEQUERIESINKEYORDERDALLOFABOVE10ASSUMETHATWEHAVEEIGHTRECORDS,WITHKEYVALUESATOH,ANDTHATTHEYAREINITIALLYPLACEDINALPHABETICALORDERNOW,CONSIDERTHERESULTOFAPPLYINGTHEFOLLOWINGACCESSPATTERNFDFGEGFADFGEIFTHELISTISORGANIZEDBYTHETRANSPOSEHEURISTIC,THENTHEFINALLISTWILLBEBAAFCDHGEBBABFDGECHCABFGDCEHDAHFDGECB2FILLTHEBLANKWITHCORRECTCCODES18SCORES1GIVENANARRAYSTORINGINTEGERSORDEREDBYVALUE,MODIFYTHEBINARYSEARCHROUTINESTORETURNTHEPOSITIONOFTHEFIRSTINTEGERWITHTHELEASTVALUEGREATERTHANKWHENKITSELFDOESNOTAPPEARINTHEARRAYRETURNERRORIFTHEGREATESTVALUEINTHEARRAYISLESSTHANK14SCORES/RETURNPOSITIONOFLESTELEMENTKINTNEWBINARYINTARRAY,INTN,INTKINTL1INTRN/LANDRBEYONDARRAYBOUNDSWHILEL1R/STOPWHENLANDRMEET_/CHECKMIDDLEOFREMAININGSUBARRAYIFKARRAYI_LLR/2_/INRIGHTHALF/KISNOTINARRAYORTHEGREATESTVALUEISLESSTHANKIF_RN_THENRETURN_I_/THEFIRSTINTEGERWITHTHELEASTVALUEGREATERTHANK/WHENKITSELFDOESNOTAPPEARINTHEARRAYELSERETURN_ERROR_/THEGREATESTVALUEINTHEARRAYISLESSTHANK2THEHEIGHTOFTHESHORTESTTREEANDTHETALLESTTREEWITHBOTHNNODESISRESPECTIVELY_2ORNN2_AND_N_,SUPPOSETHATTHEHEIGHTOFTHEONENODETREEIS14SCORES3PLEASECALCULATETHENUMBEROFBINARYTREESINDIFFERENTSHAPEWITH3NODESINTOTAL,AND4NODES4SCORES5144SHOWTHEMINHEAPTHATRESULTSFROMRUNNINGBUILDHEAPONTHEFOLLOWINGVALUESSTOREDINANARRAY4,2,5,8,3,6,10,146SCORES5TRACEBYHANDTHEEXECUTIONOFQUICKSORTALGORITHMONTHEARRAYINTA44,77,55,99,66,33,22,88,79THEPIVOTIS66INTHEFIRSTPASS,THESECONDIS55AND88,THETHIRDIS33AND77,THEFOURIS22,ANDSOONTILLTHEALGORITHMISFINISHED8SCORES6BUILDTHEHUFFMANCODINGTREEANDDETERMINETHECODESFORTHEFOLLOWINGSETOFLETTERSANDWEIGHTSABCDEFGH525361110364DRAWTHEHUFFMANCODINGTREEANDGIVETHEHUFFMANCODEFOREACHLETTERSWHATISTHEEXPECTEDLENGTHINBITSOFAMESSAGECONTAININGNCHARACTERSFORTHISFREQUENCYDISTRIBUTIONTHEPROCESSOFYOURSOLUTIONISREQUIRED8SCORES7ASSUMEADISKDRIVEISCONFIGUREDASFOLLOWSTHETOTALSTORAGEISAPPROXIMATELY675MDIVIDEDAMONG15SURFACESEACHSURFACEHAS612TRACKSTHEREARE144SECTORS/TRACK,512BYTE/SECTOR,AND16SECTORS/CLUSTERTHEINTERLEAVINGFACTORISFIVETHEDISKTURNSAT3600RMP1667MS/RTHETRACKTOTRACKSEEKTIMEIS20MS,ANDTHEAVERAGESEEKTIMEIS80MSNOWHOWLONGDOESITTAKETOREADALLOFTHEDATAINA360KBFILEONTHEDISKASSUMETHATTHEFILESCLUSTERSARESPREADRANDOMLYACROSSTHEDISKASEEKMUSTBEPERFORMEDEACHTIMETHEI/OREADERMOVESTOANEWTRACKSHOWYOURCALCULATIONSTHEPROCESSOFYOURSOLUTIONISREQUIRED8CORES8USINGCLOSEDHASHING,WITHDOUBLEHASHINGTORESOLVECOLLISIONS,INSERTTHEFOLLOWINGKEYSINTOAHASHTABLEOFELEVENSLOTSTHESLOTSARENUMBERED0THROUGH10THEHASHFUNCTIONSTOBEUSEDAREH1ANDH2,DEFINEDBELOWYOUSHOULDSHOWTHEHASHTABLEAFTERALLEIGHTKEYSHAVEBEENINSERTEDBESURETOINDICATEHOWYOUAREUSINGH1ANDH2TODOTHEHASHINGTHEPROCESSOFYOURSOLUTIONISREQUIREDH1K3KMOD11H2K7KMOD101KEYS22,41,53,46,30,13,1,678SCORES9CONVERTINGFROMAGENERALTREETOABINARYTREE4SCORESGENERALTREEEXAMPLEGRAPH10ADRAWTHEADJACENCYMATRIXREPRESENTATIONANDADJACENCYLISTREPRESENTATIONFORTHEGRAPHOFTHEFIGUREABOVE6SCORESBUSEDIJKSTRASALG