NOIP 2016 普及组初赛试题

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

第 1 题 以下不是微软公司出品的软件是（）

{{ select(1) }}

• Powerpoint
• Word
• Excel
• Acrobat Reader

第 2 题 如果 256 种颜色用二进制编码来表示，至少需要（ ）位。

{{ select(2) }}

• 6
• 7
• 8
• 9

第 3 题 以下不属于无线通信技术的是（ ）。

{{ select(3) }}

• 蓝牙
• Wifi
• GPRS
• 以太网

第 4 题 以下不是 CPU 生产厂商的是（ ）。

{{ select(4) }}

• Intel
• AMD
• Microsoft
• IBM

第 5 题 以下不是存储设备的是（ ） 。

{{ select(5) }}

• 光盘
• 磁盘
• 固态硬盘
• 鼠标

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

{{ select(6) }}

• A
• S
• D
• a

第 7 题 二进制数 00101100 和 00010101 的和（ ）。

{{ select(7) }}

• 00101000
• 01000001
• 01000100
• 00111000

第 8 题 与二进制小数 0.1 相等的八进制数是（）。

{{ select(8) }}

• 0.8
• 0.4
• 0.2
• 0.1

第 9 题 以下是 32 位机器和 64 位机器的区别是（ ）。

{{ select(9) }}

• 显示器不同
• 硬盘大小不同
• 寻址空间不同
• 输入法不同

第 10 题 以下关于字符串的判定语句中正确的是（）。

{{ select(10) }}

• 字符串是一种特殊的线性表
• 串的长度必须大于零
• 字符串不可以用数组来表示
• 空格字符组成的串就是空串

第 11 题 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 i，则其左孩子位于下标 2i 处、右孩子位于下标 (2i+1) 处），则图中所有结点的最大下标为（ ）。

{{ select(11) }}

• 6
• 10
• 12
• 15

第 12 题 若有如下程序段，其中 s, a, b, c 均已定义为整型变量，且 a, c 均已赋值（c 大于 0）。 则与下述程序段修改 s 值的功能等价的赋值语句是（）。####

s = a;
for (b = 1; b <= c; b++)
    s = s + 1;

{{ select(12) }}

• s = a + b;

• s = a + c;

• s = s + c;

• s = b + c;

第 13 题 有以下程序：程序运行后输出的结果是（ ）。

#include <iostream>
using namespace std;

int main() {
    int k = 4, n = 0;
    while (n < k) {
        n++;
        if (n % 3 != 0)
            continue;
        k--;
    }
    cout << k << "," << n << endl;
    return 0;
}

{{ select(13) }}

• $2,2$

• $2,3$

• $3,2$

• $3,3$

第 14 题 第 14 题

给定含有 n 个不同的数的数组 L = <x1, x2, ..., xn>。如果 L 中存在 xi（1 < i < n）使得 x1 < x2 < ... < xi-1 < xi > xi+1 > ... > xn，则称 L 是单峰的，并称 xi 是 L 的“峰顶”。现在已知 L 是单峰的，请把 a-c 三行代码补全到算法中使得算法正确找到 L 的峰顶。

• Search(k+1, n)

• Search(1, k-1)

• return L[k] 正确的填空顺序是（）。 ####

Search(1, n)
1. k ← ⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then __________
6. else __________

{{ select(14) }}

• c,a,b

• c,b,a

• a,b,c

• b,a,c

第 15 题 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有( )个顶点。

{{ select(15) }}

• 10

• 12

• 8

• 16

第 16 题 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（）种放法。

{{ select(16) }}

• 7

• 8

• 21

• 37

第 17 题 下图表示一个果园灌溉系统，有 A, B, C, D 四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的是（）。

{{ select(17) }}

• B 打开，其他都关上

• AB 都打开，CD 都关上

• A 打开，其他都关上

• D 打开，其他都关上

第 18 题 Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非 A 也向他（她）分享了该照片）。现在 Lucia 已经上传了一张照片，但是她不想让 Jacob 看见这张照片，那么她可以向以下朋友 （ ）分享该照片。

{{ select(18) }}

• Dana, Michael, Eve

• Dana, Eve, Monica

• Michael, Eve, Jacob

• Micheal, Peter, Monica

第 19 题 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切菜 10 分钟，最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。

{{ select(19) }}

• 90

• 60

• 50

• 40

第 20 题 参加 NOI 比赛，以下不能带入考场的是（）。

{{ select(20) }}

• 钢笔

• 适量的衣服

• U 盘

• 铅笔

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

第21 题 请在下划线位置填入答案。

从一个 4 × 4 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有_______种方法。

答案： {{ input(21) }}

第22 题 请在下划线位置填入答案。

约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（  ）个叶子结点；一棵结点数为 2016 的二叉树最小的高度值是（  ）。

答案1：{{ input(22) }} 答案2：{{ input(23) }}

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

第1题 阅读程序写结果：

#include<iostream>
#include <iostream>
using namespace std;
int main()
{
    int max, min, sum, count = 0;
    int tmp;
    cin >> tmp;
    if (tmp == 0)
        return 0;
    max = min = sum = tmp;
    count++;
    while (tmp != 0)
    {
        cin >> tmp;
        if (tmp != 0)
        {
            sum += tmp;
            count++;
            if (tmp > max)
                max = tmp;
            if (tmp < min)
                min = tmp;
        }
    }
    cout << max << "," << min << "," << sum / count << endl;
    return 0;
}

输入：1 2 3 4 5 6 0 7

输出：{{ input(24) }}

第2题 阅读程序写结果：

#include <iostream>
using namespace std;

int main()
{
	int i = 100, x = 0, y = 0;
	while (i > 0)
	{
		i--;
		x = i % 8;
		if (x == 1)
			y++;
	}
	cout << y << endl;
	return 0;
}

输出：{{ input(25) }}

第3题 阅读程序写结果：

#include <iostream>
using namespace std;

int main(){
	int a[6] = {1, 2, 3, 4, 5, 6};
	int pi = 0;
	int pj = 5;
	int t, i;
	while (pi < pj)
	{
		t = a[pi];
		a[pi] = a[pj];
		a[pj] = t;
		pi++;
		pj--;
	}
	for (i = 0; i < 6; i++)
		cout << a[i] << ",";
	cout << endl;
	return 0;
}

输出：{{ input(26) }}

第 4 题 阅读程序写结果：

#include <iostream>
using namespace std;
int main()
{
	int i, length1, length2;
	string s1, s2;
	s1 = "I have a dream.";
	s2 = "I Have A Dream.";
	length1 = s1.size();
	length2 = s2.size();
	for (i = 0; i < length1; i++)
		if (s1[i] >= 'a' && s1[i] <= 'z')
			s1[i] -= 'a' - 'A';
	for (i = 0; i < length2; i++)
		if (s2[i] >= 'a' && s2[i] <= 'z')
			s2[i] -= 'a' - 'A';
	if (s1 == s2)
		cout << "=" << endl;
	else if (s1 > s2)
		cout << ">" << endl;
	else
		cout << "<" << endl;
	return 0;
}

输出 ：{{ input(27) }}

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

第1题：# 完善程序：####

请完善下面的程序，使得程序能够 读入两个 int 范围内的整数，并将这两个整数 分别输出，每行一个。

---

评分说明：

• 第一空：2.5 分
• 第五空：2.5 分
• 其余每空：3 分

---

输入格式：

输入的整数之间和前后只会出现 空格或回车。
输入数据保证合法。

---

示例：

输入： 123 -789

输出：

123
-789

程序如下：

#include <iostream>
using namespace std;

int readint(){
	int num = 0;	      // 存储读取到的整数
	int negative = 0;    // 负数标识
	char c;	              // 存储当前读取到的字符
	c = cin.get();
	while ((c < '0' || c > '9') && c != '-')
		c = ①;
	if (c == '-')
		negative = 1;
	else
		②;
	c = cin.get();
	while (③){
		④;
		c = cin.get();
	}
	if (negative == 1)
		⑤;
	return num;
}
int main()
{
	int a, b;
	a = readint();
	b = readint();
	cout << a << endl<< b << endl;
	return 0;
}

①{{ input(28) }} ②{{ input(29) }} ③{{ input(30) }} ④{{ input(31) }} ⑤{{ input(32) }}

第2题：# 完善程序：####

郊游活动问题描述

有 n 名同学参加学校组织的郊游活动。

• 学校提供的总经费为 A 元；
• 第 i 位同学自己携带了 M_i 元；
• 活动地点提供 B（B ≥ n）辆自行车供租用；
• 第 j 辆自行车的租用价格为 C_j 元。

每位同学只能为自己租用一辆自行车。
每位同学可以使用自己携带的钱或学校的经费来支付自行车费用。
每位同学不能借钱给他人。

---

问题目标

想知道 最多有多少位同学能够租用到自行车。

---

解题思路

本题采用 二分法 来求解。

对于区间 [l, r]，我们取中间点 mid，并判断：
是否可以让 至少 mid 位同学租用到自行车。

这个判断过程使用 贪心算法 实现。

得分说明

• 第四空：2.5 分
• 第五空：2.5 分
• 其余每空：3 分

程序如下：

#include <iostream>
using namespace std;
#define MAXN 1000000

int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid;

bool check(int nn) {
	int count = 0, i, j;
	i = ①;
	j = 1;
	while (i <= n) {
		if(②)
			count += C[j] - M[i];
		i++;
		j++;
	}
	return ③;
}
	
void sort(int a[], int l, int r) {
	int i = l, j = r, x = a[(l + r) / 2], y;
	while (i <= j) {
		while (a[i] < x) i++;
		while (a[j] > x) j--;
		if (i <= j) {
			y = a[i]; a[i] = a[j]; a[j] = y;
			i++; j--;
		}
	}
if (i < r) sort(a, i, r);
if (l < j) sort(a, l, j);
}

int main() {
	int i;
	cin >> n >> B >> A;
	for (i = 1; i <= n; i++)
		cin >> M[i];
	for (i = 1; i <= B; i++)
		cin >> C[i];
	sort(M, 1, n);
	sort(C, 1, B);
	l = 0;
	r = n;
	while (l <= r) {
		mid = (l + r) / 2;
		if(④){
            ans = mid;
			l = mid + 1;
		}else
			r = ⑤;
	}
	cout << ans << endl;
	return 0;
}

①{{ input(33) }} ②{{ input(34) }} ③{{ input(35) }} ④{{ input(36) }} ⑤{{ input(37) }}