北邮数据结构2001.doc

文档介绍：北邮2001年硕士研究生考试题(f)
(20分,每空2分):
:__________________;
,只有两种方法,它们是__________和___________;
3. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_____行,第_____列的元素。
‘ababaaab’的nextval函数值为__________;
;
,但在之前必须先生成___________;
,则在排序过程中,组要进行的两种基本操作是关键字的________和记录的_________;
三,简答(15分,每题5分);
特殊矩阵和系数矩阵哪一种压缩穿促后失去随机存取的功能? 为什么?
试问线索二叉树的目的何在?
3, 在多关键字排序时,LSD和MSD两种方法的特点是什么?
四,应用(25分,每题5分);
1,画出按下表中元素的顺序构造的平衡二叉排序树,并求其在等概率的情况下查找成功下的平均查找长度。(15, 12 ,24, 3, 27, 21, 18, 6,36,33,30,26,32);
2,假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的幅度分别为{,,,,,,,},
(1),为这7个字母统计哈夫曼编码;
(2)为这7个字母进行等长编码,至少需要几位二进制数?哈夫曼编码比等长编码使电文总长压缩多少?
3,试推导出总盘数为n的Hanoi塔的移动次数。
4,一棵满k叉树,按层次遍历存储在一维数组中,试计算结点下标的u的结点的第一个孩子的下标以及结点为v的结点的父母结点的下标;
5,有一图的邻接矩阵如下,试给出用弗洛伊德算