NOIP 2017初赛普及组C/C++答案详解

￡神魔★判官ぃ 2022-05-26 06:26 572阅读 0赞

竞赛时间： 2017 年 10月14日 14:30~ 16:30  
选手注意：不得使用任何电子设备（如计算器、手机、电子词典等 ）或查阅任何书籍资料

# 一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） #

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

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

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

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

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

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

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

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

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

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

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

12.表达式`a*(b+c)*d`的后缀形式是（ ）  
A. `abcd*+*`  
B. `abc+*d*`  
C. `a*bc+*d`  
D. `b+c*a*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;

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

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

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

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

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

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

20.以下和计算机领域密切相关的奖项是（ ）  
A． 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 普利策奖

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

1.一个人站在坐标（0，0）处，面朝x轴正方向。第一轮，他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位 距离，然后右转……他一直这么走下去。请问第2017轮后，他的坐标是：（***,***\_）。（请在答题纸上用逗号隔开两空答案）

![2-1.png][]

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

![2-2.png][]

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

#include <stdio.h>
    #include <string.h>
    
    int main()
    {
        int t[256];
        char s[10];
        int i;
        scanf("%s", s);
    
        for(i = 0; i < 256; i++)
            t[i] = 0;
    
        for(i = 0; i < strlen(s); i++)
            t[s[i]]++;
    
        for(i = 0; i < strlen(s); i++)
            if(t[s[i]] == 1)
            {
                printf("%c\n", s[i]);
                return 0;
            }
    
        printf("no\n");
    
        return 0;
    }

输入： xyzxyw  
输出：\_\_\_\_\_\_\_\_\_\_\_.

#include <stdio.h>
    
    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;
        scanf("%d%d", &m, &n);
        printf("%d\n", g(m, n, 0));
    
        return  0;
    }

输入： 7 3  
输出：\_\_\_\_\_\_\_\_\_\_.

#include <stdio.h>
    #include <string.h>
    
    int main()
    {
        char ch[200];
        int a[200];
        int b[200];
        int n, i, t, res;
    
        scanf("%s", ch);
        n = strlen(ch);
        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;
        }
    
        printf("%d\n", res);
    
        return 0;
    }

输入： 1001101011001101101011110001  
输出：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

#include <stdio.h>
    
    int main()
    {
        int n, m;
        scanf("%d%d", &n, &m);
    
        int x = 1;
        int y = 1;
        int dx = 1;
        int dy = 1;
        int cnt = 0;
        int myCnt = 0;
    
        while(cnt != 2)
        {
            myCnt++;
            cnt = 0;
            x = x + dx;
            y = y + dy;
    
            if(x == 1 || x == n)
            {
                ++cnt;
                dx = -dx;
            }
    
            if(y == 1 || y == m)
            {
                ++cnt;
                dy = -dy;
            }
        }
    
        printf("%d %d\n", x, y);
    
        return  0 ;
    }

输入1： 4 3  
输出1： \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_（3分）

输入2：2017 1014  
输出 2： \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ (5分)

# 四、完善程序 （共2题，每题14分，共计28分） #

1.（快速幂）请完善下面的程序，该程序使用分治法求 x^p mod m的值。（第一空2分，其余3分）  
输入：三个不超过 10000的正整数 x, p, m .  
输出：x^p mod m的值。  
提示：若p为偶数，`x^p = (x^2)^p/2`; 若p为奇数，`x^p = x * (x^2)^(p-1)/2`

#include  <stdio.h>
    int x, p, m, i, result;
    
    int main()  
    {
        scanf("%d%d%d", &x, &p, &m) ;
        result = __(1)_____;
        
        while( __(2)______)  
        {
            if(p % 2 == 1)
                result = __(3)_______;
            p /= 2;
            x = __(4)_______;
        }
        
        printf("%d\n", __(5)_____);
        
        return  0 ;
    }

2.(切割绳子) 有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。（第一、二空2.5分，其余3分）  
输入：第一行是一个不超过100的正整数n,第二行是n个不超过10 ^ 6的正整数，表示每条绳子的长度，第三行是一个不超过10 ^ 8的正整数m。  
输出 ：绳段的最大长度，若无法切割，输出Failed.

#include  <stdio.h>
    
    int n, m, i, lbound, ubound, mid, count;
    int  len[100];  //绳子长度
       
    int main()  
    {
        scanf("%d", &n) ;
        count = 0;
        
        for(i = 0; i < n; i++) 
        {
             scanf("%d", &len[i]);
             ____(1)________;
        }
        
        scanf("%d", &m);
        
        if( ___(2)_____)  
        {
            printf("Failed\n") ;
            return  0 ;
        }
        
        lbound =1 ;
        ubound =1000000 ;
        while ( ____(3)______ )  
        {
            mid = ___(4)______;
            count =0 ;
        
            for(i = 0; i < n; i++ )
                ___(5)_____ ;
                
            if(count < m) 
              ubound = mid – 1 ;
            else 
              lbound = mid ;
        }
           
        printf("%d\n", lbound);
        
        return 0;
    }

# 参考答案 #

## 一、单项选择题 ##

1 B  
原码、反码、补码请参考 [https://www.jianshu.com/p/b53fe5765884][https_www.jianshu.com_p_b53fe5765884]  
正数的原码与反码、补码相同。  
负数的反码为原码取反，最高位符号位不变；负数的补码为原码取反加1，最高位符号位不变。

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

2 B

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

4 A  
8 bit = 1 B  
1024 B = 1KB  
800 \* 600 \* 16 / (8 \* 1024) = 937.5kB

5 A  
美国最早用于计算弹道和射击路线，即数值分析

6 A  
C语言是面向过程的语言

7 B  
NOI: National Olypiad in Infomatics，全国青少年信息学奥林匹克竞赛  
NOIP: National Olypiad in Infomatics in Provices，全国青少年信息学奥林匹克联赛

8 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 = 星期五。

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

10 A

![a-1.jpg][]

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

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

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

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

13 B  
考察栈的数据结构，可参考 [https://www.jianshu.com/p/f9e4961bf145][https_www.jianshu.com_p_f9e4961bf145]  
新元素入栈后，要把栈顶指针指到新元素的位置。

14 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

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

17 D  
考察归并排序，可参考《大话数据结构》9.8节。  
这题考的是比较次数，而不是时间复杂度或空间复杂度。

先看看最好的情况，设有序数组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 C  
从2022年开始，不可使用C和Pascal，只能使用C++

19 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 B  
奥斯卡是电影类的奖项  
诺贝尔有六种奖项：物理、化学、生物和医疗、文学、经济、和平  
普利策是新闻类的奖项

## 二、问题求解 ##

> 少儿编程答疑、算法答疑请加微信307591841或QQ307591841  
> ![公众号.jpg][.jpg]

[2-1.png]: /images/20220526/b6cda31a5ada443e85bd6cee550ae2f0.png
[2-2.png]: /images/20220526/28994b35909f4ea3ab7dba0a0f332376.png
[https_www.jianshu.com_p_b53fe5765884]: https://www.jianshu.com/p/b53fe5765884
[a-1.jpg]: /images/20220526/25793afcc77049bbbb1baaff1190892e.png
[https_www.jianshu.com_p_f9e4961bf145]: https://www.jianshu.com/p/f9e4961bf145
[.jpg]: /images/20220526/ba86fe6d53744e29b7c9f75694bc406b.png