NOIP2015初赛普及组试题及参考答案_C++

### NOIP2015初赛普及组试题及参考答案_C++ #### 背景介绍 这份文档提供了第二十一届全国青少年信息学奥林匹克联赛初赛（NOIP2015）普及组C++语言试题及其参考答案。考试时间为2015年10月11日14:30-16:30。该试卷主要分为三个部分：单项选择题、问题求解题和阅读程序写结果题。 #### 单项选择题解析 1. **1MB等于(D.1024×1024字节)** - **知识点**：计算机存储单位。在计算机科学中，1MB（兆字节）通常定义为1024×1024字节。这是因为计算机采用二进制计数系统，每个单位是基于2的幂次方来定义的。 2. **在PC机中，PENTIUM(奔腾)、酷睿、赛扬等是指(C.CPU的型号)** - **知识点**：处理器型号。Pentium（奔腾）、酷睿(Core)和赛扬(Celeron)等术语指的是不同类型的中央处理器（CPU）型号。这些型号由Intel公司生产，并广泛应用于个人计算机中。 3. **操作系统的作用是(C.控制和管理系统资源)** - **知识点**：操作系统的功能。操作系统是管理计算机硬件与软件资源的程序，它负责分配和协调计算机的各种资源，包括处理器时间、内存空间等，确保计算机系统的正常运行。 4. **在计算机内部用来传送、存贮、加工处理的数据或指令都是以(A.二进制码)形式进行的** - **知识点**：数据表示。计算机内部的所有数据和指令都以二进制形式表示。二进制是由0和1组成的数字系统，这是计算机能够理解和处理的基础。 5. **下列说法正确的是(A.CPU的主要任务是执行数据运算和程序控制)** - **知识点**：CPU的功能。中央处理器（CPU）的主要职责是执行指令集，包括数据运算和逻辑判断等，以及控制程序的执行流程。 6. **二进制数00100100和00010100的和是(C.01000100)** - **知识点**：二进制加法。二进制数的加法遵循基本的位运算规则，即0+0=0、0+1=1、1+0=1、1+1=10。因此，00100100 + 00010100 = 01000100。 7. **与二进制小数0.1相等的十六进制数是(C.0.2)** - **知识点**：二进制与十六进制转换。二进制小数0.1相当于十六进制中的0.2。这是因为0.1在二进制中表示为1/2，在十六进制中表示为2/10。 8. **所谓的“中断”是指(B.当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的过程)** - **知识点**：中断机制。计算机中的中断是一种允许系统响应外部事件的机制。当外部设备（如键盘）需要与CPU交互时，会向CPU发送一个中断信号，此时CPU会暂停当前正在执行的任务，转去处理这个新的请求。 9. **计算机病毒是(B.人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合)** - **知识点**：计算机病毒定义。计算机病毒是指一种恶意程序，它可以自我复制并附着于其他合法程序上，通过传播和执行破坏计算机系统或窃取用户信息。 10. **FTP可以用于(A.远程传输文件)** - **知识点**：FTP协议。FTP（文件传输协议）主要用于在网络上传输文件。用户可以通过FTP客户端软件连接到FTP服务器，实现文件的上传和下载。 11. **下面哪种软件不属于即时通信软件(D.P2P)** - **知识点**：即时通信软件。QQ、MSN和微信都是常用的即时通信软件，而P2P（点对点）技术主要用于文件共享，不属于即时通信软件。 12. **6个顶点的连通图的最小生成树，其边数为(B.5)** - **知识点**：最小生成树。对于一个包含n个顶点的连通图，它的最小生成树将包含n-1条边。 13. **链表不具备的特点是(A.可随机访问任何一个元素)** - **知识点**：链表特性。链表是一种线性数据结构，其中每个元素都包含指向下一个元素的链接。链表的一个主要缺点是不能像数组那样通过索引直接访问任意位置的元素。 14. **线性表若采用链表存储结构，要求内存中可用存储单元地址(D.连续不连续均可)** - **知识点**：链表存储。链表的存储不需要连续的内存空间，每个节点可以存储在内存中的任何位置，通过指针链接起来形成链表。 15. **今有一空栈S，对下列待进栈的数据元素序列a，b，c，d，e，f依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S的栈顶元素为(C.a)** - **知识点**：栈操作。按照题目描述的操作顺序，最后栈中剩余的元素为a和b，且a位于栈顶。 16. **前序遍历序列与中序遍历序列相同的二叉树为(D.只有根结点的二叉树或非叶子结点只有右子树的二叉树)** - **知识点**：二叉树遍历。前序遍历和中序遍历结果相同的二叉树要么只有一个根结点，要么所有的非叶子结点都没有左子树。 17. **如果根的高度为1,具有61个结点的完全二叉树的高度为(B.6)** - **知识点**：完全二叉树高度。对于具有n个结点的完全二叉树，其高度可以通过公式\[ \lceil log_2(n+1) \rceil \]来计算。 18. **下列选项中不属于视频文件格式的是(A.TXT)** - **知识点**：视频文件格式。TXT是文本文件格式，不属于视频文件格式。常见的视频文件格式包括AVI、MOV和RMVB等。 19. **设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1，则该算法的时间复杂度为(D.O(n^2))** - **知识点**：递归时间复杂度分析。根据递推关系式分析，该算法的时间复杂度为O(n^2)。 20. **在NOI系列赛事中参赛选手必须使用累承办单位统一提供的设备。下列物品中不允许选手自带的是(C.身份证)** - **知识点**：竞赛规则。身份证属于个人身份证明文件，通常不允许选手自带，以防止作弊。 #### 题目解答示例 1. **重新排列1234使得每一个数字都不在原来的位置上，一共有种排法。** - **知识点**：错排问题。对于n个元素的错排问题，答案可以通过递推公式\( D_n = (n-1) * (D_{n-1} + D_{n-2}) \)来计算，其中\( D_0 = 1 \)且\( D_1 = 0 \)。对于本题，n=4，答案为\( D_4 = 9 \)。 2. **一棵结点数为2015的二叉树最多有个叶子结点。** - **知识点**：二叉树叶子结点数量。在二叉树中，当所有非叶子结点都有两个子结点时，叶子结点的数量最多。设树中有n个结点，那么最多有\(\lfloor n/2 \rfloor\)个叶子结点。对于2015个结点的二叉树，最多有1007个叶子结点。 #### 阅读程序写结果题解析 1. **程序1输出：** - **代码分析**：这段程序首先声明了三个整型变量a、b、c，并分别赋值为1、2、3。然后通过if语句判断a和b的大小，如果a大于b，则进一步判断a和c的大小。根据条件，最终输出c的值。 - **输出结果**：3 2. **程序2输出：** - **代码分析**：程序定义了一个名为`EX`的结构体，其中包含两个整型变量a和b以及一个结构体`point`类型的变量c。`point`结构体包含两个整型变量x和y。程序通过结构体成员操作符来给`EX`类型的变量e的成员赋值，并输出c的x和y的值。 - **输出结果**：3,2 以上是对NOIP2015初赛普及组试题及参考答案的详细解析，旨在帮助读者更好地理解计算机基础知识及编程技巧。