1988年度程序员水平考试——下午试题

试题一 [说明]

本流程图是对某种简单密码文(密文)解密.密文由字符序列组成,解密后产

生的字母序列称为原文.解密算法如下:

把密文s1s2...sn按顺时针方向看成一个环,如下所示:

s1

sn

s3

sn-1

si

解密时按读入的整数值KEY(KEY>1),从S1起顺时针计数,当计数到第KEY个字

符时,取出该字符作为原文的第一个字符,并把它从环中删去.接着从下一个字符

起继续计数,取出第KEY个字符作为原文的第二个字符,并从环中删去.依次类推,

直至N个字符全部取完.由上述算法依次取出的字符序列即为原文.

例如,当KEY=3时,密文NUITP的原文为INPUT.

开始解密时,密文存放在字符数组S中, 长度为N(N>1),所得到的原文也存

放在数组S中.为了从S(1)起依次存放原文字符,在必要时部分未解密的字符作适

当的移动.


试题三(15分)

[程序说明] 本题给出的是计算两个多项式之积的子程序.

设两个多项式分别为

n n-1

Ｆ(Ｘ)=ＦnＸ +Ｆn-1Ｘ +...+Ｆ1Ｘ+Ｆ0

m m-1

Ｇ(Ｘ)=ＧmＸ +Ｇm-1Ｘ +...+Ｇ1Ｘ+Ｇ0


则它们的积多项式为

k k-1

Ｐ(ｘ)=Ｆ(Ｘ)Ｇ(Ｘ)=ＰkＸ +Ｐk-1Ｘ +...Ｐ1Ｘ+Ｐ0


其中, k=n+m; Ｐi=∑Ｆi-j*Ｇj (i=0,...,k);

j


记号∑Ｆi-j*Ｇj;表示对给定的i(0≤i≤n+m),和所有满足

0≤i-j≤n,≤j≤m

的j,对Ｆi-j*Ｇj求和.

程序用数组存贮多项式的序数,即数组的第i(≥0)个元素存贮多项式i次幂

的系数.例如:

5 3 2

Ｆ(Ｘ)=5.7Ｘ -10.8Ｘ +0.49Ｘ +2.7用数组表示为

0 1 2 3 4 5

2.7 0 0.49 -10.8 0 5.7

设程序已定义了如下的数据类型:

const maxp=100; {允许的多项式最高次幂}

type poly=record

power: 0..maxp; {多项式的最高次幂}

coef: array[0..maxp] of real

{coef 存贮多项式的i次幂项的系数}

end;


[程序]

procedure prod(f,g: poly; var p:poly);* var i,j,low,high:integer;

temp: real;

begin

for i:=0 to f.power + g.power do

begin

if __________________

then low:= ____________________

else low:=0;

if __________________

then high:= ____________________

else high:=i;

temp:=0.0;

for j:=low to high do

temp:= _____________________

p.coef:=temp

end;

_______________________

end;


　

试题七

[程序说明] 本程序用于判别输入的字符串是否为如下形式的字符串:

Ｗ＆Ｍ＄

其中子字符串M是子字符串W的字符反向排列.在此假定W不含有字符&和字符$,

字符&用作W与M的分隔符,字符$用字符串的输入结束符.

例如,对输入的以下字符串:

ab&ba$, 11&12$

ab&dd$, &$

程序将分别输出

OK.(是), NO.(不是),

NO.(不是), OK.(是).

[程序]

program aclearcase/" target="_blank" >ccept (input,output);

const

midch='&';

endch='$';

var

an:bollean; ch :char;

procedure match (var answer: boolean);

var

ch1,ch2:char;

f:boolean;

begin

read(ch1);

if ch1<>endch then

if ________________ then

begin

match (f);

if f then

begin

read (ch2); answer:=____________________

end

else answer:=false

end

else ___________________

else ___________________

end;

begin

writeln('Enter string:');

match (an);

if an

then begin

_______________________

if __________________________ then writeln ('OK.')

else writeln ('NO.')

end

else writeln ('NO.')

end.


试题十一

[程序说明] 本题给出的是将数组ａ的元素ａ1,ａ2,...,ａn从大到小排列的子程序.

子程序采用改进的选择方法,该方法基于以下思想:

在选择第一大元过程中,ａl与ａj(j=n,n-1,...2)逐个比较,若发现ａj1〉

ａl,则ａj1与ａ1交换,交换后新的ａj1有性质ａj1≥ａt(j1<t≤n).若再有ａj2

〉ａ1(j2<j1),ａj2与ａ1交换,则交换后的ａj2也有性质ａj2≥ａt(j2<t≤n).

如在挑选第一大元过程中,与ａ1交换的元素有k(k≥0)个,依次为ａj1,ａj2,...

ａjk则它们都满足这一性质.它们的下标满足n≥j1>j2>...>jk>1.有了这些下标,

在确定第二大元时,可只考虑ａ2与ａj(j=jk,jk-1,...,3)逐个比较.倘若jk=2,

则可不经比较就知道ａ2就是第二大元.在选择第二大元过程中,将与ａ2交换过

的元素下标也记录下来,可供选择其他大元使用.但在选则第二大元时,应保证与

ａ2交换的那些位置上的新值也都满足上的述性质.依次类推,顺序选择第一,第

二,...第n01大元,实现对ａ的排序.

设程序包含有常量和类型定义:

const maxn=1000;

type vector=array [1..maxn] of integer;

index=1..maxn;

[程序]

procedure sort (var a:vector;n:index);

var

p:vector;

i,j,k,m,t:integer;

begin

k:=0;i:=1;m:=n;

while i<n do

begin

for j:=m downto i+1 do

if a<a[j] then

t:=a;a:=a[j];a[j]:=t;

k:=k+1;______________

end;

repeat

______________;

if _____________ then _____________

else

begin m:=p[k];k:=k-1 end

until (i<m) or (i=n);

if _____________ then

begin

t:=a;__________;___________

end

end

end;

原文转自：http://www.ltesting.net