《数据结构》-数据结构样卷3(英文)

重庆大学数据结构课程样卷3A卷B卷开课学院计算机学院课程号18001035考试日期考试方式开卷闭卷其他考试时间120分钟题号一二三四五六七八九十总分得分一、SINGLECHOICE1MERGETWOORDEREDLIST,BOTHOFTHEMCONTAINNELEMENTS,THELEASTTIMESOFCOMPARISONISANB2N1C2NDN12SEQUENTIALSTOREDLINEARLISTWITHTHELENGTHOF1000,IFWEINSERTANELEMENTINTOANYPOSITION,THEPOSSIBILITYISEQUAL,WHENWEINSERTANEWELEMENT,THEAVERAGENUMBEROFREMOVINGELEMENTSISA1000B1001C500D4993ASSUMETHATTHEINITIALSTATUSOFSTACKSANDQUEUEQAREBOTHNULL,PUSHELEMENTSE1,E2,E3,E4,E5,E6INTOTHESTACKSONEBYONE,ANELEMENTPOPSFROMSTACK,THENENTERINTOQUEUEQIFTHESEQUENCEWHICHTHESIXELEMENTSINTHEDEQUEUEISE2,E4,E6,E5,E3,E1,THECAPACITYOFSTACKSISATLEASTA6B4C3D24TWODIMENSIONALARRAYA1020,510STORESINLINESEQUENCE,EACHELEMENTOCCUPIES4STORAGELOCATION,ANDTHEMEMORYADDRESSOFA10,5IS1000,THENTHEADDRESSOFA20,9ISA1212B1256C1368D13645ATREEWITHDEGREE3,ITHAS2NODESWITHTHEDEGREE3,ONENODEWITHTHEDEGREE2,AND2NODESWITHTHEDEGREE1,SOTHENUMBEROFNODESWITHDEGREE0ISA4B5C6D76THEINORDERSEQUENCEOFABINARYTREEISABCDEFG,ANDITSPOSTORDERSEQUENCEISBDCAFGE,SOITSPREORDERSEQUENCEISAEGFACDBBEACBDGFCEAGCFBDDEGAFCDB7AHUFFMANTREEWITHNLEAFNODES,ITSTOTALNUMBEROFNODESISAN1BN1C2N1D2N18INANADJACENCYLISTOFUNDIRECTEDGRAPHWITHNVERTEXESANDEEDGES,THENUMBEROFEDGENODEISANBNECED2E9THEDEGREESUMOFINDEGREEANDOUTDEGREEOFADIRECTEDGRAPHISK1,ANDTHENUMBEROFOUTDEGREEISK2THEREFORE,INITSADJACENCYLIST,THENUMBEROFEDGENODESINTHISSINGLYLINKEDLISTISAK1BK2CK1K2DK1K210IFTHEGRAPHHASNVERTEXESISACIRCLE,SOITHASSPANNINGTREEANB2NCN1DN111WHENLOOKUPASEQUENTIALLISTWITHTHELENGTH3,THEPOSSIBILITYTHATWEFINDTHEFIRSTELEMENTIS1/2,ANDTHEPOSSIBILITYTHATWEFINDTHESECONDELEMENTIS1/3,THEPOSSIBILITYTHATWEFINDTHETHIRDELEMENTIS1/6,SOTHEAVERAGESEARCHINGLENGTHTOSEARCHANYELEMENTFINDITSUCCESSFULLYANDTHESENTRYISATTHEENDOFTHELISTISA5/3B2C7/3D4/312THEREISANORDEREDLIST3,5,7,8,11,15,17,22,23,27,29,33,BYBINARYSEARCHTOSEARCH27,SOTHENUMBEROFCOMPARISONISA2B3C4D513SORTTHEFOLLOWINGKEYWORDSEQUENCESBYUSINGQUICKSORT,ANDTHESLOWESTONEISA19,23,3,15,7,21,28B23,21,28,15,19,3,7C19,7,15,28,23,21,3D3,7,15,19,21,23,2814HEAPSORTNEEDSADDITIONALSTORAGECOMPLEXITYISAONBONLOG2NCON2DO115IFWESORTANARRAYWITHINTHETIMECOMPLEXITYOFONLOG2N,NEEDINGSORTITSTABLY,THEWAYTHATWECANCHOOSEIS命题人组题人审题人命题时间教务处制学院专业、班年级学号姓名公平竞争、诚实守信、严肃考纪、拒绝作弊封线密AMERGESORTBDIRECTINSERTIONSORTCHEAPSORTDQUICKSORT二、FILLTHEBLANKS1ASSUMETHATTHESTRUCTUREOFTHENODESINDOUBLYCIRCULARLINKEDLISTISDATA,LLINK,RLINK,WITHOUTAHEADNODEINTHELIST,IFWEWANTTOINSERTTHENODEWHICHPOINTERSPOINTSAFTERTHENODEPOINTERPPOINTS,THENEXECUTEASTHEFOLLOWINGSTATEMENTS_2BOTHSTACKANDQUEUEARE_LINEARSTRUCTURE3THEFOURLEAFNODESWITHTHEWEIGHT9,2,5,7FORMAHUFFMANTREE,ITSWEIGHTEDPATHLENGTHIS_4INORDERTOENSURETHATANUNDIRECTEDGRAPHWITHSIXVERTEXESISCONNECTED,NEEDATLEAST_EDGES5ANNVERTEXDIRECTEDGRAPH,IFTHESUMOFALLVERTICESOUTDEGREEISS,THENTHESUMOFALLVERTICESDEGREEIS_6THEDEPTHFIRSTTRAVERSALOFAGRAPHISSIMILARTOTHEBINARYTREE_TRAVERSALTHEBREADTHFIRSTGRAPHTRAVERSALALGORITHMISSIMILARTOTHEBINARYTREE_TRAVERSAL7ACONNECTEDGRAPHWITHNVERTEXESANDEEDGESHAS_EDGESOFITSSPANNINGTREE8THETIMECOMPLEXITYOFBINARYSEARCHINGIS_IFTHEREARE100ELEMENTS,THEMAXIMUMNUMBEROFCOMPARISONSBYBINARYSEARCHINGIS_9SORTNELEMENTSBYMERGESORT,THEREQUIRINGAUXILIARYSPACEIS_10SORTALINEARLISTWITH8ELEMENTSBYQUICKSORT,ATTHEBEST,THECOMPARISONTIMEIS_三、APPLICATION1BEGINFROMTHEVERTEXA,SEEKTHEMINIMUMSPANNINGTREEBYUSINGPRIMALGORITHMSV0A15V1V3V5V8V2V4V7V9V6A27A33A75A118A149A105A53A46A64A84A96A122A138A1532THEFOLLOWINGISAOENETWORK1HOWMUCHTIMEDOESITTAKETOCOMPLETETHEWHOLEPROJECT2FINDOUTALLOFTHECRITICALPATH9POINTS3ASSUMETHATASETOFKEYWORDSIS1，12，5，8，3，10，7，13，97,TRYTOCOMPLETETHEFOLLOWINGQUESTIONS9POINTS1CHOOSETHEKEYWORDSINSEQUENCETOBUILDABINARYSORTTREEBT2DRAWTHESTRUCTUREOFTHETREEAFTERDELETINGNODE“12”FROMTHEBINARYTREEBT4THEKEYWORDSEQUENCEIS503,87,512,61,908,170,897,275,653,462,USINGRADIXSORTINGMETHODTOSORTTHEMINASCENDINGORDER,TRYTOWRITEEVERYTRIPRESULTSOFSORT（9POINTS）四、ALGORITHM1THEFOLLOWINGALGORITHMEXECUTEONASINGLYLINKEDLISTWITHOUTHEADNODE,TRYTOANALYZEANDWRITEITSFUNCTION5POINTSVOIDFUNCTIONLINKNODEHEADLINKNODEP,Q,RPHEADQPNEXTWHILEQNULLRQNEXTQNEXTPPQQRHEADNEXTNULLHEADP2DESIGNANALGORITHMTODIVIDEASINGLYLINKEDLISTAWITHAHEADPOINTERAINTOTWOSINGLYLINKEDLISTAANDB,WHOSEHEADPOINTERSAREAANDB,RESPECTIVELYONTHECONDITIONTHATLINKEDLISTAHASALLELEMENTSOFODDSERIALNUMBERINTHEPREVIOUSLINKEDLISTAANDLINKEDLISTBHASALLELEMENTSOFEVENSERIALNUMBERINTHEPREVIOUSLINKEDLISTA,INADDITION,THERELATIVE