2017年第二十三届NOIP(C语言)普及组初赛试题及详细答案

竞赛时间: 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)称为逆序对当且仅当 iaj .那么序列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.如右图所示,共有13个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要_次操作。

三、阅读程序写结果(共4题,每题8分,共计32分)

1.

#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 输出:_.

2.

#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 输出:__.

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 输出:________________.

4.

#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.(快速幂)请完善下面的程序,该程序使用分治法求 xp 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 正数的原码与反码、补码相同。 负数的反码为原码取反,最高位符号位不变;负数的补码为原码取反加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 = 星期五。

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

10 A

树的节点数 = 边数 + 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 考察二叉树数据结构,可参考 https://www.jianshu.com/p/c95ea81b726d

如果没有指明是前缀(前序)、中缀(中序)还是后缀(后序),那么默认指的是中序遍历。 上图二叉树中, 中序遍历为a*(b+c)*d 后序遍历为abc+*d* 前序遍历为**a+bcd

13 B 考察栈的数据结构,可参考 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 考察归并排序,可参考 https://www.jianshu.com/p/5b08c571762d 设A中的元素为a1, a2, a3; B中的元素为b1, b2, b3; 依题意有a1 < a2 < a3 且 b1 < b2 < b3 比较的代码为

        while (left <= center && centerNext <= right) {
            //从两个数组中取出最小的放入临时数组
            if (data[left] <= data[centerNext]) {
                tmpArr[tmp++] = data[left++];
            } else {
                tmpArr[tmp++] = data[centerNext++];
            }
        }

这段代码是每比较一次,就把一个元素放到tmpArr中。 (1)比较最多的情况,比如tmpArr = {a1, b1, a2, b2, a3},或者tempArr = {a1, a2, b1, b2, a3},或者tmpArr = {b1, b2, a1, a2, a3},或者{b1, b2, a1, a2, b3}之类的。 注意最后一个元素肯定放在最后,不用比较。所以是2n - 1次。 (2)更少的情况,比如tmpArr = {a1, a2, b1, a3},这样比较2n - 2次就可以了。 (3)最少的情况,比如a3 < b1,则有tmpArr = {a1, a2, a3},这样比较n次就可以了。 所以,最多比较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 奥斯卡是电影类的奖项 诺贝尔有六种奖项:物理、化学、生物和医疗、文学、经济、和平 普利策是新闻类的奖项

1 坐标为(1009,) 先列出前十个坐标,然后找归律 第0轮:(0, 0) 第1轮:(1, 0) 第2轮:(1, -2) 第3轮:(-2, -2) 第4轮:(-2, 2) 第5轮:(3, 2) 第6轮:(3, -4) 第7轮:(-4, -4) 第8轮:(-4, 4) 第9轮:(5, 4) 第10轮:(5, -6) 可以看出,x的规律为(n + 1) / 2 * (-1) ^ ((n - 1) / 2) 所以x_2017 = 1009 * (-1) ^ 1008 = 1009 y的规律为(int(n + 2) / 4) * 2 * (-1) ^ (n / 2) 所以,y_2017 = (int(2017 + 2) / 4) * 2 * (-1) ^ (2017 / 2) = 504 * 2 * (-1) ^ 1008 = 1008

欲购完整答案请加微信307591841,想了解小朋友学编程请加QQ群581357582

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1008: [HNOI2008]越狱(组合数)

监狱有连续编号为 1…N1…N 的 NN 个房间,每个房间关押一个犯人,有 MM 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱...

5420
来自专栏Python数据科学

使用Pandas&NumPy进行数据清洗的6大常用方法

数据科学家花了大量的时间清洗数据集,并将这些数据转换为他们可以处理的格式。事实上,很多数据科学家声称开始获取和清洗数据的工作量要占整个工作的80%。

28920
来自专栏ImportSource

来来来,快来围观那个Kotlin

这个世界怎么了?我都惊了。 kotlin来了,就因为Google背书了一哈,你们就无条件的沸腾了。 这年头出来了所谓语言还少吗? ? 三天两头搞些新花样。 你们...

536110
来自专栏数据结构与算法

43:相关月

43:相关月 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 “相关月”是指那些在一年中月份的第一天星期数相同的月份。例如...

37160
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day11-接口;多态案例练习

Java基础-day11-接口&多态案例练习 题目要求1(多态): 定义家类 方法:饲养动物 动物类: 属性:年龄、姓名 方法:吃饭、睡觉 猫类、狗类、猪类均为...

42640
来自专栏大数据钻研

每个程序员都应该收藏的算法复杂度速查表

算法复杂度这件事 这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 O(Big-O)复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和...

33760
来自专栏小樱的经验随笔

基数排序与桶排序,计数排序【详解】

桶排序简单入门篇^-^ 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮...

39270
来自专栏coding for love

JS进阶系列03-JS面向对象的三大特征之多态

多态是同一个行为具有多个不同表现形式或形态的能力。在JAVA中,多态通过在子类中重写父类方法去实现。但是在JS中,由于JS本身是动态的,天生就支持多态。大家可以...

11520
来自专栏数说工作室

class 类—老司机的必修课 | 统计师的Python日记 第11课

本文是【统计师的Python日记】第11天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函...

382100
来自专栏阮一峰的网络日志

关于2的补码

问一个基本的问题。 负数在计算机中如何表示? 举例来说,+8在计算机中表示为二进制的1000,那么-8怎么表示呢? 很容易想到,可以将一个二进制位(bit)专门...

29330

扫码关注云+社区

领取腾讯云代金券