资源描述：
《数据结构 ( 第3次 )》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第3次作业一、填空题（本大题共30分，共10小题，每小题3分）1.栈是一种特殊的线性表，允许插入和删除运算的一端称为______。不允许插入和删除运算的一端称为______。2.二叉树由，，三个基本单元组成。3. 构造连通网最小生成树的两个典型算法是______。4.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。5.直接插入排序用监视哨的作用是_______。6.AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。7.已知指针p指向单链表L中的某结点，则删除其后继结
2、点的语句是________。8.一棵深度为6的满二叉树有______个分支结点和______个叶子。9.已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是。10.在哈希文件中，处理冲突的方法通常有______、______、______和______四种。二、算法设计题（本大题共20分，共2小题，每小题10分）1.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。2.设稀疏矩阵Mmxn中有t个非零元素，用三元组顺序表的
3、方式存储。请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O(n+t)。三、简答题（本大题共20分，共4小题，每小题5分）1.假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}. (1)为这8个字母设计哈夫曼编码。 (2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?2.若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列
4、均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。3. 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。4.给定集合{15,3,14,2,6,9,16,17}(1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树：(2)(2分)计算它的
5、带权路径长度：(3)（2分)写出它的huffman编码：(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。四、程序设计题（本大题共30分，共2小题，每小题15分）1.以二叉链表为存储结构，写出求二叉树叶子总数的算法2.设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入算法：InsertList答案：一、填空题（30分，共10题，每小题3分）1.参考答案：栈顶，栈底解题方案：评分标准：2.参考答案：根结点，左子树，右子树解题方案：评分标准：3.参考答案：普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法解题方案：评分标准：4.参考答
6、案：行号、列号、元素值解题方案：评分标准：5.参考答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。解题方案：评分标准：6.参考答案：(1)活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间解题方案：评分标准：7.参考答案：q=p->next;p->next=q->next;free(q);解题方案：评分标准：8.参考答案：n1+n2=0+n2=n0-1=31，26-1=32解题方案：评分标准：9.参考答案：DGEBFCA解题方案：评分标准：10.参考答案：开放地址法、再哈希法、链地址法、建立一个公共溢出区解题方案：评分标准：二、算法设计题（20分
7、，共2题，每小题10分）1.参考答案：将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。算法如下：#include#includetypedefintElemType;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList; voiddivide(LinkList&pa,
