数据结构试卷答案
第一大题 单项选择(每小题 2 分 共 20 分)1、C 2、C 3、B 4、B 5、B 6、C 7、 8、 9、 10、D 第二大题 填空(每空 1 分 共 10 分)1、线性结构 树形结构 图型结构 2、F=R 3、三元组表 4、2i+15、e 2e 6、冲突 7、 (49,13,27,50,76,38,65,97)第三大题 简答(每小题 8 分 共 48 分)1、二叉树如下图所示:(答对给 5 分)二叉树的先序遍历序列:ABCDEFGH (答对给 3 分)二* 二* 学年 第 * 学期 数据结构 试卷 参考答案及评分标准AGDBC HFE2、 (1)该图的邻接矩阵:(答对给 4 分)(2)该图的深度优先遍历序列:ABCED (答对给 2 分)(3)该图的广度优先遍历序列:ABCDE (答对给 2 分)3、(答对给 5 分)53527 9163910 13230 1 1 0 00 0 1 1 00 0 0 0 10 0 1 0 01 0 0 1 0二* 二* 学年 第 * 学期 数据结构 试卷 参考答案及评分标准WPL=(2+3)*4+5*3+(7+9+13)*2=93 (答对给 3 分)4、克鲁斯卡尔(Kruskal)算法构造最小生成树的过程如下所示:(答对给 8 分)5、 (1)散列表如下图所示: (答对给 6 分)0 1 2 3 4 5 663 36 15 22 40(2)ASL=1.6 (答对给 2 分)6、起泡排序各趟排序结果如下: (答对给 6 分)(4)45(3)6A DCBE7(2)(1)二* 二* 学年 第 * 学期 数据结构 试卷 参考答案及评分标准初始:49,38,65,97,76,13,27第一趟:38,49,65,76,13,27,97第二趟:38,49,65,13,27,76,97第三趟:38,49,13,27,65,76,97第四趟:38,13,27,49,65,76,97第五趟:13,27,38,49,65,76,97第六趟:13,27,38,49,65,76,97起泡排序是稳定排序。 (答对给 2 分)第四大题 算法分析与设计(本大题共 2 小题 共 22 分)1、 (1)7 (答对给 5 分)(2)f 的功能是输出链表中最后一个(若存在)大于 A 小于B 的元素的值。 (答对给 5分)2、算法如下:void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La->next; pb=Lb->next;Lc=pc=La;二* 二* 学年 第 * 学期 数据结构 试卷 参考答案及评分标准while(pa&&pb)if(pa->data data)pc->next=pa;pc=pa;pa=pa->next; else pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;free(Lb);/MergeList (答对给 12分)