2016第二十二届全国青少年信息学奥林匹克联赛初赛
摘要
单项选择题
本题考察计算机基础知识和基本概念：
- 识别微软公司出品软件（D项）；
- 理解二进制编码（C项）；
- 判断无线通信技术（D项）；
- 分析CPU厂商（C项）；
- 区分存储设备（D项）；
- 解决字符串操作问题（C项）；
- 掌握数据结构中的二叉树性质（B项）；
- 理解算法复杂度分析（A项）；
- 应用逻辑推理解决问题（B项）；
问题求解
计算从4×4棋盘中选取两个不在同一行或列的方法数：
使用行列式方法计算排列组合总数为50种。
确定一棵2016结点的二叉树最少叶子节点数及最小高度：
最少叶子节点数为1024个；最小高度为11层。
阅读程序写结果
输入序列“1 2 3 4 5 6 0 7”后输出的结果为：
6,7,5；
输出的结果为y=3；
输出的结果为6,5,4,3,2,1；
输出的结果为false；
完善程序
完善读入整数函数：
填充条件语句(1)：c < '0' || c == '-'；
填充条件语句(2)：c > '9'；
填充条件语句(3)：c > '9' && c != '-'；
填充赋值语句(4)：num = num *10 + (c-'0')；
完善判断租用自行车人数的函数：
填充初始条件(1)：i = n;
填充判断条件(2)：M[i] <= C[j];
填充返回条件(3)：count >= mid;
填充判断条件(4)：check(mid);
填充更新条件(5)：r = mid –1;
一、单项选择题（共 20 题， 每题 1.5 分， 共计 30 分； 每题有且仅有一个正确选 项）
1. 以下不是微软公司出品的软件是（ D ）。
A. Powerpoint
C. Excel
B. Word
D. Acrobat Reader
Adobe是著名的软件公司，拥有photoshop,acrobat,audition等软件。
2. 如果 256 种颜色用二进制编码来表示，至少需要（ C ）位。
A. 6 B. 7 C. 8 D. 9
本题考查二进制的基本知识。256=2222222*2，故需要至少8位编码。
3. 以下不属于无线通信技术的是（ D ）。
A. 蓝牙 B. WiFi C. GPRS D. 以太网
以太网使用的是有线连接。
4. 以下不是 CPU 生产厂商的是（ C ）。
A. Intel B. AMD C. Microsoft D. IBM
Microsoft属于软件公司，没有硬件产品，IBM软硬件都生产。
5. 以下不是存储设备的是（ D ）。
A. 光盘 B. 磁盘 C. 固态硬盘 D. 鼠标
鼠标属于输入设备。
假设最初计算机处于小写输入模式，则一只反复按压CapsLock键后依次按A、S、D键的小老鼠将导致屏幕显示特定字符。具体而言，在该操作序列重复进行的情况下，第81个字符将被显示为大写字母C。
A. A B. S C. D D. a
输出的字符以“ASDasd” 为循环，81%6=3，故应该为第三个字符，即大写字母D。
7. 二进制数 00101100 和 00010101 的和是（ B ）。
A. 00101000 B. 01000001 C. 01000100 D. 00111000
二进制加法。逢二进一
8. 与二进制小数 0.1 相等的八进制数是（ ）。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
9. 以下是 32 位机器和 64 位机器的区别的是（ C ）。
A. 显示器不同
C. 寻址空间不同
B. 硬盘大小不同
D. 输入法不同
32位、64位指的是地址总线的位数
10. 以下关于字符串的判定语句中正确的是（ A ）。
A. 字符串是一种特殊的线性表
C. 字符串不可以用数组来表示
B. 串的长度必须大于零
D. 空格字符组成的串就是空串
本题运用了排他法进行处理。
将该字符串视为长度为零的空串来剔除选项B。
字符数组同样具备字符串功能从而被剔除。
空串指的是不包含任何字符，长度为0的字符串，因此排除D。
给定一棵二叉树的结构图，请问：当采用顺序存储方式时（即通过一维数组来存储该二叉树中的各个结点），其中根结点的位置定义为索引1。对于任意一个结点而言，假设其索引位置为i，则其左子节点的位置是2i，右子节点的位置是2i+1）。那么这棵二叉树中所有结点的最大索引是多少？
A. 6 B. 10 C. 12 D. 15
下标最大的节点为最下最右的节点。2的4次方减1=15。
12. 若有如下程序段，其中s 、a 、b 、c 均已定义为整型变量，且a 、c 均已赋值 （c 大于 0）。
s = a;
for (b = 1; b <= c; b++)
s = s + 1;
则与上述程序段修改 s 值的功能等价的赋值语句是 （ B ）。
A. s = a + b; B. s = a + c; C. s = s +c; D. s = b + c;
循环语句执行c次加1，就是求a和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;
}
AI助手程序运行后的输出结果是（ D ）。
A. 2,2 B. 2,3 C. 3,2 D. 3,3
continue 语句的功能在于跳过当前循环体中尚未执行的指令（如 k--），从而使得程序能够顺利进入下一个循环周期。这种控制结构的应用场景通常是在需要延迟执行某个操作的情况下进行操作处理。
n=3时才会执行k--使得k=3，并终止循环。
包含n个唯一元素的数组L=<x₁, x₂, ..., xₙ>具有以下特性：当且仅当存在一个索引i（其中1 < i < n），使得从第一个元素到第i个元素呈现严格递增趋势（即x₁ < x₂ < ... < x_{i-1} < x_i），并且从第i个元素到最后一个元素呈现严格递减趋势（即x_i > x_{i+1} > ... > xₙ），则该数组被定义为单峰序列，并称其第i项x_i为该序列的峰值点。
基于L是单峰的这一前提条件，请在a至c这三行代码处补充相应的逻辑设计内容，并以确保算法能够准确识别L的峰值点位置。
a. Search(k+1, n)
b. Search(1, k-1)
c. return L[k]
Search(1, n)
-
k←⌊n/2⌋
-
if L[k] > L[k-1] and L[k]
-
then __________
-
else if L[k] > L[k-1] and
-
then __________
-
else __________
正确的填空顺序是（ ）。
A. c, a, b B. c, b, a
L[k+1]
L[k] < L[k+1]
C. a, b, c D. b, a, c
15. 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶
。
A. 10 B. 12 C. 8 D. 16
16. 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（ ）种放法。
A. 7 B. 8 C. 21 D. 37
17. 下图表示一个果园灌溉系统， 有 A、B、C、D 四个阀门， 每个阀门可以打开
或关上， 所有管道粗细相同， 以下设置阀门的方法中， 可以让果树浇上水的
果树
是（ ）。
A. B 打开，其他都关上
C. A 打开，其他都关上
B. AB 都打开， CD 都关上
D. D 打开，其他都关上
Lucia及其朋友圈成员均在某一社交平台上注册了个人账户。下图展示了她们的关系网络图示意图，在此网络中任意两人之间若存在连线则表示彼此为好友关系而无连接线则表明两人互不相识。根据该社交平台的规定若用户A将某张图片分享给好友B那么B即可对这一图片进行评论但与此同时当B对图片做出评论后其所有好友将可查看这一评论及相应的图片内容但只有当A也已将该图片分享给上述好友时方能允许他们对同一图片进行回复评论
A. Dana, Michael, Eve
C. Michael, Eve, Jacob
B. Dana, Eve, Monica
D. Micheal, Peter, Monica
周末时分，小明与父母三人打算共同制作三道菜肴。由小明负责洗菜、父亲负责切 cooking、母亲负责炒烹饪。假设每一道菜肴的制作流程均为：首先需用时10分钟清洗蔬菜；随后进行切 cooking（即烹饪），这一过程占用10分钟；最后是炒 cooking阶段也是10分钟。因此完成一道菜肴总共需时30分钟。需要注意的是，在同一时间段内无法同时进行相同步骤的任务（例如洗厨房用品或切割食材）。那么完成这三道菜肴所需的最短时间为（ ）分钟？
A. 90 B. 60 C. 50 D. 40
20. 参加 NOI 比赛，以下不能带入考场的是（ C ）。
A. 钢笔 B. 适量的衣服 C. U 盘 D. 铅笔
U盘是可以存储信息的设备，不需要也不允许选手带入考场。
二、问题求解（包含两道题目共计10分）：其中全部解答正确可以获得满分（每道题目均值为5分）。具体得分为：第一小题答对即可获得全部分数（不得部分分数）；第二小题包含两个小问，在第一个空格处获得2分，在第二个空处获得3分
在一个不可旋转的4 \times 4棋盘上进行选择，在不考虑同行或同列的情况下，有多少种方法？
- 规定根节点的高度设为1。
一棵具有2016个结点的完全二叉树最少拥有多少个叶子节点；一棵具有2016个结点的完全二叉树最低的高度是多少。
。
三、阅读程序写结果（共 4 题， 每题 8 分， 共计 32 分）
1. #include
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
输出： _________
2. #include
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;
}
输出： _________
3. #include
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;
}
输出： _________
4. #include
int main() {
int i, length1, length2;
string s1, s2;
s1 = "I have a dream.";
CCF NOIP2016 初赛普及组 C++语言试题
第 6 页 ， 共 9 页
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;
}
输出： _________
四、完善程序（共 2 题，每题 14 分， 共计 28 分）
1. （读入整数）请完善下面的程序， 使得程序能够读入两个 int 范围内的整数，
请输出这两个整数，并要求每行输出一个。（其中第一题与第五题各得2.5分）其他部分每题得3分）需要注意的是，在输入时，请确保各整数值之间以及前后仅以空格或回车分隔符分开。假设输入数据合法有效。
例如： 输入：
输出：
#include
123 -789
123
-789
using namespace std;
int readint() {
int num = 0;
int negative = 0; char c;
c = cin.get();
while ((c < '0' || c =(1) ;
// 存储读取到的整数
// 负数标识
// 存储当前读取到的字符
c > '9') && c != '-')
if (c == '-')
negative = 1;
else
(2)__ ;
c = cin.get();
while ((3)) {
(4)__ ;
c = cin.get();
}
if (negative == 1)
(5)__ ;
return num;
}
int main() {
int a, b;
a = readint();
b = readint();
cout << a << endl << b << endl;
return 0;
}
学校派往某地执行郊游活动的任务共有n名学生。其中学校的郊游预算为A元。与此同时每位学生的个人支出预算为Mi元。为了简化管理学校统一将所有学生的出行安排统一调度：共有B辆自行车（B至少等于n）可供租用每辆车的日租金费用分别为Cj元（j=1,2,...,B）。每位学生可以选择使用自己的零花钱Mi或从学校的拨款中提取资金用于租车费用每位学生的费用支出必须独立计算不允许任何形式的资金周转以确保账务核算的透明化问题在于：在这种情况下最多能有多少学生能够顺利获得一辆自行车进行日常出行？
本题运用二分法进行求解。在区间 [l,r] 内，我们选取中间位置 mid，并通过计算确定自行车租赁人数是否能够达到mid的数量。通过贪心算法完成这一过程。
#include
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 =(1) ;
j = 1;
while (i <= n) {
if ((2))
count += C[j] - M[i];
i++;
j++;
}
return (3) ;
}
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 ((4)) {
ans = mid;
l = mid + 1;
} else
r =(5) ;
}
cout << ans << endl;
return 0;
}
[
用于获取地理信息数据的API请求路径：/api/v1/61b17c289e6cb947db56bae5/c/ip