15．完善算法：求kmp算法中next数组。
proc get _next(t:string,var next:array[1..t.len] of integer);
begin
j:=1; k:=(1)__; next[1]:=0;
while j
if k=0 or t.ch[j]=t.ch[k] then begin j:=j+1; k:=k+1; next[j]:=k;end
else k:=(2)___;
end;
【中山大学 1998 四、1 （4分）】
16．下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。
例如:s=‘abcdefcdek’，t=‘cde’,则indse(s,t)=3, index(s,’aaa’)=0 。已知t，s的串长分别是mt,ms
func index(s,t,ms,mt);
i:=1;j:=1;
while (i if s[i]=t[j] then [ (1)__; (2)__]
else [ (3)___; (4)_ ]
if j>mt then return (5)____; else return (6)__
endf;
【南京理工大学 1999 三、2 （6分）】
17．阅读下列程序说明和pascal程序,把应填入其中的（ ）处的字句写在答题纸上。
程序说明：
本程序用于判别输入的字符串是否为如下形式的字符串:
w&m$ 其中,子字符串m是子字符串w的字符反向排列,在此假定w不含有字符&和字符$,字符&用作w与m的分隔符,字符$用作字符串的输入结束符。
例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出ok.(是),no.(不是)。
程序
program accept(input,output);
const midch=’&’; endch=’$’;
var an:boolean; ch:char;
procedure match(var answer: boolean);
var ch1,ch2:char; f:boolean;
begin
read(ch1);
if ch1<>endch
then if (1)__
then begin match(f);
if f then begin read(ch2); answer:=(2)_ end else answer:=false
end
else (3)___
else (4)___
end;
begin
writeln(‘enter string:’);
match(an);
if an then begin
(5)__ if (6)_ then writeln(‘ok.’) else writeln(‘no.’)
end
else writeln(‘no.’)
end. 【上海海运学院 1998 七 （15分）】
18．试利用下列栈和串的基本操作完成下述填空题。
initstack(s) 置s为空栈；
push(s,x) 元素x入栈;
pop(s) 出栈操作;
gettop(s) 返回栈顶元素；
sempty(s) 判栈空函数；
setnull(st) 置串st为空串；
length(st) 返回串st的长度；
equal(s1,s2) 判串s1和s2是否相等的函数；
concat(s1,s2) 返回联接s1和s2之后的串；
sub(s,i,1) 返回s中第i个字符；
empty(st) 判串空函数
func invert(pre:string; var exp:string):boolean;
{若给定的表达式的前缀式pre正确，本过程求得和它相应的表达式exp并返回“true”，否则exp为空串，并返回“false”。已知原表达式中不包含括弧，opset为运算符的集合。}
var s:stack; i,n:integer; succ:boolean; ch: char;
begin
i:=1; n:=length(pre); succ:=true;
(1)__; (2)__;
while (i begin ch:=sub（pre,i,l）;
if (3)_ then (4)__
else if (5)__then (6)_
else begin
exp:=concat((7)___,(8)____);
exp:=concat((9)___,(10)___);
(11)__;
end;
i:=i+1
end;
if (12)___then
begin exp:=concat(exp,sub(pre,n,1)); invert:=true end
else begin setnull(exp); invert:=false end
end;
注意：每个空格只填一个语句。 【清华大学 1996 八】
责任编辑：小草
