NOIP普及组竞赛复赛题目与答案

NOIP普及组竞赛复赛题目与答案考试时间：______分钟总分：______分姓名：______一、选择题1.下列关于算法的描述，正确的是（）。A.算法必须有输入B.算法必须有输出C.算法执行的操作数量必须是有限的D.算法执行的步骤必须是可定义的2.在长度为n的数组中查找最大元素，最坏情况下需要比较的次数为（）。A.n/2B.nC.n+1D.log2n3.下列排序算法中，不稳定排序是（）。A.冒泡排序B.插入排序C.选择排序D.快速排序4.计算机存储信息的基本单位是（）。A.位（bit）B.字节（Byte）C.字（Word）D.千字节（KB）5.一个整数除以3的余数可能是（）。A.-1B.0C.1D.26.下列数据结构中，属于线性结构的是（）。A.栈B.队列C.树D.图7.下列关于二叉树的描述，正确的是（）。A.二叉树的任何节点都有且只有两个子节点B.二叉树可以是空树C.二叉树的度为2D.二叉树不是线性结构8.下列程序段执行后，变量`c`的值为（）。```cinta=5,b=3,c;c=a%b;```A.0B.1C.2D.39.在C/C++语言中，用于输出信息的标准库函数是（）。A.`input()`B.`print()`C.`printf()`D.`scanf()`10.下列哪个运算符的优先级最高？（）A.`+`B.`*`C.`==`D.`=`11.若变量`x`是整型，表达式`x>0&&x<100`的值是（）。A.0B.1C.`true`D.`false`12.下列关于循环的描述，正确的是（）。A.循环体至少执行一次B.while循环和for循环可以完全互换C.do-while循环的判断条件在循环体之后检查D.break语句用于终止整个程序的执行13.下列哪个是合法的C/C++变量名？（）A.2timesB.-countC.intD.result_12314.若有定义`intarr[5]={1,2,3,4,5};`，则`arr[3]`的值是（）。A.1B.2C.3D.415.字符串常量在C/C++中存储在（）。A.数组B.字符指针C.结构体D.共享内存二、多选题1.下列关于递归的描述，正确的有（）。A.递归函数必须调用自身B.递归函数必须有终止条件C.递归是一种编程技巧D.递归函数会占用更多的内存空间2.下列关于数组操作的描述，正确的有（）。A.可以通过下标访问数组元素B.数组的大小在定义后可以改变C.数组可以存储不同类型的数据D.数组的下标通常从0开始3.贪心算法通常适用于解决（）问题。A.最优路径选择B.背包问题C.作业调度问题D.单源最短路径问题4.下列关于函数的描述，正确的有（）。A.函数可以提高代码的可重用性B.函数必须有返回值C.函数可以嵌套定义D.main函数是所有C/C++程序的入口5.在二叉搜索树中，对于任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值，下列描述正确的有（）。A.树中不存在重复值B.可以通过中序遍历得到有序序列C.可以通过前序遍历得到有序序列D.插入和删除操作相对简单6.下列关于运算符的描述，正确的有（）。A.`!`是单目运算符B.`*`是双目运算符C.`>`是三目运算符D.`+=`是复合赋值运算符7.在C/C++语言中，用于输入数据的标准库函数是（）。A.`printf()`B.`scanf()`C.`gets()`D.`putchar()`8.下列关于选择结构的描述，正确的有（）。A.if语句可以单独使用B.if-else语句可以嵌套使用C.switch语句的case标签必须是常量表达式D.switch语句可以与break语句结合使用9.下列关于字符串处理的描述，正确的有（）。A.字符串的长度是指其包含的字符数量B.字符串可以用字符数组表示C.`strlen()`函数可以计算字符串的长度D.字符串可以用`printf()`函数输出10.下列关于内存的描述，正确的有（）。A.栈内存通常由系统自动分配和回收B.堆内存的大小通常比栈内存大C.全局变量存储在栈内存中D.局部变量存储在堆内存中三、编程题1.写一个函数，接受一个整数n作为参数，返回1到n之间所有整数的和。例如，调用`sum(5)`应返回`1+2+3+4+5=15`。请使用循环实现。2.写一个函数，接受一个字符串`s`作为参数，返回该字符串的长度。假设字符串以空字符`'\0'`结尾。注意：不要使用库函数`strlen()`。请使用循环实现。3.有一个简单的密码规则：将输入的每个小写字母替换为其在字母表中后面第3位的字母，例如`a`变成`d`，`b`变成`e`，`z`变成`c`（因为`z`后面第3位是`a`）。非小写字母保持不变。写一个程序，接受一个字符串作为输入，输出加密后的字符串。4.有一个整数数组`arr`和一个目标值`target`，请编写代码找出数组中和为`target`的任意两个数，并返回它们的索引。假设每个输入都有且只有一组解，且不能重复使用同一个元素。例如，给定`arr=[2,7,11,15]`，`target=9`，返回`[0,1]`，因为`arr[0]+arr[1]=2+7=9`。请使用嵌套循环实现。5.编写一个程序，接受一行输入，该行包含若干个用空格分隔的整数。程序应输出这些整数按从小到大的顺序排列的结果，每个整数之间用空格分隔。请使用排序算法（如冒泡排序或选择排序）对输入的整数进行排序。假设输入的整数数量不超过100个。试卷答案一、选择题1.C解析：算法的基本特性包括有穷性、确定性、可行性。有穷性指算法必须在执行有限步骤后终止；确定性指算法的每一步都有确切的含义，无歧义；可行性指算法的每一步都可以被精确地执行。输入和输出不一定是必须的，但通常算法需要有输出才能体现其作用。2.B解析：查找最大元素需要遍历整个数组，依次比较每个元素与当前最大元素的大小。对于长度为n的数组，最坏情况是最大元素位于最后一个位置，或者需要比较所有元素才能确定最大值，因此比较次数为n次。3.C解析：选择排序在每一轮中从未排序的部分选择最小（或最大）的元素，并将其与未排序部分的第一个元素交换。这种交换可能会破坏相等元素的相对顺序。例如，数组[4,5,3,3,2]，第一次选择3，与第一个4交换后变为[3,5,4,3,2]，两个3的相对顺序发生了变化，因此选择排序是不稳定的。4.A解析：位（bit）是计算机中最小的数据单位，可以表示0或1两种状态。字节（Byte）通常由8个位组成，是计算机存储和传输信息的基本单位。字（Word）是计算机处理数据的基本单位，其位数因具体计算机架构而异。KB是千字节的缩写。5.B,C,D解析：整数除以3的余数只能是0、1或2。余数的范围取决于除数，除以3时，余数在[0,2]范围内。6.A,B解析：栈和队列都是线性结构，它们的数据元素具有一对一的逻辑关系。树是典型的非线性结构。图也是非线性结构。7.B解析：二叉树可以是空树（没有节点）。二叉树的节点最多有两个子节点，但不一定每个节点都有两个子节点（可以只有一个或没有）。二叉树的度是指最大度数，对于二叉树，最大度数为2。二叉树是一种非线性结构。8.B解析：`a%b`表示a除以b的余数。5除以3的商是1，余数是2。因此，`c=a%b;`执行后，`c=2`。9.C解析：`printf()`是C/C++标准库中的函数，用于格式化输出到控制台（通常是终端或命令行窗口）。`scanf()`用于从控制台读取格式化的输入。10.D解析：运算符的优先级从高到低大致为：括号`()`、单目运算符（如`!`,`-`）、乘除`*/%`、加减`+-`、关系运算符`<<=>>=`、相等与不等`==!=`、逻辑与`&&`、逻辑或`||`、赋值运算符`=`。`=`是赋值运算符，优先级最低。11.C解析：在C/C++中，关系运算符和逻辑运算符的结果都是整型值。`true`通常表示为1，`false`通常表示为0。表达式`x>0&&x<100`的逻辑值为`true`当且仅当`x`同时满足大于0且小于100，此时表达式的整型值为1。12.A,B,D解析：while循环和for循环都可以实现重复执行代码块的功能，但语法和适用场景不同。while循环的循环体至少执行一次当且仅当初始条件为真。if语句可以单独使用作为选择结构。do-while循环的循环体至少执行一次，因为判断条件在循环体之后检查。break语句用于立即退出最近的包含它的循环或switch语句，而不是终止整个程序。13.D解析：变量名必须以字母或下划线开头，后面可以跟字母、数字或下划线。选项A以数字开头，选项B以负号开头，选项C`int`是关键字，选项D`result_123`符合命名规则。14.D解析：数组的下标从0开始。`arr[5]`表示数组的第6个元素。数组`arr[5]={1,2,3,4,5};`中，`arr[0]=1`,`arr[1]=2`,`arr[2]=3`,`arr[3]=4`,`arr[4]=5`,`arr[5]=0`（默认初始化为0）。因此`arr[3]`的值是4。15.A,B解析：在C/C++中，字符串常量存储在一个字符数组中，以空字符`'\0'`结尾。字符串也可以通过字符指针来访问。C和D描述不准确，字符串不是存储在结构体或共享内存中的基本概念。二、多选题1.A,B,C,D解析：递归函数必须调用自身（否则不是递归），必须有终止条件（否则会无限递归），是一种重要的编程技巧，并且递归调用会消耗额外的栈空间用于存储调用记录。2.A,B,D解析：数组可以通过下标（正整数或从0开始的整数）访问元素。数组的大小在定义后通常是固定的（对于静态数组），但可以通过动态内存分配改变（对于指针指向的数组）。数组在定义时需要指定元素类型，同一数组中的元素类型必须相同。数组的下标通常从0开始。3.A,C解析：贪心算法在每一步选择当前看起来最优的选择，希望最终得到全局最优解。最优路径选择问题（如最小生成树、最短路径）有时可以用贪心算法解决（如Prim/Kruskal算法用于最小生成树，Dijkstra算法部分思想）。作业调度问题中，某些类型的调度可以用贪心算法解决。背包问题通常需要动态规划或贪心（分数背包）。单源最短路径问题通常使用Dijkstra或Bellman-Ford算法（非贪心）。4.A,D解析：函数的主要目的是提高代码的模块化、可重用性和可维护性。函数可以有返回值（也可以没有，通过void表示），也可以嵌套定义（在另一个函数内部定义）。main函数是C/C++程序的入口点。5.A,B解析：二叉搜索树的性质保证了其左子树所有节点值小于根节点值，右子树所有节点值大于根节点值。中序遍历（左-根-右）会得到一个升序排列的序列（如果所有节点值唯一）。前序遍历（根-左-右）不一定得到有序序列。插入和删除操作相对简单，但最坏情况下的时间复杂度可能较高（O(n)）。6.A,B,D解析：`!`（逻辑非）作用于单个操作数，是单目运算符。`*`（乘法）需要两个操作数，是双目运算符。`>`（大于）需要两个操作数，是双目运算符。`+=`（加等于）是复合赋值运算符，属于单目运算符（作用于左侧变量）和双目运算符（加号）的组合。7.B,C解析：`scanf()`用于从标准输入（通常是键盘）读取格式化的数据。`printf()`用于向标准输出（通常是屏幕）打印格式化的数据。`gets()`和`putchar()`不是用于处理空格分隔的整数序列的标准函数。8.A,B,C,D解析：if语句可以单独使用（作为单分支选择结构）。if-else语句可以嵌套使用，实现多分支选择。switch语句的case标签必须是常量表达式（或常量表达式的一部分）。switch语句通常与break语句结合使用，以防止穿透到下一个case，但也可以不使用break实现级联匹配。9.A,B,C,D解析：字符串的长度是指其包含的字符数量，不包括结尾的空字符`'\0'`。字符串可以用字符数组表示，数组的最后一个元素必须是空字符`'\0'`。`strlen()`函数计算字符串的长度，不包括空字符。`printf()`函数可以用`%s`格式说明符输出以空字符结尾的字符串。10.A,B,C解析：栈内存（Stack）通常由系统在函数调用时自动分配和回收，用于存储局部变量和函数参数。堆内存（Heap）由程序员通过`malloc`/`new`等分配，大小动态，生命周期不由作用域决定，需要手动释放。全局变量存储在全局/静态存储区。局部变量存储在栈内存中。选项D错误。三、编程题1.```cintsum(intn){inttotal=0;for(inti=1;i<=n;++i){total+=i;}returntotal;}```解析思路：要计算1到n的和，可以使用循环。初始化一个变量`total`为0，用于累加和。从1开始，依次循环到n，在每次循环中，将当前的循环变量`i`加到`total`上。循环结束后，`total`就是1到n的和。使用`for`循环结构清晰简洁。2.```cintstring_length(constchar*s){intlength=0;while(s[length]!='\0'){length++;}returnlength;}```解析思路：要计算字符串的长度，不包括结尾的空字符`'\0'`。可以定义一个变量`length`为0，用于计数。使用`while`循环遍历字符串`s`，循环条件是当前字符不是空字符`'\0'`。每次循环，将`length`加1，并将指针`s`移动到下一个字符。当遇到`'\0'`时，循环结束，此时`length`的值就是字符串的长度。3.```c#include<stdio.h>voidencrypt_string(char*s){while(*s!='\0'){if(*s>='a'&&*s<='z'){*s=(*s-'a'+3)%26+'a';}s++;//移动到下一个字符}}intmain(){charinput[1000];printf("Enterastring:");scanf("%s",input);//假设输入不包含空格encrypt_string(input);printf("Encryptedstring:%s\n",input);return0;}```解析思路：加密规则是将小写字母替换为其后面第3位的字母。对于字母`a`，后面第3位是`d`；对于`b`，后面第3位是`e`；依此类推；对于`z`，后面第3位是`c`。这可以通过计算字母的ASCII码来实现。如果当前字符是小写字母（ASCII码在`'a'`到`'z'`之间），则计算其与`'a'`的差值加3，然后对26取模（字母表有26个字母），最后再加上`'a'`得到新的字符。例如，字符`'c'`，`'c'-'a'+3=2+3=5`，`5%26=5`，`5+'a'='f'`。非小写字母保持不变。程序中定义一个`encrypt_string`函数，遍历字符串，对每个字符进行判断和转换。`main`函数用于接收输入和输出结果。4.```c#include<stdio.h>voidfind_two_sum(intarr[],intsize,inttarget,intresult[2]){for(inti=0;i<size-1;++i){for(intj=i+1;j<size;++j){if(arr[i]+arr[j]==target){result[0]=i;result[1]=j;return;//找到一组解即可返回}}}//如果没有找到，可以设置result为{-1,-1}或其他标记result[0]=-1;result[1]=-1;}intmain(){intarr[]={2,7,11,15};intsize=sizeof(arr)/sizeof(arr[0]);inttarget=9;intresult[2];find_two_sum(arr,size,target,result);if(result[0]!=-1){printf("[%d,%d]\n",result[0],result[1]);}else{printf("Nosolutionfound.\n");}return0;}```解析思路：要找出数组中和为`target`的两个数及其索引。最简单的方法是使用嵌套循环。外层循环遍历数组中的每个元素，作为第一个加数。内层循环从当前元素的下一个元素开始，遍历数组的其余部分，作为第二个加数。对于每一对加数，检查它们的和是否等于`target`。如果等于，则记录下这两个数的索引（注意内层循环的索引`j`是当前外层循环`i`的下一个元素的索引）。找到一组解后，可以立即返回。如果没有找到，可以返回一个标记（如`{-1,-1}`）。程序中定义了`find_two_sum`函数实现这个逻辑，并在`main`函数中测试。5.```c#include<stdio.h>voidbubble_sort(intarr[],intsize){for(inti=0;i<size-1;++i){for(intj=0;j<size-1-i;++j){if