Noip初赛复习指南、题目分类解析(7)

sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; for i:=4 to 7 do g[1,i]:=tree[1,i-2]; while__________①_________do begin

p:=g[sp1,2];n2:=g[sp1,3];_________②________;j:=4; while _________③_________do begin

n1:=g[sp1,j];j:=j+1;__________④_________; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1; for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1]; end;

__________⑤_________; end;

writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0; for i:=2 to sp2 do

if __________⑥__________then j:=j+1 else begin

if j>jmax then jmax:=j;

__________⑦________;k:=g[Ｉ,2]; end; if j>jmax then jmax:=j; writeln('max1=',jmax); end. 解答：

1） 本题的数据结构含义，首先要搞清楚：tree[i,j]存储编号为i的结点的第j号孩子（2<=j<=5,即

最多4个孩子），tree[i,j]=0表示不存在；g[i,k]是一个队列，sp1为读取队列用的指针,sp2为存储队列用的指针。g[i,1] 存储i的父结点，g[i,2]存储i所在的层次，g[i,3]存储本结点的编号i，g[i,4],g[i,5],g[i,6],g[i,7]存储i的孩子结点编号。列出g的表格形式，以便更加直观！！！ 2） 程序关键在红色和蓝色的两段。先看红色段，①显然表示队列非空时做??，所以应该填：sp1<=sp2；

变量p是用来存放层次的，所以②填：p:=p+1；为该结点的孩子结点准备好层次；n2是表示当前处理的结点号，n1是表示n2的孩子结点号(用j循环)，③这个地方的循环是为了遍历本结点的所有孩子，所以③填：g[sp1,j]<>0；那么④⑤干什么呢？不要忘记一个重要的事情，队列的读取都需要移动指针（sp1,sp2），所以正好，④为下面的存入操作作准备，即sp2:=sp2+1;⑤为下一个结点的遍历操作作准备，即读指针下移：sp1:=sp1+1；

3） 下面看看蓝色的程序段，目的很明显是为了输出。再注意题目的目的：输出树的宽度和深度！深度

简单，其实就是g[sp2,2]。题目也没有考你！！！那么剩下的问题显然就是为了求宽度。方法也很简单，就是求每一层的宽度（即g[I,4]~g[I,7]中的非0个数，或者按本题的方法是看g[I,2]中最多有几个数相同），然后打擂台找出最大值。因此，⑥填：g[I,2]=k，计算层次相同的元素个数放在j中，用j与jmax打擂台，注意一层完了，j值要还原，宽度至少为1,所以⑦填：j:=1；

（2000年高中组试题）问题与上一样，只是写程序的人不一样，具体的风格不同而已。

小结：本题其实很重要的是队列的操作，经常出现的还有：堆栈操作、模拟法（解决递归等问题的现场保护和恢复）。

31

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Noip初赛复习指南、题目分类解析(7)在线全文阅读。