第 3 次作业一、填空题（本大题共 30 分，共 10 小题，每小题 3 分）栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和删除运算的一端称为 。二叉树由 ， ， 三个基本单元组成。构造连通网最小生成树的两个典型算法是。在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三项。直接插入排序用监视哨的作用是。 网中结点表示边表示。 网中结点表示边表示。已知指针  指向单链表  中的某结点，则删除其后继结点的语句是。 解题方案：评分标准：三、简答题（20 分，共 4 题，每小题 5 分）参考答案：（）哈夫曼编码OQP根据上图可得编码表：　　　R　　　R　　　'R　　　(R　　　)R　　　*R　　　+R　　　,R　　（）用三位二进行数进行的等长编码平均长度为 ，而根据哈夫曼树编码的平均码长为：C$C$C$C$C$C$C$CFBFFS其平均码长是等长码的 S，所以平均压缩率为S。解题方案：评分标准：参考答案：#%已知二叉树的前序序列为 01 和中序序列 01，则可以根据前序序列找到根结点为 ，由此，通过中序序列可知它的两棵子树包分别含有 0 和 1 结点，又由前序序列可知  和  分别为两棵子树的根结点以此类推可画出所有结点： ○BT○○BBT○○○BTB○○0○1#%以同样的方法可画出该二叉树：○BT○○TT○○BTT○○○0#%这两棵不同的二叉树为：○○BT○○ 解题方案：评分标准：参考答案：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。　　这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。　　在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。解题方案：评分标准：参考答案：（）OQP（）I:F#$%C$C$#$$%C$#$%CF（）编码为：RRRRRRRR#%常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。解题方案： 评分标准：四、程序设计题（30 分，共 2 题，每小题 15 分）参考答案：!?)()*',6!@?)ABB定义 !@?) 类型　!?)()*5!62'! =()&　　　　!@?)(!A　　　　5!62'! =()C:',7:(C6',7:(ABB左右孩子子树　　-7 @"=()ABB结点类型!?)()*7 @"=()C7 @6))ABB二叉树类型 7 !)*#7 @6))@%　　&BB算叶子数　　　7*#@%　　　　7*#@4>:',7:(FF"H%EE#@4>6',7:(FF"H%　　　　　6)!26 A　　　　):5)6)!26 )*#@4>:',7:(%$"=()#@4>6',7:(%A　　　):5)6)!26 A　　-解题方案：评分标准：参考答案：;()U )75!L7G)BB假定表空间大小为 !?)()*7 !!@?)ABB假定 !@?) 的类型为 7 ! 型!?)()*5!62'!&!@?)(!O75!L7G)PABB向量 (! 用于存放表结点7 !:) +!,ABB当前的表长度 -L)K:75!ABB以上为定义表结构D=7(1 5)6!75!#L)K:75!C!!?)7 !7%&BB将新结点  插入  所指的顺序表的第 7 个结点 7 的位置上，即插入的合法位置为：<F7<F4>:) +!,7 !NA7*#7<VV7>4>:) +!,%66=6#W=57!7= )66=6W%ABB非法位置，退出，该函数定义见教材 Q7*#4>:) +!,>F75!L7G)%66=6#X=D)6Y=IW%A*=6#NF4>:) +!,4AN>F7AN44%4>(!ON$PF4>(!ONPA4>(!O7PFA4>:) +!,$$A-解题方案：评分标准： 一棵深度为  的满二叉树有个分支结点和个叶子。已知二叉树前序为 ，中序为 ，则后序一定是 。在哈希文件中，处理冲突的方法通常有、、和四种。二、算法设计题（本大题共 20 分，共 2 小题，每小题 10 分）编写一个算法将一个头结点指针为  的单链表  分解成两个单链表  和，其头结点指针分别为  和 ，使得  链表中含有原链表  中序号为奇数的元素，而链表  中含有原链表  中序号为偶数的元素，且保持原来的相对顺序。设稀疏矩阵  中有 ! 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵  的转置矩阵 "，要求转置算法的时间复杂度为 # $!%。三、简答题（本大题共 20 分，共 4 小题，每小题 5 分）假设用于通信的电文由字符集&'()*+,-中的字母构成，这  个字母在电文中出现的概率分别为&-#%为这  个字母设计哈夫曼编码。#%若用这三位二进制数#.%对这  个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几/它使电文总长平均压缩多少/ 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。#%已知一棵二叉树的前序序列和中序序列分别为 01 和01，请画出此二叉树。#%已知一棵二叉树的在序序列和后序序列分别为 0 和0，请画出此二叉树。#%已知一棵二叉树的前序序列和后序序列分别为  和 ，请画出这两棵不同的二叉树。 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 给定集合&-#%（ 分）用□表示外部结点，用○表示内部结点，构造相应的 ,23 树：#%# 分%计算它的带权路径长度：#%（ 分%写出它的 ,23 编码：#%（ 分%,23 编码常用来译码，请用语言叙述写出其译码的过程。四、程序设计题（本大题共 30 分，共 2 小题，每小题 15 分）以二叉链表为存储结构，写出求二叉树叶子总数的算法 设线性表的 个结点定义为# 4%，重写顺序表上实现的插入算法：1 5)6!75! 答案：一、填空题（30 分，共 10 题，每小题 3 分）参考答案：栈顶，栈底解题方案：评分标准：参考答案：根结点，左子树，右子树解题方案：评分标准：参考答案：普里姆（67）算法和克鲁斯卡尔（86259:）算法解题方案：评分标准：参考答案：行号、列号、元素值解题方案：评分标准： 参考答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。解题方案：评分标准：参考答案：#%活动（）活动间的优先关系（）事件（）活动边上的权代表活动持续时间解题方案：评分标准：参考答案：q=p->next; p->next=q->next; free(q);解题方案：评分标准：参考答案：n1+n2=0+ n2= n0-1=31，26-1 =32解题方案：评分标准：参考答案： 解题方案：评分标准：参考答案：开放地址法、再哈希法、链地址法、建立一个公共溢出区解题方案：评分标准：二、算法设计题（20 分，共 2 题，每小题 10 分）参考答案：将单链表  中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表 。算法如下： ;7 ':2()<5!(7=,>;7 ':2()<::=',>!?)()*7 !:)@?)A!?)()*5!62'!"=()&:)@?)(!ABB数据域5!62'!"=()C )!ABB指针域-"=()C7 975!A D=7((7D7()#7 975!E7 975!E%&F#"=()C%::='#57G)=*#"=()C%%A4> )!F"HA6FAF4> )!AI,7:)#JF"HEE4> )!JF"H%&KF4> )!A7*#KJF"H%&4> )!FK4> )!A64> )!FKA6FKAF4> )!A--64> )!F"HA-解题方案： 评分标准：参考答案：转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序。这种方法时间复杂度是 # C!%，当 ! 和 C 同量级时，时间复杂度为 # %。另一种转置方法称作快速转置，使时间复杂度降为 #C %。需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，因此设置了两个附加向量。下面分别给出两个算法。@L!67@6 5!67#@L!67@L!67"%&M采用三元组表方式存储，按列序实现矩阵的转置"F A" FA":) F:) AM行数、列数和非零元素个数7*#":) %&K＝:AM设置 " 中第一个非零元素从下标  开始存储*=6#N＝AN＜＝ AN$$%M按列，共  列*=6#＝A＜＝:) A$$%M在 :) 个元素中查找7*#(!OP'=:FFN%M转置&"(!OKP6=IF(!OP'=:A"(!OKP'=:F(!OP6=IA"(!OKP)F(!OP)AK$$A--6)!26 "A -M@6 5!67@L!675!@6 5!67#@L!67@L!67"%&M三元组表上实现矩阵的快速转置的算法"F A" FA":) F:) A7*#:) %&*=6#NFAN<F AN$$% 2ONPFAM矩阵  每一列非零元初始化为零 *=6#!FA!<F:) A!$$% 2O(!O!P'=:P$$AM求矩阵  每一列得非零元个数=5OPFAM第  列第一个非零元在转置后的三元组中下标是 *=6#NFAN<F AN$$%M求 (! 第 N 列第一个非零元在 "(! 中的序号=5O'=:PF=5O'=:4P$ 2O'=:4PA*=6#FA<F:) A$$%M求转置矩阵 " 的三元组表&NF(!OP'=:AKF=5ONPA"(!OKP6=IF(!OP'=:A"(!OKP'=:F(!OP6=IA"(!OKP)F(!OP)A=5ONP$$AM同列下一非零元素位置--6)!26 "A-