|
第3次作业
一、填空题（本大题共30分，共 10 小题，每小题 3 分）
1. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 ______ 。不允许插入和删除运算的一端称为 ______ 。
2.
二叉树由 ， ， 三个基本单元组成。
3.
构造连通网最小生成树的两个典型算法是______。
4.
在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。
5.
直接插入排序用监视哨的作用是_______。
6.
AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。
7.
已知指针p指向单链表L中的某结点，则删除其后继结点的语句是________。
8.
一棵深度为6的满二叉树有______个分支结点和______个叶子。
9.
已知二叉树前序为ABDEGCF，中序为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.
假设用于通信的电文由字符集{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.
若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。 (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分，共 2 小题，每小题 15 分）
1.
以二叉链表为存储结构，写出求二叉树叶子总数的算法
2.
设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入算法：InsertList
答案：
| 
