NOIP2017提高组C++考试

第二十三届全国青少年信息学奥林匹克联赛初赛

提高组C++语言试题

竞赛时间：2017年10月14日14:30~16:30

选手注意：

0试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在

试题纸上的一律无效。矚慫润厲钐瘗睞枥庑赖。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题 1.5分，共计22.5分；每题有且仅有一个正确选项）

1.从（）年开始，NOIP竞赛将不再支持Pascal语言。

A.2020

B. 2021

C. 2022

D. 2023

2.在8位二进制补码中，10101011表示的数是十进制下的（）。

A.43

B. -85

C. -43

D. -84

3.分辨率为1600x900、16位色的位图，存储图像信息所需的空间为（）。

A.2812.5KB

B. 4218.75KB

C. 4320KB

D. 2880KB

4.2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（）。

A.星期三

B. 星期日

C. 星期六

D. 星期二

5.设G是有n个结点、m条边（n≤m）的连通图，必须删去G的（）条边，

才能使得G变成一棵树。

A. m – n + 1

B. m - n

C. m + n + 1

D. n – m + 1

6.若某算法的计算时间表示为递推关系式：

T(N) = 2T(N / 2) + N log

N T(1) = 1

则该算法的时间复杂度为（）。

A.O(N)

B.O(N log N)

C.O(N log2 N)

D.O(N2)

7.表达式a * (b + c) * d的后缀形式是（）。

A.a b c d * + *

B.a b c + * d *

C.a * b c + * d

D.b + c * a * d聞創沟燴鐺險爱氇谴净。

8.由四个不同的点构成的简单无向连通图的个数是（）。

A.32

B.35

C.38

D.41

CCF NOIP2016 初赛提高组 C++语言试题

第1页，共10页

9.将7个名额分给4个不同的班级，允许有的班级没有名额，有（）种不

同的分配方案。

A.60

B.84

C.96

D.120

10.若f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2，则随着i的增大，f[i]将接近

于（）。残骛楼諍锩瀨濟溆塹籟。

A. 1/2

B. 2/3

C. √5 ? 1

D. 1

2

11.设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排

好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做（）次比较。酽锕极額閉镇桧猪訣锥。

A.n2

B.n log n

C.2n

D.2n-1

12.在n（n≥3）枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），

如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。彈贸摄尔霁毙攬砖卤庑。

a.k?∪?

b.k?

c.k ||

算法Coin(A, n)

1.k?v3?

2.将A中硬币分成X，Y，Z三个集合，使得|?| = |?| = , |?| = K 2謀荞抟箧飆

鐸怼类蒋薔。

3.if ?(?) ≠?(?)//W(X), W(Y)分别为 X 或 Y 的重量

4.then __________

5.else __________

6.__________

7.if n>2 then goto 1

8.if n=2 then 任取 A 中 1 枚硬币与拿走硬币比较，若不等，则它不合格；

若相等，则A中剩下的硬币不合格.

9.if n=1 then A 中硬币不合格

正确的填空顺序是（）。

A. b, c, a

B. c, b, a

C. c, a, b

D. a, b, c

13.有正实数构成的数字三角形排列形式如图所示。a11

第一行的数为a11；第二行的数从左到右依次为a21a22

a21, a22；…第 n 行的数为 a n1, a n2, …, a nn。从 a11a31a32a33

开始，每一行的数a ij只有两条边可以分别通向……

下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算a n1 a n2…………. a nn 法找出一条从a11向下通到a n1, a n2,…, a nn中某

CCF NOIP2016 初赛提高组 C++语言试题

第2页，共10页

个数的路径，使得该路径上的数之和达到最大。

令C[i,j]是从a11到a ij的路径上的数的最大和，并且C[i,0]=C[0,j]=0,厦礴恳蹒骈時盡继價骚。

则C[i,j]=（）。

A.max{C[i-1,j-1], C[i-1,j]} + a ij

B.C[i-1,j-1] + C[i-1,j]

C.max{C[i-1,j-1], C[i-1,j]} + 1

D.max{C[i,j-1],C[i-1,j]} + a ij

14.小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航

班准点的概率是0.9，第2个航班准点的概率为0.8,第3个航班准点的概率为0.9。如果存在第i 个（i=1,2）航班晚点，第i+1 个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是（）。茕桢广鳓鯡选块网羈泪。

A.0.5

B.0.648

C.0.72

D.0.74

15.欢乐喷球：儿童游乐场有个游戏叫“欢

乐喷球”，正方形场地中心能不断喷出

彩色乒乓球，以场地中心为圆心还有一

个圆形轨道，轨道上有一列小火车在匀

速运动，火车有六节车厢。假设乒乓球

等概率落到正方形场地的每个地点，包

括火车车厢。小朋友玩这个游戏时，只

能坐在同一个火车车厢里，可以在自己

的车厢里捡落在该车厢内的所有乒乓鹅娅

尽損鹌惨歷茏鴛賴。

球，每个人每次游戏有三分钟时间，则

一个小朋友独自玩一次游戏期望可以

得到（）个乒乓球。假设乒乓球喷

出的速度为2个/秒，每节车厢的面积

是整个场地面积的1/20。

A. 60

B. 108

C. 18

D. 20

二、不定项选择题（共5题，每题 1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分）籟丛妈羥为贍偾蛏练淨。

1.以下排序算法在最坏情况下时间复杂度最优的有（）。

A.冒泡排序

B.快速排序

C.归并排序

D.堆排序

2.对于入栈顺序为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

D.g, f, e, d, c, b, a

CCF NOIP2016 初赛提高组 C++语言试题

第3页，共10页

3.下列算法中，（）是稳定的排序算法。

A.快速排序

B.堆排序

C.希尔排序

D.插入排序

4.以下是面向对象的高级语言的有（）。

A.汇编语言

B.C++

C.Fortran

D.Java

5.以下和计算机领域密切相关的奖项有（）。

A.奥斯卡奖

B.图灵奖

C.诺贝尔奖

D.王选奖

三、问题求解（共2题，每题5分，共计10分）

1.如右图所示，共有13个格子。对任何一个格子进行

一次操作，会使得它自己以及与它上下左右相邻的格

子中的数字改变（由1变0，或由0变1）。现在要

使得所有的格子中的数字都变为0，至少需要

_________次操作。預頌圣鉉儐歲龈讶骅籴。

2.如下图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一

条粗的边的代价是2，要让A、B不连通，最小代价是_________（2分），最小代价的不同方案数是_________（3分）。（只要有一条删除的边不同，就是不同的方案）渗釤呛俨匀谔鱉调硯錦。

四、阅读程序写结果（共4题，每题8分，共计32分）

1.#include

using namespace

std;

int g(int m, int n, int x)

{ int ans = 0;

int i;

if (n == 1)

CCF NOIP2016 初赛提高组 C++语言试题

第4页，共10页

return 1;

for (i = x; i <= m / n; i++)

ans += g(m - i, n - 1, i);

铙誅卧泻噦圣骋贶頂廡。

return ans;

}

int main() { int

t, m, n;

cin >> m >> n;

cout << g(m, n, 0) <<

endl; return 0;

}

输入：8 4

输出：_________

2.#include

using namespace

std;

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 * n - 1;

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

CCF NOIP2016 初赛提高组 C++语言试题

第5页，共10页