NOIP 2017信息学奥赛普及组C++试题

信息学奥林匹克竞赛（NOIP）是面向中学生的计算机编程竞赛，普及组针对的是初中生。普及组考试主要考察学生对计算机科学与编程的基础知识，逻辑思维能力以及解决实际问题的能力。本次试题主要涉及计算机科学中的基础知识，编程思想，以及算法分析等方面。 第一部分是单项选择题，共20题，每题1.5分，共计30分。涉及到的知识点包括二进制和十进制数的转换、计算机存储单位、电子邮件相关协议、图像分辨率与颜色位深度的关系、计算机应用最早领域、面向对象编程语言、全国信息学奥林匹克竞赛（NOI）的缩写、日期计算、组合数学问题、图论基础、逆序对概念、后缀表达式、数据结构（链式栈）、字符串子串数的计算、十进制小数转二进制、栈的操作序列、数组排序、Pascal语言支持情况以及概率计算等。 第二部分是问题求解，共2题，每题5分，共计10分。这部分题目需要考生根据实际问题进行编程求解，考验的是考生运用所学知识解决实际问题的能力。 第三部分是阅读程序写结果，共4题，每题8分，共计32分。这部分题目要求考生阅读给定的C++代码，并预测代码执行后的输出结果，考查对程序逻辑的理解和分析能力。 通过对这些题目的解答，参赛者可以对自己的计算机科学知识和编程技能有清晰的认识。尤其对于中学生来说，这些问题不仅能够激发他们学习计算机科学的兴趣，还能为他们未来在科学、工程和数学（STEM）领域的学习和工作打下坚实的基础。 下面，我将详细阐述每个知识点： 1. 二进制数表示：问题1涉及8位二进制数转换成十进制数。在这里，***二进制数实际上是一个补码形式的负数表示，在补码中最高位为符号位，1代表负数。补码的计算规则是正数的原码等于其补码，负数的补码等于其原码除符号位外所有位取反后加1。因此，***的原码为***（负数），加上1后得到***，转换为十进制即为-85。 2. 存储单位：问题2考察对计算机存储单位的理解。通常，计算机数据存储的基本单位是字节（Byte），而bit是数据的基本单位，1字节=8位。 3. 电子邮件协议：问题3要求识别与电子邮件相关的协议。其中，POP3（Post Office Protocol 3）、SMTP（Simple Mail Transfer Protocol）、IMAP（Internet Message Access Protocol）都是与电子邮件处理相关的协议，而WTO并不是一个标准的电子邮件相关协议。 4. 图像分辨率与颜色位深：问题4涉及到图像的分辨率和颜色深度对存储空间大小的影响。分辨率800x600表示图像宽度为800像素，高度为600像素。16位色意味着每个像素需要2个字节来存储颜色信息（因为2^16=65536种颜色）。因此，所需存储空间为800*600*2字节。 5. 计算机应用领域：问题5考察计算机应用最早领域的问题。历史上，计算机最初是为了解决数值计算的问题而被发明的，因此选项A是正确的。 6. 面向对象程序设计语言：问题6要求辨认不是面向对象程序设计语言的选项。选项C，C++是一种面向对象的编程语言。C#同样也是一种面向对象的语言。因此，选项A和D都不是面向对象语言。 7. 全国信息学奥林匹克竞赛缩写：问题7的正确答案是B，全国青少年信息学奥林匹克竞赛。 8. 日期计算：问题8要求使用星期的周期性进行计算。2017年与1999年相差18年，若1999年10月1日是星期五，则加上18年的周期数（假设每年周期数为365天，共6个完整周期+2天）得到的日期应该是星期三，但考虑到闰年的影响，答案可能会有所变化。 9. 组合数学问题：问题9通过组合数学的方法计算不同选课方案的总数，考察了排列组合的概念。 10. 图论基础：问题10询问如何将一个连通图变成树，需要了解图论中树的定义及边的性质。 11. 逆序对概念：问题11要求找出序列中的逆序对数量，是基础算法问题。 12. 后缀表达式：问题12考察后缀表达式的理解和转换方法，这是常见的计算机科学基础知识。 13. 链式栈操作：问题13涉及到数据结构中的栈操作，特别是链式栈的插入操作。 14. 字符串子串数：问题14要求计算给定字符串的子串数量，涉及字符串处理的算法。 15. 十进制与二进制转换：问题15是将十进制小数转换成二进制，需要了解小数的二进制转换规则。 16. 栈的合法操作序列：问题16考察栈操作序列的合法性，这是数据结构栈的一个重要应用。 17. 归并排序算法：问题17要求分析在最坏情况下归并排序算法需要比较的次数，这是一个基础的算法问题。 18. NOIP竞赛语言支持：问题18考察竞赛对编程语言支持的变更情况。 19. 概率计算：问题19是基础的概率问题，涉及组合数学的原理。 20. 计算机领域奖项：问题20要求识别与计算机科学领域密切相关的奖项，图灵奖是公认的计算机科学领域的最高荣誉。 通过这些题目，我们能够看到，信息学奥赛普及组C++试题考察的是学生对于计算机科学基础知识的掌握程度，以及在实际问题中运用这些知识的能力。参加此类竞赛对于培养学生的逻辑思维、编程能力和问题解决能力具有重要意义。