《数据结构》-华南理工大学数据结构

诚信应考,考试作弊将带来严重后果华南理工大学期末考试DATASTRUCTUREA试卷注意事项1考前请将密封线内填写清楚；2所有答案请直接答在试卷上；3考试形式闭卷；4本试卷共十大题，满分100分，考试时间120分钟。题号一二三四五六七八九十总分得分评卷人1SELECTTHECORRECTCHOICE20SCORES,EACH2SCORES1ANALGORITHMMUSTBEORDOALLOFTHEFOLLOWINGEXCEPTDACORRECT正确的BFINITE有限的CTERMINATE终止的DAMBIGUOUS模糊2PICKTHEGROWTHRATE增长率THATCORRESPONDSTOTHEMOSTEFFICIENT有效率的ALGORITHMASNGETSLARGECANB2NC10NLOGND2N23IFADATAELEMENTREQUIRES6BYTESANDAPOINTERREQUIRES4BYTES,THENALINKEDLISTREPRESENTATIONWILLBEMORESPACEEFFICIENTTHANASTANDARDARRAYREPRESENTATIONWHENTHEFRACTIONOFNONNULLELEMENTSISLESSTHANABOUTBA2/3B3/5C3/4D1/24WHICHSTATEMENTISNOTCORRECTAMONGTHEFOLLOWINGFOUR下面那个描述是不正确的AATHEWORSTCASEFORMYALGORITHMISNBECOMINGLARGERANDLARGERBECAUSETHATISTHESLOWESTBACLUSTER簇ISTHESMALLESTUNITOFALLOCATION分配FORAFILE,SOALLFILESOCCUPY占据AMULTIPLE倍数OFTHECLUSTERSIZECTHESELECTIONSORTISANUNSTABLE不稳定的SORTINGALGORITHMDTHENUMBEROFLEAVESINANONEMPTYFULLBINARYTREEISONEMORETHANTHENUMBEROFINTERNALNODES5WHICHOFTHEFOLLOWINGISATRUESTATEMENTCAINABST,THELEFTCHILDOFANYNODEISLESSTHANTHERIGHTCHILD,ANDINAHEAP,THELEFTCHILDOFANYNODEISLESSTHANTHERIGHTCHILDBINABST,THELEFTCHILDOFANYNODECOULDBELESSORGREATERTHANTHERIGHTCHILD,BUTINAHEAP,THELEFTCHILDOFANYNODEMUSTBELESSTHANTHERIGHTCHILDCINABST,THELEFTCHILDOFANYNODEISLESSTHANTHERIGHTCHILD,BUTINAHEAP,THELEFTCHILDOFANYNODECOULDBELESSTHANORGREATERTHANTHERIGHTCHILDDINBOTHABSTANDAHEAP,THELEFTCHILDOFANYNODECOULDBEEITHERLESSTHANORGREATERTHANTHERIGHTCHILD_6THEMOSTEFFECTIVEWAYTOREDUCETHETIMEREQUIREDBYADISKBASEDPROGRAMISTOBAIMPROVETHEBASICOPERATIONSBMINIMIZETHENUMBEROFDISKACCESSESCELIMINATETHERECURSIVECALLSDREDUCEMAINMEMORYUSE7THEMAXHEAPCONSTRUCTEDBYASEQUENCEOFKEY46,79,56,38,40,84ISA79,46,56,38,40,84B84,79,56,46,40,38C84,79,46,38,40,56D84,56,79,40,46,388IFTHEREIS05MBWORKINGMEMORY,4KBBLOCKS,YIELD128BLOCKSFORWORKINGMEMORYBYTHEMULTIWAYMERGEINEXTERNALSORTING,THEAVERAGERUNSIZEANDTHESORTEDSIZEINONEPASSOFMULTIWAYMERGEONAVERAGEARESEPARATELYAA1MB,128MBB1MB,64MBC2MB,64MBD05MB,128MB9TREEINDEXINGMETHODSAREMEANTTOOVERCOMEWHATDEFICIENCYINHASHINGDAINABILITYTOHANDLERANGEQUERIESBINABILITYTOMAXIMUMQUERIESCINABILITYTOHANDLEQUERIESINKEYORDERDALLOFABOVE10ASSUMETHATWEHAVEEIGHTRECORDS,WITHKEYVALUESATOH,ANDTHATTHEYAREINITIALLYPLACEDINALPHABETICALORDERNOW,CONSIDERTHERESULTOFAPPLYINGTHEFOLLOWINGACCESSPATTERNEDFGBGFAFEGB,IFTHELISTISORGANIZEDBYTHEMOVETOFRONTHEURISTIC,THENTHEFINALLISTWILLBEBABGEFDACHBBGEFADCHCABFDGECHDFDGEABCH2FILLTHEBLANKWITHCORRECTCCODES13SCORES1GIVENANARRAYSTORINGINTEGERSORDEREDBYVALUE,MODIFYTHEBINARYSEARCHROUTINESTORETURNTHEPOSITIONOFTHEFIRSTINTEGERWITHTHEGREATESTVALUELESSTHANKWHENKITSELFDOESNOTAPPEARINTHEARRAYRETURNERRORIFTHELEASTVALUEINTHEARRAYISGREATERTHANK10SCORES/RETURNPOSITIONOFGREATESTELEMENTARRAYI_LI_/INRIGHTHALF/SEARCHVALUENOTINARRAY_RETURNL_/LATFIRSTVALUELESSTHANK/L1,NOVALUELESSTHANK2AFULL5ARYTREEWITH100INTERNALVERTICESHAS_501_VERTICES3SCORES3ACERTAINBINARYTREEHASTHEPREORDERENUMERATIONASABECDFGHIJANDTHEINORDERENUMERATIONASEBCDAFHIGJTRYTODRAWTHEBINARYTREEANDGIVETHEPOSTORDERENUMERATIONTHEPROCESSOFYOURSOLUTIONISREQUIRED8SCORESPOSTORDERENUMERATIONEDCBIH