2018颍上一中青少年信息学奥林匹克竞赛测题

2018第24届全国青少年信息学奥林匹克联赛初赛+答案第24届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018 年10 月13 日14:30~16:30选手注意：1、试题纸共有7 页，答题纸共有2 页，满分100 分。

请在答题纸上作答，写在试题纸上的一律无效。

2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备:( )A.扫描仪B.键盘C.鼠标D.打印机2. 下列四个不同进制的数中，与其它三项数值上不相等的是( )。

A. (269)16 (注解：2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617)C. (1151)8 （注解：1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617）D. (1001101011)23. 1MB等于( )。

A. 1000 字节B. 1024 字节C. 1000 X 1000字节D. 1024 X 1024字节4. 广域网的英文缩写是( )。

A. LANB. WAN (Wide Area Network)C. MAND.LNA5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 19856. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、......，屏幕上输出的第81 个字符是字母( )。

A. AB. SC. DD. a7. 根节点深度为0，一棵深度为h 的满k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有( )个结点。

A. (k h+1-1)/(k-1)B. k h-1C. k hD. (k h-1) / (k - 1)8. 以下排序算法中，不需要进行关键字比较操作的算法是( )。

例13-4迷宫寻宝【问题描述】一个n行m列的迷宫（1<=n,m<=5），入口在左上角，规定只能向下或向右走。

迷宫的某些地方藏有不同价值（>0）的宝藏，同时又存在一些障碍无法通过。

求到达右下角出口时收集宝藏的最大值。

【输入】第一行n和m一下n行m列描述迷宫矩阵a[I,j]（-1：障碍）；最大值【样例输入】342-150513-16-18910【样例输出】33【分析】A[I,j]保存第i行第j列的宝藏价值。

令f[I,j]为从（1，1）走到第i行第j列时所能收集的宝藏的最大价值。

状态转移方程：F[I,j]=max{f[I-1,j],f[I,j-1]}+a[I,j](i<=n,1<=m)条件：n[I,j]<>-1初始：f[1,1]=a[1,1]目标：f[n,m]【参考程序】Const maxn=50;maxm=50;Fin=’b1.in’;Fout=’b1.out’;VarF,a:array[0..maxn+1,0..maxm+1]of integer;I,j,k,n,m,t:integer;Procedure init;BeginAssign(input,fin);Reset(input);Readln(n,m);For i:=0to n+1doFor j:=0to m+1do a[I,j]:=-1;A[0,1]:=0;For i:=1to n doFor j:=1to m doBeginRead(a[I,j]);If(a[I,j-1]=-1)and(a[i-1,j]=-1)then a[I,j]:=-1;//很关键的预处理End;Close(input);End;Function max(a,b:integer):integer;Begin max:=a;if b>a then max:=b;end;Procedure work;BeginFillchar(f,sizeof(f),0);For i:=1to n doFor j:=1to m doIf a[I,j]<>-1Then f[I,j]:=max(f[i-1,j],f[I,j-1])+a[I,j];End;Procedure print;BeginAssign(output,fout);Rewrite(output);Writeln(f[n,m]);Close(output);End;BeginInit;Work;Print;End.13-5花店橱窗布置（IOI1999）【问题描述】假设你想以最美观的方式布置花店的橱窗。

2018NOIP普及组初赛试题第二十四届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018 年10 月13 日14:30~16:30选手注意：试题纸共有7 页，答题纸共有2 页，满分100 分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机2、下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A.(269)16B.(617)10C.(1151)8D.(1001101011)23、1MB 等于（）。

A.1000 字节B.B. 1024 字节C.1000 X 1000 字节D.D. 1024 X 1024 字节4、广域网的英文缩写是（）。

A. LANB. WANC. MAND. LNA5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983C. 1985D. 19866、如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母A. AB. SC. DD. a7、根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。

A.(k h+1 - 1) / (k - 1)B.k h-1C.k hD.(k h-1) / (k - 1)8、以下排序算法中，不需要进行关键字比较操作的算法是（）。

A. 基数排序B. 冒泡排序C. 堆排序D. 直接插入排序9、给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要N - 1 次比较操作。

第十八届全国青少年信息学奥林匹克竞赛初赛普及组参考答案第十八届全国青少年信息学奥林匹克竞赛初赛普及组试题和参考答案一、单项选择题（共20题，每题1.5分，共计30分，每题有且仅有一个正确答案）1、计算机如果缺少（），将无法正常启动。

A、内存B、鼠标C、U盘D、摄像头2、（）是一种先进先出的线性表。

A、栈B、队列C、哈希表D、二叉树3、目前计算机芯片（集成电路）制造的主要原料是（），它是一种能从沙子中提炼出来的物质。

A、硅B、铜C、锗D、铝4、十六进制数9A在（）进制下是232。

A、四B、八C、十D、十二5、（）不属于操作系统。

A、WindowsB、DOSC、PhotoshopD、NOI Linux6、如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。

A、ABCB、CBAC、ACBD、BAC7、目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。

A、显示器B、CPUC、内存D、鼠标8、使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5、4、3、2、1需要进行（）次交换，才能完成冒泡排序。

A、0B、5C、10D、159、1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。

A、电子管B、晶体管C、集成电路D、超大规模集成电路10、无论是TCP/IP模型，还是OSI模型，都可视为网络的分层模型，每个网络协议都可以被归为某一层中，如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。

11、矢量图图形文件所占的存储空间较小，并且不论如何放大、缩小或旋转等都不会失真，是因为它（）A、记录了大量像素块的色彩值来表示图像B、用点、直线或多边形等基于数学方程的几何图元来表示图像C、每个像素点的颜色信息均用矢量表示D、把文件保存在互联网，采用在线浏览的方式查看图像12、如果一个栈初识时为空，且当前栈中的元素从栈底到栈顶依次为a、b、c，另有元素d已经出栈，则可能的入栈顺序是（）。

信息学命题（十）A 、二进制码B 、八进制码C 、十进制码D 、智能拼音码2、计算机的软件系统通常分为（A 、硬件系统和软件系统 C 、系统软件和应用软件3、关于软盘读写孔，正确的说法是（ ）。

A .从该孔读信息C.当该孔处于开状态时，不能删除盘中文件。

D .该孔没有作用4、一棵二叉树的中序遍历序列为 DGBAECHF 后序遍历序列为 GDBEHFCA 则前序遍历的序列是（）b5E2RGbCAPA 、ABCDFGHEB 、ABDGCEFHC 、ACBGDHEFD 、ACEFHBGD lEanqFDPw5、下列叙述中错误的是（）。

A.微型计算机应避免置于强磁场之中B •微型计算机使用时间不宜过长，而应隔几个小时关机一次C.微型计算机应避免频繁关开，以延长其使用寿命D.计算机应经常使用，不宜长期闲置不用6、 计算机网络最主要的优点是（ ）。

A 、运算速度快B 、共享资源C 、精度高D 、存储容量大7、 下列4个不同进制表示的数中，最大的一个数是（ ）A 、（220.1）10B 、（11011011.1）2C 、（334.1）8 &为了区分汉字与 ASCII 码，计算机中汉字编码的最高位为（ ）A 、1B 、0C 、-1D 、2 9、下列正确的文件名是（）。

A. comma nd 。

ComB. comma nd_comC. comma nd,comD. comma RTCrpUDGiT10、 .一般来说，TCP/IP 的IP 提供的服务是（ A.运输层服务B.会话层服务 C 表示层服务11、 通信时，模拟信号也可以用数字信道来传输， 5PCzVD7HxAA 、D/AB 、A/DC ModemD 、 Codec12、一个栈的输入顺序为 1、 2、 3、4、5,卜列序列中可能是栈的输出序列是（）A 、 54312B 、 24135C 、 21543D 、 1253413、属于In ternet 的功能是（）A 、聊天B 、远程教育C 、查询资料D 、传送能量14、下列描述计算机病毒的特性中，（）是正确的。

2018年noip普及组第二题1、本文将对2018年noip普及组的第二题进行分析和讨论，探究题目的背景、要求以及解题思路，帮助读者更好地理解和解决这道题目。

2、题目背景2018年noip是全国青少年信息学奥林匹克竞赛，分为普及组和提高组，旨在激发学生对计算机科学和算法设计的兴趣，提高他们的创新能力和复杂问题解决能力。

第二题是普及组的比赛题目之一，要求参赛选手熟练运用基本的算法和数据结构知识，解决一个具体的问题。

3、题目要求2018年noip普及组第二题的要求是：给定一个N* M的地图，每个位置上有一个非负权值，从（1,1）点开始，要求找到一条路径，使得路径上所有点的权值和最大，且路径仅能向右或向下延伸。

要求编写程序，计算出该最大权值和。

4、解题思路解决这道题目需要考察动态规划的思想。

我们可以定义一个二维数组dp，dp[i][j]表示到达位置(i, j)时的最大权值和。

在递推的过程中，可以使用状态转移方程来更新dp数组的数值，即dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]，其中arr[i][j]表示地图上位置(i, j)的权值。

dp[N][M]即为题目所求的最大权值和。

5、结论通过上述分析，我们可以看到2018年noip普及组第二题的解题思路是比较清晰的，借助动态规划算法，可以较为高效地解决这个问题。

这也反映了noip竞赛题目的特点，既考察了基本的算法知识，又需要选手具备一定的分析和推理能力。

希望本文能为读者对该题目有所启发，也希望更多的青少年能参与到这样的计算机科学竞赛中，从中受益并成长。

6、进一步分析在解决2018年noip普及组第二题时，我们不仅需要考虑动态规划的思想，还需要思考如何提高程序的效率。

由于题目要求只能向右或向下延伸路径，并且每个位置上有一个非负权值，因此我们可以利用空间复杂度更低的方法进行优化。

我们可以观察到，对于位置(i, j)，计算最大权值和只需要用到它上方（i-1, j）和左方（i, j-1）的位置的最大权值和。

第1~10题为基础题，第11~20题为提高题，第21~33为综合题注：因为在本文档中需要用到一些特殊的数学符号（如：求和号、分数等），所以当您在百度文库中浏览时，一些数学符号可能会显示不出来，不过当您把本文档下载下来在本地浏览时，所有的符号即可全部都显示出来。

^_^基础题：【1 Prime Frequency】【问题描述】给出一个仅包含字母和数字（0-9, A-Z 以及a-z）的字符串，请您计算频率（字符出现的次数），并仅报告哪些字符的频率是素数。

输入：输入的第一行给出一个整数T( 0<T<201)，表示测试用例个数。

后面的T行每行给出一个测试用例：一个字母-数字组成的字符串。

字符串的长度是小于2001的一个正整数。

输出：对输入的每个测试用例输出一行，给出一个输出序列号，然后给出在输入的字符串中频率是素数的字符。

这些字符按字母升序排列。

所谓“字母升序”意谓按ASCII 值升序排列。

如果没有字符的频率是素数，输出“empty”（没有引号）。

注：试题来源：Bangladesh National Computer Programming Contest在线测试：UV A 10789提示先离线计算出[2‥2200]的素数筛u[]。

然后每输入一个测试串，以ASCLL码为下标统计各字符的频率p[]，并按照ASCLL码递增的顺序（0≤i≤299）输出频率为素数的字符（即u [p[i]]=1且ASCLL码值为i的字符）。

若没有频率为素数的字符，则输出失败信息。

【2 Twin Primes】【问题描述】双素数（Twin Primes）是形式为(p, p+2)，术语“双素数”由Paul Stäckel (1892-1919)给出，前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。

在本题中请你给出第S对双素数，其中S是输入中给出的整数。

2018年全国青少年信息学奥林匹克江西省队选拔赛第一试竞赛时间：8:30–12:00题目名称排序问题游戏守卫目录sort game guard可执行文件名sort game guard输入文件名sort.in game.in guard.in 输出文件名sort.out game.out guard.out 每个测试点时限1s1s1s内存限制512MB512MB512MB测试点数目101010每个测试点分值101010是否有部分分否否否题目类型传统型传统型传统型是否有附加文件是是是提交源程序必须加后缀对于C++语言sort.cpp game.cpp guard.cpp 对于C语言sort.c game.c guard.c 对于Pascal语言sort.pas game.pas guard.pas编译开关对于C++语言-O2-lm-O2-lm-O2-lm 对于C语言-O2-lm-O2-lm-O2-lm 对于Pascal语言-O2-O2-O21排序问题1.1题目描述九条可怜是一个热爱思考的女孩子。

九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法：gobo sort！Gobo sort的算法描述大致如下：• 1.假设我们要对一个大小为n的数列a排序。

• 2.等概率随机生成一个大小为n的排列p。

• 3.构造一个大小为n的数列b满足b i=a p，检查b是否有序，如果b已经有序了就结i束算法，并返回b，不然返回步骤2。

显然这个算法的期望时间复杂度是O(n×n!)的，但是九条可怜惊奇的发现，利用量子的神奇性质，在量子系统中，可以把这个算法的时间复杂度优化到线性。

九条可怜对这个排序算法进行了进一步研究，她发现如果一个序列满足一些性质，那么Gobo sort会很快计算出正确的结果。

为了量化这个速度，她定义Gobo sort的执行轮数是步骤2的执行次数。

于是她就想到了这么一个问题：现在有一个长度为n的序列x，九条可怜会在这个序列后面加入m个元素，每个元素是[l,r]内的正整数。

NOIP2018初赛普及组C++题目+解析二十四届全国青少年信息学奥林匹克联赛初赛——普及组一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机答案:D解析:扫描仪是输出设备显而易见2. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)2答案: D解析：都转成二进制，然后前3个都是1001101001，跟D不同3. 1MB 等于（）。

A. 1000 字节B. 1024 字节C. 1000 X 1000 字节D. 1024 X 1024 字节答案:D解析:1 M B = 1024 K B = 1024 ∗1024 B1MB=1024KB=1024*1024B1MB=1024KB=1024∗1024B 4. 广域网的英文缩写是（）。

B. WANC. MAND. LNA广域网（英语：Wide Area Network，缩写为WAN），又称广域网、外网、公网。

是连围从几十公里到几千公里，它能连接多个地区、城市和国家，或横跨几个洲并能提供远距LAN（Local Area Network (缩写:LAN)）局域网的覆盖范围一般是方圆几千米之内，其具备的安装便捷、成本节约、扩展方便等特点使其在各类办公室内运用广泛。

局域网可以实现全，能够有效地保护资料安全，保证局域网网络能够正常稳定的运行。

答案:B A是局域网C是城域网5. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984D. 1986答案:B6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母（）。

第二十四届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018 年10 月13 日14:30~16:30选手注意：试题纸共有7 页，答题纸共有2 页，满分100 分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机2、下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A.(269)16B.(617)10C.(1151)8D.(1001101011)23、1MB 等于（）。

A.1000 字节B.B. 1024 字节C.1000 X 1000 字节D.D. 1024 X 1024 字节4、广域网的英文缩写是（）。

A. LANB. WANC. MAND. LNA5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 19866、如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母（）。

A. AB. SC. DD. a7、根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。

A.(k h+1- 1) / (k - 1)B.k h-1C.k hD.(k h-1) / (k - 1)8、以下排序算法中，不需要进行关键字比较操作的算法是（）。

A. 基数排序B. 冒泡排序C. 堆排序D. 直接插入排序9、给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要N - 1 次比较操作。