雨课堂在线学堂《数据结构（Data Structures）》单元考核测试答案

目录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分)学生在文本框中输入答案：，之后系统会根据数值判断答案：是否正确。

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分