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

NOIP2026全国青少年信息学奥林匹克联赛提高组初赛试题及详细答案一、单项选择题（共15题，每题2分，共计30分。每题仅有一个正确选项）1.下列不属于计算机基础进制转换常用进制的是（）A.二进制B.六进制C.八进制D.十六进制2.十进制数127转换为二进制数是（）A.1111111B.10000000C.11111110D.10101013.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则其后序遍历序列为（）A.CBEFDAB.FEDCBAC.CBEDFAD.BCEDFA4.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.直接插入排序C.归并排序D.选择排序5.栈和队列的核心区别是（）A.存储结构不同B.元素访问规则不同C.数据容量不同D.遍历方式不同6.一个无向连通图有n个顶点、m条边，其最小生成树的边数为（）A.n-1B.nC.m-1D.m-n+17.下列数据结构中，能够实现“先进后出”特性的是（）A.队列B.栈C.数组D.链表8.TCP协议中，用于可靠建立连接的机制是（）A.一次握手B.二次握手C.三次握手D.四次握手9.哈希表的查找、插入、删除操作的平均时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(n²)10.下列算法中，属于贪心算法典型应用的是（）A.最长公共子序列B.01背包问题C.活动选择问题D.最短路径Floyd算法11.完全二叉树共有2026个节点，其叶子节点个数为（）A.1013B.1012C.1014D.101112.下列文件格式中，属于视频文件的是（）A.PNGB.MP4C.TXTD.JPG13.图的深度优先遍历（DFS）采用的辅助数据结构是（）A.栈B.队列C.堆D.树14.二分查找算法适用于（）A.无序数组B.有序顺序存储数组C.有序链表D.任意线性结构15.下列关于动态规划算法的描述，正确的是（）A.无需存储子问题答案B.具备最优子结构和重叠子问题特性C.时间复杂度一定低于贪心算法D.无法解决最优化问题二、不定项选择题（共5题，每题2分，共计10分。每题有一个或多个正确选项，多选、少选、错选均不得分）1.下列排序算法中，属于稳定排序的有（）A.冒泡排序B.归并排序C.快速排序D.基数排序2.下列属于树结构基本性质的有（）A.n个节点的树必有n-1条边B.任意两点间有且仅有一条简单路径C.树中不存在环D.任意添加一条边必会产生唯一环3.下列算法中，可求解图最短路径的有（）A.DijkstraB.FloydC.KruskalD.SPFA4.下列关于链表的描述，正确的有（）A.动态分配内存空间B.随机访问效率高于数组C.插入删除操作无需移动大量元素D.单链表可双向遍历5.下列属于计算机网络拓扑结构的有（）A.星型B.总线型C.环型D.树型三、判断题（共10题，每题1分，共计10分。正确选√，错误选×）1.二叉搜索树的中序遍历序列一定是递增有序序列。（）2.堆排序是稳定排序算法。（）3.无向图的邻接矩阵一定是对称矩阵。（）4.贪心算法求解的问题，一定可以用动态规划求解。（）5.队列的遍历顺序遵循先进先出原则。（）6.哈希冲突无法完全避免，只能通过方法优化减少。（）7.任意一棵平衡二叉树一定是完全二叉树。（）8.时间复杂度O(n²)的算法一定比O(nlogn)的算法运行速度慢。（）9.最小生成树一定包含图中权值最小的边。（）10.顺序表的随机访问时间复杂度为O(1)。（）四、阅读程序写结果（共4题，每题8分，共计32分）程序1cpp

#include<iostream>

usingnamespacestd;

intmain(){

inta=18,b=24;

while(b!=0){

intt=a%b;

a=b;

b=t;

}

cout<<a<<endl;

return0;

}输出结果：__________程序2cpp

#include<iostream>

usingnamespacestd;

intf(intn){

if(n<=2)return1;

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

}

intmain(){

cout<<f(7)<<endl;

return0;

}输出结果：__________程序3cpp

#include<iostream>

usingnamespacestd;

intmain(){

ints=0;

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

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

elses-=i;

}

cout<<s<<endl;

return0;

}输出结果：__________程序4cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

stringstr="noip2026";

intlen=str.size();

intans=0;

for(inti=0;i<len;i++){

if(str[i]>='0'&&str[i]<='9'){

ans=ans*10+(str[i]-'0');

}

}

cout<<ans<<endl;

return0;

}输出结果：__________五、完善程序（共2题，每题9分，共计18分）1.二分查找完善程序功能：在严格递增的有序数组中查找目标值x，找到则返回下标，未找到返回-1。cpp

#include<iostream>

usingnamespacestd;

intbinarySearch(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-1;

}

intmain(){

intarr[10]={1,3,5,7,9,11,13,15,17,19};

intx;

cin>>x;

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

return0;

}空(1)：__________空(2)：__________2.斐波那契数列求和完善程序功能：计算前n项斐波那契数列的和（f(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2)）cpp

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

if(n==0){cout<<0;return0;}

if(n==1||n==2){cout<<n;return0;}

inta=1,b=1,sum=2;

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

intc=___(1)___;

sum+=c;

a=b;

___(2)___;

}

cout<<sum<<endl;

return0;

}空(1)：__________空(2)：__________详细答案与解析一、单项选择题（每题2分，共30分）1.答案：B解析：计算机基础进制常用二进制、八进制、十进制、十六进制，六进制无通用应用场景，不属于标准进制。2.答案：A解析：2⁷-1=127，7位二进制全1即为1111111。3.答案：A解析：由前序ABCDEF确定A为根节点，结合中序CBAEDF，得CB为左子树、EDF为右子树，递归推导后序遍历为CBEFDA。4.答案：C解析：冒泡、插入、选择排序时间复杂度均为O(n²)，归并排序稳定为O(nlogn)。5.答案：B解析：栈先进后出，队列先进先出，二者核心差异为元素存取规则，存储结构可同为顺序或链式结构。6.答案：A解析：n个顶点的连通图，最小生成树为无环连通图，固定包含n-1条边。7.答案：B解析：栈的核心特性为先进后出，队列为先进先出，数组、链表无固定存取顺序。8.答案：C解析：TCP通过三次握手建立可靠连接，四次握手用于断开连接。9.答案：A解析：理想状态下哈希表通过哈希映射直接定位元素，增删查平均时间复杂度为O(1)。10.答案：C解析：活动选择问题为经典贪心应用；01背包、最长公共子序列用动态规划，Floyd为多源最短路动态规划算法。11.答案：A解析：完全二叉树节点数为偶数时，叶子节点数为n/2；2026/2=1013。12.答案：B解析：PNG、JPG为图片格式，TXT为文本格式，MP4为标准视频格式。13.答案：A解析：深度优先遍历递归回溯特性匹配栈先进后出规则，广度优先遍历使用队列。14.答案：B解析：二分查找依赖有序、可随机访问的结构，仅适用于有序顺序存储数组，链表无法随机访问，不能使用二分查找。15.答案：B解析：动态规划核心两大特性为最优子结构与重叠子问题，需存储子问题答案，时间复杂度不一定低于贪心，专门用于求解最优化问题。二、不定项选择题（每题2分，共10分）1.答案：ABD解析：冒泡、归并、基数排序均为稳定排序；快速排序存在元素跨越相等元素交换，属于不稳定排序。2.答案：ABCD解析：树的四大基本性质：n点n-1边、无环、任意两点唯一路径、加边必成唯一环。3.答案：ABD解析：Dijkstra、SPFA求解单源最短路，Floyd求解多源最短路；Kruskal为最小生成树算法，不求解最短路径。4.答案：AC解析：链表动态分配内存，插入删除无需移动大量元素；链表仅支持顺序访问，效率低于数组，单链表仅能单向遍历。5.答案：ABCD解析：常见网络拓扑结构包含星型、总线型、环型、树型、网状型。三、判断题（每题1分，共10分）1.√解析：二叉搜索树左子树值<根值<右子树值，中序遍历必然递增有序。2.×解析：堆排序调整堆结构时会打乱相等元素相对位置，属于不稳定排序。3.√解析：无向图边无方向，u到v、v到u均连通，邻接矩阵对称。4.×解析：贪心仅适用于具备贪心选择性质的问题，部分贪心问题无重叠子问题，无法用动态规划求解。5.√解析：队列核心规则为先进先出。6.√解析：无论开放定址法、链地址法，均只能优化哈希冲突，无法彻底消除。7.×解析：平衡二叉树仅要求左右子树高度差不超过1，不一定是完全二叉树。8.×解析：时间复杂度为渐进趋势，小数据范围下O(n²)算法可能运行更快。9.√解析：最小生成树选取全局最优边，必然包含图中权值最小的边。10.√解析：顺序表通过下标直接访问元素，随机访问时间复杂度O(1)。四、阅读程序写结果（每题8分，共32分）1.答案：6解析：程序实现欧几里得辗转相除法，求解18和24的最大公约数，结果为6。2.答案：13解析：递归实现斐波那契数列，f(1)=1、f(2)=1、f(3)=2、f(4)=3、f(5)=5、f(6)=8、f(7)=13。3.答案：5解析：奇数相