第二十四届全国青少年信息学奥林匹克联赛初赛提高组试题答案Word格式文档下载.docx
《第二十四届全国青少年信息学奥林匹克联赛初赛提高组试题答案Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《第二十四届全国青少年信息学奥林匹克联赛初赛提高组试题答案Word格式文档下载.docx（14页珍藏版）》请在冰点文库上搜索。
B.-*ad*bc
C.a*d-b*c
D.-**adbc
7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。
A.1/2
B.1/3
C.2/3
D.3/5
8.关于Catalan数Cn=（2n）!
/（n+1）!
/n！
，下列说法中错误的是（）。
A.Cn表示有n+1个结点的不同形态的二叉树的个数。
B.Cn表示含n对括号的合法括号序列的个数。
C.Cn表示长度为n的入栈序列对应的合法出栈序列个数。
D.Cn表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数。
9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。
有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：
抽中蓝球则继续抽球，抽中红球则停止。
最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于
（）。
A.1:
2
B.2:
1
C.1:
3
D.1:
10.为了统计一个非负整数的二进制形式中1的个数，代码如下：
intCountBit（intx）
{
intret=0;
while（x）
ret++;
________;
}
returnret;
则空格内要填入的语句是（）。
A.x>
>
=1
B.x&
=x-1
C.x|=x>
D.x<
<
二、不定项选择题（共5题，每题2分，共计10分；
每题有一个或多个正确选项，多选或少选均不得分）
1.NOIP初赛中，选手可以带入考场的有（）。
A.笔
B.橡皮
C.手机（关机）
D.草稿纸
2.2-3树是一种特殊的树，它满足两个条件：
（1）每个内部结点有两个或三个子结点；
（2）所有的叶结点到根的路径长度相同。
如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。
A.5
B.6
C.7
D.8
3.下列关于最短路算法的说法正确的有（）。
A.当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。
B.当图中不存在负权边时，调用多次Dijkstra算法能求出每对顶点间最短路径。
C.图中存在负权回路时，调用一次Dijkstra算法也一定能求出源点到所有点的最短路。
D.当图中不存在负权边时，调用一次Dijkstra算法不能用于每对顶点间最短路计算。
4.下列说法中，是树的性质的有（）。
A.无环
B.任意两个结点之间有且只有一条简单路径
C.有且只有一个简单环
D.边的数目恰是顶点数目减1
5.下列关于图灵奖的说法中，正确的有（）。
A.图灵奖是由电气和电子工程师协会（IEEE）设立的。
B.目前获得该奖项的华人学者只有姚期智教授一人。
C.其名称取自计算机科学的先驱、英国科学家艾伦·
麦席森·
图灵。
D.它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。
三、问题求解（共2题，每题5分，共计10分）
1.甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨，并且乙不去，则甲一定不去；
②如果乙去，则丁一定去；
③如果丙去，则丁一定不去；
④如果丁不去，而且甲不去，则丙一定不去。
如果周末丙去了，则甲________（去了/没去）（1分），乙________（去
了/没去）（1分），丁________（去了/没去）（1分），周末________（下雨/没下雨）（2分）。
2.方程a*b=（aorb）*（aandb），在a,b都取[0,31]中的整数时，共有_____组解。
（*表示乘法；
or表示按位或运算；
and表示按位与运算）
四、阅读程序写结果（共4题，每题8分，共计32分）
1.#include<
cstdio>
intmain（）{
intx;
scanf（"
%d"
&
x）;
intres=0;
for（inti=0;
i<
x;
++i）{
if（i*i%x==1）{
++res;
}
printf（"
res）;
return0;
输入：
15
输出：
_________
2.#include<
intn,d[100];
boolv[100];
n）;
n;
d+i）;
v[i]=false;
intcnt=0;
if（!
v[i]）{
for（intj=i;
!
v[j];
j=d[j]）{
v[j]=true;
++cnt;
printf（"
%d\n"
cnt）;
return0;
107143259806
3.#include<
iostream>
usingnamespacestd;
strings;
longlongmagic（intl,intr）{
longlongans=0;
for（inti=l;
=r;
ans=ans*4+s[i]-'
a'
+1;
returnans;
cin>
s;
intlen=s.length（）;
intans=0;
for（intl1=0;
l1<
len;
++l1）{
for（intr1=l1;
r1<
++r1）{
boolbo=true;
for（intl2=0;
l2<
++l2）{
for（intr2=l2;
r2<
++r2）{
if（magic（l1,r1）==magic（l2,r2）&
&
（l1!
=
l2||r1!
=r2））{
bo=false;
if（bo）{
ans+=1;
cout<
ans<
endl;
abacaba
4.#include<
constintN=110;
boolisUse[N];
intn,t;
inta[N],b[N];
boolisSmall（）{
for（inti=1;
=n;
++i）
if（a[i]!
=b[i]）returna[i]<
b[i];
returnfalse;
boolgetPermutation（intpos）{
if（pos>
n）{
returnisSmall（）;
isUse[i]）{
b[pos]=i;
isUse[i]=true;
if（getPermutation（pos+1））{
returntrue;
isUse[i]=false;
voidgetNext（）{
getPermutation
（1）;
a[i]=b[i];
%d%d"
n,&
t）;
a[i]）;
=t;
getNext（）;
a[i]）;
if（i==n）putchar（'
\n'
）;
elseputchar（'
'
输入1：
610164532
输出1：
_________（3分）
输入2：
6200153426
输出2：
_________（5分）
五、完善程序（共2题，每题14分，共计28分）
1.对于一个1到
下列程序读入了排列
数据范围1≤
#include<
constintN=100010;
intn;
intL[N],R[N],a[N];
（1）;
R[i]=
（2）;
L[i]=i-1;
L[（3）]=L[a[i]];
R[L[a[i]]]=R[（4）];
（5）<
"
;
2.一只小猪要买N件物品（N不超过1000）。
它要买的所有物品在两家商店里都有卖。
第i件物品在第一家商店的价格是a[i]，在第二家商店的价格是b[i]，两个价格都不小于0且不超过10000。
如
果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95折（价格变为原来的0.95倍）。
求小猪买齐所有物品所需最少的总额。
第一行一个数N。
接下来N行，每行两个数。
第i行的两个数分别代
表a[i]，b[i]。
输出一行一个数，表示最少需要的总额，保留两位小数。
试补全程序。
（第一空2分，其余3分）
algorithm>
constintInf=1000000000;
constintthreshold=50000;
constintmaxn=1000;
intn,a[maxn],b[maxn];
boolput_a[maxn];
inttotal_a,total_b;
doubleans;
intf[threshold];
total_a=total_b=0;
a+i,b+i）;
if（a[i]<
=b[i]）total_a+=a[i];
elsetotal_b+=b[i];
ans=total_a+total_b;
if（
（1））{
put_a[i]=true;
total_a+=a[i];
}else{
put_a[i]=false;
total_b+=b[i];
if（
（2））{
%.2f"
total_a*0.95+total_b）;
f[0]=0;
threshold;
f[i]=Inf;
inttotal_b_prefix=0;
put_a[i]）{
total_b_prefix+=b[i];
for（intj=threshold-1;
j>
=0;
--j）{
if（（3）>
=threshold&
f[j]!
=Inf）
ans=min（ans,（total_a+j+a[i]）*0.95
+（4））;
f[j]=min（f[j]+b[i],j>
=a[i]?
（5）:
Inf）;
ans）;
}
参考答案：
升级会员 