NOIP普及组初赛模拟试题与答案分享

NOIP普及组初赛模拟试题与答案分享考试时间：______分钟总分：______分姓名：______一、问题1：排序与查找已知一个包含N个正整数的数组`arr`，其元素各不相同且可能为负数。请编写程序实现以下功能：1.首先，对数组`arr`进行升序排序。2.然后，使用二分查找算法在排序后的数组中查找给定整数`target`。如果找到`target`，请输出其在数组中的索引（从0开始）；如果未找到，请输出`-1`。输入：第一行包含一个整数N，表示数组的长度。第二行包含N个整数，表示数组`arr`的元素。第三行包含一个整数`target`，表示要查找的目标值。输出：输出一行，包含一个整数，表示查找结果（索引或`-1`）。若数组为空，则输出`-1`。示例：输入：```54-13021```输出：```-1```二、问题2：字符串统计给定一个仅包含小写字母的字符串`s`，以及一个正整数`k`。请编写程序统计并输出字符串`s`中所有长度为`k`的子串（子串是指数组中连续的元素组成的序列）的出现次数。子串在字符串中的出现位置可以重叠。输入：第一行包含一个字符串`s`。第二行包含一个正整数`k`，满足`1<=k<=|s|`（|s|表示字符串`s`的长度）。输出：输出一行，包含一个整数，表示满足条件的子串出现次数。示例：输入：```abcabc2```输出：```6```三、问题3：简单动态规划给定一个非负整数数组`coins`，其中`coins[i]`表示第`i`种硬币的面值。另外给定一个非负整数`amount`，表示需要凑出的总金额。请编写程序计算并输出凑出`amount`金额所需的最少硬币数量。如果无法凑出该金额，则输出`-1`。输入：第一行包含一个整数`N`，表示硬币的种类数量。第二行包含`N`个非负整数，表示每种硬币的面值，整数之间用空格分隔。第三行包含一个非负整数`amount`。输出：输出一行，包含一个整数，表示最少硬币数量或`-1`。示例：输入：```312511```输出：```3```说明：可以凑出11的方法有：5+5+1、2+2+2+2+1、1+1+1+1+1+1+1+1+1+1+1。其中5+5+1使用了最少（3）枚硬币。四、问题4：数论与循环请编写程序计算并输出从1到`M`（包含`M`）的整数中，所有满足以下条件的整数的和：一个整数`x`满足条件：`x`是一个素数，且`x`的各位数字之和也是一个素数。输入：一行，包含一个正整数`M`（`1<=M<=10^6`）。输出：输出一行，包含一个整数，表示满足条件的所有数的和。示例：输入：```10```输出：```17```说明：满足条件的数有：2,3,5,7,11,13,17。它们的和为17。五、问题5：模拟与数组操作假设有一个长度为`N`的环形队列，队列的初始状态为空（所有元素为0）。现在进行`Q`次操作，每次操作由一个整数`op_type`表示操作类型：1.`op_type=1`：在队列的最左端（头部）插入一个元素`x`（`0<=x<=100`）。如果队列已满，则不执行插入操作。2.`op_type=2`：在队列的最右端（尾部）插入一个元素`x`（`0<=x<=100`）。如果队列已满，则不执行插入操作。3.`op_type=3`：删除队列的最左端（头部）的一个元素。如果队列为空，则不执行删除操作。4.`op_type=4`：删除队列的最右端（尾部）的一个元素。如果队列为空，则不执行删除操作。所有操作按输入顺序依次进行。假设队列的最大容量为`K`（`N<=K`）。请编写程序模拟这些操作，并在所有操作执行完毕后，输出队列中所有元素的值，按从头部到尾部的顺序排列，用空格分隔。如果队列为空，则输出一行一个字串`""`（空字符串）。输入：第一行包含三个整数`N`,`K`,`Q`，分别表示队列长度、队列最大容量和操作次数。输出：输出一行，包含若干个由空格分隔的整数，表示队列当前的状态。若队列为空，则输出空字符串`""`。示例：输入：```355152334```输出：```53```六、问题6：递归与树结构（简化版）请编写一个递归函数，计算一棵给定结构的“完美二叉树”的所有叶子节点的总数。这里的“完美二叉树”指的是一棵二叉树，其中所有内部节点的子节点数量都恰好为2，且所有叶子节点都在同一层级。树的表示：使用前序遍历序列来表示这棵树。其中，一个正整数表示一个内部节点，其左右子树分别由其后的两个子序列表示。一个值为`-1`的标记表示该位置的子树为空（即该节点没有对应的子节点）。例如，序列`[3,1,-1,-1,2,-1,-1]`表示一棵结构如下：```3/\12```输入：一行，包含一个由数字和`-1`组成的序列，表示树的前序遍历。输出：输出一行，包含一个整数，表示叶子节点的总数。示例：输入：```31-1-12-1-1```输出：```2```七、问题7：数组遍历与条件判断给定一个包含`N`个整数的数组`arr`，请编写程序计算并输出数组中所有“峰值元素”的数量。数组中的峰值元素指的是：该元素的值大于其左右相邻元素的值（如果存在）。数组的首尾元素不算作峰值元素（除非它们两侧没有其他元素）。输入：第一行包含一个整数`N`，表示数组的长度。第二行包含`N`个整数，表示数组`arr`的元素。输出：输出一行，包含一个整数，表示峰值元素的数量。示例：输入：```71324351```输出：```3```说明：峰值元素是第2个元素（3），第4个元素（4），第6个元素（5）。试卷答案一、问题1：排序与查找解析思路：1.首先对数组`arr`进行排序。可以使用内置的排序函数，如C++的`std::sort`，Java的`Arrays.sort`等。排序的时间复杂度通常为O(NlogN)。2.对排序后的数组进行二分查找。二分查找的基本思想是每次将查找范围缩小一半。初始时，定义左右指针`left`和`right`，分别指向数组的开始和结束。计算中间位置`mid`，比较`arr[mid]`与`target`：*如果`arr[mid]==target`，则找到，输出`mid`。*如果`arr[mid]<target`，则将`left`移动到`mid+1`。*如果`arr[mid]>target`，则将`right`移动到`mid-1`。*如果`left>right`，则未找到，输出`-1`。二分查找的时间复杂度为O(logN)。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;intmain(){intN;cin>>N;vector<int>arr(N);for(auto&x:arr)cin>>x;sort(arr.begin(),arr.end());inttarget;cin>>target;intleft=0,right=N-1;intres=-1;while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target){res=mid;break;}elseif(arr[mid]<target){left=mid+1;}else{right=mid-1;}}cout<<res;}```二、问题2：字符串统计解析思路：1.遍历字符串`s`的所有可能的位置，对于每个位置`i`，检查从`i`开始长度为`k`的子串`s[i..i+k-1]`。2.统计所有这样的子串出现的总次数。由于子串可以重叠，直接计算所有可能的起始位置`i`（`0<=i<=|s|-k`）的数量即可。3.遍历的时间复杂度为O(|s|)，检查子串和计数是常数时间操作。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;intk;cin>>k;intcount=0;intlen=s.length();for(inti=0;i<=len-k;++i){count++;}cout<<count;}```三、问题3：简单动态规划解析思路：1.使用动态规划数组`dp`，其中`dp[i]`表示凑出金额`i`所需的最少硬币数量。初始化`dp[0]=0`（凑出0金额需要0枚硬币），其余`dp[i]`初始化为一个大数（如`INT32_MAX`或`1e9`）。2.对于每一个金额`i`从`1`到`amount`，遍历所有种类的硬币`coin`：*如果`coin<=i`，则尝试使用这枚硬币，更新`dp[i]=min(dp[i],dp[i-coin]+1)`。3.最后，检查`dp[amount]`的值。如果`dp[amount]`仍然是初始的大数值，说明无法凑出，输出`-1`；否则，输出`dp[amount]`。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;intmain(){intN;cin>>N;vector<int>coins(N);for(auto&x:coins)cin>>x;intamount;cin>>amount;vector<int>dp(amount+1,1e9);dp[0]=0;for(inti=1;i<=amount;++i){for(autocoin:coins){if(coin<=i){dp[i]=min(dp[i],dp[i-coin]+1);}}}if(dp[amount]==1e9){cout<<-1;}else{cout<<dp[amount];}}```四、问题4：数论与循环解析思路：1.需要编写一个函数来判断一个数是否为素数。对于数`x`，从`2`到`sqrt(x)`检查是否有任何数能整除`x`。如果没有，则`x`是素数。2.需要编写一个函数来计算一个数的各位数字之和，并判断这个和是否为素数。3.遍历从`1`到`M`的所有整数`x`。对于每个`x`，首先判断`x`是否为素数，如果是，再判断`x`的各位数字之和是否为素数。如果两个条件都满足，则将`x`加到总和中。4.输出最终的总和。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;boolis_prime(intx){if(x<2)returnfalse;for(inti=2;i<=sqrt(x);++i){if(x%i==0)returnfalse;}returntrue;}intsum_of_digits(intx){intsum=0;while(x>0){sum+=x%10;x/=10;}returnsum;}intmain(){intM;cin>>M;longlongsum=0;for(intx=1;x<=M;++x){if(is_prime(x)){intdigit_sum=sum_of_digits(x);if(is_prime(digit_sum)){sum+=x;}}}cout<<sum;}```五、问题5：模拟与数组操作解析思路：1.实现一个环形队列，可以使用一个固定大小的数组`queue`和两个指针`front`（指向队头）和`rear`（指向队尾的下一个位置）。初始时`front=0`,`rear=0`。队列大小为`K`。2.根据`op_type`执行相应操作：*`op_type=1`（入队头部）：检查队列是否已满(`(rear+1)%K==front`)。若不满，将`x`插入到`queue[front]`，然后`front=(front+1)%K`。*`op_type=2`（入队尾部）：检查队列是否已满。若不满，将`x`插入到`queue[rear]`，然后`rear=(rear+1)%K`。*`op_type=3`（出队头部）：检查队列是否为空(`front==rear`)。若不为空，将`front=(front+K-1)%K`。*`op_type=4`（出队尾部）：检查队列是否为空。若不为空，将`rear=(rear+K-1)%K`。3.所有操作执行完毕后，根据`front`和`rear`的位置，按顺序输出队列中的元素。如果队列为空(`front==rear`)，输出空字符串`""`。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;intmain(){intN,K,Q;cin>>N>>K>>Q;intfront=0,rear=0;vector<int>queue(K,0);//环形队列for(inti=0;i<Q;++i){intop_type,x;cin>>op_type>>x;if(op_type==1){if((rear+1)%K!=front){queue[rear]=x;rear=(rear+1)%K;}}elseif(op_type==2){if((rear+1)%K!=front){queue[rear]=x;rear=(rear+1)%K;}}elseif(op_type==3){if(front!=rear){front=(front+K-1)%K;}}elseif(op_type==4){if(front!=rear){rear=(rear+K-1)%K;}}}if(front==rear){cout<<"";}else{vector<int>result;inti=front;while(i!=rear){result.push_back(queue[i]);i=(i+1)%K;}for(inti=0;i<result.size();++i){if(i>0)cout<<"";cout<<result[i];}}}```六、问题6：递归与树结构（简化版）解析思路：1.递归函数`count_leaves(pre,index)`接收前序遍历序列`pre`和当前遍历到的索引`index`。2.如果`index`超出了序列长度，或者当前节点值为`-1`，表示子树为空，返回0。3.读取当前节点的值`node_val=pre[index]`。如果`node_val==-1`，则当前节点是叶子节点（因为它没有子节点），返回1。否则，当前节点是内部节点。4.递归计算左子树的叶子节点数`left_leaves`（从`index+1`开始）和右子树的叶子节点数`right_leaves`（从`index+2`开始）。5.当前树的叶子节点总数为`left_leaves+right_leaves`。6.递归结束条件是遍历完整个序列。参考代码（以C++为例）：```cpp#include<bits/stdc++.h>usingnamespacestd;intcount_leaves(vector<int>&pre,intindex){if(index>=pre.size()||pre[index]==-1){return0;}intnode_val=pre[index];if(node_val==-1){return1;//-1标记的节点是叶子}//递归计算左右子树的叶子数intleft_leaves=count_leaves(pre,index+1);intright_leaves=count_leaves(pre,index+2);returnle