北邮2001年硕士研究生考试题(f)
二．填空（20分，每空2分）：
1．数据的逻辑结构是指：__________________；
2．区分循环队列的满与空，只有两种方法，它们是__________和___________;
3. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i 2),B中的第8个元素是A 中的第_____行，第_____列的元素。
4．字符串‘ababaaab’的nextval函数值为__________；
5．右图中的强连通分量的个数为___________个；</IMG>
6．外部排序的基本方法是归并排序，但在之前必须先生成___________；
7．若不考虑基数排序，则在排序过程中，组要进行的两种基本操作是关键字的________和记录的_________；
三，简答（15分，每题5分）；
1，特殊矩阵和系数矩阵哪一种压缩穿促后失去随机存取的功能？ 为什么？
2，试问线索二叉树的目的何在？
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}中的字母构成。它们在电文中出现的幅度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},
(1),为这7个字母统计哈夫曼编码；
（2）为这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？
3，试推导出总盘数为n的Hanoi塔的移动次数。
4，一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标的u的结点的第一个孩子的下标以及结点为v的结点的父母结点的下标；
5，有一图的邻接矩阵如下，试给出用弗洛伊德算法求各
</IMG>
五，算法（30分，每题10分）；
1，在单链表中，每个结点含有5 个正整型的 数据元素（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，落链表中不存在该数据元素则还回空指针；
2，将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线形探测法处理冲突（H（key 1，H（key） 2…H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找，INSERT，和删除三个基本操作算法；
3，给出算法将二叉树表示的表达式二叉树按 中缀表达式输出，并加上相应的括号。