2017NOIP真题题解：

程序员文章站 2024-03-18 21:41:58

...

2017年普通组详解：

1.在8位二进制补码中，10101011表示的数是十进制下的（）
A． 43 B. -85 C. -43 D. -84

1答案：B
正数的原码与反码、补码相同。
负数的反码为原码取反，最高位符号位不变；负数的补码为原码取反加1，最高位符号位不变。

所以，负数的原码为补码减1取反，最高位为符号位不用变。
10101011减1变成10101010，再取反变成11010101
11010101 = -(64 + 16 + 4 + 1) = -85

2.计算机存储数据的基本单位是（ B）
A. bit B. Byte C. GB D. KB

3.下列协议中与电子邮件无关的是（）
A. POP3 B. SMTP C WTO D IMAP

答案： C
POP3: Post Office Protocol - Version 3，邮局协议3
SMTP: Simple Mail Transfer Protocol，简单邮件传输协议
WTO: World Trade Organization，世界贸易组织
IMAP: Internet Mail Access Protocol，因特网邮件访问协议

4.分辨率为800*600、16位色的位图，存储图像信息所需的空间为（）
A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB

答案：A
8 bit = 1 B
1024 B = 1KB
800 * 600 * 16 / (8 * 1024) = 937.5kB

5.计算机应用的最早领域是（ A）
A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制

6.下列不属于面向对象程序设计语言的是（ A）
A. C B. C++ C. Java D. C#

7.NOI的中文意思是（B ）
A. 中国信息学联赛 B. 全国青少年信息学奥林匹克竞赛
C. 中国青少年信息学奥林匹克竞赛 D. 中国计算机学会

8.2017年10月1日是星期日，1999年10月1日是（ C）
A. 星期三 B.星期日 C. 星期五 D.星期二

解析：非闰年，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 = 星期五。

9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有（ C）
A. 36 B. 48 C. 96 D. 192

解析：
求组合数：C(4, 2) * C(4, 3) * C(4, 3) = 6 * 4 * 4 = 96

10.设G是有n个结点、m条边（n≤m）的连接图，必须删去G的（A ）条边，才能使得G变成一棵树。
A. m-n+1 B. m-n C. m+n+1 D. n-m+1

解析：

树的节点数 = 边数 + 1，比如上图中节点10个，边有9条。
题目中，图要变成树，只能保留n - 1条边。m - (n - 1) = m - n + 1

11.对于给定的序列｛ak｝,我们把（i , j）称为逆序对当且仅当 i<j且ai > aj .那么序列1，7，2，3，5，4的逆序对数为（B）个
A. 4 B. 5 C. 6 D. 7

7 2， 7 3， 7 5， 7 4， 5 4。共五对。

12.表达式a*(b+c)*d的后缀形式是（）
A. abcd*+*
B. abc+*d*
C. a*bc+*d
D. b+c*a*d

解析：

考察利用栈将中缀表达式变为后缀表达式。
中缀表达式转换成后缀表达式的规则：
（1）遇到操作数：直接输出（添加到后缀表达式中）
（2）栈为空时，遇到运算符，直接入栈
（3）遇到左括号：将其入栈
（4）遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出
（5）遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
（6）最终将栈中的元素依次出栈，输出

本题中的执行顺序为：
（1）输出a，
（2）“”、“(”依次入栈
（3）输出b
（4）“+”入栈
（5）输出c
（6）遇到右括号，将栈顶元素“+”出栈并输出，将栈顶元素“（”出栈但不用输出
（7）遇到“”，因为栈中只有一个元素“”，运算符相等，所以“”出栈并输出，新遇到的“”入栈
（8）输出d
（9）将栈中的元素“”输出
所以，输出的顺序，即后缀形式为“abc+d”

13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（B ）
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;

解析：新元素入栈后，要把栈顶指针指到新元素的位置。

14.若串S=“copyright”，其子串的个数是（C ）
A. 72 B. 45 C. 46 D. 36

解析：

长度为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

15.十进制小数13.375对应的二进制数是（）
A. 1101.011 B. 10111.011 C. 1101.101 D. 1010.01

解析：

整数部分，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

解析：

A中，每次进栈一个字母，然后该字母立马出栈
B中，先入栈a，弹出a；再入栈bcd，弹出dcb；第三次入栈e，弹出e；最后入栈fg，弹出gf
C中，无论怎样入栈，都不会有db的出栈顺序
D中，把所有字母进栈，再把所有字母出栈

17.设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（）次比较
A. n2 B. n log n C. 2n D. 2n-1

解析：

这题考的是比较次数，而不是时间复杂度或空间复杂度。

先看看最好的情况，设有序数组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次

18.从（）年开始，NOIP竞赛将不再支持Pascal语言
A. 2020 B. 2021 C. 2022 D. 2023

解析：

从2022年开始，不可使用C和Pascal，只能使用C++

19.一家四口人，至少两个人生日属于同一月份的概率是（ )
(假定每个人生日属于每个月份的概率相同且不同人之间相互独立)
A. 1/12 B. 1/144 C. 41/96 D. 3/4

解析：

设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. 普利策奖

解析：奥斯卡是电影类的奖项
诺贝尔有六种奖项：物理、化学、生物和医疗、文学、经济、和平
普利策是新闻类的奖项

个人站在坐标（0, 0）处，面朝x 轴正方向。第一轮，他向前走1 单位距离，然后右转；第二轮，他向前走2 单位距离，然后右转；第三轮，他向前走3 单位距离，然后右转……他一直这么走下去。请问第2017 轮后，他的坐标是：（，）。

【解析】

2017NOIP真题题解：

走法见上图，第1步，X轴+1，第2步，Y轴-2，第3步X轴-3，第4步，Y轴+4，第5步，X轴+5，...，可以找出规律：假设走的步数为n，n%4，余1是X轴+n，余2是Y轴-n，余3是X轴-n，余0是Y轴+n，2017%4=1，2016%4=0，所以x轴是1-3+5-7+9...+2017=1+(-3+5-7+9...-2015+2017)=1+1008/2*2=1009，y轴是-2+4-6+8-10...+2016=1008/2*2=1008。所以最终坐标是（1009，1008）

22，如下图所示，共有 13 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 1 变 0，或由 0 变 1）。现在要使得所有的格子中的数字都变为 0，至少需要___3______次操作。
2017NOIP真题题解：

【解析】尽可能操作一次多改变几个格子。第1次操作第三行第四个，第2次操作第三排第三个，第三次操作第一排第一个。答案3。

第 23 题

** 阅读程序写结果: **

#include<iostream>
using namespace std;
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______

第 24 题

**阅读程序写结果: **

#include<iostream>
using namespace std;
int g(int m, int n, 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_____

第 25 题

**阅读程序写结果: **

#include<iostream>
using namespace std;
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______

第 26 题

** 阅读程序写结果 **

#include<iostream>
using namespace std;
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：___1 3______（3 分）

输入 2：2017 1014
输出 2：___ 2017 1______（5 分）

27 题

完善程序：
（快速幂） 请完善下面的程序，该程序使用分治法求x^{p}\ mod\ mxp mod m 的值。（第一空 2 分，其余 3 分）

输入：三个不超过 10000 的正整数 x，p，m。
输出：x^{p}\ mod\ mxp mod m的值。
提示：若 pp 为偶数，x^{p}=(x^{2})^{p/2}xp=(x2)p/2；若 pp 为奇数，x^{p}=x^{*}(x^{2})^{(p-1)/2}xp=x∗(x2)(p−1)/2。

#include<iostream>
using namespace std;
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 / p
正确答案： result * x % m
正确答案： x * x % m
正确答案： result
第 28 题完善程序：

（切割绳子） 有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。（第一、二空 2.5 分，其余 3 分）

输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过10^{6}106的正整数，表示每条绳子的长度，第三行是一个不超过10^{8}108的正整数 m。输出：绳段的最大长度，若无法切割，输出 Failed。

#include<iostream>
using namespace std;
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;
        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;
}

1.
正确答案： count=count+len[i] / count+=len[i]
2.
正确答案： count<m / m>count
3.
正确答案： lbound<ubound / ubound>lbound
4.
正确答案： (lbound+ubound+1)/2 / (lbound+ubound+1)>>1 / (lbound+ubound)/2+1
5.
正确答案： count=count+len[i]/mid / count+=len[i]/mid

2017NOIP真题题解：