|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
西北工业大学 99 年数据结构试题
LBHIDDEN[0]LBHIDDEN 西北工业大学 99 考研题
一．（15 分）请给出下列概念或术语的解释。
1．广义表
2．平衡因子
3．平均查找长度（ASL）
4．伙伴空间
5．AOE-网的关键路径
二．（8 分）简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂
度和排序稳定性上的差别。
三．（8 分）一个循环队列的数据结构描述如下：
TYPE seuueuetp=RECORD
elem：ARRAY[1。。maxsize] OF elemtp；
Front，rear：0。。maxize；
END；
给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影
响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？
四．（10 分）试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，
检索，插入，删除记录时的优点和缺点。
五．（10 分）一个深度为 L 的满 K*树有以下性质：第 L 层的结点都是叶子结点，其余各层
上么个结点都有 K 棵非空子树，如果按层次顺序从 1 开始对全部结点进行编号，求：
1． 各层的结点的数目是多少？
2． 编号为 n 的结点的双亲结点（若存在）的编号是多少？
3． 编号为 n 的结点的第 i 个孩子结点（若存在）的编号是多少？
4． 编号为 n 的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？
请给出计算和推导过程。
六．（14 分）阅读下列算法的类 PASCAL 描述，根据算法的要求，对相应的空格处写出正确
合理的语句。
1． 后序遍历二*树的非递归算法，bt 是二*树的根，S 是一个栈，maxsize 是栈的最大容量。
TYPE bitreptr=^bnodetp;
bitreptr=RECORD
data:datatype;
lchild,rchild:bitreptr
END;
TYPE stacktyp=RECORD
data:ARRAY[1„maxsize] OF bitreptr；
top：0„maxsize；
END；
PROCEDURE posterorder（be：bitreptr）；
BEGIN
S．Top：=0；p：=bt；
REPEAT
WHILE pNIL DO
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
