全国青少年信息学奥林匹克分区联赛初赛模拟题高中组汇总Word文档下载推荐.docx
《全国青少年信息学奥林匹克分区联赛初赛模拟题高中组汇总Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《全国青少年信息学奥林匹克分区联赛初赛模拟题高中组汇总Word文档下载推荐.docx（15页珍藏版）》请在冰点文库上搜索。
读过a，c两本书的有2人；
读过b，c两本书的有3人。
则读过a的人数是_____。
（A）12人（B）30人（C）10人（D）24人
8、下列if语句中，endif表示相应if的结束：
y=0
ifx<
0theny=5else
10theny=10
100theny=100endif
elsey=200
endif
则当x=80时，运行的结果为______。
（A）y=5（B）y=100（C）y=10（D）y=200
9、如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。
例如：
试问这种表示法的整数a的范围应是_______。
↑符号位表示负表示－1
（A）-127≤a≤127（B）-128≤a≤128
（C）-128≤a<
128（D）-128<
a≤128
10、在上题所述表示法中，以下_____说法是正确的。
（A）范围内的每一个数都只有唯一的格式
（B）范围内的每一个数都有两种格式
（C）范围内的一半数有两种格式
（D）范围内只有一个数有两种表示格式
11、设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不再进栈）：
进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是________。
（A）{5，4，3，2，1}（B）{2，1}
（C）{2，3}（D）{3，4}
12、快速排序在平均情况下的时间复杂度是____。
（A）O（nlogn）（B）O（n^2）（C）O（n）
13、整数在计算机中的二进制表示是____。
（A）原码（B）补码（C）反码
14、一棵包含n个节点的树有几条边：
____。
（A）n（B）n-1（C）不一定
15、在Hanoi塔问题中，搬动四个圆盘需要几次____。
（A）15（B）13（C）11
16、下列哪一个不是运用动态规划解题时必须满足的条件：
（A）最优化原理（B）无后效性（C）子问题重叠
17、有10道NOI备选题，要从中选出6道，有几种选法？
_____。
（A）210（B）420（C）1440
18、三个顶点的无向完全图有几条边？
（A）2（B）3（C）6
19、已知ASCII码表中的大写字母后有6个其他字符，接着便是小写字母。
现已知：
A字母的ASCII码为（41）16{表示16进制数41}，试写出字母t用十进制表示的ASCII码：
（）10
20、一个汉字的机内码目前常用二个字节来表示：
第一字节是区位码的区号加（160）10；
第二个字节是区位码的位码加（160）10，已知：
汉字“却”的区位码是4020，试写出其机内码两个
字节的二进制代码：
_________、________。
二、问题求解：
（20%，每题小题5%）
21、下图中用点表示城市，点与点之间的联线表示城市间的道路：
试问：
①能否找出一条从A城市出发，经过图中所有道路一次后又回到出发点的通路来？
②能否从A出发，找出去每个城市且只去一次
的通路来？
若能，则写出通路；
否则说明理由。
22、为了便于处理表达式，常常将普通表达式
（称为中缀表示）转换为前缀{运算符在前，如
X/Y写为/XY}和后缀{运算符在后，如X/Y写为XY/}
的表达式。
在这样的表示中可以不用括号即可确定
求值的顺序，如：
（P+Q）*（R-S）→*+PQ-RS或→PQ+RS-*
①试将下面的表达式改写成前缀与后缀的表示形式：
（a）A+B*C/D（b）A-C*D+B^E②试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：
+△A*B△C{前缀式中△表示一元运算符取负号，如△A表示（-A）}
23、设A是一个n阶上三角阵，将这个上三角阵按列序存储一维数组b[n*（n+1）/2]中，如果a[I,j]存放在b[k]，那么请给出求解k的计算公式。
设A是一个一维数组a[m*n]，现将这个数组按列序存储在一个m*n的矩阵B中，如果a[k]存放在b[I,J]，那么请给出求解I,J的计算公式。
24、用邻接矩阵表示下面的无向图：
三、阅读程序写出运行结果（20%）:
25、（6%）
programexp1（input,output）;
constMaxn=100;
Maxk=100;
typearr=array[1..Maxn]ofinteger;
ktype=1..Maxk;
vari,n,k:
integer;
a,b:
arr;
procedurecounting（a,b:
n:
k:
ktype）;
vari,j:
c:
array[1..Maxk]ofinteger;
begin
fillchar（c,sizeof（c）,0）;
forj:
=1tondo
c[a[j]]:
=c[a[j]]+1;
fori:
=2tokdoc[i]:
=c[i]+c[i-1];
=ndownto1dobegin
b[c[a[j]]]:
=a[j];
=c[a[j]]-1;
end;
=1tondowrite（b[i]:
5）;
writeln;
write（'
N,K='
）;
readln（n,k）;
=1tondobegin
read（a[i]）;
ifa[i]>
kthen
beginwriteln（'
error'
halt;
counting（a,b,n,k）;
readln;
end.
键盘输入：
86
36413414
输出：
26、（7%）设数组a[1]，a[2]，„，a[n]，已存入了数据，调用不同的排序程序，则数据比较的次数将会不同，试计算分别调用下列不同的排序过程的比较运算的次数。
其中swap（i，j）表示a[i]与a[j]进行交换。
（1）proceduresort1（n：
integer）；
vari，j：
integer；
fori：
=1ton-1do
fOrj：
ifa[j]<
a[i]thenswap（i，j）
end；
调用该过程的语句为sort1（n），比较运算的次数为：
_____
（2）proceduresort2（i，n：
varj：
ifi=nthenwrite（a[n]）
else
forj：
=i+1tondo
a[i]thenswap（i，j）;
wrrite（a[i]）；
sort2（i+1，n）；
end
调用该过程的语句为sort2（0，n），比较运算的次数为：
（3）proceduresort3（i，j：
varm：
ifi<
>
jthen
m：
=（i+j）div2；
sort3（i，m）；
sort3（m+1，j）；
merge；
{假设合并的元素分别为p、q个，需要比较p+q次}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:
temp:
char;
a:
se;
Begin
=1ton*2doread（a[i]）;
readln;
s:
=0;
t:
=1ton*2do
ifa[i]='
1'
thens:
=s+1
elseifa[i]='
0'
thent:
=t+1;
if（s<
n）or（t<
n）thenwriteln（'
）
elsebegins1:
=1to2*n-1do
ifa[i]<
a[i+1]thens1:
=s1+1;
writeln（'
jamp='
s1）;
swap:
=i+1to2*ndo
a[j]thenbegin
temp:
=a[i];
a[i]:
a[j]:
=temp;
forL:
ifa[L]<
a[L+1]thens:
=s+1;
ifs>
swapthenbegin
swap:
=s;
i1:
=i;
j1:
=jend;
=temp
ifswap>
0then
maxswap='
swap-s1,'
i='
i1,'
j='
j1）
End.
输入：
10101100输出：
四、根据题意，补充完善以下程序：
（30%）
28．金蝉素数
【问题描述】某古寺的一块石碑上依稀刻有一些三位与四位的神秘自然数。
专家研究发现：
这些数是素数，且从低位去掉一位，或两位，„„后都仍为素数，从高位去掉一位，或两位，„„后也都仍为素数，更奇妙的是同时去掉它的最高位与最低位数字后还是素数。
因此，人们把这些神秘的素数称为金蝉素数，喻意金蝉脱壳之后仍为美丽的金蝉。
试求出石碑上的金蝉素数。
【程序清单】
vara:
array[1..400]ofinteger;
s,u,i,j,k,l,v,t,m,w,n:
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;
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:
（4）;
If（5）Thenwriteln（k）;
END
End.
29、多项式乘法运算
【问题描述】
多项式乘法运算：
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中。
其输出格式是：
依次用一对括号内的（系数、指数）分别来表示。
如上例7
的输出结果表示为：
（2，3）（1，2）（1，0）
jp:
readln（x,y）;
whilex<
0do
=jp+l;
p[jp,1]:
=x;
p[jp,2]:
=y;
end;
jq:
=jq+1;
q[jq,1]:
q[jq,2]:
readln（x,y）;
jc:
c[jc,1]:
c[jc,2]:
=-1000;
fori:
=1tojpdo
___
（1）___
y:
=p[i,2];
=1tojqdo
___
（2）___
y1:
=y+q[j,2];
whiley1<
c[k,2]dok:
=k+1;
ify1=c[k,2]then___（3）___elsebegin
forl:
=jcdowntokdobegin
c[l+1,1]:
=c[l,1];
c[l+1,2]:
=c[l,2];
c[k,1]:
=x1;
c[k,2]:
=y1;
___（4）___
=1tojcdo
if___（5）___then
（'
c[i,1],'
'
c[i,2],'
）'
）;
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<
i2<
i3<
„<
ie且有a（i1）<
a（i2）<
a（ie）则称为长度为e的不下降序列。
如上例中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）则存在长度为2的不下降序列a（n-1），a（n）。
②若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='
Q21.TXT'
;
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
READ（F,D[I,1]）;
D[I,2]:
D[I,3]:
=0
END;
__
（1）__
PROCEDUREMAKE;
VARI,J,P:
=__
（2）__DO
P:
FORJ:
=I+1TONDO
IF（D[I,1]<
D[J,1]）AND（D[J,2]>
L）THENBEGINL:
=D[J,2];
__（3）__;
IF__（4）__THEN
BEGIND[I,2]:
=L+1;
D[I,3]:
=P;
END;
PROCEDUREOUTPUT;
VARI,L,DMAX:
WRITE（'
SOURCE:
'
=1TONDOWRITE（D[I,1]:
WRITELN;
DMAX:
=D[1,2];
=2TON-1DO
IFD[I,2]>
DMAXTHEN
BEGIN__（5）__;
=I;
RESULTIS:
'
WHILEL<
0DO
BEGINWRITE（D[L,1]:
=D[L,3];
WRITELN（'
MAXLENGTH='
D[DMAX,2]）;
INIT;
MAKE;
OUTPUT;
END.
升级会员 