2017年NOIP普及组初赛C++语言试题详解
郁孤台下清江水，中间多少行人泪。西北望长安，可怜无数山。青山遮不住，毕竟东流去。江晚正愁余，山深闻鹧鸪。
原创+纯手打，如有说的不对的地方，务必轻喷，如果觉得说的还行，就点个赞吧！
NOIP2017普及组初赛解析。初步评价，整体来说，难度比2016增大了，倒并不是说题目思维难度加大很多，而是直接了当的题目少了一些，有10%左右分值的题目是有坑的，一不小心就错了。2017年无论是提高组还是普及组，数学味道都非常浓，计算机科学的基础学科是数学，所以我们要重视数学学科的学习，尤其是与计算机科学相关的组合数学、概率论、离散数学、数列等知识的学习，在OI中，这些知识与数奥的方向并不完全一致，所以对于普及组打基础的小朋友来说，没学过数奥的也不要方！
话不多说，详解如下：
1.在8位二进制补码中，10101011表示的数是十进制下的( )。
A. 43 B. -85 C. -43 D. -84
【解析】B
正数的原码与反码、补码相同。
负数的反码为原码取反，最高位符号位不变；负数的补码为原码取反加1，最高位符号位不变。
所以，负数的原码为补码减1取反，最高位为符号位不用变。
10101011减1变成10101010，再取反变成11010101
11010101 = -(64 + 16 + 4 + 1) = -85
点评：第一题就有坑，虽然不能算坑。注意这是补码！所以要先转为原码才做进制转换！
补码转原码，取反加1，得到11010101。符号位是1，表明是负数，利用位权法求得-85。
第一道题就暗藏杀机！够狠！
难度指数：☆☆
2.计算机存储数据的基本单位是( )。
A. bit B. Byte C. GB D. KB
【解析】B
计算机存储数据的基本单位是字节Byte
点评：字节（Byte）是基本单位，比特（bit）是最小单位，注意区分。
难度指数：☆
3.下列协议中与电子邮件无关的是( )。
A. POP3 B. SMTP C. WTO D. IMAP
【解析】C
WTO: World Trade Organization，世界贸易组织
点评：算是常识题了。就算对邮件协议不是特别了解，WTO这个单词头上有一个大大的提示：“选我”。
难度指数：☆
4.分辨率为800x600、16位色的位图，存储图像信息所需的空间为( )。
A.937.5KB B. 4218.75KB C.4320KB D. 2880KB
【解析】A
8 bit = 1 B1024 B = 1KB800 * 600 * 16 / (8 * 1024) = 937.5kB
点评：高中生做这道题似乎更得心应手些。公式：像素点数量*每个像素点的颜色深度，800*600*16 bit，再进行单位换算。
难度指数：☆☆
5.计算机应用的最早领域是( )。
A.数值计算 B.人工智能 C.机器人 D.过程控制
【解析】A
美国最早用于计算弹道和射击路线，即数值分析
点评：送分题
难度指数：☆
6.下列不属于面向对象程序设计语言的是( )。
A. C B. C++ C. Java D. C#
【解析】A
C语言是面向过程的语言
点评：程序设计语言知识，难度不大，算常识题，但是平时不注意积累的同学可能不会。
难度指数：☆
7.NOI的中文意思是( )。
A.中国信息学联赛
B.全国青少年信息学奥林匹克竞赛
C.中国青少年信息学奥林匹克竞赛
D.中国计算机协会
【解析】B
NOI: National Olypiad in Infomatics，全国青少年信息学奥林匹克竞赛
点评：广告题第一题。试卷抬头就是答案提示。
难度指数：☆
8. 2017年10月1日是星期日，1999年10月1日是( )。
A.星期三 B.星期日 C.星期五 D.星期二
【解析】C
非闰年，X年10月1日到X+1年10月1日，经过365天。365 % 7 = 1，在星期上相当于过了一天。
闰年一年366天，366 % 7 = 2，在星期上相当于过了二天。
判断闰年有两个条件：能被400整除；或能被4整除且不能被100整除。
1999年10月1日~2017年10月1日，这18年里有13个非闰年5个闰年（2000，2004，2008，2012，2016），相当于经过13 + 5 * 2 = 23天，23 % 7 = 2，相当于经过了2天。
星期日 - 2 = 星期五。
点评：小学数奥题吗？平年365天，365%7-1，所以正常来说，现在星期x，一年后就是星期x+1，闰年就是x+2，然后可以反推，找出变化的循环节，甚至生推到1999年也行。
难度指数：☆☆☆
9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。
A. 36 B. 48 C. 96 D. 192
【解析】C
求组合数：
点评：基础的排列组合题。首先判断应用分步原理，然后具体每个选择的时候是一个组合问题，
难度指数：☆☆☆
10.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。
A.m–n+1 B. m-n C. m+n+1 D.n–m+1
【解析】A
树的节点数 = 边数 + 1，比如上图中节点10个，边有9条。题目中，图要变 成 树，只能保留n - 1条边。m - (n - 1) = m - n + 1
点评：学习生成树的时候，就知道n个顶点的生成树有n-1条边。所以答案就是m-（n-1）。比较直接的一道题。
难度指数：☆☆
11.对于给定的序列{ak}，我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么序列1, 7, 2, 3, 5, 4的逆序对数为( )个。
A. 4 B. 5 C. 6 D. 7
【解析】B
7 2， 7 3， 7 5， 7 4， 5 4。共五对。
点评：可以算是学习题，理解了逆序对的概念后，不难统计出来。比较科学的方法是遍历，按顺序分别统计以1开头的逆序对数量，以7开头的逆序对数量。
逆序对前几年也考过一次
难度指数：☆☆☆
12.表达式a * (b + c) * d的后缀形式是( )。
A. abcd*+* B. abc+*d*C. a*bc+*d D. b+c*a*d
【解析】B
考察利用栈将中缀表达式变为后缀表达式。
本题中的执行顺序为：
（1）输出a，
（2）“”、“(”依次入栈
（3）输出b
（4）“+”入栈
（5）输出c
（6）遇到右括号，将栈顶元素“+”出栈并输出，将栈顶元素“（”出栈但不用输出
（7）遇到“”，因为栈中只有一个元素“”，运算符相等，所以“”出栈并输出，新遇到的“”入栈
（8）输出d
（9）将栈中的元素“”输出
所以，输出的顺序，即后缀形式为“abc+d”
点评：经典题，考了很多次了。二叉树遍历衍生题型。
两种方法，一种根据中缀表达式画出表达式树，做后序遍历。一种就是加 括号的方式，然后把每层括号中的运算符移到后面（熟练之后括号也 不用加，直接移），去除括号即可。
难度指数：☆☆☆☆
13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。
A. hs->next=s;
B.s->next=hs;hs=s;
C.s->next=hs->next;hs->next=s;
D.s->next=hs;hs=hs->next;
【解析】B
考察栈的数据结构，新元素入栈后，要把栈顶指针指到新元素的位置。
点评：有一定难度，而且容易对题意理解错误。注意hs 只是一个栈顶指针，其并没有 next 指针域。
在栈顶插入，只需要保证s->next能指向当前栈顶元素，然后修改hs的指向，把s作为栈顶元素即可。
难度指数：☆☆☆☆
14.若串S = “copyright”，其子串的个数是( )。
A. 72 B. 45 C. 46 D. 36
【解析】C
长度为9的子串有9-9+1=1个，即S本身。
长度为8的子串有9-8+1=2个，即"copyrigh"和"opyright"。
长度为7的子串有9-7+1=3个，即"copyrig", “opyrigh"和"pyright”
……
长度为1的子串有9-1+1=9个，即"c", “o”, “p”, “y”, “r”, “i”, “g”, “h”, “t”
长度为0的子串有1个，即空串""
公式cnt = len * (len + 1) / 2 + 1
点评：一道老题，以前考过“Olympiad”，非常容易漏掉空串的情况。
难度指数：☆☆☆
15.十进制小数13.375对应的二进制数是( )。
A.1101.011 B. 1011.011 C.1101.101 D. 1010.01
【解析】A
整数部分，1101 = 2^3 + 2^2 + 2^0 = 13，排除BD
小数部分，小数十进制转二进制，就是小数部分不断乘以2直到小数完全消失，计算过程中每次取整数部分作为二进制值。
0.375 * 2 = 0.75 ，取整数部分0
0.75 * 2 = 1.5，取整数部分1，其小数部分0.5参与下次计算
0.5 * 2 = 1，取整数部分1
所以小数部分为011
点评：经典的进制转换题，分整数和小数部分计算。手算用拼凑法比较快。
难度指数：☆☆
16.对于入栈顺序为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
【解析】C
A中，每次进栈一个字母，然后该字母立马出栈B中，先入栈a，弹出a；再入栈bcd，弹出dcb；第三次入栈e，弹出e；最后入栈fg，弹出gfC中，无论怎样入栈，都不会有db的出栈顺序D中，把所有字母进栈，再把所有字母出栈
点评：又是经典的判断出栈序列是否合法的问题。基本的做法就是按照进栈顺序，结合选项模拟，选择出现矛盾的选项。
难度指数：☆☆
17.设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做( )次比较。
A. n2 B. n*logn C. 2n D. 2n-1
【解析】D
考察归并排序
这题考的是比较次数，而不是时间复杂度或空间复杂度。
先看看最好的情况，设有序数组A[4] = {1, 3, 5, 7}, 有序数组B[4] = {8, 10, 12, 14}, 数组C[8]用来存储比较后的结果。
1与8比较，把1放到C中，C[] = {1}
3与8比较，把3放到C中，C[] = {1, 3}
5与8比较，把5放到C中，C[] = {1, 3, 5}
7与8比较，把7放到C中，C[] = {1, 3, 5, 7}
剩下的不用比较，直接放到C中，C[] = {1, 3, 5, 7, 8, 10, 12, 14}
共比较了4次，即n次
再看看最坏的情况，设有序数组A[4] = {1, 3, 5, 7}, 有序数组B[4] = {2, 4, 6, 8}, 数组C[8]用来存储比较后的结果。
1与2比较，把1放到C中，C[] = {1}
2与3比较，把2放到C中，C[] = {1, 2}
3与4比较，把3放到C中，C[] = {1, 2, 3}
4与5比较，把4放到C中，C[] = {1, 2, 3, 4}
5与6比较，把5放到C中，C[] = {1, 2, 3, 4, 5}
6与7比较，把6放到C中，C[] = {1, 2, 3, 4, 5,6}
7与8比较，把7放到C中，C[] = {1, 2, 3, 4, 5, 6, 7}
最后的8不用比较，直接放到C中，C[] = {1, 2, 3, 4, 5, 6, 7, 8}
共比较了7次，即2n - 1次
点评：特殊值法比较快，比如n=1时，要一次比较，代入发现ABD均可，再代入n=2时，比如A是1和3，B是2和4，那么要3次比较，这样只有D答案符合。
难度指数：☆☆☆
18.从（ ）年开始，NOIP竞赛竟不再支持Pascal语言。
A. 2020 B. 2021 C. 2022 D. 2023
【解析】C
从2022年开始，不可使用C和Pascal，只能使用C++
点评：又是一道广告题！有点不按基本法出题了。
难度指数：☆
19.一家四口人，至少两个人生日属于同一月份的概率是()(假定每个人生日属于每个月份的概率相同且不同人之间相互独立)。
A. 1/12 B. 1/144 C. 41/96D. 3/4
【解析】C
设P(A)表示至少两个人生日在同一月份的概率，P(A’)表示四个人的生日都不在同一月份的概率，则P(A) = 1 - P(A’)
P(A’) = A(12, 4) / 12 ^ 4 = 12 * 11 * 10 * 9 / (12 * 12 * 12 * 12）= 55 / 96
P(A) = 1 - P(A’) = 41 / 96
点评：最难的一道题，概率题，高考级别？
难度指数：☆☆☆☆☆
20.以下和计算机领域密切相关的奖项是( )。
A.奥斯卡奖 B.图灵奖 C.诺贝尔奖 D.普利策奖
【解析】B
奥斯卡是电影类的奖项诺贝尔有六种奖项：物理、化学、生物和医疗、文学、经济、和平普利策是新闻类的奖项
点评：送分题
难度指数：☆
选择题总评：
9、13、19比较难，4虽然不一定学过，但是根据选项可以尝试精测计算，8需要细心。总体而言，对于经过系统培训足够时间的学生来说，难度不算很大。考题也比较常规，除了两道广告题以外。
二、问题求解（共2题，每题5分，共计10分）1.一个人站在坐标(0, 0)处，面朝x轴正方向。第一轮，他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位距离，然后右转......他一直这么走下去。请问第2017轮后，他的坐标是: _____________________。(请在答题纸上用逗号隔开两空答案)
参考答案：(1009,1008)
【解析】
根据题意描述，可以比较容易的发现坐标变化规律。
x+1
y-2
x-3
y+4
X+5
y-6
x-7
y+8
....
y+2016
x+2017
以4为周期，容易看出x的变化是
1-3+5-7+..+2013-2015+2017=（1-3）+（5-7）+.+（2013-2015）+20172017/4=504，有504个循环节，所以x=-2*504+2017=1009
类似地，
y的变化规律是
-2+4-6+..+2016=2*504=1008
2.如图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0，至少需要__________次操作。
参考答案：3
【解析】
分别把黄、红和绿色部分操作，即可达到目的。此题可能来源于摩尔庄园中的一个游戏
问题求解总评：问题求解比较注重考查观察和思维，数学好的同学会占有优势。
难度指数：☆☆☆
三、阅读程序写结果（共4题，每题8分，共计32分）1.
#include
using namespacestd;
int main() {
int t[256];
string s;
int i;
cin >> s;
for (i = 0; i < 256; i++)
t[i] = 0;
for (i = 0; i < s.length(); i++)
t[s[i]]++;
for (i = 0; i < s.length(); i++)
if (t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}
输入: xyzxyw
输出:__________。
参考答案：z
【解析】
注意到if语句中的return0；输出第一个字符之后直接结束程序了。
程序功能是统计字符串中个字符出现的次数，并且输出第一个只出现一次的字符。
点评：目测又会引发很多惨案，很多人没注意到if语句中的returm0；输出第一个字符之后直接结束程序了
难度指数：☆☆☆
2.
#include
using namespacestd;
int g(int m, intn, 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;
}
输入: 7 3
输出:____________。
参考答案：8
【解析】
一个比较简单的递归程序。细心一些是可以直接计算出来的。
g（7，3，0）=g（7，2，0）+g（6，2，1）+g（5，2，2）
再分别展开计算各部分
g（7.2，0）-g（7，1，0）+g（6，1，1）+g（5，1，2）+g（4.1，3）=1+1+1+1=4
g（6，2，1）=g（5，1，1）+g（4，1，2）+g（3，1，3）=1+1+1=3
g（5.2.2）=g（3，1，2）=1
最后计算出结果。
点评：一个比较简单的递归程序。细心一些是可以直接计算出来的。
难度指数：☆☆
3.
#include
using namespacestd;
int main() {
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for (i = 0; i < 200; i++)
b[i] = 0;
for (i = 1; i <= n; i++) {
a[i] = ch[i - 1] - '0';
b[i] = b[i - 1] + a[i];
}
res = b[n];
t = 0;
for (i = n; i > 0; i--) {
if (a[i] == 0)
t++;
if (b[i - 1] + t < res)
res = b[i - 1] + t;
}
cout << res << endl;
return 0;
}
输入: 1001101011001101101011110001
输出:_______________。
参考答案：11
点评：代码其实不长，直接模拟，细心些可以做出来。
难度指数：☆☆☆
4.
#include
using namespacestd;
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:____________。(3分)
输入2: 2017 1014
输出2:____________。(5分)
参考答案：
输出1: 1 3 输出2: 2017 1
【解析】
经过输入1的尝试，可以发现一些规律：
x的变化：1 2 3 4 3 2 1
y的变化：1 2 3 2 1 2 3
x和y的数据变化都有各自的周期，当恰好同时满足（x==1or x==）和（y==1or y==m）的时候就输出。
所以输入2可以
x：1 2 3 4..............2017
y：1 2 3 4..1014 1013..1
点评：简单规律题，暴力模拟即可
难度指数：☆
四、完善程序（共2题，每题14分，共计28分）1.快速幂
请完善下面的程序，该程序使用分治法求xp mod m的值。（第一空2分，其余3分）
输入：三个不超过10000的正整数x，p，m。
输出：xpmod m的值。
提示：若p为偶数，xp=(x2)p/2;若p为奇数，xp=x*(x2)(p-1)/2。
#include
using namespacestd;
int x, p, m, i,result;
int main() {
cin >> x >> p >> m;
result = ____①__ ;
while (___②___) {
if (p % 2 == 1)
result= ___③_____;
p /= 2;
x=____④_____ ;
}
cout << _______⑤______<< endl;
return 0;
}
参考答案：
|
① |
② |
③ |
④ |
⑤ |
|
1 |
p>0或p!=0 |
result*x%m |
x*x%m |
result |
点评：学习过的很快就能全部填出来，没学过的只能现学了，总体来说，都是比较好猜的，至少2个空是可以的。
难度指数：☆☆☆☆
2.切割绳子
有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。（第一、二空 2.5 分，其余 3 分）
输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过 106 的正整数，表示每条绳子的长度，第三行是一个不超过 108 的正整数 m。
输出：绳段的最大长度，若无法切割，输出Failed。
#include
using namespacestd;
int n, m, i,lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main() {
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
____①_____;
}
cin >> m;
if(____②____){
cout << "Failed" <<endl;< p="">
return 0;
}
lbound = 1;
ubound = 1000000;
while (____③____){
mid =____④____;
count = 0;
for (i = 0; i < n; i++)
____⑤____;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
参考答案：
|
① |
count =count+len[i]或count +=len[i] |
|
② |
countcount |
|
③ |
lboundlbound |
|
④ |
(1bound+ubound+1)/2或(1bound+ubound)/2+1 |
|
⑤ |
count=count+1en[i]/mid或count+=len[i]/mid |
点评：充分理解题意后还是比较好填空的，3、4空比较好填，其次是1、2空。
难度指数：☆☆☆
完善程序总评：
经典算法还是喜欢考，二分法尤其喜欢考，提高喜欢考，普及也喜欢考。要加强 NOIP必备算法的学习了。
以上是对2017NOIP初赛题目的解析，希望对大家复盘有所帮助，毕竟很快就要考试了！希望各位都能有一个好成绩！
--end--
声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com
