期末考试试卷（A卷）标准答案及评分标准.doc
武汉工业学院 2005 2006 学年第 1学期期末考试试卷（A卷）标准答案及评分标准课程名称 数据结构 课程编号 05110 一、填空题（每空1分，共20分）1. 四种类型的数据结构分别是： 表 、 树 、 图 和 集合 。2. 假设按低下标行优先存储整数数组时，第一个元素的字节地址是100，每个整数占四个字节，则的存储地址是 100 ，的存储地址是 168 。3. 在顺序表中插入或删除一个元素，平均需要移动 n/2 个元素，具体移动的元素个数与 位置 有关。4. 二叉树的五种基本形态是 空树 、 只有根节点 、 根节点和左子树 根节点和右子树 和 根节点、左子树和右子树 。（也可用图表示）5. 常用的有向图5种存储方法分别是 邻接表 、 逆邻接表、 十字链表 、 邻接矩阵 和 多重邻接表 。6. 内部排序算法中的两种基本操作是 比较 和 交换 。二、简答题（每小题8分，共40分）1. 请给出以下有向图的：（1） 邻接矩阵； （2分）（2） 邻接表；（2分）（3） 从顶点a出发的深度优先遍历序列；（2分）（4） 从顶点e出发的广度优先遍历序列；（2分）解答：（1）、邻接矩阵（2）（2分）邻接表ab bfcddveeuffvuacvb（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：1000.32：010.19：0010.03：000010.02：000000.21：110.06：00010.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），假设哈希函数为，分别画出以线形探测再散列（存储空间为a0.15）和链地址法处理冲突的哈希表，并分别计算在记录查找等概率的条件下的平均查找长度。解答：（1）（4分）线形探测再散列存储结构为： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15017968551920842311101427 1 2 1 2 1 1 3 1 1 3 1 2等概率的条件下的平均查找长度=（1*7+2*3+3*2）/12=1.583（1分）（2）（4分）链地址法的存储结构为：0 101792368554561984720891023101111121314142715等概率的条件下的平均查找长度=（1*7+2*5）/12=1.417（1分）四、算法设计。算法描述可以采用类C语言并给出必要注释。（每题10分，共30分）1. 试写一算法在带头节点的单链表上实现length(L)。解答：节点类型定义为（2分）typedef structure LinkNode ElemType data ;LinkNode next; LinkNode,*LinkPoint; 求单链表长度的算法为：（8分） int length(LinkPoint L) int Length=0; LinkPoint p; p=L->next;while(!p) Length+; p=p->next; return Length; 2. 试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线形表逆置为。解答：节点类型定义为（2分）#define MAXLENGTH 100typedef structure SqList ElemType aMAXLENGTH;int Length; SqList, 数组逆置的算法为：（8分） status traverlist(SqList LA) for(i=0;i< LA. Length/2;i+) LA.aißà LA.aLA. Length i-1 return OK; 3、试以单链表为存储结构实现简单选择排序的算法。解答：节点类型定义为（2分）typedef structure LinkNode ElemType data ;LinkNode next; LinkNode,*LinkPoint; 简单选择排序的算法为：（8分） status SelectSortLinkList(LinkPoint L)/假设单链表带附加头节点 int n= Length(l);/求单链表的长度 LinkPoint p,q,t; for(i=1;i<n;i+) p=q=L->next;while(!q) q=q->next; if(qàdata<pàdata) p=q; /end while pp=GetElement(L,&q);/ 在链表L中，获取q指向的节点，用pp/指向该节点，并将该节点从链表L中删除AppList(LinkPoint &t, pp)；/ 将指向的节点插入到链表t的最后/end for L->next=t; return OK; / end SelectSortLinkList
