数据结构与算法试卷A答案

1、-滁州学院2013/2014学年度第一学期期末考试试卷参考答案1开始的按照所画的邻接矩阵写出深度优先遍历和广度优先遍历顺序。地理信息系统专业（本）12级数据结构与算法A卷邻接矩阵一、题号一二三四五总分分值2010204010100得分（时间120分钟）选择题（每题1分，共20分）0101000101001001010101010100000100101100010000110（3分）邻接表:名姓 .级班级年 .业专1-5 DCDDA 6-10 CDDAB 11-15 DADDC 16-20 CACCA二、判读正误题（每题1分，共10分）1-5 VVXVV 6-10 VXXXX三、算法阅读填空题

2、（每题5分，共20分）1、写出算法划线语句的执行次数和x的结果。（答对执行次数55或者结果55给2分）执行次数55次x的结果552、在划线处填空，完成循环队列入队（答错任何一个字符给0分）cq-rear=(cq-rear+1)%MAXCSIZE:3、在划线处填空，完成单链表的查找（答对一空给2分）while( p!=NULL & p-data!=x )4、在划线处填空，完成顺序栈弹栈（栈使用base数组存储数据）*e = s-base-s-top:（答案使用先对top减；再把结果赋给e两条语句也正确）四、计算操作题（每题10分，共40分）1、给定如图所示，画出该图的邻接表存储结构；画出该图的邻

3、接矩阵；分别给出从顶点123456724NULLNULL2145*43766NULLMZ：NULL广度优先：1243657；（2分）深度优先：1234576（2分）NULLNULLNULL（3分）2、设权值集合W=5、29、7、8、14、23、3、11，以W为基础，建立一颗霍夫曼树， 并求出其WPL的值。答：（6分，不同形态也对）WPL=29*2+12*3+3*4+8*4+3*4+5*4+11*3+23*2=271（4 分，缺少中间这一步扣 2 分）3、已知一颗二叉树的中序遍历序列和后序遍历序列分别为：中序：CBEDAFIGH，后序: CEDBIFHGA。试画出这颗二叉树，并写出其先序遍历序列

4、。答：此树为：（6分）此树的先序遍历序列为：ABCDEGFIH（4分）4、已知无向图如下图所示，完成：从顶点1开始，使用普里姆算法构造最小代价生成树（需 要中间过程）；以1为源点，使用迪杰斯特拉算法求各个点最短路径（需要中间过程）。Prim算法构造过程：结点1为初始点。（5分，少一个步骤扣1分）五、算法设计题（每题10分，共10分）1、设计一个算法，实现在顺序表上的起（冒）泡排序。#define MAXSIZE 20（1 分）typedef int ElemType;（ 1 分）typedef struct （ElemType rMAXSIZE+1;int length; SqList;（3 分）void BubbleSort（SqList &L）int i,j,t;BOOL change;for（i=L.count-1,change=True;i0&change;-i）change=False;for（j=0;jL.elemwordj+1）t=L.elemwordj;L.elemwordj=L.elemwordj+1;L.elemwordj+1=t;change=True;（5 分）本题首先考查基于C语言的顺序表实现，并在此基础上利用起泡排序算法对顺序表中的元 素进行排序阅卷时