|
希赛·研究生学院 2006 年网上辅导火热招生！
希赛网
北邮 2001 年硕士研究生考试题
（数据结构）
一、填空（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 分）；
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 的结点的父母结点的下标；
·研究生学院，http://master.csai.cn，0731-8662005-8000，kaoyan@csai.cn (第 1 页)
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
