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

NOIP2018全国青少年信息学奥林匹克联赛初赛提高组试题及详细答案考试时间：2小时满分：100分一、单项选择题（共10题，每题2分，共计20分。每题仅有一个正确答案）1.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。A.1983B.1984C.1985D.19862.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F……，刚按下第81次按键时，屏幕上输出的字符是（）。A.aB.SC.DD.f3.一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为BAEDCF，则其后序遍历序列为（）。A.BEDFCAB.BEFDCAC.EBDFCAD.BEDFAC4.设根节点深度为0，一棵深度为h的满k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，其结点总数为（）。A.(kʰ⁺¹-1)/(k-1)B.kʰ-1C.kʰD.(kʰ-1)/(k-1)5.以下排序算法中，不需要比较关键字的是（）。A.快速排序B.基数排序C.堆排序D.冒泡排序6.甲乙丙三位同学周末去操场跑步，甲每2天跑一次，乙每3天跑一次，丙每4天跑一次。若2018年10月1日三人同时跑步，则下一次三人同时跑步的日期是（）。A.10月13日B.10月12日C.10月25日D.10月24日7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。A.1/2B.1/3C.2/3D.3/58.关于C++语言的变量，以下说法正确的是（）。A.全局变量和局部变量不可以重名B.未初始化的局部变量值一定为0C.静态局部变量全程只初始化一次D.全局变量存储在栈空间中9.二进制数1001101011对应的十进制数是（）。A.619B.620C.621D.62210.复杂度为O(nlogn)的排序算法是（）。A.冒泡排序B.归并排序C.选择排序D.插入排序二、不定项选择题（共5题，每题3分，共计15分。每题正确答案数量不唯一，多选、少选、错选均不得分）1.下列关于计算机存储与进制的说法正确的有（）。A.1Byte=8bitB.十六进制数末尾加0，数值扩大16倍C.二进制小数可以精准表示所有十进制小数D.计算机内存的基本存储单元是字节2.下列属于图的遍历算法的有（）。A.DFSB.BFSC.FloydD.Dijkstra3.关于栈和队列，说法正确的有（）。A.栈遵循先进后出规则B.队列遵循先进先出规则C.栈和队列都可以用数组实现D.栈可以实现括号匹配校验4.以下哪些是合法的C++标识符（）。A._numB.3abcC.abc_3D.abc-35.关于时间复杂度，说法正确的有（）。A.时间复杂度只关注最高阶项B.O(n²)优于O(nlogn)C.常数级复杂度记作O(1)D.双重循环的时间复杂度一定是O(n²)三、问题求解（共2题，每题5分，共计10分）1.现有10个一模一样的小球，分给3个不同的同学，要求每个同学至少分到1个小球，共有多少种不同的分配方案？2.已知一棵2-3树，高度为3（根节点高度为0），该树最多有多少个叶子节点？四、阅读程序写结果（共4题，每题8分，共计32分）程序1PlainText

#include<iostream>

usingnamespacestd;

intmain(){

inta=10,b=20;

a=a^b;

b=a^b;

a=a^b;

cout<<a<<""<<b<<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(){

ints=0;

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

if(i%3==0)continue;

s+=i;

}

cout<<s<<endl;

return0;

}程序4PlainText

#include<iostream>

usingnamespacestd;

intmain(){

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

int*p=a;

cout<<*(p++)<<""<<*p<<endl;

return0;

}五、完善程序（共2题，第1题11分，第2题12分，共计23分）1.【最大公约数】利用欧几里得算法（辗转相除法）求解两个正整数的最大公约数，补全代码。PlainText

#include<iostream>

usingnamespacestd;

intgcd(inta,intb){

if(____(1)____)

returna;

returngcd(b,____(2)____);

}

intmain(){

intx,y;

cin>>x>>y;

cout<<____(3)____<<endl;

return0;

}2.【冒泡排序】实现对数组的升序冒泡排序，优化排序过程，无交换时提前结束，补全代码。PlainText

#include<iostream>

usingnamespacestd;

intmain(){

intn,a[105];

cin>>n;

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

cin>>a[i];

boolflag;

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

flag=____(1)____;

for(intj=0;j<____(2)____;j++){

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

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

flag=____(3)____;

}

}

if(!flag)____(4)____;

}

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

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

return0;

}详细答案与逐题解析一、单项选择题答案及解析1.答案：B解析：全国青少年计算机程序设计竞赛由中国计算机学会1984年创办，是国内信息学竞赛的开端赛事。2.答案：B解析：按键循环序列：CapsLock(1)、A(2)、S(3)、D(4)、F(5)，5次按键为一轮。81÷5=16轮余1。初始小写，每轮第一个按键切换大小写，16轮后状态为小写，第81次为新一轮第一个键CapsLock，切换为大写。第80次按键为F（小写），第81次切换大写，后续第82次A、83次S，题目问第81次按键后输出字符，结合按键顺序逻辑，最终输出S。3.答案：A解析：前序遍历根左右，中序遍历左根右。前序首位A为根，中序中A左侧B为左子树，右侧EDCF为右子树。递归拆分遍历，最终得到后序遍历BEDFCA。4.答案：A解析：满k叉树节点总数为等比数列求和，层数0~h共h+1层，总和S=k⁰+k¹+…+kʰ=(kʰ⁺¹-1)/(k-1)。5.答案：B解析：基数排序基于关键字数位排序，无需元素之间比较；快速、堆、冒泡排序均依赖关键字比较。6.答案：A解析：求2、3、4最小公倍数为12，10月1日加12天为10月13日。7.答案：B解析：线段随机两点长度期望为经典概率问题，结论固定为1/3。8.答案：C解析：局部变量可与全局变量重名；未初始化局部变量是随机垃圾值；静态局部变量仅初始化一次；全局变量存储在静态存储区，栈仅存放局部变量。9.答案：D解析：二进制转十进制：1×2⁹+0×2⁸+0×2⁷+1×2⁶+1×2⁵+0×2⁴+1×2³+0×2²+1×2¹+1×2⁰=512+64+32+8+2+1=622。10.答案：B解析：冒泡、选择、插入排序时间复杂度均为O(n²)；归并排序稳定O(nlogn)。二、不定项选择题答案及解析1.答案：ABD解析：二进制小数无法精准表示部分十进制小数（如0.1），C错误；其余选项均为计算机存储基础常识。2.答案：AB解析：DFS深度优先、BFS广度优先是图遍历算法；Floyd、Dijkstra是图最短路算法，不属于遍历。3.答案：ABCD解析：栈先进后出、队列先进先出，二者均可通过数组模拟实现，栈的经典应用即为括号匹配校验，四个选项均正确。4.答案：AC解析：C++标识符只能由字母、数字、下划线组成，且不能以数字开头。B以数字开头、D含横线，均不合法。5.答案：AC解析：O(nlogn)复杂度优于O(n²)，B错误；嵌套循环层数不固定时，双重循环复杂度不一定是O(n²)，D错误；其余选项正确。三、问题求解答案及解析1.答案：36解析：经典隔板法问题，10个球形成9个空隙，插入2个隔板，方案数C(9,2)=9×8÷2=36。2.答案：18解析：2-3树每个内部节点最多3个子节点，高度3（根0层），共4层。叶子节点在最底层，每层节点最多三子节点，最大叶子数：3×3×2=18。四、阅读程序写结果答案及解析程序1答案：2010解析：利用异或运算交换两个变量，无需临时变量，最终a、b数值互换。程序2答案：13解析：递归实现斐波那契数列，f(0)=1、f(1)=1，递推得f(6)=13。程序3答案：37解析：累加1-10中不能被3整除的数，1+2+4+5+7+8+10=37。程序4答案：12解析：p++先取值后自增，首次输出*p即a[1]=1，自增后p指向a[2]，第二