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

NOIP2026全国青少年信息学奥林匹克联赛提高组初赛试题比赛时长：120分钟满分：100分答题须知：1.本试卷全部为笔试作答，答案需写在指定答题区域，写在试题卷上无效。2.选择题答案唯一/多选严格按要求作答，多选、漏选、错选均不得分。3.程序题、计算题需规范书写步骤，按要点给分。一、单项选择题（共10题，每题1.5分，共15分。每题仅有一个正确选项）1.以下不属于线性数据结构的是（）A.队列B.栈C.二叉树D.链表2.十进制数2026转换为二进制数的位数为（）A.10位B.11位C.12位D.13位3.已知某算法的时间复杂度为O(nlogn)，下列排序算法中复杂度与此一致的是（）A.冒泡排序B.快速排序（平均）C.选择排序D.插入排序4.在C++中，以下关键字中用于定义常量的是（）A.staticB.constC.externD.inline5.一棵深度为5的满二叉树的节点总数为（）A.16B.31C.32D.156.栈的核心操作特性是（）A.先进先出B.先进后出C.随机存取D.有序插入7.下列进制转换正确的是（）A.(1011)₂=(13)₁₀B.(FF)₁₆=(254)₁₀C.(77)₈=(63)₁₀D.(1001)₂=(11)₁₀8.图的广度优先遍历（BFS）最适合借助以下哪种数据结构实现（）A.栈B.队列C.堆D.树9.C++中，int类型变量占用字节数通常为（）A.1字节B.2字节C.4字节D.8字节10.下列关于二分查找的说法正确的是（）A.可在无序数组中使用B.时间复杂度为O(n)C.仅适用于有序序列D.空间复杂度极高二、不定项选择题（共10题，每题1.5分，共15分。每题1-5个正确选项，全部选对得分，少选、多选、错选不得分）11.以下属于稳定排序的有（）A.冒泡排序B.归并排序C.快速排序D.基数排序12.下列属于图的存储结构的是（）A.邻接矩阵B.邻接表C.十字链表D.孩子链表13.C++中，以下合法的变量名有（）A.num_1B.1_sumC.maxValD.intE._temp14.关于二叉树的性质，说法正确的有（）A.度为0的节点数比度为2的节点数多1B.满二叉树一定是完全二叉树C.完全二叉树一定是满二叉树D.二叉树的子树有左右之分15.以下算法中，属于贪心算法思想的有（）A.活动选择问题B.哈夫曼编码C.最短路径Dijkstra算法D.背包问题（01背包暴力解法）16.下列关于队列的说法正确的有（）A.遵循先进先出规则B.循环队列可解决假溢出问题C.只能顺序存储D.可用于层次遍历17.C++中，以下运算符优先级高于赋值运算符的有（）A.算术运算符B.关系运算符C.逻辑运算符D.逗号运算符18.属于动态规划算法特征的有（）A.最优子结构B.重叠子问题C.贪心选择性D.无后效性19.以下数据结构中可以实现排序功能的有（）A.优先队列B.平衡二叉树C.栈D.哈希表20.下列关于复杂度的说法错误的有（）A.O(1)优于O(n)B.O(n²)优于O(nlogn)C.O(2ⁿ)是多项式复杂度D.常数复杂度与数据规模无关三、问题求解（共2题，每题5分，共10分）21.现有长度为10的有序数组，采用二分查找查找目标元素，最坏情况下需要比较多少次？请写出计算过程。22.已知一个无向图有8个顶点、12条边，该图的最小生成树包含多少条边？若移除一条最小生成树的边，图会变成几个连通分量？四、阅读程序写结果（共4题，每题8分，共32分）程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta=12,b=5;

intres=a%b+a/b;

cout<<res<<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;

if(sum>15)break;

}

cout<<sum<<endl;

return0;

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

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings="noip2026";

intcnt=0;

for(inti=0;i<s.size();i++){

if(s[i]>='0'&&s[i]<='9')cnt++;

}

cout<<cnt<<endl;

return0;

}请写出程序运行结果：__________五、完善程序（共2题，每题14分，共28分）程序1：冒泡排序优化题目功能：实现优化版冒泡排序，对整型数组进行升序排序，若某一轮遍历无交换，说明数组已有序，直接提前结束排序，降低时间复杂度。PlainText

#include<iostream>

usingnamespacestd;

constintN=105;

inta[N],n;

voidbubble_sort(){

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

boolflag=____①____;

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

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

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

flag=____②____;

}

}

if(____③____)break;

}

}

intmain(){

cin>>n;

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

bubble_sort();

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

return0;

}①__________②__________③__________程序2：斐波那契数列统计题目功能：输入正整数n，计算并输出前n项斐波那契数列，同时统计前n项中偶数的个数（斐波那契数列定义：f(1)=1，f(2)=1，f(n)=f(n-1)+f(n-2)）。PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intn,cnt=0;

longlongf1=1,f2=1,temp;

cin>>n;

if(n>=1)cout<<f1<<"";

if(n>=2)cout<<f2<<"";

if(f1%2==0)cnt++;

if(f2%2==0)cnt++;

for(inti=____④____;i<=n;i++){

temp=____⑤____;

f1=f2;

f2=temp;

cout<<f2<<"";

if(____⑥____)cnt++;

}

cout<<endl<<"偶数个数："<<cnt<<endl;

return0;

}④__________⑤__________⑥__________参考答案及详细解析一、单项选择题（15分）1.C解析：二叉树为树形非线性结构，队列、栈、链表均为线性结构。2.B解析：2¹⁰=1024，2¹¹=2048，2026介于两者之间，共11位二进制数。3.B解析：冒泡、选择、插入排序平均复杂度均为O(n²)，快速排序平均O(nlogn)。4.B解析：const用于定义只读常量，static为静态变量，extern为外部变量，inline为内联函数。5.B解析：深度为k的满二叉树节点总数为2ᵏ-1，2⁵-1=31。6.B解析：栈遵循先进后出（LIFO），队列遵循先进先出。7.A解析：(1011)₂=8+2+1=13；FF₁₆=255；77₈=63；1001₂=9。8.B解析：BFS借助队列实现层级遍历，DFS借助栈实现深度遍历。9.C解析：标准C++中int类型默认占用4字节内存。10.C解析：二分查找仅适用于有序序列，时间复杂度O(logn)。二、不定项选择题（15分）11.ABD解析：快速排序为不稳定排序，其余均为稳定排序。12.ABC解析：邻接矩阵、邻接表、十字链表为图的存储结构，孩子链表为树的存储结构。13.ACE解析：变量名不能以数字开头、不能使用关键字，BD不合法。14.ABD解析：满二叉树是特殊的完全二叉树，完全二叉树不一定是满二叉树。15.ABC解析：01背包暴力解法为枚举思想，不属于贪心算法。16.ABD解析：队列可顺序存储也可链式存储，C错误。17.ABC解析：逗号运算符优先级低于赋值运算符。18.ABD解析：贪心选择性为贪心算法特征，非动态规划特征。19.AB解析：优先队列、平衡二叉树可实现排序，栈和哈希表无排序特性。20.BC解析：O(nlogn)优于O(n²)，O(2ⁿ)为指数复杂度，非多项式复杂度。三、问题求解（10分）21.答案：4次解析：二分查找最坏比较次数为⌊log₂n⌋+1，n=10，log₂10≈3.32，向下取整为3，3+1=4次。22.答案：7条；2个解析：n个顶点的无向图最小生成树固定含n-1条边，8-1=7条；最小生成树是连通无环图，移除任意一条边，图会分裂为2个连通分量。四、阅读程序写结果（32分）1.结果：4解析：12%5=2，12/5=2，2+2=4。2.结果：13解析：递归求解斐波那契数列，f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5