南京理工大学课程考试-----答案及评分标准

《南京理工大学课程考试-----答案及评分标准》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京理工大学课程考试-----答案及评分标准课程名称：数据结构b学分：3大纲编号062204试卷编号：考试方式：笔试满分分值：100考试时间：120分钟组卷日期：2006年5月18日组卷教师（签字）张宏审定人（签字）王树梅注意：请将答案按题号和序号写在答题纸上一、选择题（1.5*20=30分）1.C2.B3.C4.C5．C6．C7.C8.D9.A10.C11.D12.C13.A14.C15.A16.A17.D18.B19A20.D二、填空题（16分,每空1分）1．(1)top=top->next2．(2)4(3)873(4)为负则不能满足按

2、路径递增产生路径4．(5)深度优先（6）广度优先5．(7)快速排序堆排序归并排序6.(8)12(9)20497.(10)108.(11)5(12)59.(13)数据已有序(14)O(n2)10．(15)2k-2+1(16)「log2i

3、+1三、简答题（39分）1．1）(3分)82567128513212346520152)(3分)用Dijkstra算法求从顶点1开始的到其余顶点的最短路径（给出路径长度和中间点）1->5:81->2:121->(5)->4:131->(5-,4)6:181->(5,4,6)->3:203）（3分）画出邻接表5

4、6432125126123∧45621241558∧313∧1665∧45620∧3257∧3254）（3分）权之和3052(1)（4分）28801582250561040649060804090删除9050201528810810删除5650806020154028(3）（4分）908105680602015405028(2)(4分)(4）（4分）40∧∧3、（4分）ABGDCHNEIOFKPLRMST4、（4分）9080286040221550568105、拓扑排序算法（4分）设置一个边集合E，开始为空。重复以下工作n-1次（n为图顶点

5、数）（1）在图G中选最小的边删除（2）该边加到集合E中，若加入后在E中形成回路，则丢弃四、算法设计（14分）1）（7分）treeleaf(p){if(p){m=treeleaf(p->lchild);n=treeleaf(p->rchild);if(m+n==0)return1;elsereturnm+n;}elsereturn0;}}2）（7分）finddegree(adj,n){for(i=0;in

6、ext;}//whlie}//for}//finddegree