数据结构习题guide

《数据结构习题guide》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.Examguidelines-Theexamwilllast2hours.-Theexamisclosed-bookandclosed-notes.-Theexamcoversthematerialdetailedintheexamsyllabus.2.Examstructure-Theexamisinthreeparts.-Part1:Thereare20multiple-choicequestionswith1.5pointsforeachone.Choosethecorrectanswerf

2、oreachquestion.-Part2:Thereare15true-falsequestionswith2pointsforeachone.IndicatewhethereachofthequestionsisTRUEorFALSE-Part3:Thereare4questionswith10pointsforeachone,oneofwhichissimilartoanexerciseofChapter3.lDescribeanalgorithmlCodeanalgorithmlAnalyze

3、thetimecomplexityofyouralgorithmlFamiliarwiththeoperationsofBSTandAVLtreeslTheanswerorsolutionshouldbeginwith“Answer:”/“Ans:”/“Solution:”/“Sol:”SamplequestionsPart11.Anon-circulardoublylinkedlistcanbestandmostgenerallybedefinedasa.alinearsequence（顺序）ofe

4、lementschainedtogetherwithpointersb.alinearsequenceofelementsinsequentialmemorylocationsc.asetofelementschainedtogetherwithpointersd.asetofelementsinsequentialmemorylocations2.Arecursivefunctioncancauseaninfinite（无穷的）sequence（结果）offunctioncallsifa.thepr

5、oblemsizeishalvedateachstepb.thetermination（终止）conditionismissingc.nousefulincrementalcomputationisdoneineachstepd.aandc3.Whichoftheseisthecorrectbig-Oexpressionfor1+2+3+...+n?a.O(logn)b.O(n)c.O(nlogn)d.O(n²)4.Hereissomecodeforanintegervariablen:while(n

6、>0){n=n/10;//Useintegerdivision}Whatistheworst-casetimeanalysisfortheaboveloop?a.O(1)b.O(logn)c.O(n)d.O(n²)2.Considerthefollowingstatements:inti=42;intj=80;int*p1;int*p2;p1=&i;p2=&j;*p1=*p2;cout<

7、andthenanother42b.42andthen80c.80andthen42d.80andthenanother801.Whatkindoflistisbesttoanswerquestionssuchas"Whatistheitematpositionn?"a.Listsimplementedwithanarray.b.Doubly-linkedlists.c.Singly-linkedlists.d.Doubly-linkedorsingly-linkedlistsareequallybe

8、st2.lSupposewehaveanarrayimpementationofthestackclass,withtenitemsinthestackstoredatdata[0]throughdata[9].Wheredoesthepushmemberfunctionplacethenewentryinthearray?a.data[0]b.data[1]c.data[9]d.data[10]3.Isitpossibleforamemberfunct