b北邮数据结构n2001.docVIP

北邮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．右图中的强连通分量的个数为___________个； 6．外部排序的基本方法是归并排序，但在之前必须先生成___________； 7．若不考虑基数排序，则在排序过程中，组要进行的两种基本操作是关键字的________和记录的_________； 三，简答（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}中的字母构成。它们在电文中出现的幅度分别为{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，有一图的邻接矩阵如下，试给出用弗洛伊德算法求各 序为A1，A2，A3，A4； 0 2 ∞ ∞ ∞ 0 1 6 A= 5 ∞ 0 4 3 ∞ ∞ 0 五，算法（30分，每题10分）； 在单链表中，每个结点含有5 个正整型的 数据元素（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n0）的数据元素所在的结点指针以及在该结点中的序号，落链表中不存在该数据元素则还回空指针； 将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线形探测法处理冲突（H（key+1，H（key）+2…H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找，INSERT，和删除三个基本操作算法； 给出算法将二叉树表示的表达式二叉树按 中缀表达式输出，并加上相应的括号。