第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版.docx
- 文档编号:9314365
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:15
- 大小:20.07KB
第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版.docx
《第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版.docx》由会员分享,可在线阅读,更多相关《第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版.docx(15页珍藏版)》请在冰点文库上搜索。
第二十四届全国青少年信息学奥林匹克联赛初赛提高组含答案WORD重新整理排版
第二十四届全国青少年信息学奥林匹克联赛初赛
提高组C++语言试题
竞赛时间:
2018年10月13日14:
30~16:
30
(WORD重新整理排版)
选手注意:
●试题纸共有9页,答题纸共有2页,满分100分。
请在答题纸上作答,写在试题纸上的一律无效。
●不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。
一、单项选择题(共10题,每题2分,共计20分;每题有且仅有一个正确选项)
1.下列四个不同进制的数中,与其它三项数值上不相等的是()。
A.(269)16
B.(617)10
C.(1151)8
D.(1001101011)2
2.下列属于解释执行的程序设计语言是()。
A.C
B.C++
C.Pascal
D.Python
3.中国计算机学会于()年创办全国青少年计算机程序设计竞赛。
A.1983
B.1984
C.1985
D.1986
4.设根节点深度为0,一棵深度为h的满k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有k个子结点的树,共有()个结点。
A.(kh+1-1)/(k-1)
B.kh-1
C.kh
D.(kh-1)/(k-1)
5.设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)+n(n为正整数)及T(0)=1,则该算法的时间复杂度为()。
A.O(logn)B.O(nlogn)C.O(n)D.O(n2)
6.表达式a*d-b*c的前缀形式是()。
A.ad*bc*-
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:
1
10.为了统计一个非负整数的二进制形式中1的个数,代码如下:
intCountBit(intx)
{
intret=0;
while(x)
{
ret++;
________;
}
returnret;
}
则空格内要填入的语句是()。
A.x>>=1
B.x&=x-1
C.x|=x>>1
D.x<<=1
二、不定项选择题(共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
intmain(){
intx;
scanf("%d",&x);
intres=0;
for(inti=0;i if(i*i%x==1){ ++res; } } printf("%d",res); return0; } 输入: 15 输出: __________ 2. #include intn,d[100]; boolv[100]; intmain(){ scanf("%d",&n); for(inti=0;i scanf("%d",d+i); v[i]=false; } intcnt=0; for(inti=0;i if(! v[i]){ for(intj=i;! v[j];j=d[j]){ v[j]=true; } ++cnt; } } printf("%d\n",cnt); return0; } 输入: 107143259806 输出: ___________ 3. #include usingnamespacestd; strings; longlongmagic(intl,intr){ longlongans=0; for(inti=l;i<=r;++i){ ans=ans*4+s[i]-'a'+1; } returnans; } intmain(){ cin>>s; intlen=s.length(); intans=0; for(intl1=0;l1 for(intr1=l1;r1 boolbo=true; for(intl2=0;l2 for(intr2=l2;r2 if(magic(l1,r1)==magic(l2,r2)&&(l1! =l2||r1! =r2)){ bo=false; } } } if(bo){ ans+=1; } } } cout< return0; } 输入: abacaba 输出: ________________ 4. #include usingnamespacestd; constintN=110; boolisUse[N]; intn,t; inta[N],b[N]; boolisSmall(){ for(inti=1;i<=n;++i) if(a[i]! =b[i])returna[i] returnfalse; } boolgetPermutation(intpos){ if(pos>n){ returnisSmall(); } for(inti=1;i<=n;++i){ if(! isUse[i]){ b[pos]=i;isUse[i]=true; if(getPermutation(pos+1)){ returntrue; } isUse[i]=false; } } returnfalse; } voidgetNext(){ for(inti=1;i<=n;++i){ isUse[i]=false; } getPermutation (1); for(inti=1;i<=n;++i){ a[i]=b[i]; } } intmain(){ scanf("%d%d",&n,&t); for(inti=1;i<=n;++i){ scanf("%d",&a[i]); } for(inti=1;i<=t;++i){ getNext(); } for(inti=1;i<=n;++i){ printf("%d",a[i]); if(i==n)putchar('\n');elseputchar(''); } return0; } 输入1: 610164532 输出1: __________(3分) 输入2: 6200153426 输出2: __________(5分) 五、完善程序(共共2题,每题14分,共计28分) 1.对于一个1到n的排列P(即1到n中每一个数在P中出现了恰好一次),令qi为第𝑖个位置之后第一个比Pi值更大的位置,如果不存在这样的位置,则qi=n+1。 举例来说,如果n=5且P为15423,则P为26656。 下列程序读入了排列P,使用双向链表求解了答案。 试补全程序。 (第二空2分,其余3分) 数据范围1≤n≤105。 #include usingnamespacestd; constintN=100010; intn; intL[N],R[N],a[N]; intmain(){ cin>>n; for(inti=1;i<=n;++i){ intx; cin>>x; (1); } for(inti=1;i<=n;++i){ R[i]= (2); L[i]=i-1; } for(inti=1;i<=n;++i){ L[(3)]=L[a[i]]; R[L[a[i]]]=R[(4)]; } for(inti=1;i<=n;++i){ cout<<(5)<<""; } cout< return0; } 2.一只小猪要买N件物品(N不超过1000)。 它要买的所有物品在两家商店里都有卖。 第i件物品在第一家商店的价格是a[i],在第二家商店的价格是b[i],两个价格都不小于0且不超过10000。 如果在第一家商店买的物品的总额于不少于50000,那么在第一家店买的物品都可以打95折(价格变为原来的0.95倍)。 求小猪买齐所有物品所需最少的总额。 输入: 第一行一个数N。 接下来N行,每行两个数。 第i行的两个数分别代表a[i],b[i]。 输出: 输出一行一个数,表示最少需要的总额,保留两位小数。 试补全程序。 (第一空2分,其余3分) #include #include usingnamespacestd; constintInf=1000000000; constintthreshold=50000; constintmaxn=1000; intn,a[maxn],b[maxn]; boolput_a[maxn]; inttotal_a,total_b; doubleans; intf[threshold]; intmain(){ scanf("%d",&n); total_a=total_b=0; for(inti=0;i scanf("%d%d",a+i,b+i); if(a[i]<=b[i])total_a+=a[i]; elsetotal_b+=b[i]; } ans=total_a+total_b; total_a=total_b=0; for(inti=0;i if( (1)){ put_a[i]=true; total_a+=a[i]; }else{ put_a[i]=false; total_b+=b[i]; } } if( (2)){ printf("%.2f",total_a*0.95+total_b); return0; } f[0]=0; for(inti=1;i f[i]=Inf; inttotal_b_prefix=0; for(inti=0;i if(! 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); } } printf("%.2f",ans); return0; } 第二十四届全国青少年信息学奥林匹克联赛初赛 提高组参考答案 一、单项选择题(共10题,每题2分,共计20分) 1 2 3 4 5 6 7 8 9 10 D D B A D B B A D B 二、不定项选择题(共5题,每题2分,共计10分;每题有一个或多个正确选项,没有部分分) 1 2 3 4 5 AB CD ABD ABD BCD 三、问题求解(共2题,每题5分,共计10分) 1.去了没去没去没下雨(第4空2分,其余1分) 2.454 四、阅读程序写结果(共4题,每题8分,共计32分) 1.4 2.6 3.16 4.输出1: 213564(3分)输出2: 325614(5分) 五、完善程序(共计28分,以下各程序填空可能还有一些等价的写法,由各省赛区组织本省专家审定及上机验证,可以不上报CCFNOI科学委员会复核) Pascal语言 C++语言 C语言 分值 1 (1) a[x]: =i a[x]=i 3 (2) i+1 2 (3) R[a[i]] 3 (4) a[i] 3 (5) R[i] 3 2 (1) a[i]*0.95<=b[i]或b[i]>=a[i]*0.95 2 (2) total_a>=threshold或threshold<=total_a或total_a>=50000或50000<=total_a 3 (3) total_a+j+a[i] 3 (4) f[j]+total_b-total_b_prefix 3 (5) f[j-a[i]] 2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 十四 全国青少年 信息学 奥林匹克 联赛 初赛 提高 答案 WORD 重新 整理 排版