浙大数据结构期末考试2009-2010.pdf

浙江大学2009 –2010 学年秋学期 《数据结构基础》课程期末考试试卷(A) 课程号： 211C0020_，开课学院：_计算机科学与技术_ 考试试卷：√A 卷、B 卷（请在选定项上打√） 考试形式：√闭、开卷（请在选定项上打√），允许带____无___入场 考试日期： 2009 年 11 月 17 日,考试时间： 120 分钟 诚信考试，沉着应考，杜绝违纪。 考生姓名： 学号： 所属院系： _ 题序 一 二 三 四 总 分 得分 评卷人 Answer Sheet Part I (24) 1. 2. 3. 4. 5. 6. 7. 8a. 8b. 9. 10. 11. Part II (18) 1. ______________ _________________ _______________ ________________ 2. _________________ _________________ Part III (43) 1. 2. (a) The initial max-heap sequence is: (b) The sequences of the first 4 runs are: 3. (a) DFS: (b) BFS: (c) Topological order: 4. S 1 2 3 4 5 6 7 8 9 10 Union(1,2) Union(3,4) Union(1,3) Union(3,5) Union(6,7) Union(1,7) Union(7,8) Union(4,10) 5. One possible inserting sequence is: Part IV (15) NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (24 points) (1) Given as following the recurrence relations of the time complexities of two programs: P1. T(1)=1, T(N)=T(N/2)+1; and P2. T(1)=1, T(N)=2T(N/2)+1; What conclusion can be made about the time complexities of the two programs? a. both are O(logN) b. O(logN) and O(NlogN) respectively c. both are O(N) d. O(logN) and O(N) respectively (2) In a singly linked list with N nodes, which