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

发表于:2007-05-26来源:作者:点击数: 标签:
试题一 [说明] 本流程图是对某种简单密码文(密文)解密.密文由字符序列组成,解密后产 生的字母序列称为原文.解密算法如下: 把密文s1s2...sn按顺时针方向看成一个环,如下所示: s1 sn s3 sn-1 si 解密时按读入的整数值KEY(KEY1),从S1起顺时针计数,当计数到第KEY

试题一 [说明]

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

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

把密文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

F(X)=FnX +Fn-1X +...+F1X+F0

m m-1

G(X)=GmX +Gm-1X +...+G1X+G0


则它们的积多项式为

k k-1

P(x)=F(X)G(X)=PkX +Pk-1X +...P1X+P0


其中, k=n+m; Pi=∑Fi-j*Gj (i=0,...,k);

j


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

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

的j,对Fi-j*Gj求和.

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

的系数.例如:

5 3 2

F(X)=5.7X -10.8X +0.49X +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;


 

试题七

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

W&M$

其中子字符串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.


试题十一

[程序说明] 本题给出的是将数组a的元素a1,a2,...,an从大到小排列的子程序.

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

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

al,则aj1与a1交换,交换后新的aj1有性质aj1≥at(j1<t≤n).若再有aj2

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

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

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

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

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

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

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

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

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

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