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

-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有---------------------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有--------------武汉工业学院2005–2006学年第1学期期末考试试卷（A卷）标准答案及评分标准课程名称数据结构课程编号05110一、填空题（每空1分，共20分）1.四种类型的数据结构分别是：表、树、图和集合。2.假设按低下标行优先存储整数数组时，第一个元素的字节地址是100，每个整数占四个字节，则的存储地址是100，的存储地址是168。3.在顺序表中插入或删除一个元素，平均需要移动n/2个元素，具体移动的元素个数与位置有关。4.二叉树的五种基本形态是空树、只有根节点、根节点和左子树根节点和右子树和根节点、左子树和右子树。（也可用图表示）5.常用的有向图5种存储方法分别是邻接表、逆邻接表、十字链表、邻接矩阵和多重邻接表。6.内部排序算法中的两种基本操作是比较和交换。二、简答题（每小题8分，共40分）请给出以下有向图的：邻接矩阵；（2分）邻接表；（2分）从顶点a出发的深度优先遍历序列；（2分）从顶点e出发的广度优先遍历序列；（2分）解答：（1）、邻接矩阵（2）（2分）邻接表abb^bff^cdd^dv^v^eeufuf^fvv^ua^a^cvbb^（3）abfvucde（其它符合规则的序列也可得分）（4）eufbvaca（其它符合规则的序列也可得分）2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该二叉树。解答：该二叉树为：（画错一个分支扣0.5分）3、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造一棵哈夫曼树并为这8个字母设计哈夫曼编码。解答：哈夫曼树为（4分）：（画错一个分支扣0.5分）哈夫曼编码为（4分）：（画一个编码扣0.5分）0.07：100 0.32：010.19：001 0.03：000010.02：00000 0.21：110.06：0001 0.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分） 删除50和68后2-3树的状态分别为：（2分，画错一个状态扣1分） 5.求出下图的最小生成树，并计算最小生成树的权值。解答：最小生成树为：（6分）最小生成树的权值为：26（2分）三、计算题（共10分）已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），假设哈希函数为，分别画出以线形探测再散列（存储空间为a[0..15]）和链地址法处理冲突的哈希表，并分别计算在记录查找等概率的条件下的平均查找长度。解答：（1）（4分）线形探测再散列存储结构为：0123456789101112131415017968551920842311101427121211311312等概率的条件下的平均查找长度=（1*7+2*3+3*2）/12=1.583（1分）（2）（4分）链地址法的存储结构为：0^1017979^2^3685555^4^5^6198484^720^8^9^10231010^1111^12^13^14142727^15^等概率的条件下的平均查找长度=（1*7+2*5）/12=1.417（1分）四、算法设计。算法描述可以采用类C语言并给出必要注释。（每题10分，共30分）1.试写一算法在带头节点的单链表上实现length(L)。解答：节点类型定义为（2分）typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;求单链表长度的算法为：（8分）intlength(LinkPointL){intLength=0;LinkPointp; p=L->next;while(!p){Length++;p=p->next;} returnLength;}2.试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线形表逆置为。解答：节点类型定义为（2分）#defineMAXLENGTH100typedefstructureSqList{ElemTypea[MAXLENGTH];intLength;}SqList,数组逆置的算法为：（8分）statustraverlist(SqListLA){for(i=0;i<LA.Length/2;i++)LA.a[i]LA.a[LA.Length–i-1] returnOK;}3、试以单链表为存储结构实现简单选择排序的算法。解答：节点类型定义为（2分）typedefstructureLinkNode{ElemTypedata;LinkNodenext; }LinkNode,*LinkPoint;简单选择排序的算法为：（8分）statusSelectSortLinkList(LinkPointL){//假设单链表带附加头节点intn=Length(l);//求单链表的长度LinkPointp,q,t;for(i=1;i<n;i++){p=q=L->next;while(!q){q=q->next;;if(qdata<pdata)p=q;}//endwhile pp=GetElement(L,&q);//在链表L中，获取q指向的节点，