noip普及组初赛历年试题及答案

noip普及组初赛历年试题及答案全国青少年信息学奥林匹克联赛普及组初赛试卷一、单项选择题（每题3分，共30分）1.下列哪个选项不是算法的基本特征？A.有穷性B.确定性C.可行性D.最优性2.计算机存储容量的单位“KB”表示：A.1000字节B.1024字节C.1000位D.1024位3.在C++中，用于输出信息的标准库函数是：A.`scanf()`B.`printf()`C.`input()`D.`output()`4.下列哪个表达式在Python中正确？A.`3+4`B.`5/0`C.`“hello”+123`D.`True==1`5.一个长度为10的数组，其合法的索引范围是：A.0到9B.1到10C.0到10D.1到116.下列哪个排序算法的平均时间复杂度是O(n²)？A.快速排序B.归并排序C.堆排序D.插入排序7.在二叉树中，节点的度为：A.指向子节点的指针个数B.节点的子节点个数C.节点的父节点个数D.树的高度8.下列哪个数据结构是先进先出（FIFO）的？A.栈B.队列C.链表D.堆9.计算机网络中，IP地址的长度通常是：A.32位B.64位C.128位D.256位10.下列哪个是正确的逻辑表达式？A.`1<2>3`B.`True&&False`C.`3==3.0`D.`"abc"==[‘a’,‘b’,‘c’]`二、填空题（每空2分，共20分）1.在Java中，定义一个整型变量需要使用关键字______。2.若一个算法的时间复杂度为O(n³)，当n=1000时，其执行时间大约是n=100时的______倍。3.在二叉搜索树中，左子树的所有节点值均______根节点的值。4.堆排序算法构建初始堆的时间复杂度是______。5.IP地址192.168.1.1属于______类地址。6.在链表中，删除一个节点需要记录其______节点的地址。7.计算斐波那契数列第n项的递归公式是______。8.若一个图的邻接矩阵为稀疏矩阵，则更适合使用______存储。9.将十进制数100转换为二进制表示为______。10.在SQL中，用于查询不同值的函数是______。三、程序填空题（每空4分，共20分）```pythondeffind_max(nums):max_num=______初始化最大值fornuminnums:ifnum>______:比较当前数与最大值max_num=______return______返回最大值``````cppinclude<iostream>usingnamespacestd;intfactorial(intn){if(n==0)return______;//0的阶乘为1returnn______;//递归计算n的阶乘}``````javapublicintsum(inta,intb){return______;//返回a与b的和}``````pythondefis_prime(n):ifn<=1:returnFalseforiin______:检查2到sqrt(n)是否有因数ifn%i==0:returnFalsereturnTrue``````cppvoidreverse_string(string&s){intleft=0,right=s.length()-1;while(left<______)://交换左右字符swap(s[left],s[______]);left++;right--;}```四、简答题（每题8分，共32分）1.简述栈和队列的区别。2.解释什么是二叉搜索树，并说明其性质。3.什么是时间复杂度？如何计算一个算法的时间复杂度？4.描述冒泡排序的算法思想，并分析其时间复杂度。五、综合应用题（共18分）给定一个包含n个整数的数组，要求：1.找出数组中最大的三个数，并按从大到小的顺序输出（时间复杂度要求O(n)）。2.统计数组中正数、负数和零的个数，并输出统计结果。参考数据：nums=[3,-1,5,7,0,8,-3,2,5,-6]注意：-请分别用Python和C++实现上述功能，并展示关键代码片段。-要求详细说明算法设计思路，并分析时间复杂度。---标准答案及解析一、单项选择题1.D（最优性不是算法的基本特征）2.B（1KB=1024字节）3.B（C++中`printf()`用于输出）4.D（`True==1`在Python中为真）5.A（数组索引从0开始）6.D（插入排序的平均时间复杂度为O(n²)）7.A（节点的度为指向子节点的指针个数）8.B（队列是先进先出结构）9.A（IPv4地址长度为32位）10.C（3与3.0在Python中视为相等）二、填空题1.`int`2.10（1000²vs100²=10000vs10000）3.小于4.O(n)5.C类6.前驱7.`fib(n)=fib(n-1)+fib(n-2)`8.邻接表9.`1100100`10.`DISTINCT`三、程序填空题```pythondeffind_max(nums):max_num=nums[0]初始化最大值fornuminnums:ifnum>max_num:比较当前数与最大值max_num=numreturnmax_num返回最大值``````cppinclude<iostream>usingnamespacestd;intfactorial(intn){if(n==0)return1;//0的阶乘为1returnnfactorial(n-1);//递归计算n的阶乘}``````javapublicintsum(inta,intb){returna+b;//返回a与b的和}``````pythondefis_prime(n):ifn<=1:returnFalseforiinrange(2,int(n0.5)+1):检查2到sqrt(n)是否有因数ifn%i==0:returnFalsereturnTrue``````cppvoidreverse_string(string&s){intleft=0,right=s.length()-1;while(left<right)://交换左右字符swap(s[left],s[right]);left++;right--;}```四、简答题1.栈和队列的区别-栈：后进先出（LIFO），只能在一端（栈顶）进行插入和删除操作。-队列：先进先出（FIFO），在一端（队尾）插入，另一端（队头）删除。2.二叉搜索树及其性质-定义：左子树所有节点值小于根节点，右子树所有节点值大于根节点。-性质：无重复值，支持高效查找、插入和删除操作（平均O(logn)）。3.时间复杂度-定义：描述算法执行时间随输入规模增长的变化趋势。-计算方法：统计基本操作次数，用大O表示法简化（如O(n),O(n²)）。4.冒泡排序-思想：重复遍历数组，相邻元素比较并交换，使较大元素“冒泡”至末尾。-时间复杂度：O(n²)，因需n-1轮遍历，每轮比较n-1次。五、综合应用题Python实现：```pythonnums=[3,-1,5,7,0,8,-3,2,5,-6]max1,max2,max3=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>max1:max3=max2max2=max1max1=numelifnum>max2:max3=max2max2=numelifnum>max3:max3=numprint(f"最大三个数：{max1},{max2},{max3}")positive,negative,zero=0,0,0fornuminnums:ifnum>0:positive+=1elifnum<0:negative+=1else:zero+=1print(f"正数：{positive},负数：{negative},零：{zero}")```C++实现：```cppinclude<vector>include<algorithm>usingnamespacestd;intmain(){vector<int>nums={3,-1,5,7,0,8,-3,2,5,-6};vector<int>max3(3,INT_MIN);for(autonum:nums){if(num>max3[0]){max3[2]=max3[1];max3[1]=max3[0];max3[0]=num;}elseif(num>max3[1]){max3[2]=max3[1];max3[1]=num;}elseif(num>max3[2]){max3[2]=num;}}cout<<"最大三个数："<<max3[0]<<","<<max3[1]<<","<<max3[2]<<endl;intpositive=0,negative=0,zero=0;for(autonum:nums){