浙江大学远程教育学院标准答案B 卷课程名称 数据结构与算法 年级专业(层次) 计算机 一.单项选择题（每项选择 1.5 分，共 60 分）1、 B D 2、 D B 3、 C 4、 A 5、 C 6、 A C 7、 B 8、 C 9、 D A 10、 D 11、 C 12、 D 13、 B 14、 B 15、 A 16、 D 17、 C 18、 B 19、 A 20、 D 21、 C 22、 D 23、 A 24、 A 25、 A B 26、 D 27、 D B 28、 B 29、 A 30、 D 31、 C 32、 C 33、 C 34、 D 二.填空题（将正确的答案填在相应的空位中,每空 1-2 分，共 20 分）1、 n*m-n(n-1)/2 或 n*m-n(n+1)/2 (给 2 分)； n*m 或 O(m*n) (给 1 分)2、 n-i+1 (给 2 分)； n-i (给 1 分)3、 栈 或 堆栈 (给 2 分)；4、 两个字符串的长度相等且对应的字符相同 (给 2 分)；5、 i*(i+1)/2 + j+1 (给 2 分)； i*(i+1)/2 + j 或 i*(i-1)/2 + j (给 1 分)6、 a f e,f,g,h 4 3 4 (各给 1 分)7、 n-1 (给 2 分)8、 希尔排序、选择排序、快速排序、堆排序 (各给 0.5 分，多选一个扣 0.5 分)三.分析题（每题 5 分，共 20 分）1、算法 xxxx 的功能是 先序遍历二叉树 T (功能的意思正确给 3 分,遗漏先序或写成其它顺序给 2 分)这个算法的思想是 采用非递归的方法，利用堆栈作为数据结构 （给 2 分，指出非递归或者堆栈就给分）2、 （表 1 正确给 2 分，部分正确给 1 分；表 2 正确给 3 分，部分正确给 1-2 分）j 1 2 3 4 5 6 7uj b a a b a c anextj 0 1 1 1/0 2 3 1表 1j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17vj a b c a a b b a a b c a b a a b cnextj 0 1 1 1/0 2 2 3 1/0 2 2 3 4 2 3 2 2 3表 23、 （画出网络图给 1 分；最小生成树正确给 2 分,部分正确给 1 分；深度优先遍历正确给 2 分)(1)网络图如下:(2) 最小生成树如下:(3) V5 出发的深度优先遍历序列为: V5,V1,V2,V3,V4,V6,V7.4、 （前 2 趟 2 分,最后 1 趟 1 分) 初始: 503，61，512，87，908，170，897，2751 趟: 275，61，170，87 503 908，897，5122 趟: 87，61， 170 275, 503 512，897 9083 趟: 61 87，170 275, 503, 512，897, 908