试卷 2018年第二十四届NOIP信奥赛普及组初赛C++试题
2018年第二十四届NOIP信奥赛普及组初赛C++试题
一、单项选择题
第 1 题    单选题

以下哪一种设备属于输出设备:( )。(2018)

A.

扫描仪

B.

键盘

C.

鼠标

D.

打印机

第 2 题    单选题

下列四个不同进制的数中,与其它三项数值上不相等的是( )。

A.

(269)16

B.

(617)10

C.

(1151)8

D.

(1001101011)2

第 3 题    单选题

1MB 等于( )。

A.

1000 字节

B.

1024 字节

C.

1000X1000 字节

D.

1024X1024 字节

第 4 题    单选题

广域网的英文缩写是( )。(2018)

A.

LAN

B.

WAN

C.

MAN

D.

LNA

第 5 题    单选题

中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。(2018)

A.

1983

B.

1984

C.

1985

D.

1986

第 6 题    单选题

如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照CapsLock、 字母键A、字母键S、字母键D、字母键 F 的顺序循环按键, 即CapsLock、A、S 、D 、F 、CapsLock 、A 、S 、D 、F 、……,屏幕上输出的第81个字符是字母 ( ) 。

A.

A

B.

S

C.

D

D.

a

第 7 题    单选题

根节点深度为0 ,一棵深度为 h 的满k(k>1)叉树, 即除最后一层无任何子 节点外,每一层上的所有结点都有 k 个子结点的树,共有( )个结点。

A.

(kh+1 - 1) / (k - 1)

B.

kh-1

C.

kh

D.

(kh-1) / (k - 1)

第 8 题    单选题

以下排序算法中,不需要进行关键字比较操作的算法是( )。

A.

基数排序

B.

冒泡排序

C.

堆排序

D.

直接插入排序

第 9 题    单选题

给定一个含N个不相同数字的数组,在最坏情况下,找出其中最大或最小的 数,至少需要N - 1次比较操作。则最坏情况下,在该数组中同时找最大与  最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整, ⌊ ⌋表示向下取整)

A.

⌈3N / 2⌉ - 2

B.

⌊3N / 2⌋ - 2

C.

2N - 2

D.

2N - 4

第 10 题    单选题

下面的故事与( )算法有着异曲同工之妙。

从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座 山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里 有座庙,庙里有个老和尚给小和尚讲故事…… ’”

A.

枚举

B.

递归

C.

贪心

D.

分治

第 11 题    单选题

由四个没有区别的点构成的简单无向连通图的个数是( )。(2018)

A.

6

B.

7

C.

8

D.

9

第 12 题    单选题

设含有10个元素的集合的全部子集数为S,其中由7个元素组成的子集数为T,则T/S的值为( )。

A.

5/32

B.

15/128

C.

1/8

D.

21/128

第 13 题    单选题

10000以内,与10000互质的正整数有( )个。

A.

2000

B.

4000

C.

6000

D.

8000

第 14 题    单选题

为了统计一个非负整数的二进制形式中1的个数,代码如下: 

int CountBit(int x)

{

int ret = 0;

while (x)

{

ret++;

                          ;

}

return ret;

}

则空格内要填入的语句是( )。

A.

x >>= 1

B.

x &= x - 1

C.

x  |= x >> 1

D.

x <<= 1

第 15 题    单选题

下图中所使用的数据结构是( )。(2018)

A.

哈希表

B.

C.

队列

D.

二叉树

二、问题求解
第 16 题    填空题

甲乙丙丁四人在考虑周末要不要外出郊游。

已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定 去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不 去。如果周末丙去了,则甲            (去了/没去) (1 分),乙            (去 了/没去) (1 分),丁            (去了/没去) (1 分),周末            (下雨/ 没下雨) (2 分)。


第 17 题    填空题

从1到2018这2018个数中, 共有        个包含数字8的数。

包含数字8的数是指有某一位是“8”的数,  例如“2018”与“188”。

三、阅读程序写结果
第 18 题    填空题
#include <cstdio>
char st[100];
int main() {
	scanf("%s", st);
	for (int i = 0; st[i]; ++i) {
		if ('A' <= st[i] && st[i] <= 'Z')
			st[i] += 1;
	}
	printf("%s\n", st);
	return 0;
}

输入: QuanGuoLianSai

输出:                                     

第 19 题    填空题
#include <cstdio>
int main() {
	int x;
	scanf("%d", &x);
	int res = 0;
	for (int i = 0; i < x; ++i) {
		if (i * i % x == 1) {
			++res;
		}
	}
	printf("%d", res);
	return 0;
}

输入: 15

输出:         

第 20 题    填空题
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
	if (n == 0) return m;
	if (m == 0) return n % 3;
	return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
	cin >> n >> m;
	cout << findans(n, m) << endl;
	return 0;
}

输入: 5 6

输出:          

第 21 题    填空题
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", d + i);
		v[i] = false;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (!v[i]) {
			for (int j = i; !v[j]; j = d[j]) {
				v[j] = true;
			}
			++cnt;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

输入: 10 7 1 4 3 2 5 9 8 0 6

输出:          

四、完善程序
第 22 题    问答题

(最大公约数之和)下列程序想要求解整数n的所有约数两两之间最大公约 数的和对10007求余后的值,试补全程序。(第一空 2 分,其余 3 分)

举例来说,4的所有约数是1,2,4 。1和2的最大公约数为1;2和4的最大公约 数为2;1和4的最大公约数为1。于是答案为1+2+1=4。

要求 getDivisor 函数的复杂度为o(√n),gcd 函数的复杂度为为o(log max(a, b))。


#include <iostream>

using namespace std;

const int N = 110000, P = 10007;

int n;

int a[N], len;

int ans;

void getDivisor() {

len = 0;

for (int i = 1;     (1)     <= n; ++i)

if (n % i == 0) {

a[++len] = i;

if (     (2)      != i) a[++len] = n / i;

}

}

int gcd(int a, int b) {

if (b == 0) {

                       (3)           ;

}

return gcd(b,      (4)     );

}

int main() {

cin >> n;

getDivisor();

ans = 0;

for (int i = 1; i <= len; ++i) {

for (int j = i + 1; j <= len; ++j) {

ans = (      (5)     ) % P;

}

}

cout << ans << endl;

return 0;

}

第 23 题    问答题

对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi  = n + 1。

举例来说,如果n=5且p为1  5  4   2  3,则q为2  6  6  5  6。

下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2分,其余3分)

数据范围 1≤n≤105


#include <iostream>

using namespace std;

const int N = 100010;

int n;

int L[N], R[N], a[N];

int main() {

cin >> n;

for (int i = 1; i <= n; ++i) {

int x;

cin >> x;

                 (1)      ;

}

for (int i = 1; i <= n; ++i) {

R[i] =      (2)     ;

L[i] = i - 1;

}

for (int i = 1; i <= n; ++i) {

L[       (3)     ] = L[a[i]];

R[L[a[i]]] = R[      (4)     ];

}

for (int i = 1; i <= n; ++i) {

cout <<      (5)      << " ";

}

cout << endl;

return 0;

}

答题卡
一、单项选择题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
二、问题求解
16 17
三、阅读程序写结果
四、完善程序
22 23
题目总数:23
总分数:100
时间:不限时
QQ
公众号
客服
扫一扫