历届奥赛试题解析-初赛讲解(9)

省淳中信息学奥赛辅导 奥赛试题解析

BCAEDF

输出：___55____ 【分析】 【1.状态描述】

（1）left[i], right[i], father[i]分别记录第s1中第i个点的左右子树编号、父节点

编号

（2）S1是先序字符串，S2是中序序字符串 【2.算法分析】

（1）根据第一个输入的字符串通过深度搜索先序构建一棵二叉树

（2）再中序遍列这棵树得到的字符串再与第二个输入的字符串比较，如果相等则表示构建的

二叉树正确，否则要回溯

（3）left[i], right[i], father[i]分别记录第s1中第i个点的左右子树编号、父节点编号

【3.算法设计】深度搜索先序构建一棵二叉树

1.初始状态：以第s1[1]字符为根，s1[2]作为它的子树

2. 状态转移：以第s1[x]字符为根，s1[th]作为它的子树，先左后右

procedure dfs(x,th :integer); begin

1. 终结状态判断:s1中所有的字符已加入到树中，中序遍列树是否正确 if th = n+1 then

begin

check(1); //中序遍列生成的树，遍列结果放入s3中

end;

2. 试探各种可能——s1[th]先作为s1[x]的左子树，如果不正确回溯再作为其右子树 3. 修改状态：x的左为ch, ch的父为x ：

left[x] := th; father[th] := x;

4. 深度搜索下一个字符：以ch为根，s1[ch+1]为其子树：

dfs(th, th+1);

5. 回溯，s1[th]不是s1[x]的左子树 father[th] := 0; left[x] := 0; 6. 尝试s1[th]作为s1[x]的右子树：…………

end;

41

省淳中信息学奥赛辅导 奥赛试题解析

五、完善程序（第1题第2空3分，其余每空2.5分，共计28分）

2．(新壳栈)小Z设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹

出操作。此外，其栈顶的前c个元素是它的壳，支持翻转操作。其中，c>2是一个固定的正整数，表示壳的厚度。小Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足c个，应当输出相应的错误信息。

const NSIZE = 100000;

42

省淳中信息学奥赛辅导 奥赛试题解析

CSIZE = 1000;

n,c,r,tail,head :longint; s : array[1..NSIZE] of longint; //数组s模拟一个栈，n为栈的元素个数 q :array[1..CSIZE] of longint;

//数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标 direction,empty :boolean; //表示队列q有没有翻转、是否空

var

function previous(k :longint) :longint; //确定队列q的前一个位置 begin

function next(k :longint) begin

procedure push; //入栈 var element :longint; begin

procedure pop; //出栈 begin

if direction then previous := ((k+c-2) mod c) + 1; else previous := (k mod c) + 1;

end;

:longint; //确定队列q的后一个位置

if direction then (1) next:=k mod c+1 else next := ((k+c-2) mod c)+1;

end;

read(element);

if next(head) = tail then //Q满时要将数据入栈S begin inc(n);

(2) s[n]:=q[tail]; ; tail := next(tail); end;

if empty then empty := false else head := next(head);

(3) q[head] := element; //入栈数据先存入Q中

end;

if empty then begin

43

省淳中信息学奥赛辅导 奥赛试题解析

writeln('Error: the stack is empty!'); exit; end:

writeln( (4) q[head] ); if tail = head then empty := true else begin

head := previous(head);

procedure reverse; //翻转只在队列q中进行 var temp :longint; begin

if (6) next(head) = tail then begin

if n > 0 then //数组栈S中有数据，要出栈给Q begin end;

(5) q[tail] := s[n]; dec(n);

tail := previous(tail);

end;

end;

direction := not direction; temp := head; head := tail; tail := temp;

end

else writeln('Error:less than',c,' elements in the stack!'); end; begin

readln(c); n := 0;

tail := 1; //确定队列q的头尾下标位置，队头放最新的数据 head := 1;

empty := true; //初始队列q中没有任何数 direction := true; //初始队列q没翻转 repeat

read(r);

44

省淳中信息学奥赛辅导 奥赛试题解析

case r of

1: push; 2: pop; 3: reverse;

end; until r = 0;

end.

【分析】知识点：队列、栈。 以壳厚度C=4为例讨论，算法上属于模拟算法 【1.模拟过程】

（1）数据在压入的数数量小于壳厚度C时是放在队列Q中。数据的入栈出栈操作是通过队列Q

来完成。

（2）本题的关键是队列Q具有部分栈的功能。数据入栈先放入队列Q的Q[head]中，当入栈数

据数量超过壳厚度C时将队列Q中的Q[tail]移出放入栈S中。 （3）队列Q，依次输入的字符为ABCDEFGHIJKL

45