2017年第二十三届NOIP信息学奥赛提高组初赛C++试题参考答案

一、单选题

1、从( )年开始，NOIP竞赛将不再支持Pascal语言。

A 2020

B 2021

C 2022

D 2023

2、在8位二进制补码中，10101011表示的数是十进制下的( )。(2017年提高组)

A、

B、

-85

C、

-43

D、

-84

3、分辨率为1600×900、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、

p(N)

B、

O(Nlog N)

C、

O(Nlog²N)

D、

O(N²)

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

A abcd*+*

B abc+*d*

C a*bc+*

D b+c*a*d

8、由四个不同的点构成的简单无向连通图的个数是( )。

A 32

B 35

C 38

D 41

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

D 1

11、设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。

A、

n²

B、

n logn

C、

D、

2n-1

12、在n(n≥3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。

正确的填空顺序是( )。

A b,c,a

B c,b,a

C c,a,b

D a,b,c

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

第一行的数为a₁₁；第二行的数从左到右依次为a₂₁，a,₂₂;…第n行的数为a_n1, a_n2,…. a_nn。从a₁₁开始，每一行的数a_ij只有两条边可以分别通向下一行的两个数a_(i+1)j和a_(i+1)(j+1)。用动态规划算法找出一条从a₁₁向下通到a_n1,a_n2.…,a_nn中某个数的路径，使得该路径上的数之和达到最大。

令C[i,j]是从a₁₁到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

二、多选题

16、以下排序算法在最坏情况下时间复杂度最优的有( )。

A 冒泡排序

B 快速排序

C 归并排序

D 堆排序

17、对于入栈顺序为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

18、下列算法中，( )是稳定的排序算法。

A 快速排序

B 堆排序

C 希尔排序

D 插入排序

19、以下是面向对象的高级语言的有( )。

A 汇编语言

B C++

C Fortran

D Java

20、以下和计算机领域密切相关的奖项有( )。

A 奥斯卡奖

B 图灵奖

C 诺贝尔奖

D 王选奖

三、简答题

21、如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要次操作。

参考答案：根据题目，我们可以发现，对于任意一个格子进行操作，都会改变它自己和它上下左右相邻的格子的数字。因此，我们可以从边缘的格子开始操作，每次操作都会使得它自己和它相邻的格子发生变化，从而使得内部的格子逐渐变为0。通过观察图片，我们可以发现，对于第一行的格子，进行一次操作后，第一行的数字会全部变为0，同时第二行的最左侧和最右侧的格子也会变为0。同样地，对于最后一行的格子，进行一次操作后，最后一行的数字会全部变为0，同时倒数第二行的最左侧和最右侧的格子也会变为0。然后，我们可以对第二行的中间7个格子和倒数第二行的中间7个格子进行操作，每次操作都会使得它们自己和它们相邻的格子发生变化，从而使得第一行和最后一行之间的格子也逐渐变为0。因此，最少需要13次操作才能使所有的格子中的数字都变为0。

22、如下图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是_____(2分)，最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同，就是不同的方案)

参考答案：最小代价是2，最小代价的不同方案数是3。

四、实操题

23、

#include <iostream>
using namespace std;

int g(int m, int n, int x) {
	int ans = 0;
	int i;
	if (n == 1)
		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

输出：_________

参考答案：28

24、

#include <iostream>
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

输出：_________

参考答案：输出：1 3 5 7 9

25、

#include <iostream>
using namespace std;

int n, s, a[100005], t[100005], i;
void mergesort(int l, 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++;
	}
	while (j <= r) {
		t[p] = a[j];
		p++;
		j++;
	}
	for (i = l; i <= r; i++)
		a[i] = t[i];
}
int main() {
	cin >> n;
	for (i = 1; i <= n; i++)
		cin >> a[i];
	mergesort(1, n);
	cout << s << endl;
	return 0;
}

输入：

2 6 3 4 5 1

输出：_________

参考答案：2

26、

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int x = 1;
	int y = 1;
	int dx = 1;
	int dy = 1;
	int cnt = 0;
	while (cnt != 2) {
		cnt = 0;
		x = x + dx;
		y = y + dy;
		if (x == 1 || x == n) {
			++cnt;
			dx = -dx;
		}
		if (y == 1 || y == m) {
			++cnt;
			dy = -dy;
		}
	}
	cout << x << " " << y << endl;
	return 0;
}

输入1：4 3

输出1：_________（2 分）

输入2：2017 1014

输出 2：_________（3 分）

输入3：987 321

输出3：_________（3 分）

参考答案：输入1：4 3输出1：2 3输入2：2017 1014输出 2：2017 1输入3：987 321输出3：321 1

27、（大整数除法）给定两个正整数p和q，其中p不超过10¹⁰⁰，q不超过100000，

求p除以q的商和余数。（第一空2分，其余3分）

输入：第一行是p的位数n，第二行是正整数p，第三行是正整数q。

输出：两行，分别是p除以q的商和余数。

#include <iostream>

using namespace std;

int p[100];

int n, i, q, rest;

char c;

int main() {

cin >> n;

for (i = 0; i < n; i++) {

cin >> c;

p[i] = c - '0';

}

cin >> q;

rest = (1) ;

i = 1;

while ( (2) && i < n) {

rest = rest * 10 + p[i];

i++;

}

if (rest < q)

cout << 0 << endl;

else {

cout << (3) ;

while (i < n) {

rest = (4) ;

i++;

cout << rest / q;

}

cout << endl;

}

cout << (5) << endl;

return 0;

}

参考答案：(1) 0(2) cin >> c(3) p[i](4) rest = rest * 10 + p[i](5) rest % q

28、（最长路径）给定一个有向无环图，每条边长度为1，求图中的最长路径长度。（第五空2分，其余3分）

输入：第一行是结点数n（不超过100）和边数m，接下来m行，每行两个整数a，b，表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。

输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

#include <iostream>

using namespace std;

int n, m, i, j, a, b, head, tail, ans;

int graph[100][100]; // 用邻接矩阵存储图

int degree[100]; // 记录每个结点的入度

int len[100]; // 记录以各结点为终点的最长路径长度

int queue[100]; // 存放拓扑排序结果

int main() {

cin >> n >> m;

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

graph[i][j] = 0;

for (i = 0; i < n; i++)

degree[i] = 0;

for (i = 0; i < m; i++) {

cin >> a >> b;

graph[a][b] = 1;

(1) ;

}

tail = 0;

for (i = 0; i < n; i++)

if ( (2) ) {

queue[tail] = i;

tail++;

}

head = 0;

while (tail < n - 1) {

for (i = 0; i < n; i++)

if (graph[queue[head] ][i] == 1) {

(3) ;

if (degree[i] == 0) {

queue[tail] = i;

tail++;

}

(4) ;

}

ans = 0;

for (i = 0; i < n; i++) {

a = queue[i];

len[a] = 1;

for (j = 0; j < n; j++)

if (graph[j][a] == 1 && len[j] + 1 > len[a])

len[a] = len[j] + 1;

if ( (5) )

ans = len[a];

}

cout << ans << endl;

return 0;

}

参考答案：1. 初始化邻接矩阵和入度数组。2. 读入边信息，建立邻接矩阵。3. 初始化队列，将入度为0的节点加入队列。4. 拓扑排序，每次从未入队的节点中选取一个，将其所有邻居的入度减1，若邻居的入度变为0，则将其加入队列。5. 计算最长路径。从队列中取出节点，更新以其为终点的最长路径长度，并更新答案。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！

2017年第二十三届NOIP信息学奥赛提高组初赛C++试题参考答案

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！