期末考试试卷(A卷)标准答案及评分标准1

武汉工业学院2005–2006学年第1学期期末考试试卷（A卷）标准答案及评分标准课程名称数据结构课程编号05110一、填空题（每空1分，共20分）1.四种类型的数据结构分别是：、、和集合。表树图A2.假设按低下标行优先存储整数数组时，第一个元素的字节地址是100，每个整数占75aa四个字节，则的存储地址是100，的存储地址是168。00323.在顺序表中插入或删除一个元素，平均需要移动n/2个元素，具体移动的元素个数与位置有关。4.二叉树的五种基本形态是空树、只有根节点、根节点和左子树根节点和右子树和根节点、左子树和右子树。（也可用图表示）5.常用的有向图5种存储方法分别是邻接表、逆邻接表、十字链表、邻接矩阵和多邻重接表。6.内部排序算法中的两种基本操作是比较和交换。二、简答题（每小题8分，共40分）1.请给出以下有向图的：（1）邻接矩阵；（2分）（2）邻接表；（2分）（3）从顶点a出发的深度优先遍历序列；（2分）（4）从顶点e出发的广度优先遍历序列；（2分）audbcefv01000000000001000001000000000101解答：（1）、邻接矩阵00001100000000010010000001000000（2）（2分）邻接表abf^^^bcdefdeuvcbvf^^^^uva^（3）abfvucde（其它符合规则的序列也可得分）（4）eufbvaca（其它符合规则的序列也可得分）2.假设一棵二叉树的先序序列为ABCDEFGHIJK，请画出该二叉树。解答：该二叉树为：（画错一个分支扣0.5分）EBADCFHGIKJ和中序序列为EBFADHJCAIK3、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造一棵个字母设哈夫曼树并为这8计哈夫曼编码。哈夫曼树为（4分）：解答：（画错一个分支扣0.5分）10062193810303217721115623哈夫曼编码为（4分）：（画一个编码扣0.5分）0.07：1000.19：0010.02：000000.06：00010.32：010.03：000010.21：110.10：1014、试从空树开始，画出按以下次序向2-3树（即3阶B-数）插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后2-3树的状态。解答：顺序插入20，30，50，52，60，68，70的2-3树的状态分别为：（6分，画错一个状态扣0.5分）30302020302050205052523052305250306820506020606820506070删除50和68后2-3树的状态分别为：（2分，画错一个状态扣1分）52686052203070203060705.求出下图的最小生成树，并计算最小生成树的权值。e93b74f4356ad5255gch65解答：最小生成树为：（6分）e3bf4ad255gc43h最小生成树的权值为：26（2分）三、计算题（共10分）已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），假设哈希函数为H(key)keyMOD13，分别画出以线形探测再散列（存储空间为a[0..15]）和链地址法处理冲突的哈希表，并分别计算在记录查找等概率的条件下的平均查找长度。解答：（1）（4分）线形探测再散列存储结构为：0120179685512134567891011121314151920841323111014271221113等概率的条件下的平均查找长度=（1*7+2*3+3*2）/12=1.583（1分）（2）（4分）链地址法的存储结构为：0123456789^016879^55^^^^1920^84^^^102310^1111^1213^^14141527^^等概率的条件下的平均查找长度=（1*7+2*5）/12=1.417（1分）四、算法设计。算法描述可以采用类C语言并给出必要注释。（每题10分，共30分）1.试写一算法在带头节点的单链表上实现length(L)。解答：节点类型定义为（2分）typedefstructureLinkNode{ElemTypedata;LinkNodenext;}LinkNode,*LinkPoint;求单链表长度的算法为：（8分）intlength(LinkPoint{L)intLength=0;p;LinkPointp=L->next;while(!p){Length++;p=p->next;}returnLength;}2.试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线形表(a,a,,a)(a,a,,a)。n11逆置为12nn解答：节点类型定义为（2分）#defineMAXLENGTH100typedefstructureSqList{ElemTypea[MAXLENGTH];intLength;}SqList,数组逆置的算法为：（(8分）LA)statustraverlistSqList{for(i=0;i<LA.Length/2;i++)LA.a[i]LA.a[LA.Length–i-1]returnOK;}3、试以单链表为存储结构实现简单选择排序的算法。解答：节点类型定义为（typedefstructureLinkNode{ElemTypedata;2分）LinkNodenext;}LinkNode,*LinkPoint;简单选择排序的算法为：（8分）(L)带附加头节点statusSelectSortLinkListLinkPoint{//假设单链表intn=Length(l);//求单链表的长度p,q,t;LinkPointfor(i=1;i<n;i++){p=q=L->next;while(!q){q=q->next;;if(qdata<pdata)p=q;}//endwhi