《数据结构与算法》试卷

1、四川大学期末考试试题（闭卷）（2009-2010学年第2学期）课程号：311036030课程名称：数据结构与算法（D卷）任课教师：孙界平杨秋辉张卫华适用专业年级：软件工程2009级学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学考试工作管理办法和四川大学考场规则。有考试违纪作弊行为的，一律按照四川大学学生考试违纪作弊处罚条例进行处理。四川大学各级各类考试的监考人员，必须严格执行四川大学考试工作管理办法、四川大学考场规则和四川大学监考人员职责。有违反学校有关规定的，严格按照四川大学教学事故认定及处理办法进行处理。题号一(30%)二（10%）三（15%

2、）四（20%）五(25%)卷面成绩得分阅卷时间注意事项：1.请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上2.请将答案全部填写在本试题纸上；3.考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。得分一、单项选择题（本大题共15小题，每小题2分，共30分）提示：在每小题列(D)Thespecificinputinstanceofagivensizethatgivesthegreatestcost.4. Recursionisgenerallyimplementedusing()(A) Asortedlist.(B) Astack.(C) Aqueue.(D)

3、Aheap5. ThebeststructureforHuffmantreeis()(A) leftchildandrightsibling(B) leftchildandrightchild(C) leftmostchildandrightsibling(D) leftmostchildandnextchild6. Weusetheparentpointerrepresentationforgeneraltreestosolvewhichproblem?()(A) Shortestpaths(B) Generaltreetraversal(C) Equivalenceclasses(D) E

4、xact-matchquery7. Whensortingnrecords,Insertionsorthasworst-casecost:()(A) O(logn).(B) O(n).(C) O(nlogn).(D) O(n2)8. Intheworstcase,theverybestthatasortingalgorithmcandowhensortingnrecordsis:()(A) O(logn).(B) O(n).(C) O(nlogn).(D) O(n2)9. Themosttime-consumingpartofarandomaccesstodiskisusually:()(A)

5、Theseek.(B) Therotationaldelay.(C) ThetimeforthedatatomoveundertheI/Ohead.(D) Noneoftheabove.10. Self-organizinglistsattempttokeepthelistsortedby:()(A) Value(B) frequencyofrecordaccess(C) sizeofrecord(D) Noneoftheabove11. Acollisionresolutiontechniquethatplacesallrecordsdirectlyintothehashtableiscal

6、led:()(A) Openhashing.(B) Separatechaining.(C) Closedhashing.(D) Probefunction.12. Theprimarykeyis:()(A) Auniqueidentifierforarecord.(B) Themainsearchkeyusedbyusersofthedatabase.(C) Thefirstkeyintheindex.(D) Orderofarrival.13. Whichisnotthenameforastandardgraphtraversal?()(A) Preorder.(B) Depthfirst

7、.(C) Breadthfirst.(D) Noneoftheabove.14. Dijkstra'salgorithmrequiresthatverticesbevisitedin:()(A) Depth-firstorder.(B) Breadth-firstorder.(C) Orderofdistancefromthesourcevertex.(D) Noparticularorder.15. Whatstructureisusedbytopologicalsort()(A) ADG(B) GAD(C) DAG(D) AGD评阅教师得分：一、判断题(本大题共5小题，每小题2分，

8、共10分)提示：正确打T,错误打F,:将其结果填写在答题纸上。1. Thespace/timetradeoffprinciplesaysthatonecanoftenachieveareductionintimeifoneiswillingtosacrificespaceorviceversa.()2. Theupperboundforanalgorithmisthesameastheworstcaseforthatalgorithm.()3. Array-basedlistsaregenerallymorespaceefficientthanlistedlistswhentheuserkno

9、wsinadvanceapproximatelyhowlargethelistwillbecome.()4. Thenumberofemptysubtreesinanon-emptybinarytreeisonemorethanthenumberofnodesinthetree.()5. Forgraphrepresentation,adjacencymatrixismorespaceefficientthanadjacencylistbecausetheformerrequiresnooverheadforpointers.()|评阅弟师*得？分二三、名词解释题(本大题共3小题，每小题5分，

10、共15分)。提示：解释每小题所；给名词的含义，若解释正确则给分，若解释错误则无分，若解释不准确或不全面，则酌情扣分。1. topologicalsort2. simplepath3. loadfactor，评阅教师j得分！四、应用题(本大题共4小题，每小题5分，共20分)。提示：请给出准确答案，|j!如果有中间步骤，答案错误的情况下有步骤分。1. BuildaMAXheapof40,55,49,73,12,27,98,81,64,362. BuildaHuffmantreeofABCDEFGHIJ237111519233143863. AVLtreeofinputsequence16,3,7,

11、11,9,26,18,14,154. Usemathematicalinductiontoprovethatthenumberofleavesinanon-emptyfullK-arytreeis(K-1)n+1,wherenisthenumberofinternalnodes.五、编程题（本大题共2小题，共25分）。提示：每小题给出了一个程序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。1. Writearecursivefunctionthatreturnsacountofthenumberofleafnodesinabinarytre邳10分)2

12、. WriteaC/C+functiontocheckthematchofbrackets.妹15分)Example input:Example output:Example input:Example output:x+y*5/(32-6)+2matching!a+b *c-d口not matching!boolCheckMatching(stringstrExpression)/pleasefinishthisfunction;出的四个备选项中只有一个是符合题目要求的，请将其代码填写在答题纸上。错选、多选或未选均无分。1. Asethasthefollowingproperties:()(A) Mayhaveduplicates,elementhaveaposition.(B) Mayhaveduplicates,elementsdonothaveaposition.(C) Maynothaveduplicates,elementshaveaposition.(D) Maynothaveduplicates,elementsdonothaveaposition.2. Pickthegrowthratethatcorrespondstothemostefficientalgorithmwhenn=4.()(A)5n(B) 20logn(C) 2n*