西北工业99.doc

考研数据结构各个高校的考试习题

西北工业大学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 p<>NIL DO 
         BEGIN
   S.top:=s.top+1;
   IF S.top>maxsize THEN stackfull
   ELSE BEGIN S.data[S.top]:=p
           (1)_____________________;
END
END;
IF S.data[top]^.rchild<>NIL THEN  (2)_________________
ELSE BEGIN
      REPEAT
         Write (S.data[top]^.data);
      UNTIL S.top=0 or S.data[top]^.rchild<>S.data[S.top+1];
      IF S.data[top]^.rchild<> S.data[S.top+1];
      THEN (3)_________________;
UNTIL(4)______________________;
END
2.算术表达式求值的流程，其中OPTR为算术符栈，OPND2为操作数栈，precede(oper 1，oper2)是比较运算符优先级别的函数，operate(opnd1,oper,opnd2)为两操作数的运算结果。（#表示运算起始和终止符号）
   FUNCTION  exp_reduced:operandtype;
   INITSTACK(OPTR);PUsH(OPTR"#"INITSTACK(OPND);read(w)
   WHILE NOT((W='#") and (GETTOP(OPTR)='#'))DO
       IF w NOT in op then PUSH(OPND,w);
       ELSE CASE precede(GETTOP(OPTR),w)of
             '<':[(1)                    ;read(w0;);
             '=':[(2)                      ; read(w);];
             '>':[theta-POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)               ；]
   ENDC;
RETURN(GETTOP(OPND);
ENDF;
七、（10分）简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作（图的遍历，有向图的拓扑排序等）中有什么样的优越性？
八、（15分）遍历一棵二叉树的中序序列和后序序列分别为，中序BFDGAEHC，后序FGDBHCA，写出这棵二叉树的逻辑结构和存储结构，已知一棵二叉树的中序序列和后序序列分别由INO[1..n]和POST[1..n]数据存放，并且假定没有数据域值相同的结点，证明可由此生成一棵唯一的二叉树，并写出生成的算法。
九、（10分）考虑边界标志法的两种策略（最佳适配和首次适配）：
1． 数据结构的主要区别是什么？
2． 分配算法的主要区别是什么？
3． 回收算法的主要区别是什么？
要求写出相应的结构和核心算法。
十、（10分）考虑空间释放遵从“最后分配者最先释放”规则的动态存储管理问题，并且设每个空间申请中都指定所申请的空闲块大小。
1． 设计一个适当的数据结构实现动态存储管理；
2． 写一个为大小为n的空间申请分配存储块的算法；
3． 写一个回收释放块的算法。