NOIP普及组初赛模拟试题（含详细答案解析）-1

NOIP普及组初赛模拟试题（含详细答案解析）考试时长：90分钟满分：100分注意事项：1.答卷前，考生务必将自己的姓名、准考证号填写在答题卡上。2.答案全部写在答题卡上，写在本试卷上无效。3.考试结束后，将本试卷和答题卡一并交回。一、单项选择题（共15题，每题2分，共30分）每题只有一个正确答案，多选、错选、不选均不得分。1.以下不属于计算机基础输入设备的是（）A.键盘B.打印机C.鼠标D.扫描仪2.二进制数101101对应的十进制数是（）A.45B.46C.47D.483.已知十六进制数2A，其对应的十进制数为（）A.42B.52C.38D.584.操作系统的核心功能是（）A.文字处理B.资源管理与程序调度C.图形绘制D.网络传输5.在TCP/IP协议体系中，负责可靠数据传输的核心协议是（）A.IPB.TCPC.UDPD.HTTP6.下列关于栈和队列的说法，正确的是（）A.栈先进先出，队列先进后出B.栈先进后出，队列先进先出C.两者均为先进先出D.两者均为先进后出7.一棵有5层的满二叉树，节点总数为（）A.16B.31C.32D.158.排序算法中，时间复杂度不受数据初始状态影响，恒为O(n²)的是（）A.冒泡排序B.插入排序C.选择排序D.快速排序9.下列变量名中，符合C++语言命名规范的是（）A.1numB.num_1C.num-1D.if10.设inta=5,b=2;表达式a%b+a/b的值是（）A.2B.3C.4D.511.面向对象程序设计的核心特性不包括（）A.封装B.继承C.迭代D.多态12.访问局域网内共享文件夹常用的网络协议是（）A.FTPB.SMBC.DNSD.DHCP13.一个长度为n的有序数组，二分查找的最坏时间复杂度为（）A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)14.下列数据结构中，不能进行随机访问的是（）A.数组B.链表C.顺序表D.哈希表15.以下属于恶意程序的是（）A.记事本程序B.木马程序C.解压工具D.浏览器二、判断题（共10题，每题1分，共10分）正确选√，错误选×，不答不得分。1.计算机内存中的数据断电后会全部丢失。（）2.十进制小数转换为二进制小数一定可以精确转换。（）3.循环队列可以有效解决顺序队列的假溢出问题。（）4.C++语言中，全局变量的作用域覆盖整个程序文件。（）5.快速排序是稳定的排序算法。（）6.所有递归算法都可以改写为非递归算法。（）7.IP地址用于本机环路测试。（）8.二叉树的叶子节点数一定比度为2的节点数多1。（）9.哈希表的查找时间复杂度一定为O(1)。（）10.编译型语言程序运行效率通常高于解释型语言。（）三、问题求解（共2题，每题5分，共10分）1.现有一串数字序列：1,3,2,5,4,7,6，采用冒泡排序进行升序排序，请问需要进行多少趟冒泡排序？总共需要多少次元素交换？2.已知一棵二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，写出该二叉树的后序遍历序列。四、程序阅读题（共4题，每题8分，共32分）阅读程序代码，写出程序运行的输出结果。程序1PlainText

#include<iostream>

usingnamespacestd;

intmain()

{

ints=0;

for(inti=1;i<=6;i++)

{

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

elses-=i;

}

cout<<s<<endl;

return0;

}程序2PlainText

#include<iostream>

usingnamespacestd;

intf(intx)

{

if(x==1)return1;

returnf(x-1)*2+1;

}

intmain()

{

cout<<f(4)<<endl;

return0;

}程序3PlainText

#include<iostream>

usingnamespacestd;

intmain()

{

inta[5]={2,4,6,8,10};

intsum=0;

for(inti=0;i<5;i++)

{

if(a[i]%4==0)sum+=a[i];

}

cout<<sum<<endl;

return0;

}程序4PlainText

#include<iostream>

usingnamespacestd;

intmain()

{

intn=15;

intcnt=0;

while(n>0)

{

cnt+=n&1;

n=n>>1;

}

cout<<cnt<<endl;

return0;

}五、程序完善题（共2题，每空2分，共18分）根据题目功能，补全程序空缺代码。1.题目：统计1~n之间所有素数的个数PlainText

#include<iostream>

usingnamespacestd;

boolisPrime(intx)

{

if(x<2)return___1___;

for(inti=2;i*i<=x;i++)

{

if(x%i==0)return___2___;

}

returntrue;

}

intmain()

{

intn,ans=0;

cin>>n;

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

{

if(___3___)ans++;

}

cout<<ans<<endl;

return0;

}空缺填空：___1___、___2___、___3___2.题目：二分查找有序数组中目标数的位置，存在则输出下标，不存在输出-1PlainText

#include<iostream>

usingnamespacestd;

intsearch(inta[],intn,intkey)

{

intl=0,r=n-1;

while(___1___)

{

intmid=(l+r)/2;

if(a[mid]==key)return___2___;

elseif(a[mid]>key)r=mid-1;

elsel=___3___;

}

return-1;

}

intmain()

{

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

intx;

cin>>x;

cout<<search(arr,6,x)<<endl;

return0;

}空缺填空：___1___、___2___、___3___参考答案与详细解析一、单项选择题（每题2分，共30分）1.B解析：打印机是输出设备，键盘、鼠标、扫描仪均为输入设备。2.A解析：101101(2)=1×32+0×16+1×8+1×4+0×2+1×1=45。3.A解析：2A(16)=2×16+10=42。4.B解析：操作系统核心作用是管理硬件、软件资源，调度程序运行。5.B解析：TCP是面向连接的可靠传输协议，UDP为不可靠传输，IP负责路由寻址。6.B解析：栈遵循后进先出（先进后出），队列遵循先进先出规则。7.B解析：k层满二叉树节点总数为2^k-1，5层即32-1=31。8.C解析：选择排序无论数据是否有序，都需要完成固定次数遍历比较，复杂度恒为O(n²)；冒泡、插入排序有序时复杂度可优化为O(n)；快速排序平均O(nlogn)。9.B解析：变量名不能以数字开头、不能含横线以外特殊字符、不能使用关键字，if为C++关键字。10.B解析：5%2=1，5/2=2，1+2=3。11.C解析：面向对象三大特性：封装、继承、多态，迭代是循环算法思想。12.B解析：SMB协议用于局域网文件共享传输；FTP为文件传输协议（外网常用），DNS域名解析，DHCP自动分配IP。13.C解析：二分查找最坏、平均时间复杂度均为O(log₂n)。14.B解析：链表只能从头节点依次遍历访问，不支持随机访问；数组、顺序表、哈希表均可随机访问。15.B解析：木马属于恶意入侵程序，其余均为正常工具软件。二、判断题（每题1分，共10分）1.√解析：内存为断电易失性存储，硬盘、U盘等外存数据断电保留。2.×解析：部分十进制小数（如0.1）无法用二进制小数精确表示，会产生精度误差。3.√解析：循环队列通过首尾指针循环移动，解决普通顺序队列假溢出问题。4.√解析：全局变量定义在函数外，作用域为整个当前源文件。5.×解析：快速排序是不稳定排序，相等元素相对顺序可能改变。6.√解析：所有递归逻辑均可通过栈模拟，改写为非递归迭代形式。7.√解析：为本地回环地址，用于测试本机网络协议栈。8.√解析：二叉树通用性质：叶子节点数=度为2的节点数+1。9.×解析：哈希表存在哈希冲突，最坏查找复杂度为O(n)，平均为O(1)。10.√解析：编译型语言提前整体编译为机器码，运行效率高于逐行解释的解释型语言。三、问题求解（每题5分，共10分）第1题答案：4趟冒泡，6次交换解析：原序列：1,3,2,5,4,7,6第1趟：交换3和2、5和4、7和6，序列变为1,2,3,4,5,6,7（3次交换），最大值归位；第2、3趟无交换，完成次大值归位；冒泡排序对n个元素，有效趟数为4趟，全程累计交换6次。第2题答案：DEBFCA解析：由前序（根左右）ABDECF、中序（左根右）DBEAFC推导：1.前序首字符A为根节点，中序中A左侧DBE为左子树，右侧FC为右子树；2.左子树前序BDE、中序DBE，得B为左子树根，D左孩子、E右孩子；3.右子树前序CF、中序FC，得C为右子树根，F左孩子；4.后序遍历（左右根）得序列：DEBFCA。四、程序阅读题（每题8分，共32分）程序1输出：3解析：循环遍历1~6，奇数减、偶数加：-1+2-3+4-5+6=3。程序2输出：15解析：递归推导：f(1)=1，f(2)=2×1+1=3，f(3)=2×3+1=7，f(4)=2×7+1=15。程序3输出：12解析：数组中能被4整除的数为4、8，求和4+8=12。