目錄1.Introduction2.List3.Tree4.Search5.Index1.Introduction1/2單選題(1分)1.Whichapplicationcanbedevelopedbasedonthegraphdatastructure?StudentmanagementsystemFamilyinformationsystemTransportationnetworksFiledirectory答案：C2/2單選題(1分)Whichoneisnotapartofanabstractdatastructure?DataAbstractoperationsImplementationofOperations答案：C

1

/1

單選題

(1分)AT(n)=c1*n+c2BT(n)=c1*n*n+c2CT(n)=c1*i*j+c2

答案：B1/4單選題(1分)Ωindicatesthe____boundLowerExactUpper答案：A2/4單選題(1分)Θindicatesthe______bound.LowerExactUpper答案：B

3

/4

單選題

(1分)Whichoneisslowest:A)B)C)D)

答案：B

4

/4

單選題

(1分)Oindicatesthe_______boundALowerBExactCUpper

答案：C

1

/1

單選題

(1分)DetermineΘforthefollowingcodeintheaveragecase.Assumethatallvariablesareoftypeint.AΘ(1)BΘ(n*n)CΘ(n)DΘ(n*logn)

答案：C2.List

1

/1

單選題

(1分)A4B5C8D3

答案：B1/1單選題(1分)GiventhepositionofanelementinanarraybasedList,thetimecosttogetthevalueoftheelementis_____?Θ(1)Θ(n)Θ(n*n)Θ(logn)答案：A1/1單選題(1分)Whenweinsertoneelementintoanarraybasedlist,weneedtomovetheelementsinthearray.Whichoneofthefollowingcodefragmentsiscorrecttoperformthedatamovement?for(inti=fence;i<listsize;i++)listArray[i]=listArray[i-1];for(inti=fence;i<listsize;i++)listArray[i-1]=listArray[i];for(inti=listSize;i>fence;i--)listArray[i]=listArray[i-1];for(inti=listSize;i>fence;i--)listArray[i-1]=listArray[i];答案：C1/2單選題(1分)Thetimecosttoremoveanelementfromanarraybasedlistis______inaveragecase?Θ(1)Θ(n)Θ(n*n)Θ(logn)答案：B2/2單選題(1分)Thetimecosttoinsertanelementintoanarraybasedlistis_________inaveragecase?Θ(1)Θ(n)Θ(n*n)Θ(logn)答案：B1/2判斷題(1分)Comparedwitharraybasedlist,linkedlistrequiresmorememorytostoreelements.答案：√2/2判斷題(1分)Theelementsinalinkedlistmustbestoredcontinuouslyinmemory.答案：×1/1單選題(1分)Givenanemptylinkedlist,thecosttoinsertnelementsinthelistis___?Θ(1)Θ(n)Θ(n*n)Θ(logn)答案：B1/1單選題(1分)Whenweremoveoneelementfromalinkedlist,____'next'pointersinthelistwillbechangedatmost?0123答案：B1/1多選題(2分)Whichoperationsoflinkedlistaremoreefficientthanarraybasedlist?insertsearchremovesetPos答案：AC1/1單選題(1分)Whichoneisnotcorrect?StackisarestrictformoflistStackhastheLIFOproperty(lastinfirstout)TheinsertionoperationofstackisperformedatthetopofthestackTheremoveoperationofstackisperformedatthebottomofthestack答案：D1/1單選題(1分)Givenaqueue{1,2,3,4,5},where1isthefrontand5istherear.Whatwillbethequeuechangedtoafterexecutingthefollowingoperations:enqueue(8),dequeue(),dequeue(),enqueue(9),dequeue(),dequeue(),dequeue(),enqueue(10),10,9,88,9,104,5,8,9,1010,9,8,4,5答案：B3.Tree1/2填空題(1分)Afullbinarytreewith11nodeshas____leaves.答案：["6"]2/2填空題(2分)Acompletebinarytreewiththeheight4has____nodesatmost,and____nodesatleast.答案：["15"]2答案：["8"]1/1填空題(1分)Inanarraybasedcompletebinarytree,theparentoftheNo.15nodeisstoredintheNo.____positionofthearray.答案：["7"]

1

/1

填空題

(2分)________

答案：["abdceghf"]2答案：["dbaghecf"]1/2判斷題(1分)ABSTmustbeafullbinarytree?答案：×2/2判斷題(1分)TheheightofaBSTwithnnodesisalwayslessthann?答案：×1/1判斷題(1分)ThetimecosttosearchavalueinaBSTisalwaysΘ(logn)inaveragecase?答案：×1/1判斷題(1分)ThetimecosttoinsertonenodeonabalancedBSTisΘ(logn)inaveragecase?答案：√1/3判斷題(1分)Aheapmustbeacompletebinarytree答案：√2/3判斷題(1分)Aheapmustbeafullbinarytree答案：×3/3判斷題(1分)Theminimumvalueofaheapisalwaysstoredinitsrootnode.答案：×

1

/1

單選題

(1分)A)B)C)D)

答案：B4.Search1/2單選題(1分)Givenasortedarraycontainingnelements,thetimecostofbinarysearchisΘ(___)inaveragecase.n*nnlognn*logn答案：C2/2單選題(1分)ThetimecosttoinsertoneelementintoasortedarrayisΘ(___)inaveragecase.n*nnlognn*logn答案：B

1

/1

單選題

(1分)學(xué)生在文本框中輸入答案：，之后系統(tǒng)會根據(jù)數(shù)值判斷答案：是否正確。

A3B4C5D6

答案：B1

/1

單選題

(1分)A1B4C7D10

答案：D5.Index1/1單選題(1分)Thetimecosttoinsertorremoveoneelementinalinearindexis:Θ(1)Θ(n)Θ(n*n)Θ(logn)答案：B1/1單選題(1分)Afterinserttheelements(8,10,30,5,15,2,20)intoanempty2-3treeonebyone,thedepthofthenodecontaining10is_________0123答案：A1/3判斷題(1分)2-3treeisalwaysbalanced?答案：√2/3判斷題(1分)Thetimecosttosearchoneelementina2-3treeisΘ(logn)inaveragecase,andΘ(1)inbestcase.答案：√3/3填空題(1分