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

武汉工业学院 2005 2006 学年第 1 学期期末考试试卷（A 卷）标准答案及评分标准课程名称 数据结构 课程编号 05110 一、填空题（每空 1 分，共 20 分）1. 四种类型的数据结构分别是： 表 、 树 、 图 和 集合 。2. 假设按低下标行优先存储整数数组 时，第一个元素的字节地址是 100，每个整数占57A四个字节，则 的存储地址是 100 ， 的存储地址是 168 。0a32a3. 在顺序表中插入或删除一个元素，平均需要移动 n/2 个元素，具体移动的元素个数与位置 有关。4. 二叉树的五种基本形态是 空树 、 只有根节点 、 根节点和左子树 根节点和右子树 和 根节点、左子树和右子树 。 （也可用图表示）5. 常用的有向图 5 种存储方法分别是 邻接表 、 逆邻接表、 十字链表 、邻接矩阵 和 多重邻接表 。6. 内部排序算法中的两种基本操作是 比较 和 交换 。二、简答题（每小题 8 分，共 40 分）1. 请给出以下有向图的：（1） 邻接矩阵； （2 分）（2） 邻接表；（2 分）（3） 从顶点 a 出发的深度优先遍历序列；（2 分）（4） 从顶点 e 出发的广度优先遍历序列；（2 分）aubecdfv解答：（1） 、邻接矩阵 01010101（2） （2 分）邻接表abcdefuv（3）abfvucde（其它符合规则的序列也可得分）（4）eufbvaca （其它符合规则的序列也可得分）2. 假设一棵二叉树的先序序列为 EBADCFHGIKJ 和中序序列为ABCDEFGHIJK，请画出该二叉树。解答：该二叉树为：（画错一个分支扣 0.5 分）EBADHACIFKJ3、假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造一棵哈夫曼树并为这8 个字母设计哈夫曼编码。解答：哈夫曼树为（4 分）：（画错一个分支扣 0.5 分）23561 107171930 2138326210哈夫曼编码为（4 分）：（画一个编码扣 0.5 分）0.07：100 0.32：010.19：001 0.03：000010.02：00000 0.21：110.06：0001 0.10：101b f d e v u f v c a b 4、试从空树开始，画出按以下次序向 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 分）2020 3 205030 2050 230205030 5260205030 5260 8205030 60706852删除 50 和 68 后 2-3 树的状态分别为：（2 分，画错一个状态扣 1 分）20 3607052 68 20 360 7525. 求出下图的最小生成树，并计算最小生成树的权值。a gbecdfh9435555 3765462解答：最小生成树为：（6 分）a gbecdfh435 3542最小生成树的权值为：26（2 分）三、计算题（共 10 分）已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79） ，假设哈希函数为 ，分别画出以线形探测再散列（存储空间13)(MODkeyH为 a015）和链地址法处理冲突的哈希表，并分别计算在记录查找等概率的条件下的平均查找长度。解答：（1） （4 分）线形探测再散列存储结构为： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1501 79 68 55 19 20 84 23 11 10 14 271 2 1 2 1 1 3 1 1 3 1 2等概率的条件下的平均查找长度=（1*7+2*3+3*2 ） /12=1.583（1 分）（2） （4 分）链地址法的存储结构为：0 1 012 3 684 5 6 197 20 8 9 10 2311 11 12 13 14 1415 等概率的条件下的平均查找长度=（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;84 27 55 10 79 while(!p)Length+;p=p-next; return Length;2. 试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线形表逆置为 。),(21na ),(1an解答：节点类型定义为（2 分）#define MAXLENGTH 100typedef structure SqList ElemType aMAXLENGTH;int Length; SqList,数组逆置的