《数据结构 ( 第3次 )讲解》由会员分享，可在线阅读，更多相关《数据结构 ( 第3次 )讲解（14页珍藏版）》请在金锄头文库上搜索。
1、第3次作业一、填空题（本大题共30分，共 10 小题，每小题 3 分）1. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 _ 。不允许插入和删除运算的一端称为 _ 。2. 二叉树由 ， ， 三个基本单元组成。3. 构造连通网最小生成树的两个典型算法是_。4. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_、_和_三项。5. 直接插入排序用监视哨的作用是_。6. AOV网中,结点表示_,边表示_。AOE网中,结点表示_,边表示_。7. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是_。8. 一棵深度为6的满二叉树有_个分支结点和_个叶子。9. 已知二叉树前序为ABD
2、EGCF，中序为DBGEACF，则后序一定是 。10. 在哈希文件中，处理冲突的方法通常有_、_ 、_和_四种。二、算法设计题（本大题共20分，共 2 小题，每小题 10 分）1. 编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。2. 设稀疏矩阵Mmxn中有t个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O(n+t)。三、简答题（本大题共20分，共 4 小题，每小题 5 分）1.
3、假设用于通信的电文由字符集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)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?2. 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBA
4、ECIF，请画出此二叉树。 (2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。3. 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 4. 给定集合15,3,14,2,6,9,16,17(1)（3分）用表示外部结点，用表示内部结点，构造相应的huffman树：(2) (2分)计算它的带权路径长度：(3)（2分)写出它的huffman编码：(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。四、程序设计题（本大题共30分
5、，共 2 小题，每小题 15 分）1. 以二叉链表为存储结构，写出求二叉树叶子总数的算法 2. 设线性表的n个结点定义为(a0,a1,.an-1)，重写顺序表上实现的插入算法：InsertList 答案：一、填空题（30分，共 10 题，每小题 3 分）1. 参考答案：栈顶，栈底解题方案：评分标准：2. 参考答案：根结点，左子树，右子树解题方案：评分标准：3. 参考答案：普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法解题方案：评分标准：4. 参考答案：行号、列号、元素值解题方案：评分标准：5. 参考答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。解题方案：评分标
6、准：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分，共 2 题，每小题 10 分）1. 参考答案：将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。
7、算法如下： #include#includetypedef int ElemType;typedef struct LNodeElemType data; /数据域struct LNode *next; /指针域 LNode,*LinkList;void divide(LinkList&pa, LinkList&pb) pb=(LNode *)malloc(sizeof(LNode *); pb-next=NULL; r=pb; p=pa-next; while(p!=NULL & p-next!=NULL) q=p-next; if(q!=NULL) p-next=q-next; r-nex
8、t=q; r=q; p=p-next; r-next=NULL; 解题方案：评分标准：2. 参考答案：转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序。这种方法时间复杂度是O(n*t)，当t和m*n同量级时，时间复杂度为O(n3)。另一种转置方法称作快速转置，使时间复杂度降为O(m*n)。需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，因此设置了两个附加向量。下面分别给出两个算法。TSMatrixTransMatrix(TSMatrixM,TSMatrix N)采用三元组表方式存储，按列序实现矩阵的转置N.m=M.n; N.n=M.m; N.len=M.l
9、en; 行数、列数和非零元素个数 if(N.len)ql; 设置N中第一个非零元素从下标1开始存储for(j1;jM.n;j+) 按列，共M.n列 for(p1;pM.len; +p) 在M.len个元素中查找 if(M.datap.col=j) 转置N.dataq.row=M.datap.col;N.dataq.col=M.datap.row;N.dataq.e=M.datap.e; q+; return N;TransMatrixTSMatrixFastTransMatrix(TSMatrix M, TSMatrix N)三元组表上实现矩阵的快速转置的算法N.m=M.n; N.n=M.m;
10、 N.len=M.len;if(M.len) for(j=1;j=M.n;j+) numbj=0; 矩阵M每一列非零元初始化为零 for(t=1;t=M.len;t+)numbM.datat.col+;求矩阵M每一列得非零元个数pos1=1; 第1列第一个非零元在转置后的三元组中下标是1 for(j=2;j=M.n;j+) 求M.data第j列第一个非零元在N.data中的序号poscol=poscol-1+numcol-1; for(p=1;p=M.len;p+)求转置矩阵N的三元组表 j=M.datap.col; q=posj;N.dataq.row=M.datap.col; N.data
11、q.col=M.datap.row;N.dataq.e=M.datap.e; posj+; 同列下一非零元素位置 return N;解题方案：评分标准：三、简答题（20分，共 4 题，每小题 5 分）1. 参考答案：（1）哈夫曼编码 P_47E42CBBE4BEF0B3804EEA501687A04A 根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000（2）用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.
12、10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。解题方案：评分标准：2. 参考答案：(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点：A / B C / / D EF / /G H I (2)以同样的方法可画出该二叉树：A / B F C G / D E H (3)这两棵不同的二叉树为：A A / B B 解题方案：评分标准：3. 参考答案：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和
