1、南 京 理 工 大 学 课 程 考 试 -答案及评分标准课程名称： 数据结构 b 学分： 3 大纲编号 062204 试卷编号： 考试方式： 笔试 满分分值： 100 考试时间： 120 分钟组卷日期： 2006 年 5 月 18 日 组卷教师（签字） 张宏 审定人（签字） 王树梅 注意：请将答案按题号和序号写在答题纸上一、选择题（1.5*20=30 分）1. C 2. B 3. C 4. C 5 C 6 C 7. C 8. D 9. A 10. C11. D 12. C 13. A 14. C 15. A16. A 17. D 18. B 19 A 20. D二、填空题（16 分,每空 1
2、分）1(1) top=top-next 2 (2)4 (3)87 3 (4) 为负则不能满足按路径递增产生路径4(5)深度优先（6）广度优先 5(7)快速排序 堆排序 归并排序6.(8)12 (9)2049 7.(10) 10 8.(11)5 (12) 5 9.(13)数据已有序 (14)O(n 2)10 (15) 2 k-2+1(16)log 2i|+1 三、 简答题（39 分）11）(3 分)8256 7128513212 34 65 20152)(3 分)用 Dijkstra 算法求从顶点 1 开始的到其余顶点的最短路径（给出路径长度和中间点） 1-5 :8 1-2:12 1-(5)-4
3、:13 1-(5-,4)6 :18 1-(5,4,6)-3:203） （3 分）画出邻接表123 4562 12 4 15 5 8 3 13 1 6 6 5 4 5 6 20 3 2 5 7 3 254） （3 分）权之和 3052 (1)（4 分）2880158 22 505610 40 64 906125212 34 65(2) (4 分 )(4） （4 分）3、 （4 分）AB GD C H NE I OF K PL RM ST4、 （4 分）90 80 28 60 40 22 15 50 56 8 105、拓扑排序算法（4 分）设置一个边集合 E，开始为空。重复以下工作 n-1 次 （
4、n 为图顶点数）（1） 在图 G 中选最小的边删除（2） 该边加到集合 E 中，若加入后在 E 中形成回路，则丢弃四、算法设计（14 分）1） （7 分）treeleaf(p)if (p ) m=treeleaf(p-lchild);56 8 5615 8010 22 2 56 56 50 60 90 40 8 102840 501520 906056 808 102840 1520 906050 80删除 5660 808 102840152050删除 90(3） （ 4 分）n=treeleaf(p-rchild);if(m+ n = =0 )return 1;else return m+n; else return 0;2） （7 分）finddegree(adj,n) for(i=0;inext; /whlie /for /finddegree
