当前位置：问答库＞考研试题

北京轻工业学院1997

一．是编写算法求出二叉树的深度

二叉树的存储结构为如下说明的二叉链表:

type btre=^bnode

bnode=record

data:datatype;

lch,rch:btre

end;

二．试写一个在线索化了的二叉树中，查找给定结点在后续后继线索化中的后继算法，并指

出实现算法对存储结构有何要求。（二叉树根节点为给出）

三．已知关键字序列：

22,12,13,8,9,20,33,42,44,38,24,48,60. 画出相对应的平衡二叉树，并删除13，给出相应的指针变化。（删除时，已知13结点指针p,13双亲接点指针fp^）.

四．对图示的AOE 网络，计算各活动弧的e(ai ) 和l(ai ) 的函数值，列出各条关键路径。

五．假设有向图以邻接表存储，是编写算法删除弧的算法。

邻接表存储结构如下：

type arcptr=^arcnode;

arcnode=record

adjvex:1..vtxptr;

nextarc:arcptr;

end;

vexnode=record

vexdata:datatype;

firstarc:arcptr

end;

orthlist=array[vtxptr] of vexnode;

六．是从空树开始，画出按以下次序向2-3树中插入关键字的建树过程：20,30,50,52,60,68,70.

如果以后在删除50和68，画出每一步执行后2-3树的状态。

七．判断以下序列是否为堆，如果不是，则把它调整为堆。

1）(100,86,48,73,35,39,42,57,66).

2) (12,70,33,65,24,56,48,92,86).

八．试编写算法，在根结点指针为t 的m-阶B 树上查找关键字k, 返回纪录(pt,I,tag).

若查找成功，则特征tag=1,等于k 的关键字即为指针pt 所指结点中的第I 个关键字；若查找不成功，则特征位tag=0，等于k 的关键字应插入到指针pt 所指结点中第i 个和第i+1个关键字之间