NOIP提高组初赛模拟试题（真实真题风格）

NOIP提高组初赛模拟试题（真实真题风格）适用级别：普及提高组初赛考试时长：90分钟满分：100分注意事项：1.答案必须写在答题卡上，写在试卷上无效。2.考试结束后，仅上交答题卡。3.严禁携带电子设备、资料入场，违规按作弊处理。一、单项选择题（共15题，每题2分，共30分）每题仅有一个正确选项，多选、错选、不选均不得分。1.以下不属于计算机基础逻辑运算的是（）A.与运算B.或运算C.取模运算D.异或运算2.二进制数101101对应的十进制数是（）A.43B.45C.53D.613.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则该二叉树的后序遍历序列为（）A.CBEFDAB.CBAFEDC.BCEDFAD.无法确定4.栈和队列的主要区别是（）A.存储结构不同B.元素访问规则不同C.空间复杂度不同D.时间复杂度不同5.排序算法中，时间复杂度最坏为O(nA.快速排序B.堆排序C.冒泡排序D.简单选择排序6.一个无向连通图有6个顶点、8条边，其最小生成树的边数为（）A.5B.6C.7D.87.以下关于哈希表的说法，错误的是（）A.哈希表查找平均时间复杂度为O(1)B.链地址法可以解决哈希冲突C.哈希表一定不会出现元素堆积D.哈希函数的优劣直接影响查找效率8.十进制数2026转换为十六进制数为（）A.7EAB.7EBC.8EAD.8EB9.下列不属于操作系统的是（）A.LinuxB.Windows11C.PythonD.macOS10.一棵深度为4的满二叉树，节点总数为（）A.12B.15C.16D.1711.面向对象编程的核心特性不包括（）A.封装B.继承C.多态D.递归12.对长度为n的有序数组进行二分查找，最坏情况下的比较次数为（）A.log2⁡n向下取整+1B.nC.n13.下列网络协议中，用于文件传输的是（）A.HTTPB.FTPC.TCPD.UDP14.递归算法通常对应的数据结构是（）A.队列B.栈C.链表D.树15.下列排序中，不需要额外辅助空间的是（）A.归并排序B.基数排序C.堆排序D.计数排序二、多项选择题（共5题，每题3分，共15分）每题有多个正确选项，多选、少选、错选均不得分。1.以下属于线性数据结构的有（）A.栈B.队列C.二叉树D.链表2.下列算法中，时间复杂度为O(nlogA.冒泡排序B.快速排序（平均）C.堆排序D.归并排序3.解决哈希冲突的常用方法有（）A.链地址法B.线性探测法C.二次探测法D.随机探测法4.关于图的遍历，说法正确的有（）A.DFS深度优先搜索可借助栈实现B.BFS广度优先搜索可借助队列实现C.无向图遍历一定不会出现环D.遍历可用于判断图的连通性5.以下属于编程语言的有（）A.C++B.JavaC.HTMLD.Pascal三、判断题（共10题，每题1分，共10分）正确选√，错误选×1.栈遵循先进先出的规则。（）2.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）3.快速排序是稳定排序算法。（）4.一个有向图的入度之和等于出度之和。（）5.二进制原码、反码、补码对于正数是完全相同的。（）6.哈希表的查找效率与装填因子无关。（）7.递归程序一定可以改写为非递归程序。（）8.顺序表的随机访问效率高于链表。（）9.TCP协议是无连接、不可靠的传输协议。（）10.最小生成树一定唯一。（）四、问题求解（共2题，每题5分，共10分）1.已知有10个节点的无向完全图，求该图的边数以及其最小生成树的边数。2.现有一段楼梯，共8级，每次只能走1级或2级，求走完这段楼梯的总走法数。五、程序阅读理解（共2题，每题10分，共20分）程序1cpp

#include<iostream>

usingnamespacestd;

intfunc(intn){

if(n<=2)returnn;

returnfunc(n-1)+2*func(n-2);

}

intmain(){

cout<<func(6)<<endl;

return0;

}请写出程序运行结果。程序2cpp

#include<iostream>

usingnamespacestd;

intmain(){

inta[]={2,5,1,8,3,9};

intn=6,ans=0;

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

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

if(a[i]<a[j])ans++;

}

}

cout<<ans<<endl;

return0;

}请写出程序运行结果。六、程序完善（共1题，15分）题目功能：输入一个正整数n，利用二分查找判断数字x是否在有序数组中，存在输出Yes，不存在输出No。请补全空缺代码。cpp

#include<iostream>

usingnamespacestd;

intmain(){

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

intn=10,x;

cin>>x;

intl=0,r=n-1;

boolflag=false;

while(___(1)___){

intmid=___(2)___;

if(arr[mid]==x){

flag=true;

break;

}elseif(arr[mid]>x){

___(3)___;

}else{

___(4)___;

}

}

if(flag)cout<<"Yes"<<endl;

elsecout<<"No"<<endl;

return0;

}请依次写出(1)(2)(3)(4)处的代码参考答案与详细解析一、单项选择题（每题2分）1.C解析：取模是算术运算，与、或、异或为逻辑运算。2.B解析：32+8+4+1=45。3.A解析：根据前序、中序遍历还原二叉树，后序遍历为CBEFDA。4.B解析：栈先进后出，队列先进先出，核心差异为存取规则。5.C解析：冒泡排序最坏O(n2)6.A解析：n个顶点的最小生成树固定为n-1条边。7.C解析：哈希冲突会导致元素堆积，影响查找效率。8.A解析：7×169.C解析：Python是编程语言，非操作系统。10.B解析：深度k的满二叉树节点数2k−1，11.D解析：递归是算法思想，非面向对象特性。12.A解析：二分查找最坏比较次数为⌊log13.B解析：FTP为文件传输协议，HTTP超文本传输，TCP/UDP为传输层协议。14.B解析：递归调用由系统栈实现。15.C解析：堆排序为原地排序，无需额外辅助空间。二、多项选择题（每题3分）1.ABD解析：二叉树为非线性结构。2.BCD解析：冒泡排序复杂度为O(n3.ABCD解析：四种均为常见哈希冲突解决方法。4.ABD解析：无向图可能存在环，遍历可检测连通性。5.ABD解析：HTML是标记语言，非编程语言。三、判断题（每题1分）1.×解析：栈先进后出，队列先进先出。2.√解析：满二叉树是特殊的完全二叉树。3.×解析：快速排序属于不稳定排序。4.√解析：有向图所有顶点入度之和恒等于出度之和。5.√解析：正数的原码、反码、补码完全一致。6.×解析：装填因子越大，哈希冲突越多，效率越低。7.√解析：所有递归算法均可转化为栈模拟的非递归形式。8.√解析：顺序表支持随机访问，链表仅支持顺序访问。9.×解析：TCP面向连接、可靠；UDP无连接、不可靠。10.×解析：权值相同的图，最小生成树可能不唯一。四、问题求解（每题5分）1.答案：无向完全图边数45，最小生成树边数9。解析：n个节点无向完全图边数公式：n(n−1)/2=10×9/2.答案：34种解析：经典递推问题，f(n)=f(n−1)+f(n−2)，斐波那契数列，f(1)=1,f(2)=2，推导得f(8)=34。五、程序阅读理解（每题10分）1.运行结果：26解析：递推公式f(n)=f(n−1)+2f(n−2)，f(1)=1,f(2)=2f(3)=2+2×1=4，f(4)=4+2×2=8，f(5)=8+2×4