NOIP普及组初赛常见试题及参考答案

NOIP普及组初赛常见试题及参考答案考试时间：______分钟总分：______分姓名：______选择题（1-20题，每题2分，共40分）1.计算机中存储一个汉字的内码需要多少字节？A.1B.2C.4D.82.CPU不能直接访问的存储器是？A.内存B.高速缓存C.硬盘D.寄存器3.以下C++变量命名中，合法的是？A.2varB.var-nameC._123D.if4.执行以下代码后，变量x的值是？```cppintx=5,y=2;x=y+++++x;```A.7B.8C.9D.105.以下排序算法中，平均时间复杂度为O(n²)的是？A.快速排序B.归并排序C.堆排序D.冒泡排序6.以下数据结构中，是“先进先出”的是？A.栈B.队列C.堆D.二叉树7.在C++中，`inta[10];`定义的数组a有10个元素，下标范围是？A.1~10B.0~9C.1~9D.0~108.以下哪个是C++的关键字？A.variableB.intC.nameD.value9.二叉树的深度为3，最多有多少个节点？A.7B.8C.9D.1010.以下哪个算法用于查找无序数组中的最大值？A.二分查找B.顺序查找C.快速排序D.归并排序11.在C++中，`doublea=5/2;`，变量a的值是？A.2.5B.2C.3D.512.以下哪个数据结构是线性结构？A.树B.图C.队列D.堆13.执行以下代码后，输出结果是？```cppcout<<(3+4*2)<<endl;```A.11B.14C.7D.914.以下哪个是递归算法的必要条件？A.循环语句B.递归终止条件C.全局变量D.数组15.在C++中，`charstr[]="Hello";`，数组str的大小是？A.5B.6C.7D.816.以下哪个算法的时间复杂度是O(logn)？A.冒泡排序B.二分查找C.线性查找D.选择排序17.以下哪个是正确的C++注释？A.//这是注释B.这是注释C./*这是注释*/D.以上都是18.斐波那契数列的前两项是？A.F(1)=0,F(2)=1B.F(1)=1,F(2)=1C.F(1)=2,F(2)=3D.F(1)=0,F(2)=019.在C++中，`if(x=5)`是合法的语句吗？A.是B.否C.取决于x的类型D.取决于编译器20.以下哪个是广度优先搜索（BFS）使用的数据结构？A.栈B.队列C.堆D.树判断题（21-30题，每题2分，共20分）21.在C++中，`inta[10];`定义的数组a有10个元素，下标范围是1~10。（）22.递归算法必须有递归终止条件，否则会导致栈溢出。（）23.二叉树的叶子节点是指没有子节点的节点。（）24.在C++中，`floata=3.5;`，变量a的值是3。（）25.快速排序的平均时间复杂度是O(nlogn)。（）26.在C++中，`for(inti=0;i<5;i++)`循环会执行5次。（）27.栈是“先进先出”的数据结构。（）28.在C++中，`int*p=newint[10];`需要手动释放内存。（）29.归并排序是稳定的排序算法。（）30.在C++中，`if(x==5)`和`if(x=5)`效果相同。（）问题求解题（31-32题，每题5分，共10分）31.斐波那契数列定义如下：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3）。则F(10)的值是______。32.从1~9中选取3个不同的数字，使其和为15，共有______种不同的选法。阅读程序题（33-36题，每题5分，共20分）33.阅读以下C++代码，写出程序输出结果。```cpp#include<iostream>usingnamespacestd;intmain(){inta=1,b=1,c=0;for(inti=1;i<=4;i++){c=a+b;a=b;b=c;}cout<<c<<endl;return0;}```34.阅读以下C++代码，写出程序输出结果。```cpp#include<iostream>usingnamespacestd;intmain(){intsum=0;for(inti=1;i<=10;i++){if(i%2==0)continue;sum+=i;}cout<<sum<<endl;return0;}```35.阅读以下C++代码，写出程序输出结果。```cpp#include<iostream>usingnamespacestd;intmain(){intx=10,y=5;if(x>y){cout<<x+y<<endl;}else{cout<<x-y<<endl;}return0;}```36.阅读以下C++代码，写出程序输出结果。```cpp#include<iostream>usingnamespacestd;intmain(){inta[5]={1,2,3,4,5};intsum=0;for(inti=0;i<5;i++){sum+=a[i];}cout<<sum<<endl;return0;}```完善程序题（37题，每题10分，共10分）37.以下代码用二分查找法在有序数组a中查找元素x，若找到返回下标，否则返回-1。请补全缺失部分。```cpp#include<iostream>usingnamespacestd;intbinarySearch(inta[],intn,intx){intleft=0,right=n-1;while(left<=right){intmid=______;//计算中间位置if(a[mid]==x)returnmid;elseif(a[mid]<x)______;//调整左边界else______;//调整右边界}return-1;}```试卷答案选择题（1-20题，每题2分，共40分）1.B解析：汉字编码标准（如GBK）中，一个汉字通常用2字节表示。2.C解析：CPU只能直接访问内存、高速缓存和寄存器，硬盘属于外存，需调入内存后才能访问。3.C解析：C++标识符必须以字母或下划线开头，不能包含特殊字符（如连字符）或关键字（如if）。4.B解析：`y++`后缀自增先取值（2）再加1，`++x`前缀自增先加1（x=6）再取值，故`2+6=8`。5.D解析：冒泡排序平均和最坏时间复杂度均为O(n²)，其他选项为O(nlogn)。6.B解析：队列是“先进先出”结构，栈是“后进先出”。7.B解析：C++数组下标从0开始，`a[10]`的下标范围是0~9。8.B解析：`int`是C++关键字，其他选项不是。9.A解析：深度为3的二叉树最多节点数为2³-1=7。10.B解析：顺序查找适用于无序数组，遍历比较即可找到最大值。11.B解析：`5/2`为整数除法，结果为2，赋值给`double`类型后为2.0，但选项中2最接近（实际为2.0，但选项无2.0时选2）。12.C解析：队列是线性结构，树和图是非线性，堆是特殊线性结构但通常归为非线性。13.A解析：运算符优先级：乘法优先于加法，`4*2=8`，`3+8=11`。14.B解析：递归必须包含终止条件，否则无限递归导致栈溢出。15.B解析：字符串`"Hello"`包含5个字符，末尾有隐藏的`\0`，故数组大小为6。16.B解析：二分查找在有序数组中时间复杂度为O(logn)，其他选项为O(n)或O(n²)。17.D解析：`//`和`/**/`都是C++合法注释方式。18.B解析：斐波那契数列标准定义前两项为F(1)=1，F(2)=1。19.A解析：`if(x=5)`是合法语句（赋值表达式），但逻辑错误（应为`x==5`）。20.B解析：BFS使用队列按层次遍历节点。判断题（21-30题，每题2分，共20分）21.×解析：数组下标从0开始，`a[10]`下标范围是0~9。22.√解析：递归终止条件是递归算法的必要条件，否则会导致无限递归和栈溢出。23.√解析：叶子节点是度为0的节点（无子节点）。24.×解析：`3.5`是浮点数，赋值给`float`类型时保留小数部分，值为3.5。25.√解析：快速排序平均时间复杂度为O(nlogn)。26.√解析：循环变量i从0到4（共5次：0,1,2,3,4）。27.×解析：栈是“后进先出”，队列是“先进先出”。28.√解析：动态分配的数组需用`delete[]`释放内存，否则内存泄漏。29.√解析：归并排序是稳定排序，相同元素的相对顺序不变。30.×解析：`if(x==5)`是判断相等，`if(x=5)`是赋值且判断非零，效果完全不同。问题求解题（31-32题，每题5分，共10分）31.55解析：斐波那契数列逐项计算：F(3)=2,F(4)=3,F(5)=5,F(6)=8,F(7)=13,F(8)=21,F(9)=34,F(10)=55。32.8解析：枚举所有3数组合（1+5+9,1+6+8,2+4+9,2+5+8,2+6+7,3+4+8,3+5+7,4+5+6），共8种。阅读程序题（33-36题，每题5分，共20分）33.8解析：循环计算斐波那契数列：i=1时c=2（F3）,i=2时c=3（F4）,i=3时c=5（F5）,i=4时c=8（F6），输出8。34.25解析：跳过偶数，累加1~10的奇数：1+3+5+7+9=25。35.15解析：x=10>y=5，输出`x+y=15