NOIP2026 全国青少年信息学奥林匹克联赛提高组初赛试题

NOIP2026全国青少年信息学奥林匹克联赛提高组初赛试题竞赛时间：2026年10月18日14:30-16:30（共2小时）满分：100分选手注意：1.本试卷共10页，全部为笔试闭卷试题，答案必须写在答题纸上，写在试题纸上无效；2.不得使用计算器、手机、电子词典等各类电子设备；3.严格遵守竞赛纪律，违规者取消竞赛成绩。题型分值说明：一、选择题：共20题，每题1.5分，总计30分。1-10题为单选题，每题仅有一个正确答案；11-20题为不定项选择题，每题1-5个正确答案，全部选对得分，少选、多选、错选均不得分。二、问题求解：共2题，每题5分，总计10分，填写最终结果即可。三、阅读程序写结果：共4题，每题8分，总计32分，根据程序代码输出对应运行结果。四、完善程序：共2题，每题14分，总计28分，根据算法逻辑补全程序空缺代码。一、选择题（共20题，每题1.5分，共30分）（一）单项选择题（1-10题）1.以下不属于计算机基础进制的是（）A.二进制B.八进制C.六进制D.十六进制2.一个32位二进制整数，能够表示的最大无符号十进制数值为（）A.2³²-1B.2³¹-1C.2³²D.2³¹3.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的后序遍历序列为（）A.BDFECAB.BDEFCAC.DBFECAD.DBEFCA4.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.快速排序C.选择排序D.插入排序5.长度为n的有序线性表，采用二分查找，最坏情况下的比较次数为（）A.O(n)B.O(n²)C.O(logn)D.O(nlogn)6.栈和队列的核心区别是（）A.存储结构不同B.元素访问规则不同C.数据类型不同D.空间复杂度不同7.十进制数127转换为二进制数为（）A.1111111B.10000000C.11111111D.011111118.图的深度优先遍历（DFS）采用的辅助数据结构是（）A.队列B.栈C.树D.链表9.下列关于哈希表的说法，正确的是（）A.哈希表一定不存在冲突B.链地址法可解决哈希冲突C.哈希查找时间复杂度一定为O(1)D.哈希表只能存储整数10.面向对象编程中，以下不属于三大特性的是（）A.封装B.继承C.多态D.复用（二）不定项选择题（11-20题）11.下列属于线性数据结构的有（）A.栈B.队列C.二叉树D.顺序表12.下列排序算法中，属于稳定排序的有（）A.归并排序B.冒泡排序C.堆排序D.基数排序13.关于图的最小生成树，说法正确的有（）A.Prim算法适用于稠密图B.Kruskal算法适用于稀疏图C.最小生成树一定唯一D.含n个节点的图，最小生成树有n-1条边14.下列关于递归的说法，正确的有（）A.递归必须设置终止条件B.递归可能产生栈溢出C.递归代码一定比迭代简洁D.递归时间复杂度一定更低15.能够实现查找功能的算法/数据结构有（）A.二分查找B.哈希表C.二叉搜索树D.并查集16.下列进制转换结果正确的有（）A.(1010)₂=(10)₁₀B.(FF)₁₆=(255)₁₀C.(77)₈=(63)₁₀D.(100)₁₀=(64)₁₆17.关于队列的应用场景，合理的有（）A.操作系统进程调度B.广度优先搜索C.函数递归调用D.消息缓冲处理18.下列算法中，属于贪心算法思想的有（）A.活动选择问题B.最小生成树求解C.01背包问题D.单源最短路Dijkstra算法19.关于时间复杂度，下列等价或正确的有（）A.O(n+1)=O(n)B.O(2ⁿ)>O(n²)C.O(logn)<O(n)D.O(n²+n³)=O(n²)20.二叉平衡树（AVL树）的特性包括（）A.左右子树高度差绝对值不超过1B.中序遍历为有序序列C.所有节点度数均为2D.查找效率优于普通二叉搜索树二、问题求解（共2题，每题5分，共10分）21.现有10个不同的小球，从中任选3个组成一组，不考虑顺序，共有多少种不同的组合方式？22.已知一棵完全二叉树共有123个节点，该二叉树的叶子节点个数为多少？三、阅读程序写结果（共4题，每题8分，共32分）程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta=15,b=6;

intc=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;

}

cout<<b<<endl;

return0;

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

#include<iostream>

usingnamespacestd;

intf(intn){

if(n<=1)return1;

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

}

intmain(){

cout<<f(6)<<endl;

return0;

}请写出程序运行结果：__________程序3PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intsum=0;

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

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

elsesum-=i;

}

cout<<sum<<endl;

return0;

}请写出程序运行结果：__________程序4PlainText

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings="noip2026";

intlen=s.size();

stringres;

for(inti=len-1;i>=0;i--){

res+=s[i];

}

cout<<res<<endl;

return0;

}请写出程序运行结果：__________四、完善程序（共2题，每题14分，共28分）1.冒泡排序优化（14分）【题目描述】对给定的整型数组进行升序冒泡排序，加入标记优化，若某一轮遍历未发生交换，说明数组已有序，直接结束排序，减少循环次数。PlainText

#include<iostream>

usingnamespacestd;

constintN=105;

inta[N],n;

intmain(){

cin>>n;

for(inti=1;i<=n;i++)cin>>a[i];

for(inti=1;i<=n-1;i++){

boolflag=____①____;

for(intj=1;j<=n-i;j++){

if(a[j]>a[j+1]){

swap(a[j],a[j+1]);

flag=____②____;

}

}

if(____③____)break;

}

for(inti=1;i<=n;i++)cout<<a[i]<<"";

return0;

}①__________②__________③__________2.二分查找（14分）【题目描述】给定一个严格升序的有序数组，查找目标数值x的下标，若不存在则输出-1。PlainText

#include<iostream>

usingnamespacestd;

constintN=105;

inta[N],n,x;

intfind(intl,intr){

while(l<=r){

intmid=____④____;

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

elseif(a[mid]<x){

l=____⑤____;

}else{

r=____⑥____;