2026年NOIP全国青少年信息学奥林匹克联赛提高组初赛试题（含详细答案）

2026年NOIP全国青少年信息学奥林匹克联赛提高组初赛试题（含详细答案）考试时间：2026年10月满分：100分注意事项：1.本试卷共8页，包含选择题、填空题、程序阅读理解题、程序完善题四部分。2.所有答案必须写在答题卡对应位置，写在试卷上无效。3.考试结束后，将试卷、答题卡一并交回。一、单项选择题（共15题，每题2分，共计30分。每题仅有一个正确答案）1.以下不属于计算机基础进制转换常用进制的是（）A.二进制B.六进制C.八进制D.十六进制2.十进制数125转化为二进制数为（）A.1111101B.1111011C.1101111D.10111113.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则该二叉树的后序遍历序列为（）A.CBEFDAB.CBADEFC.BCEDFAD.CFEDAB4.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.快速排序C.选择排序D.插入排序5.栈和队列的核心区别是（）A.存储空间不同B.存取规则不同C.数据类型不同D.存储效率不同6.一个无向连通图有8个顶点、12条边，其最小生成树的边数为（）A.7B.8C.11D.127.以下数据结构中，适合实现递归调用现场保存的是（）A.队列B.栈C.链表D.数组8.逻辑表达式!(a||b)&&a的运算结果恒为（）A.真B.假C.取决于a的值D.取决于b的值9.哈希冲突解决方法中，不属于开放定址法的是（）A.线性探测B.二次探测C.链地址法D.随机探测10.完全二叉树的第5层最多有多少个节点（）A.8B.16C.32D.6411.以下关于贪心算法的说法正确的是（）A.一定能得到全局最优解B.仅能得到局部最优解，不一定全局最优C.时间复杂度一定高于动态规划D.只能用于图论问题12.在C++中，int类型变量的取值范围通常为（）A.-128~127B.-32768~32767C.-2147483648~2147483647D.0~429496729513.广度优先搜索（BFS）最适合解决的问题是（）A.求图中两点最短路径（无权图）B.求拓扑排序C.求最大子串D.求最长上升子序列14.二进制数101101转换为十六进制数为（）A.2DB.2BC.3DD.3B15.以下不属于线性数据结构的是（）A.栈B.队列C.二叉树D.顺序表二、不定项选择题（共5题，每题3分，共计15分。多选、少选、错选均不得分）1.下列排序算法中，属于稳定排序的有（）A.归并排序B.冒泡排序C.快速排序D.基数排序2.关于图的存储结构，说法正确的有（）A.邻接矩阵适合稠密图B.邻接表适合稀疏图C.邻接矩阵查询两点是否连通效率高D.邻接表占用空间固定3.下列操作中，时间复杂度为O(1)的有（）A.顺序表尾部插入元素B.栈的入栈、出栈操作C.链表随机访问元素D.队列队首出队操作4.动态规划算法的核心要素包括（）A.最优子结构B.重叠子问题C.无后效性D.贪心选择性5.下列关于二叉树的说法正确的有（）A.满二叉树一定是完全二叉树B.完全二叉树一定是满二叉树C.二叉树的度最大为2D.叶子节点只能出现在最后两层三、填空题（共5空，每空3分，共计15分）1.深度为4的满二叉树，总节点数为________。2.已知序列{5,2,9,1,7,3}，采用冒泡排序进行升序排序，第一轮排序结束后的序列为________。3.一个长度为n的有序数组，采用二分查找的最坏时间复杂度为________。4.无向图有n个顶点、m条边，其邻接矩阵的大小为________。5.递归算法必须包含两个部分：递归出口和________。四、程序阅读理解题（共3题，每题10分，共计30分）1.阅读以下C++代码，写出程序输出结果PlainText

#include<iostream>

usingnamespacestd;

intfunc(intx){

if(x==0)return0;

returnx%2+func(x/2);

}

intmain(){

cout<<func(26)<<endl;

return0;

}程序输出：________2.阅读以下C++代码，写出程序输出结果PlainText

#include<iostream>

usingnamespacestd;

intmain(){

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

intl=0,r=5,mid,ans=0;

while(l<=r){

mid=(l+r)/2;

if(a[mid]%3==0){

ans=mid;

l=mid+1;

}elseif(a[mid]%3>0){

r=mid-1;

}else{

l=mid+1;

}

}

cout<<ans<<endl;

return0;

}程序输出：________3.阅读以下C++代码，写出程序输出结果PlainText

#include<iostream>

usingnamespacestd;

intf(intn){

if(n<=2)return1;

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

}

intmain(){

intsum=0;

for(inti=3;i<=6;i++){

sum+=f(i);

}

cout<<sum<<endl;

return0;

}程序输出：________五、程序完善题（共2空，每空5分，共计10分）【题目功能】以下代码实现二分查找求有序数组中目标值最后一次出现的位置，数组为非递减有序数组，若目标值不存在，输出-1。请补全空缺代码。PlainText

#include<iostream>

usingnamespacestd;

intfindLast(inta[],intn,intx){

intl=0,r=n-1;

intres=-1;

while(l<=r){

intmid=(l+r)/2;

if(a[mid]==x){

res=mid;

__________;//第一空

}elseif(a[mid]<x){

__________;//第二空

}else{

r=mid-1;

}

}

returnres;

}

intmain(){

intarr[10]={2,2,3,3,3,5,5,7,8,8};

intx;

cin>>x;

cout<<findLast(arr,10,x)<<endl;

return0;

}第一空：________第二空：________2026年NOIP提高组初赛详细答案及解析一、单项选择题答案及解析（每题2分）1.B解析：计算机常用进制为二进制、八进制、十进制、十六进制，六进制无通用应用场景。2.A解析：125=64+32+16+8+4+1，对应二进制1111101。3.A解析：由前序ABCDEF（根左右）、中序CBAEDF（左根右），可确定根为A，左子树CB，右子树EDF，递归推导后序为CBEFDA。4.B解析：冒泡、选择、插入排序时间复杂度均为O(n²)，快速排序平均时间复杂度为O(nlogn)。5.B解析：栈为后进先出，队列为先进先出，核心差异为数据存取规则。6.A解析：n个顶点的连通图，最小生成树边数固定为n-1，8个顶点对应7条边。7.B解析：递归调用通过栈保存每层调用的局部变量、返回地址等现场信息。8.B解析：若a为真，a||b为真，!后为假，整体表达式为假；若a为假，整体表达式直接为假，结果恒假。9.C解析：链地址法是拉链法，不属于开放定址法，线性、二次、随机探测均为开放定址法。10.B解析：二叉树第k层最多节点数为2^(k-1)，第5层为2^4=16。11.B解析：贪心算法仅根据当前最优决策，只能保证局部最优，无法保证全局最优。12.C解析：标准32位int类型取值范围为-2^31~2^31-1，即-2147483648~2147483647。13.A解析：BFS按层遍历，是求解无权图两点最短路径的标准算法。14.A解析：二进制101101补位分组为00101101，对应十六进制2D。15.C解析：二叉树为树形非线性结构，栈、队列、顺序表均为线性结构。二、不定项选择题答案及解析（每题3分）1.ABD解析：快速排序是不稳定排序，归并、冒泡、基数排序均为稳定排序。2.ABC解析：邻接表存储空间随边数变化，不固定，其余三项说法均正确。3.ABD解析：链表不支持随机访问，访问任意元素时间复杂度为O(n)，其余操作均为O(1)。4.ABC解析：动态规划三大核心：最优子结构、重叠子问题、无后效性，贪心选择性是贪心算法特征。5.ACD解析：满二叉树是每层节点都满的完全二叉树，完全二叉树不一定是满二叉树，其余说法正确。三、填空题答案及解析（每空3分）1.15解析：深度k的满二叉树总节点数为2^k-1，2^4-1=15。2.{2,5,1,7,3,9}解析：冒泡升序第一轮从左到右相邻比较，将最大值9冒泡至末尾。3.O(logn)解析：二分查找每次减半区间，最坏时间复杂度为对数级O(logn)。4.n×n解析：无向图邻接矩阵为方阵，顶点数为n，矩阵维度为n行n列。5.递归递推式（递归调用）解析：递归必须具备终止条件（递归出口）和自我调用的递推过程。四、程序阅读理解题答案及解析（每题10分）1.3解析：函数func统计十进制数转为二进制后1的个数。26二进制为11010，包含3个1，输出3。2.4解析：数组a={1,3,5,7,9,11}，程序寻找能被3整除的最大下标元素。3（下标1）、9（下标4）可被