1、第 3次作业 一、填空题（本大题共 30 分，共 10 小题，每小题 3 分） 1. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 _ 。不允许插入和删除运算的一端称为 _ 。 2. 二叉树由 ， ， 三个基本单元组成。 3. 构造连通网最小生成树的两个典型算法是 _。 4. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 _、_和 _三项。 5. 直接插入排序用监视哨的作用是 _。 6. AOV网中 ,结点表示 _,边表示 _。 AOE网中 ,结点表示 _,边表示_。 7. 已知指针 p指向单链表 L中的某结点，则删除其后继结点的语句是 _。 8. 一棵深度为 6的满二叉树有
2、 _个分支结点和 _个叶子。 9. 已知二叉树前序为 ABDEGCF，中序为 DBGEACF，则后序一定是 。 10. 在哈希文件中，处理冲突的方法通常有 _、 _ 、 _和 _四种。 二、算 法设计题（本大题共 20分，共 2 小题，每小题 10 分） 1. 编写一个算法将一个头结点指针为 pa的单链表 A分解成两个单链表 A和B，其头结点指针分别为 pa和 pb，使得 A链表中含有原链表 A中序号为奇数的元素，而链表 B中含有原链表 A中序号为偶数的元素，且保持原来的相对顺序。 2. 设稀疏矩阵 Mmxn中有 t个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵 M的转置矩阵
3、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)若用这三位二进制数 (07) 对这 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. 参考答案： 普里姆
6、（ prim）算法和克鲁斯卡尔（ Kruskal）算法 解题方案： 评分标准： 4. 参考答案： 行号、列号、元素值 解题方案： 评分标准： 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. 参
7、考答案： DGEBFCA 解题方案： 评分标准： 10. 参考答案： 开放地址法、再哈希法、链地址法、建立一个公共溢出区 解题方案： 评分标准： 二、算法设计题（ 20 分，共 2 题，每小题 10 分） 1. 参考答案： 将单链表 A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表 B。算法如下： #include #include typedef int ElemType; typedef struct LNode ElemType data; /数据域 struct LNode *next; /指针域 LNode,*LinkList; void divide(LinkL
8、ist pb-next=NULL; r=pb; p=pa-next; while(p!=NULL if(q!=NULL) p-next=q-next; r-next=q; r=q; p=p-next; r-next=NULL; 解题方案： 评分标准： 2. 参考答案： 转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序。这种方法时间复杂度是 O(n*t)，当 t和 m*n同量级时，时间复杂度为 O(n3)。另一种转置方法称作快速转置，使时间复杂度降为 O(m*n)。需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，因此设置了两个附加向量。下面分别给出两个算法。
9、 TSMatrixTransMatrix(TSMatrixM,TSMatrix N) 采用三元组表方式存储，按列序实现矩阵的转置 N.m=M.n; N.n=M.m; N.len=M.len; 行数、列数和非零元素个数 if(N.len)q l; 设置 N中第一个非零元素从下标 1开始存储 for(j 1;j M.n;j+) 按列，共 M.n列 for(p 1;p M.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;
10、q+; return N; TransMatrix TSMatrixFastTransMatrix(TSMatrix M, TSMatrix N) 三元组表上实现矩阵的快速转置的算法 N.m=M.n; N.n=M.m; 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.
11、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.dataq.col=M.datap.row; N.dataq.e=M.datap.e; posj+; 同列下一非零元素位置 return N; 解题方案： 评分标准： 三、简答题（ 20 分，共 4 题，每小题 5 分） 1. 参考答案： （ 1）哈夫曼编码 P_47E42CBBE4BEF0B3804EEA501687A04A 根据上图 可得编码表： a:100
12、1 b:01 c:10111 d:1010 e:11 f:10110 g:00 h: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.10=2.61 2.61/3=0.87=87%其平均码长是等长码的 87%，所以平均压缩率为 13%。 解题方案： 评分标准： 2. 参考答案： (1)已知二叉树的前序序列为 ABDGHCEFI 和中序序列 GDHBAECIF，则可以根据前序序列找到根结点为 A，由此，通过中序序列可知它的两棵子树包分别含有 GDHB和 ECIF结点，又由前序序列可知 B 和 C分别为两棵子树的根结点 .以此类推可画出所有结点：
