NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案.docx

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案
一、单项选择题（共15题，，；每题有且仅有一个正确选项）
从（）年开始，N0IP竞赛将不再支持Pascal语言。
2020 B. 2021 C，每个人每次游 戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到()个乒乓球。假设乒乓球喷 出的速度为2个/秒，每节车厢的面积是整个场地面积的1/20。
A. 60 B. 108 C. 18 D. 20
二、不定项选择题(共5题，，；每题有一个或多个正确选项，多选 或少选均不得分)
以下排序算法在最坏情况下时间复杂度最优的有()。


对于入栈顺序为a, b, c, d, e, f, g的序列，下列()不可能是合法的出栈序列。
A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f
C. a,d,b,c,g,f,e ,f,e,d,c,b,a
下列算法中，（）是稳定的排序算法。


以下是面向对象的高级语言的是（）。
B. C++ C. For tan D. Java
以下和计算机领域密切相关的奖项是（）。

三、问题求解（共2题，每题5分，共计10分）
如图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上 下左右相邻的格子中的数字改变（由1变0,或由0变1）。现在要使得所有的格子中的数
字都变为0,至少需要3次操作。
如图所示，A到B是连通的。假设删除一条细的边的代价是1,删除一条粗的边的代价是
2,要让A、B不连通，最小代价是 4 （2分），最小代价的不同方案数是 9 （3分）。
（只要有一条删除的边不同，就是不同的方案）
四、阅读程序写结果(共4题，每题8分，共计32分)
1.
#include
using namespacestd;
int g(i nt m, intn, int x){
int ans = 0;
int i;
if( n == 1)
return 1;
for (i=x; i <=m/n; i++)
ans += g(m - i, nT, i);
return ans;
}
int main() {
int t, m, n;
cin >> m >> n;
cout〈〈 g(m, n, 0) << endl;
return 0;
}
输入：8 4
输出：15
2.
#include
using namespacestd;
int main() {
int n, i, j, x, y, nx, ny;
int a[40][40];
for (i = 0; i< 40; i++)
for (j = 0;j< 40; j++)
a[i][j]= 0;
cin >> n;
y = 0; x = n-1;
n = 2*nT;
for (i = 1; i <= n*n; i++){
a[y][x] =i;
ny = (y_1+n)%n;
nx = (x+1)%n;
if ((y == 0 && x == n-1) | | a[ny][nx] !=0)
y= y+1;
else {y = ny; x = nx;}
}
for (j = 0; j < n; j++)
cout << a[0][j]〈〈
cout << endl;
return 0;
}
输入：3
输出：17 24 1 8 15
3.
#include
using namespacestd;
int n, s,a[100005], t[100005],
void mergeso rt(intl, int r){
if (l == r)
return;
int mid = (l + r) / 2;
int p = l;
int i = l;
int j 二 mid + 1；
mergesort (l, mid);
mergesort (mid + 1, r);
while (i <= mid && j〈二 r){
if (a[j] < a[i]){
s += mid
- i+1；
t [p]=
a[j];
p++;
j++;
}
else {
t [p]=
a[i];
p++;
i++;
}
}
while (i <= mid){
t [p] = a[i]
p++；
i++；
wh