《數(shù)據(jù)結(jié)構(gòu)與算法》試卷

1、四川大學(xué)期末考試試題（閉卷）（2009-2010學(xué)年第2學(xué)期）課程號(hào)：311036030課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法（D卷）任課教師：孫界平楊秋輝張衛(wèi)華適用專業(yè)年級(jí)：軟件工程2009級(jí)學(xué)號(hào)：姓名：考試須知四川大學(xué)學(xué)生參加由學(xué)校組織或由學(xué)校承辦的各級(jí)各類考試，必須嚴(yán)格執(zhí)行四川大學(xué)考試工作管理辦法和四川大學(xué)考場(chǎng)規(guī)則。有考試違紀(jì)作弊行為的，一律按照四川大學(xué)學(xué)生考試違紀(jì)作弊處罰條例進(jìn)行處理。四川大學(xué)各級(jí)各類考試的監(jiān)考人員，必須嚴(yán)格執(zhí)行四川大學(xué)考試工作管理辦法、四川大學(xué)考場(chǎng)規(guī)則和四川大學(xué)監(jiān)考人員職責(zé)。有違反學(xué)校有關(guān)規(guī)定的，嚴(yán)格按照四川大學(xué)教學(xué)事故認(rèn)定及處理辦法進(jìn)行處理。題號(hào)一(30%)二（10%）三（15%

2、）四（20%）五(25%)卷面成績(jī)得分閱卷時(shí)間注意事項(xiàng)：1.請(qǐng)務(wù)必將本人所在學(xué)院、姓名、學(xué)號(hào)、任課教師姓名等信息準(zhǔn)確填寫(xiě)在試題紙和添卷紙上2.請(qǐng)將答案全部填寫(xiě)在本試題紙上；3.考試結(jié)束，請(qǐng)將試題紙、添卷紙和草稿紙一并交給監(jiān)考老師。得分一、單項(xiàng)選擇題（本大題共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評(píng)閱教師得分：一、判斷題(本大題共5小題，每小題2分，

8、共10分)提示：正確打T,錯(cuò)誤打F,:將其結(jié)果填寫(xiě)在答題紙上。1. Thespace/timetradeoffprinciplesaysthatonecanoftenachieveareductionintimeifoneiswillingtosacrificespaceorviceversa.()2. Theupperboundforanalgorithmisthesameastheworstcaseforthatalgorithm.()3. Array-basedlistsaregenerallymorespaceefficientthanlistedlistswhentheuserkno

9、wsinadvanceapproximatelyhowlargethelistwillbecome.()4. Thenumberofemptysubtreesinanon-emptybinarytreeisonemorethanthenumberofnodesinthetree.()5. Forgraphrepresentation,adjacencymatrixismorespaceefficientthanadjacencylistbecausetheformerrequiresnooverheadforpointers.()|評(píng)閱弟師*得？分二三、名詞解釋題(本大題共3小題，每小題5分，

10、共15分)。提示：解釋每小題所；給名詞的含義，若解釋正確則給分，若解釋錯(cuò)誤則無(wú)分，若解釋不準(zhǔn)確或不全面，則酌情扣分。1. topologicalsort2. simplepath3. loadfactor，評(píng)閱教師j得分！四、應(yīng)用題(本大題共4小題，每小題5分，共20分)。提示：請(qǐng)給出準(zhǔn)確答案，|j!如果有中間步驟，答案錯(cuò)誤的情況下有步驟分。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分）。提示：每小題給出了一個(gè)程序設(shè)計(jì)要求，請(qǐng)按照要求寫(xiě)出源程序代碼，如果源程序代碼中出現(xiàn)語(yǔ)法錯(cuò)誤或邏輯錯(cuò)誤，則酌情扣分。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;出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在答題紙上。錯(cuò)選、多選或未選均無(wú)分。1. Asethasthefollowingproperties:()(A) Mayhaveduplicates,elementhaveaposition.(B) Mayhaveduplicates,elementsdonothaveaposition.(C) Maynothaveduplicates,elementshaveaposition.(D) Maynothaveduplicates,elementsdonothaveaposition.2. Pickthegrowthratethatcorrespondstothemostefficientalgorithmwhenn=4.()(A)5n(B) 20logn(C) 2n*