《数据结构》-08数据结构

诚信应考,考试作弊将带来严重后果华南理工大学期末考试DATASTRUCTUREB试卷注意事项1考前请将密封线内填写清楚；所有答案请答题纸上；2考试形式闭卷；本试卷共十大题，满分100分，考试时间120分钟。1SELECTTHECORRECTCHOICE20SCORES,EACH2SCORES1ANALGORITHMMUSTBEORDOALLOFTHEFOLLOWINGEXCEPTBACORRECTBINFINITECNOAMBIGUOUSDCONCRETESTEPS2PICKTHEGROWTHRATETHATCORRESPONDSTOTHEMOSTEFFICIENTALGORITHMASNGETSLARGEDA4N3B2NCND30N2LOGN3IFADATAELEMENTREQUIRES8BYTESANDAPOINTERREQUIRES4BYTES,THENALINKEDLISTREPRESENTATIONWILLBEMORESPACEEFFICIENTTHANASTANDARDARRAYREPRESENTATIONWHENTHEFRACTIONOFNONNULLELEMENTSISLESSTHANABOUTBA1/4B2/3C3/5D3/44WHICHISTHEREALIZATIONOFADATATYPEASASOFTWARECOMPONENTAAANABSTRACTDATATYPEBAREALDATATYPECATYPEDADATASTRUCTURE5WEUSETHEPARENTPOINTERREPRESENTATIONFORGENERALTREESTOSOLVEBPROBLEMASHORTESTPATHSBGENERALTREETRAVERSALCEQUIVALENCECLASSESDEXACTMATCHQUERY6THEMOSTEFFECTIVEWAYTOREDUCETHETIMEREQUIREDBYADISKBASEDPROGRAMISTODAIMPROVETHEBASICOPERATIONSBREDUCEMAINMEMORYUSECELIMINATETHERECURSIVECALLSDMINIMIZETHENUMBEROFDISKACCESSES7INTHEHASHFUNCTION,COLLISIONREFERSTOBATWOELEMENTSHAVETHESAMESEQUENCENUMBERBDIFFERENTKEYSAREMAPPEDTOTHESAMEADDRESSOFHASHTABLECTWORECORDSHAVETHESAMEKEYDDATAELEMENTSARETOOMUCH8GIVENANARRAYASAMNSUPPOSEDTHATA00ISLOCATEDAT64410ANDA22ISSTOREDAT67610,ANDEVERYELEMENTOCCUPIESONESPACE“10”MEANSTHATTHENUMBERISPRESENTEDINDECIMALSTHENTHEELEMENTA3310ISATPOSITIONAA692B695C650D7089TREEINDEXINGMETHODSAREMEANTTOOVERCOMEWHATDEFICIENCYINHASHINGDAINABILITYTOHANDLERANGEQUERIESBINABILITYTOMAXIMUMQUERIES_姓名学号学院专业座位号密封线内不答题密封线线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