2012年第十八届全国青少年信息学奥林匹克联赛初赛
本次C++语言竞赛共有以下主要内容：
竞赛时间：2012年10月13日14:30~16:30
选手须知：答题纸共有2页、满分为100分；不得使用电子设备或查阅资料；答题必须写在答题纸上
单项选择题（共20题）：涵盖计算机基础知识与应用
问题求解（共2题）：涉及算法与数学思维
阅读程序写结果（共4题）：考察对程序的理解与运行结果分析能力
完善程序（共8空）：考察对算法逻辑的理解与补充
具体题目及正确答案如下：
单项选择题
题号 正确答案 1 A 2 B 3 A ... ... 问题求解 第一题的答案为5 第二题的答案为2880 阅读程序写结果 第一题的输出为 第二题的输出为 完善程序 第一部分： ① f[i] = f[i] + (x[j] < x[i] && y[j] < y[i]) ? f[j] : 0; ② if (x[j] < x[i] && y[j] < y[i]) { f[i] += f[j]; } else { break; } 第二部分： ① false ② used[data[i]] = false; ③ j = data[i]; data[i] = j + i n; used[j + i n] = true;
（普及组 C++语言试题）
竞赛时间： 2012 年 10 月 13 日 14:30~16:30
选手注意：
试题纸一共有10页，请将考试内容写在答题纸上，并规定如果书写在试题纸上则视为无效答案。答题纸共分为2页，请注意每张试卷的装订方式以及作答规范。考试总分设为100分，请认真审阅每一道题目并合理安排解题时间。
不得使用任何电子设备（如计算器、手机、电子词典等） 或查阅任何书籍资料
一、单项选择题（共 20 题，每题 1.5 分， 共计 30 分；每题且仅有一个正确选项）
1 ．计算机如果缺少（A ），将无法正常启动。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| A | B | A | B | C | C | B | C | A | A |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| B | D | B | C | C | D | C | A | C | B |
A ．内存 B ．鼠标 C ． U 盘 D ． 摄像头
目前计算机芯片（集成电路）制造的核心材料为（A），该材料是从沙石中提取出来的。
A ． 硅 B ． 铜 C ． 锗 D ． 铝
4 ．十六进制数 9A 在（ B ）进制下是 232。
A ．四 B ．八 C ．十 D ．十二
5 ．（ C）不属于操作系统。
A ．Windows B ．DOS C ．Photoshop D．NOI Linux
7 ． 目前个人电脑的（ B ）市场占有率最靠前的厂商包括 Intel 、AMD 等公司。
A．显示器 B ．CPU C．内存 D．鼠标
采用冒泡排序算法对手动排列序列进行升序调整。每次交换操作会降低一个逆序对的数量。因此，在对该序列5、4、3、2、1进行冒泡排序的过程中，总共需要（C）次交换操作才能完成排序过程。
A ．0 B ．5 C ．10 D ．15
B ． 军队发布命令
C ． 国际会议中， 每个人都与他国地位对等的人直接进行会谈
D ． 体育比赛中，每一级比赛的优胜者晋级上一级比赛
基于矢量图像（Vector Image）技术构建的图形文件具有较小的存储容量，并且无论在任意比例下进行缩放或旋转处理都不会导致图像失真现象。其本质原因是选项B。
A．记录了大量像素块的色彩值来表示图像
B．用点、直线或者多边形等基于数学方程的几何图元来表示图像
C．每个像素点的颜色信息均用矢量表示
D．把文件保存在互联网，采用在线浏览的方式查看图像
12．假设一个空栈S。其元素自上而下依次为a、b、c。已移除的元素d，则可能的入站序列是什么？选项为（D）。
A ．a, d, c, b B ．b, a, c, d C ．a, c, b, d D ．d, a, b, c
（B）其主要作用是展示网站服务器或文件存储空间中的HTML信息内容，并便于用户访问或操作这些文件的一种Web服务工具或应用程序。
A．资源管理器 B．浏览器 C．电子邮件 D．编译器
C
A．动态规划 B．贪心 C．分治 D．搜索
17．蓝牙和 Wi-Fi 都是（ C ）设备。
A．无线广域网 B．无线城域网 C．无线局域网 D．无线路由器
18 ． 在程序运行过程中， 如果递归调用的层数过多，会因为（ A）引发错误。
A．系统分配的栈空间溢出
C．系统分配的队列空间溢出
B．系统分配的堆空间溢出
D．系统分配的链表空间溢出
20．仿生学领域的诞生开创了一条具有创新性的科学技术发展之路。科学家们对生物体的结构、功能以及运作机制进行了深入研究，并将这些发现成功地应用于现代工程科技领域。在关于仿生学的知识考察中，请指出以下叙述中的错误项（B）
A．由研究蝙蝠， 发明雷达
C．由研究海豚， 发明声纳
B．由研究蜘蛛网，发明因特网
D．由研究电鱼， 发明伏特电池
二、问题求解（共 2 题， 每题 5 分， 共计 10 分）
假设在平面上任意取n个横纵坐标均为整数的格子点（即整数坐标）, 那么必定存在两个这样的格子点, 其连线的中线必然是一个新的格子点（即横纵坐标均为偶数）。因此n至少是多少？
在第29届国际信息学奥林匹克竞赛（NOI）期间, 主办单位特意安排了丰盛的晚宴以欢迎来自世界各地的参赛者。在第十十八张餐桌前, 有5名来自中国大陆的选手与5名来自中国特别行政区(港澳)的参赛者围坐在一起用餐。为促进交流, 参赛者决定交替而坐, 即每位中国大陆选手左右两侧均为港澳选手, 每位港澳选手左右两侧均为中国大陆选手。那么, 这一桌共有多少种不同的就座方案呢？
注：如果在两个方案中， 每个选手左右相邻的选手相同， 则视为同一种方案。
三、阅读程序写结果。（共 4 题，每题 8 分， 共计 32 分）
1．
#include
using namespace std;
int a,b,c,d,e,ans;
int {
3
7
10
main()
cin>>a>>b>>c;
d=a+b;
e=b+c;
ans=d+e;
cout<<ans<<endl;
return 0;
}
输入： 1 2 5
输出： 10______
2．
#include
using namespace std;
int n,i,ans;
int main()
{
cin>>n;
ans=0;
for(i=1;i<=n;i++)1 1 1 1 1 1
if(n%i==0) ans++;
cout<<ans<<endl;
return 0;
}
输入： 18
输出： 24_________
3．
#include
using namespace std;
int n,i,j,a[100][100];
int solve(int x,int y)
{
int u,v;
if(x==n) return a[x][y];
u=solve(x+1,y);
v=solve(x+1,y+1);
if(u>v) return a[x][y]+u;
else return a[x][y]+v;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++) cin>>a[i][j];
cout<<solve(1,1)<<endl;
return 0;
}
输入：
5
2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输出： ______________
4．
#include
#include
using namespace std;
int n,i,j,ans;
string s;
char get(int i)
{
if(i<n) return s[i];
else return s[i-n];
}
int main()
{
cin>>s;
n=s.size();
ans=0;
for(i=1;i<=n-1;i++)
{
for(j=0;j<=n-1;j++)
if(get(i+j)<get(ans+j))
{
ans=i;
break;
}
else if(get(i+j)>get(ans+j)) break;
}
for(j=0;j<=n-1;j++) cout<<get(ans+j);
cout<<endl;
return 0;
}
输入： CBBADADA
输出： ____________
四、完善程序（前 2 空每空 2 分，后 8 空每空 3 分，共计 28 分）
（坐标统计）给定平面上n个整数坐标点。针对每一个特定的坐标位置P(x, y)，能够控制其左下方向的所有其他坐标位置Q(x', y')（其中x' < x且y' < y）。这些被控制的位置数量定义为该坐标的'战斗 力'值V(P) = |{Q | Q在P左下方}|。计算并记录各坐标的'战斗 力'值V(P)。最后找出所有具有最大'战斗 力'值的位置，并返回其中编号最大的那个。
#include
using namespace std;
const int SIZE =100;
int x[SIZE],y[SIZE],f[SIZE];
int n,i,j,max_f,ans;
int main()
{
cin>>n;
for(i=1;i<=n;i++) cin>>x[i]>>y[i];
max_f=0;
for(i=1;i<=n;i++)
{
f[i]=__① __ ;
for(j=1;j<=n;j++)
{
if(x[j]<x[i] &&__② __)
③ __ ;
}
if(__④ __)
{
max_f=f[i];
⑤ __ ;
}
}
for(i=1;i<=n;i++) cout<<f[i]<<endl;
cout<<ans<<endl;
return 0;
}
请用户输入两个正整数n和m（其中1 < n < 20且1 < m < n），然后从数字范围[1, n]中选择m个不同的数字，并按照字典顺序从小到大列出所有可能的排列组合。例如：
输入： 3 2
输出： 1 2
1 3
2 1
2 3
3 1
3 2
#include
#include
using namespace std;
const int SIZE =25;
bool used[SIZE];
int data[SIZE];
int n,m,i,j,k;
bool flag;
int main()
{
cin>>n>>m;
memset(used,false,sizeof(used));
for(i=1;i<=m;i++)
{
data[i]=i;
used[i]=true;
}
flag=true;
while(flag)
{
for(i=1;i<=m-1;i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag=__① __ ;
for(i=m;i>=1;i--)
{
② __ ;
for(j=data[i]+1;j<=n;j++)
if(!used[j])
{
used[j]=true;
data[i]=__③ __ ;
flag=true;
break;
}
if(flag)
{
for(k=i+1;k<=m;k++)
for(j=1;j<=__④ __ ;j++)
if(!used[j])
{
data[k]=j;
used[j]=true;
break;
}
⑤ __ ;
}
}
}
return 0;
}
参考答案
一、 单项选择题（共 20 题，每题 1 ．5 分，共计 30 分；每题且仅有一个正确选项）
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| A | B | A | B | C | C | B | C | A | A |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| B | D | B | C | C | D | C | A | C | B |
二、 问题求解（共 2 题， 每题 5 分， 共计 10 分）
1． 5
2． 2880
三、阅读程序写结果。（共 4 题，每题 8 分， 共计 32 分）
10
6
14
ACBBADAD
四、完善程序（前 2 空每空 2 分，后 8 空每空 3 分，共计 28 分）
1、
① 0
② y[j]<y[i]
③ f[i]=f[i]+1;
④（ i>1） && (f[i]>f[i-1])
⑤ ans=max_f
2、
① false
② used[data[i]]=flase
③ j ④ n
⑤ break