NOIP提高组初赛模拟试题（含详细答案解析）

NOIP提高组初赛模拟试题（含详细答案解析）考试时间：90分钟满分：100分注意事项：1.本试题共六大题型，全部为笔试题，请勿使用编程工具作答；2.答案请严格按照题目要求书写，填空、简答需规范作答；3.程序相关题目默认语言为C++，语法遵循C++11标准。一、单项选择题（共15题，每题2分，共30分）每题仅有一个正确答案，多选、错选、不选均不得分。1.下列关于计算机进制转换的说法，正确的是（）A.二进制数1101转换为十进制为12B.十进制数28转换为十六进制为1CC.八进制数72转换为二进制为111000D.十六进制数3F转换为十进制为612.计算机存储容量单位中，1MB等于（）A.1000KBB.1024KBC.1000*1000BD.1024*1024KB3.下列数据结构中，属于先进后出的是（）A.队列B.栈C.链表D.二叉树4.一棵深度为5的满二叉树的节点总数为（）A.16B.31C.32D.155.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.选择排序C.归并排序D.插入排序6.已知中缀表达式：a*(b+c)-d/e，对应的后缀表达式是（）A.abc+*de/-B.ab+c*de/-C.abc*+de/-D.abcd+*/-7.图的广度优先遍历（BFS）适合解决的问题是（）A.拓扑排序B.最短路径（无权图）C.最大生成树D.强连通分量求解8.下列不属于操作系统的是（）A.LinuxB.Windows11C.PythonD.macOS9.一个无向连通图有n个顶点、m条边，其最小生成树的边数为（）A.nB.n-1C.m-1D.m-n+110.哈希冲突解决方法中，不属于开放定址法的是（）A.线性探测B.二次探测C.链地址法D.随机探测11.C++语言中，int类型变量的取值范围通常为（）A.-128~127B.0~255C.-2147483648~2147483647D.0~6553512.下列关于递归的说法，错误的是（）A.递归必须有终止条件B.递归算法一定比迭代算法时间复杂度低C.递归会产生栈空间开销D.斐波那契数列可通过递归实现13.有序数组二分查找的最坏时间复杂度为（）A.O(n)B.O(n²)C.O(logn)D.O(1)14.网络协议中，HTTP协议默认端口号是（）A.21B.80C.443D.2215.对序列{3,1,4,2,5}进行冒泡排序，第一趟排序结束后的序列为（）A.{1,3,2,4,5}B.{1,2,3,4,5}C.{3,1,2,4,5}D.{1,3,4,2,5}二、多项选择题（共5题，每题3分，共15分）每题有多个正确答案，多选、少选、错选均不得分。1.下列排序算法中，属于稳定排序的有（）A.冒泡排序B.归并排序C.快速排序D.插入排序2.下列属于线性数据结构的有（）A.栈B.队列C.二叉树D.数组3.关于图的存储结构，说法正确的有（）A.邻接矩阵适合存储稠密图B.邻接表适合存储稀疏图C.邻接矩阵的空间复杂度为O(n²)D.邻接表无法存储有向图4.C++中，以下合法的变量名有（）A.num_1B.123aC._scoreD.int5.下列算法中，属于贪心算法应用的有（）A.最小生成树Kruskal算法B.活动选择问题C.二分查找D.背包问题（部分背包）三、问题求解（共2题，每题5分，共10分）1.求序列1,3,6,10,15……的第20项数值。2.一个包含10个节点的无向完全图，共有多少条边？若删除3条边后，最多能形成多少个连通分量？四、程序阅读题（共2题，每题8分，共16分）阅读完整程序代码，写出程序输出结果。程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

ints=0;

for(inti=1;i<=10;i++){

if(i%2==0)s+=i;

elses-=i;

}

cout<<s<<endl;

return0;

}请写出程序运行输出结果：程序2PlainText

#include<iostream>

usingnamespacestd;

intf(intn){

if(n<=1)return1;

returnf(n-1)+f(n-2);

}

intmain(){

cout<<f(6)<<endl;

return0;

}请写出程序运行输出结果：五、程序填空（共2空，每空3分，共6分）以下程序实现计算数组最大值与最小值的差值，请补全空缺代码。PlainText

#include<iostream>

usingnamespacestd;

inta[10]={5,2,9,1,7,3,8,4,6,0};

intmain(){

intmaxn=a[0],minn=a[0];

for(inti=1;i<10;i++){

if(_______1_______)maxn=a[i];

if(a[i]<minn)minn=a[i];

}

cout<<_______2_______<<endl;

return0;

}六、完善程序（共3空，每空3分，共9分）以下程序实现二分查找有序升序数组中目标值的位置，若不存在目标值输出-1，请补全代码。PlainText

#include<iostream>

usingnamespacestd;

intfind(inta[],intn,intx){

intl=0,r=n-1;

while(_______1_______){

intmid=(l+r)/2;

if(a[mid]==x)returnmid;

elseif(_______2_______)r=mid-1;

elsel=mid+1;

}

return_______3_______;

}

intmain(){

intarr[6]={1,3,5,7,9,11};

intres=find(arr,6,7);

cout<<res<<endl;

return0;

}七、详细答案与解析一、单项选择题答案及解析1.答案：B解析：A选项，1101二进制转十进制为13；B选项，28÷16=1余12（C），结果1C，正确；C选项，八进制72转二进制为111010；D选项，十六进制3F转十进制为63。2.答案：B解析：计算机存储进制为2的10次方，1MB=1024KB，1KB=1024B。3.答案：B解析：栈遵循先进后出（LIFO），队列遵循先进先出（FIFO）。4.答案：B解析：深度为k的满二叉树节点总数为2^k-1，2^5-1=31。5.答案：C解析：冒泡、选择、插入排序时间复杂度均为O(n²)，归并、快速、堆排序为O(nlogn)。6.答案：A解析：中缀转后缀规则：先算括号，再乘除后加减。a*(b+c)-d/e转换后为abc+*de/-。7.答案：B解析：无权图单源最短路径优先用BFS，DFS多用于拓扑排序、连通分量求解。8.答案：C解析：Python是编程语言，不属于操作系统。9.答案：B解析：n个顶点的连通图，最小生成树一定包含n-1条边，无环且连通。10.答案：C解析：链地址法是单独的哈希冲突解决方式，线性、二次、随机探测均为开放定址法。11.答案：C解析：32位int类型取值范围为-2^31~2^31-1，即-2147483648~2147483647。12.答案：B解析：递归存在重复计算、栈开销，时间复杂度不一定优于迭代，该说法错误。13.答案：C解析：二分查找每次缩小一半查找范围，最坏时间复杂度O(logn)。14.答案：B解析：HTTP默认80端口，HTTPS默认443端口，FTP21端口，SSH22端口。15.答案：A解析：冒泡排序第一趟相邻元素两两比较，将最大值5沉到末尾，最终序列{1,3,2,4,5}。二、多项选择题答案及解析1.答案：ABD解析：快速排序是不稳定排序，冒泡、归并、插入排序均为稳定排序。2.答案：ABD解析：数组、栈、队列均为线性结构，二叉树属于树形非线性结构。3.答案：ABC解析：邻接表可存储有向图、无向图，D选项错误，其余说法均正确。4.答案：AC解析：C++变量名以字母、下划线开头，不能以数字开头，不能使用关键字，int为关键字，B、D不合法。5.答案：ABD解析：二分查找是分治算法，其余均为贪心算法典型应用。三、问题求解答案及解析1.答案：210解析：该数列为三角形数列，通项公式为aₙ=n*(n+1)/2，第20项=20*21/2=210。2.答案：45条边；4个连通分量解析：n个节点无向完全图边数公式：n*(n-1)/2，10*9/2=45条；删除3条边最多拆分出3个孤立节点，剩余7个节点连通，总连通分量=3+1=4。四、程序阅读题答案及解析程序1输出：6解析：循环遍历1-10，奇数累加负数，偶数累加正数。计算：-1+2-3+4-5+6-7+8-9+10=6。程序2输出：13解析：递归为变形斐波那契数列，f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5,f(6)=8+5=13。五、程序填空答案1：a[i]>maxn2：m