NOIP 2018 普及组初赛试题

ID: 1460

客观题

尝试: 4

已通过: 1

难度: 10

上传者:

junnyfan

标签>

NOIP 2018 普及组初赛试题

一、单选题（每题 2 分，共 30 分）

第 1 题以下哪一种设备属于输出设备？

扫描仪
键盘
鼠标
打印机

第 2 题下列四个不同进制的数中，与其它三项数值上不相等的是（）。

(269)₁₆
(617)₁₀
(1151)₈
(1001101011)₂

第 3 题1 MB 等于（）

1000 字节
1024 字节
1000×1000 字节
1024×1024 字节

第 4 题广域网的英文缩写是（）

第 5 题中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

1983
1984
1985
1986

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

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

( $k^(h+1)$ - 1) / (k - 1)
$k^h$ - 1
$k^h$
( $k^h$ - 1) / (k - 1)

第 8 题以下排序算法中，不需要进行关键字比较操作的算法是（）。

基数排序
冒泡排序
堆排序
直接插入排序

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

⌈3N/2⌉ − 2
⌊3N/2⌋ − 2
2N − 2
2N − 4

第 10 题下面的故事与（）算法有着异曲同工之妙。

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

枚举
递归
贪心
分治

第 11 题由四个没有区别的点构成的简单无向连通图的个数是（）。

第 12 题设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T/S 的值为（）。

5/32
15/128
1/18
21/128

第 13 题10000 以内，与 10000 互质的正整数有（）个。

2000
4000
6000
8000

第 14 题为了统计一个非负整数的二进制形式中 1 的个数，代码如下：

int CountBit(int x)
{
	int ret = 0;
	while (x)
	{
		ret++;
		___________;
	}
	return ret;
}

x >>= 1
x &= x - 1
x |= x >> 1
x <<= 1

第 15 下图中所使用的数据结构是（）。

哈希表
栈
队列
二叉树

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

第 1 题

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

已知： ① 如果周末下雨，并且乙不去，则甲一定不去；

② 如果乙去，则丁一定去；

③ 如果丙去，则丁一定不去；

④ 如果丁不去，而且甲不去，则丙一定不去。

如果周末丙去了，则：

甲 ________ {{ select(16) }}

去了
没去

乙 ________

去了
没去

丁 ________ {{ select(18) }}

去了
没去

周末 ________ {{ select(19) }}

下雨
没下雨

第 2 题

从 1 到 2018 这 2018 个数中，共有 __________ 个包含数字 8 的数。答案：{{ input(20) }}

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

第1题阅读程序写结果：

#include <stdio.h>
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 输出：{{ input(21) }}

第2题阅读程序写结果：

#include <stdio.h>
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 输出：{{ input(22) }}

第3题阅读程序写结果：

#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 输出：{{ input(23) }}

第4题阅读程序写结果：

#include <stdio.h>
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 输出：{{ input(24) }}

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

第1题：# 完善程序：最大公约数之和

下列程序想要求解整数 n 的所有约数两两之间最大公约数的和对 10007 取模后的值。

请补全程序。（第一空 2 分，其余 3 分）

示例说明

例如，对于整数 4：

所有约数为：1, 2, 4
各对之间的最大公约数如下：
- gcd(1, 2) = 1
- gcd(2, 4) = 2
- gcd(1, 4) = 1

因此，最大公约数之和为：1 + 2 + 1 = 4

性能要求

getDivisor() 函数的时间复杂度应为 O(√n)；
gcd(a, b) 函数的时间复杂度应为 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; ① <= n; ++i)
        if (n % i == 0) {
          a[++len] = i;
          if (② != i) a[++len] = n / i;
        }
}

int gcd(int a, int b) {
    if (b == 0) {
    	③ ;
    }
    return gcd(b, ④ );
}

int main() {
    cin >> n;
    getDivisor();
    ans = 0;
    for (int i = 1; i <= len; ++i) {
        for (int j = i + 1; j <= len; ++j) {
        	ans = (⑤ ) % P;
        }
    }
    cout << ans << endl;
    return 0;
}

①{{ input(25) }} ②{{ input(26) }} ③{{ input(27) }} ④{{ input(28) }} ⑤{{ input(29) }}

第2题：# 完善程序：最大公约数之和

对于一个 1 到 n 的排列 P（即 1 到 n 中的每个数在 P 中恰好出现一次），定义 q[i] 为：

在第 i 个位置之后，第一个比 P[i] 更大的元素的位置。
如果不存在这样的位置，则 q[i] = n + 1。

示例说明

当 n = 5，且排列 P 为 [1, 5, 4, 2, 3] 时，对应的 q 数组为 [2, 6, 6, 5, 6]。

解释如下：

P[1] = 1，后面第一个比它大的数是 5，位于位置 2
P[2] = 5，后面没有更大的数，所以 q[2] = 6
P[3] = 4，后面没有更大的数，所以 q[3] = 6
P[4] = 2，后面第一个比它大的数是 3，位于位置 5
P[5] = 3，后面没有元素，所以 q[5] = 6

程序说明

下列程序读入了排列 P，并使用双向链表的方式求解 q 数组，请补全缺失的代码部分。

#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;
        ① ;
    }
    
    for (int i = 1; i <= n; ++i) {
        R[i] = ② ;
        L[i] = i - 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        L[ ③ ] = L[a[i]];
        R[L[a[i]]] = R[ ④ ];
    }
    
    for (int i = 1; i <= n; ++i) {
    	cout << ⑤ << " ";
    }
    
    cout << endl;
    return 0;
}

①{{ input(30) }} ②{{ input(31) }} ③{{ input(32) }} ④{{ input(33) }} ⑤{{ input(34) }}

#1460. NOIP 2018 普及组初赛试题