wrrite(a[i]);
sort2(i+1,n);
end
挪用该进程的语句为sort2(0,n),比较运算的次数为:
_____
(3)proceduresort3(i,j:
integer);
varm:
integer;
begin
ifi<>jthen
begin
m:
=(i+j)div2;
sort3(i,m);sort3(m+1,j);
merge;{假设归并的元素别离为p、q个,需要比较p+q次}
end;
end;
挪用该进程的语句为sort3(0,n),比较运算的次数为:
_____
27、(7%)
programEXP3(input,output);
constn=4;
typese=array[1..n*2]ofchar;
vari,j,i1,j1,k,s,t,s1,L,swap:
integer;
temp:
char;
a:
se;
Begin
fori:
=1ton*2doread(a[i]);readln;
s:
=0;t:
=0;
fori:
=1ton*2do
ifa[i]='1'thens:
=s+1
elseifa[i]='0'thent:
=t+1;
if(s<>n)or(t<>n)thenwriteln('error')
elsebegins1:
=0;
fori:
=1to2*n-1do
ifa[i]<>a[i+1]thens1:
=s1+1;
writeln('jamp=',s1);swap:
=0;
fori:
=1to2*n-1do
forj:
=i+1to2*ndo
ifa[i]<>a[j]thenbegin
temp:
=a[i];a[i]:
=a[j];a[j]:
=temp;
s:
=0;
forL:
=1to2*n-1do
ifa[L]<>a[L+1]thens:
=s+1;
ifs>swapthenbegin
swap:
=s;i1:
=i;j1:
=jend;
temp:
=a[i];a[i]:
=a[j];a[j]:
=temp
end;
ifswap>0then
writeln('maxswap=',swap-s1,'i=',i1,'j=',j1)
end;
End.
输入:
输出:
四、按照题意,补充完善以下程序:
(30%)
28.金蝉素数
【问题描述】某古寺的一块石碑上依稀刻有一些三位与四位的神秘自然数。
专家研究发觉:
这些数是素数,且从低位去掉一名,或两位,……后都仍为素数,从高位去掉一名,或两位,……后也都仍为素数,更奇妙的是同时去掉它的最高位与最低位数字后仍是素数。
因此,人们把这些神秘的素数称为金蝉素数,喻意金蝉脱壳以后仍为美丽的金蝉。
试求出石碑上的金蝉素数。
【程序清单】
vara:
array[1..400]ofinteger;
s,u,i,j,k,l,v,t,m,w,n:
integer;
begin
a[1]:
=2;a[2]:
=3;a[3]:
=5;
a[4]:
=7;u:
=4;
Fork:
=11To9999do
ifkmod2=1thenbegin
j:
=3;
while
(1)and(kmodj<>0)doj:
=j+1;
Ifj>trunc(Sqrt(k))Thenbegin
IFa[u]<1000THENbeginu:
=u+1;
a[u]:
=kend;
IFk>100THENbegin
L:
=trunc(ln(k)/ln(10))+1;
t:
=1;s:
=0;
Fori:
=1To
(2)dobegin
t:
=t*10;w:
=trunc(k/t);
m:
=k-w*t;
V:
=1;n:
=10000;
IFi=L-1THENn:
=trunc(m/10);
WHiLE(a[v]<=W)OR(3)dobegin
Ifa[V]=wThens:
=s+1;
IFa[v]=mTHENS:
=S+1;
IFa[v]=nTHENS:
=S+1;
(4);
end;
end;
If(5)Thenwriteln(k);
END
end
end;End.
2九、多项式乘法运算
【问题描述】
多项式乘法运算:
p(x)=2x2-x+1,q(x)=x+1
p(x)*q(x)=(2x2-x+1)(x+1)=2x3+x2+1
【程序说明】
多项式的表示:
系数、指数
如上例:
p(x)系数指数q(x)系数指数
2211
-1110
1000
00
p*q的结果存入c中。
其输出格式是:
依次用一对括号内的(系数、指数)别离来表示。
如上例的输出结果表示为:
(2,3)(1,2)(1,0)
【程序清单】
begin
jp:
=0;
readln(x,y);
whilex<>0do
begin
jp:
=jp+l;p[jp,1]:
=x;
p[jp,2]:
=y;readln(x,y);
end;
jq:
=0;
readln(x,y);
whilex<>0do
begin
jq:
=jq+1;q[jq,1]:
=x;
q[jq,2]:
=y;readln(x,y);
end;
jc:
=1;c[jc,1]:
=0;c[jc,2]:
=-1000;
fori:
=1tojpdo
begin
___
(1)___
y:
=p[i,2];
forj:
=1tojqdo
begin
___
(2)___
y1:
=y+q[j,2];
k:
=1;
whiley1=k+1;
ify1=c[k,2]then___(3)___
elsebegin
forl:
=jcdowntokdo
begin
c[l+1,1]:
=c[l,1];
c[l+1,2]:
=c[l,2];
end;
c[k,1]:
=x1;c[k,2]:
=y1;
___(4)___
end;
end;
fori:
=1tojcdo
if___(5)___then
write('(',c[i,1],',',c[i,2],')');
end.
30、求最长不下降序列
【问题描述】
设有由n个不相同的整数组成的数列,记为:
a
(1)、a
(2)、……、a(n)且a(i)<>a(j)(i<>j),例如3,18,7,14,10,12,23,41,16,24。
若存在i1如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。
程序要求,当原数列给出以后,求出最长的不下降序列。
【算法分析】
按照动态计划的原理,由后往前进行搜索。
1·对a(n)来讲,由于它是最后一个数,所以当从a(n)开始查找时,只存在长度为1的不下降序列;
2·若从a(n-1)开始查找,则存在下面的两种可能性:
①若a(n-1)②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3·一般若从a(i)开始,现在最长不下降序列应该按下列方式求出:
在a(i+1),a(i+2),…,a(n)中,找出一个比a(i)大的且最长的不下降序列,作为它的后继。
4·为算法上的需要,概念一个数组
整数类型二维数组d(N,3)
d(I,1)表示点a(i)
d(I,2)表示从I位置抵达N的最长不下降序列长度
d(I,3)表示从I位置开始最长不下降序列的下一个位置
【程序清单】
PROGRAMMAX_RISE(INPUT,OUTPUT);
CONSTMAXN=100;FNAME='';
TYPETLIST=ARRAY[1..MAXN,1..3]
OFINTEGER;
VARD:
TLIST;N:
BYTE;
PROCEDUREINIT;
VARI:
INTEGER;F:
TEXT;
BEGIN
ASSIGN(F,FNAME);
RESET(F);READLN(F,N);
FORI:
=1TONDO
BEGIN
READ(F,D[I,1]);
D[I,2]:
=1;D[I,3]:
=0
END;
__
(1)__
END;
PROCEDUREMAKE;
VARI,J,P:
BYTE;L:
INTEGER;
BEGIN
FORI:
=__
(2)__DO
BEGIN
L:
=0;P:
=0;
FORJ:
=I+1TONDO
IF(D[I,1]L)THEN
BEGINL:
=D[J,2];__(3)__;END;
IF__(4)__THEN
BEGIND[I,2]:
=L+1;D[I,3]:
=P;END;
END;
END;
PROCEDUREOUTPUT;
VARI,L,DMAX:
BYTE;
BEGIN
WRITE('SOURCE:
');
FORI:
=1TONDOWRITE(D[I,1]:
5);
WRITELN;DMAX:
=D[1,2];L:
=1;
FORI:
=2TON-1DO
IFD[I,2]>DMAXTHEN
BEGIN__(5)__;L:
=I;END;
WRITE('RESULTIS:
');
WHILEL<>0DO
BEGINWRITE(D[L,1]:
5);L:
=D[L,3];END;
WRITELN;
WRITELN('MAXLENGTH=',D[DMAX,2]);
END;
BEGIN
INIT;MAKE;OUTPUT;
END.
信息学奥林匹克分区联赛初赛模拟题答题纸
班级:
________姓名:
________
(参考答案)
一、选择填空:
(30%,每小题%)
题号
1
2
3
4
5
6
7
8
9
10
答案
C
C
D
A
B
B
A
D
A
D
题号
11
12
13
14
15
16
17
18
19
20
答案
D
A
B
B
A
C
A
B
116
位码:
二、问题求解:
(20%,每题小题5%)
2一、①能
②不能,因为C与四个城市邻接,不可能一次遍历
2二、注意:
先依中缀或前缀表达式画出表达式树,再按照后序遍历方式写出后缀表达式
1)前缀:
+A/*BCD,后缀:
ABC*D/+;2)中缀:
-A+B*(-C);后缀:
A△BC△*+
23、1)K=I+J(J-1)/22)K=I+(J-1)N
24、1234567
10100000
21011000
30……
三、阅读程序写出运行结果(20%):
2五、(6%)
输出:
11334446
2六、(7%)
(1)挪用进程sort1(n),比较运算的次数为:
n(n-1)
(2)挪用进程sort2(0,n),比较运算的次数为:
n(n+3)/2
(3)挪用进程sort3(0,n),比较运算的次数为:
[log2(n-1)+log2(n/2-1)(p+q)+2
27、(7%)
输出:
jamp=5maxswap=2I=6j=7
四、按照题意,补充完善程序:
(30%,每空2%)
28.金蝉素数
(1)j<=trunc(sqrt(k))
(2)L-1(3)a[v]<=m(4)inc(v)(5)s=2*L-1
2九、多项式乘法运算
(1)x:
=p[I,1]
(2)x1:
=x*q[j,1](3)c[k,1]:
=c[k,1]+x1(4)inc(v)(5)c[I,j]<>0
30、求最长不下降序列
(1)close(F)
(2)n-1downto1(3)p:
=j(4)L>0(5)DMAX:
=D[I,2]