NOIP全国青少年信息学奥林匹克联赛初赛模拟试题（含详细答案）

NOIP全国青少年信息学奥林匹克联赛初赛模拟试题（含详细答案）考试时间：90分钟满分：100分适用组别：普及组注意事项：1.本试卷共四大题，全部为笔试题，答案需写在指定答题区域；2.选择题为单项选择，多选、错选、不选均不得分；3.程序填空、阅读程序、完善程序题目严格按照语法规范作答。一、单项选择题（共20题，每题1.5分，共计30分）1.下列不属于计算机存储设备的是（）A.固态硬盘B.内存条C.显卡D.机械硬盘2.二进制数110101转换为十进制数是（）A.53B.51C.49D.473.十六进制数2A对应的十进制数是（）A.42B.38C.52D.484.下列关于操作系统的说法，错误的是（）A.Windows、Linux均为操作系统B.操作系统负责管理计算机硬件与软件资源C.办公软件属于操作系统D.操作系统是计算机系统的核心系统软件5.一个32位二进制整数，最多可表示的无符号十进制数范围是（）A.0~2³¹-1B.0~2³²-1C.-2³¹~2³¹-1D.-2³²~2³²-16.下列数据结构中，遵循“先进先出”原则的是（）A.栈B.队列C.二叉树D.哈希表7.已知一棵二叉树有10个叶子节点，2个度为1的节点，则该二叉树总节点数为（）A.21B.22C.23D.248.下列排序算法中，时间复杂度最优且为稳定排序的是（）A.快速排序B.冒泡排序C.归并排序D.选择排序9.设有数组a[1..8]，初始值为{2,5,8,1,3,9,4,7}，对其进行升序冒泡排序，第一轮排序结束后数组状态为（）A.{2,5,1,3,8,4,7,9}B.{1,2,5,3,8,4,7,9}C.{2,5,8,1,3,9,4,7}D.{1,2,3,4,5,7,8,9}10.图的广度优先遍历（BFS）主要借助的数据结构是（）A.栈B.队列C.链表D.树11.在C++语言中，以下合法的变量名是（）A.3numB.num_3C.num-3D.int12.C++中，表达式7%3+8/2的运算结果是（）A.4B.5C.6D.713.逻辑表达式!(3>5)&&(2<4)的值为（）A.0B.1C.2D.报错14.下列不属于程序三大基本结构的是（）A.顺序结构B.跳转结构C.选择结构D.循环结构15.一棵深度为4的满二叉树，节点总数为（）A.8B.15C.16D.716.设有向图有5个顶点、6条边，其邻接矩阵的元素个数为（）A.11B.30C.25D.3617.下列进制转换正确的是（）A.(1001)₂=(11)₁₀B.(1F)₁₆=(31)₁₀C.(12)₈=(10)₁₀D.(1010)₂=(12)₁₀18.栈的入栈序列为1、2、3、4，不可能的出栈序列是（）A.1、2、3、4B.4、3、2、1C.3、1、2、4D.2、1、4、319.C++中，for循环for(inti=1;i<=5;i++)循环体执行次数为（）A.4次B.5次C.6次D.无限次20.下列关于算法的描述，正确的是（）A.算法可以没有输出B.算法步骤可以无限执行C.算法必须有明确的步骤D.算法必须使用程序代码实现二、问题求解（共2题，每题5分，共计10分）1.现有一段长度为100的有序数组，采用二分查找算法查找某个元素，最坏情况下需要比较多少次？请写出计算过程。2.已知一个无向连通图有6个顶点，最少需要多少条边可以保证图连通？最多有多少条边（无重边、无自环）？三、阅读程序写结果（共4题，每题8分，共计32分）阅读下列C++程序代码，写出程序最终输出结果。程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta=10,b=6;

intc;

c=a%b+a/b;

cout<<c<<endl;

return0;

}程序2PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intsum=0;

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

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

}

cout<<sum<<endl;

return0;

}程序3PlainText

#include<iostream>

usingnamespacestd;

intf(intn){

if(n==1)return1;

returnf(n-1)+n;

}

intmain(){

cout<<f(5)<<endl;

return0;

}程序4PlainText

#include<iostream>

usingnamespacestd;

intmain(){

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

ints=0;

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

if(a[i]%3!=0)s+=a[i];

}

cout<<s<<endl;

return0;

}四、完善程序（共2题，每题14分，共计28分）根据题目功能，补全程序空缺代码，使程序正常实现对应功能。程序1：求斐波那契数列第n项功能：输入正整数n，输出斐波那契数列第n项数值（斐波那契数列定义：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)）PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

inta=1,b=1,c;

if(n==1||n==2){

cout<<1<<endl;

return0;

}

for(inti=3;___(1)___;i++){

c=___(2)___;

a=b;

b=c;

}

cout<<___(3)___<<endl;

return0;

}程序2：数组最大值与最小值交换功能：输入8个整数存入数组，找到数组中的最大值和最小值，交换二者位置后输出整个数组。PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta[8];

intmaxp=0,minp=0;

//输入数组

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

cin>>a[i];

}

//查找最大最小值下标

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

if(a[i]>a[maxp])___(1)___;

if(a[i]<a[minp])___(2)___;

}

//交换数值

intt=a[maxp];

a[maxp]=___(3)___;

a[minp]=t;

//输出数组

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

cout<<a[i]<<"";

}

return0;

}参考答案及详细解析一、单项选择题（每题1.5分，共30分）1.答案：C解析：显卡属于计算机硬件输出设备，核心功能是图形图像处理，不具备数据存储功能；固态硬盘、机械硬盘为外存储器，内存条为内存储器，均属于存储设备。2.答案：A解析：二进制转十进制按权展开：1×2⁵+1×2⁴+0×2³+1×2²+0×2¹+1×2⁰=32+16+4+1=53。3.答案：A解析：十六进制转十进制：2×16¹+10×16⁰=32+10=42（A对应十进制10）。4.答案：C解析：办公软件属于应用软件，不属于操作系统；操作系统是管理软硬件资源的系统软件。5.答案：B解析：32位无符号整数，所有位数均表示数值，范围为0~2³²-1；有符号整数范围为-2³¹~2³¹-1。6.答案：B解析：队列遵循先进先出（FIFO），栈遵循先进后出（LIFO）。7.答案：A解析：二叉树性质：度为0的节点数=度为2的节点数+1。叶子节点（度0）10个，则度2节点9个。总节点数=10+2+9=21。8.答案：C解析：归并排序时间复杂度O(nlogn)，稳定排序；快速排序O(nlogn)不稳定；冒泡、选择排序O(n²)，效率更低。9.答案：A解析：冒泡排序第一轮从左向右两两比较，将最大值9冒泡到末尾，其余元素依次交换，最终得到{2,5,1,3,8,4,7,9}。10.答案：B解析：广度优先遍历逐层遍历节点，使用队列存储待访问节点；深度优先遍历使用栈。11.答案：B解析：C++变量名以字母、下划线开头，由字母、数字、下划线组成，不能以数字开头、不能含特殊符号、不能使用关键字。12.答案：B解析：优先级：取模、整除同级，从左到右计算。7%3=1，8/2=4，1+4=5。13.答案：B解析：3>5为假（0），!0为真（1）；2<4为真（1），1&&1=1。14.答案：B解析：程序三大基本结构：顺序、选择、循环，无跳转结构。15.答案：B解析：深度为k的满二叉树节点总数为2ᵏ-1，2⁴-1=15。16.答案：C解析：n个顶点的图，邻接矩阵为n×n方阵，5×5=25，与边数无关。17.答案：B解析：(1F)₁₆=1×16+15=31；A选项为9，C选项为10（正确）但题干B绝对正确，D选项为10。18.答案：C解析：入栈1、2、3后出栈3，此时栈内为1、2，下一个出栈只能是2，不可能是1。19.答案：B解析：i取值1、2、3、4、5，共执行5次循环。20.答案：C解析：算法特性：有穷性、确定性、可行性、有输入、有输出。算法步骤明确、有限执行，可通过自然语言、流程图、代码等多种方式实现。二、问题求解（每题5分，共10分）1.答案：7次解析：二分查找最坏比较次数计算公式：满足2ᵏ-1≥数组长度的最小整数k。2⁶=64＜100，2⁷=128≥100，因此最坏需要7次比较。2.答案：最少5条，最多15条解析：n个顶点的无向连通图，最少边数为n-1（生成树），6-1=5条；最多边数为完全无向图边数，公式n(n-1)/2，6×5/2=15条。三、阅读程序写结果（每题8分，共32分）程序1结果：4解析：a=10，b=6；10%6=4，10/6=1；c=4+1=4，输出4。程序2结果：12解析：循环遍历1~6，累加偶数：2+4+6=12。程序3结果：15解析：递归函数为累加求和，f(5)=1+2+3+4+5=15。程序4结果：22解析：数组元素1、3、5、7、9，排除3的倍数3、9，