NOIP2018-初赛-提高组

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

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

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

一、单项选择题（共10题，每题2分，共计20分；每题有且仅有一个正确选项）1.下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)22.下列属于解释执行的程序设计语言是（）。

A. CB. C++C. PascalD. Python3.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 19864.设根节点深度为0，一棵深度为h的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（）个结点。

A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1) / (k - 1)5.设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n （n为正整数）及T(0) = 1，则该算法的时间复杂度为（）。

A. O(log n)B. O(n log n)C. O(n)D. O(n2)6.表达式a * d - b * c的前缀形式是（）。

A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。

A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58.关于Catalan数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（）。

第二十四届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题竞赛时间：2018 年 10 月 13 日 14:30~16:30(WORD重新整理排版)选手注意：●试题纸共有 9 页，答题纸共有 2 页，满分 100 分。

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

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

一、单项选择题（共 10 题，每题 2 分，共计 20 分；每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（）。

A. CB. C++C. PascalD. Python3. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 19864. 设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。

A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1 ) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（）。

A. O(log n)B. O(n log n)C. O(n)D. O(n2 )6. 表达式 a * d - b * c 的前缀形式是（）。

A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。

A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n!，下列说法中错误的是（）。

第二十四届全国青少年信息学奥林匹克联赛初赛
提高组参考答案
一、单项选择题（共10题，每题2分，共计20分）
1 2 3 4 5 6 7 8 9 10
D D B A D B B A D B
二、不定项选择题（共5题，每题2分，共计10分；每题有一个或多个正确选项，没有部分分）
1 2 3 4 5
AB CD ABD ABD BCD
三、问题求解（共2题，每题5分，共计10分）
1.去了没去没去没下雨（第4空2分，其余1分）
2.454
四、阅读程序写结果（共4题，每题8分，共计32分）
1. 4
2. 6
3.16
4.输出1：2 1 3 5 6 4（3分）输出2：3 2 5 6 1 4（5分）
五、完善程序（共计28分，以下各程序填空可能还有一些等价的写法，由各省赛区组织本省专家审定及上机验证，可以不上报CCF NOI科学委员会复核）
Pascal语言C++语言C语言分值
1 . (1) a[x] := i a[x] = i 3
(2) i + 1 2
(3) R[a[i]] 3
(4) a[i] 3
(5) R[i] 3 2
2 . (1) a[i] * 0.95 <= b[i] 或b[i] >= a[i] * 0.95 2
(2)
total_a >= threshold 或threshold <= total_a 或total_a >= 50000 或50000 <=
total_a
3
(3) total_a + j + a[i] 3
(4) f[j] + total_b - total_b_prefix 3
(5) f[j - a[i]] 3。

2018年第二十四届全国青少年信息学奥林匹克联赛（NOIP 2018）广东赛区成绩公告2018年第二十四届全国青少年信息学奥林匹克联赛（NOIP 2018）广东赛区初赛实际参加人数为5201人（其中提高组1984人，普及组3217人），参赛学校337所。

复赛实际参赛人数为1469人（提高组647人，普及组822人）, 有资格参加复赛的学校有139所。

本届参赛选手程序全部由全国统一测评，其中提高组一等奖按分配名额划线，结果提高组317名同学（含初二21人，初三52人）获联赛一等奖。

今届广东省获提高组联赛一等奖分数线高出全国基准分数线65分，分数线在全国排第五，获奖人数在全国排第二，表明广东省信息学竞赛不仅普及面而且尖子层人数也在全国前列。

35年的实践表明，GDOI（广东省青少年信息学（计算机）奥林匹克竞赛活动）是培养我们国家、我省计算机优秀后备人才的成功之路。

今年提高组一、二、三等奖及普及组一、二、三等奖均由全国划定基准分数线及获奖比例，最后确认：提高组一、二、三等奖分数线分别为310、160、120，普及组一、二、三等奖分数线分别为215、100、70。

今年全国提高组一等奖分数线按初、复参赛人数及平均分计算，各省分数线差别很大，广东一等奖奖项大幅度地高于全国的基准分数线，同时，广东提高组平均分在296分以上，高于全国21个省的一等奖分数线。

按照广东省信息学竞赛评委会制定的评估方法，综合测评省内各校在开展计算机教学和科技活动中取得的成绩，从全省参加复赛的学校中评出成绩优异的前60所学校，其中校团体一等奖10所，二等奖20所，三等奖30所。

在个人奖方面，NOIP2018广东赛区复赛分数线按照中国计算机学会规定划定一、二、三等奖，边界同分同奖的规则。

获奖统计情况如下表所列：参赛人数省一等省二等省三等获奖总数提高647317人（占49%）234人（占36.17%）32人（占4.95%）583人（占90.11%）普及822214人（占26.03%）544人(占66.18%）10人(占1.22%）768人（占93.43%）总数1469531人（占36.15%）778人（占52.96%）42人（占2.86%）1351人（占91.97%）其中，提高组获奖人数（583人）占复赛90.11%，普及组获奖人数（768人）占复赛93.43%，全省获奖人数（1351人）占复赛总人数91.97%。

CCF全国信息学奥林匹克联赛（NOIP2018）复赛提高组 day2（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存32GB。

上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。

1．旅行(travel.cpp/c/pas)【问题描述】小Y是一个爱好旅行的OIer。

她来到X国，打算将各个城市都玩一遍。

小Y了解到，X国的 n 个城市之间有 m 条双向道路。

每条双向道路连接两个城市。

不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。

并且，从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。

小Y只能通过这些道路从一个城市前往另一个城市。

小Y的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。

当小Y回到起点时，她可以选择结束这次旅行或继续旅行。

需要注意的是，小Y要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小Y决定在每到达一个新的城市（包括起点）时，将它的编号记录下来。

她知道这样会形成一个长度为 n 的序列。

她希望这个序列的字典序最小，你能帮帮她吗？对于两个长度均为 n 的序列A和B，当且仅当存在一个正整数x，满足以下条件时，我们说序列A的字典序小于B。

⚫对于任意正整数1≤i<x，序列A的第i个元素A i和序列B的第i个元素B i相同。

⚫序列A的第x个元素的值小于序列B的第x个元素的值。

NOIP2018 解题报告师大学附属中学天2018/11/21（此前题目填数游戏算法五部分出现笔误，已更正由于公式编辑器问题，部分数学公式可能无常显示Day 1铺设道路road标签：贪心简化版题意：给定一个非负整数序列，每次操作可选择一段区间使其中的数全部减，求全部减为需要的最少操作次数。

这题做法有很多……主流大概这么几种：算法一：考场上怎么简单粗暴怎么来每次找到最小值然后分治，不交并总数是的时间复杂度，空间复杂度算法二单调栈：头铁就是要写线性和算法一差不多，只不过使用了单调栈维护时间复杂度/空间复杂度算法三差分完正项的和就是答案。

时间复杂度，空间复杂度作为一道送分题，算法三应该是比较正常的思路然而场上甚至有人写了线段树，不知道是不是现在的选手数据结构有点学傻了……货币系统money标签：贪心，dp，背包简化版题意：给定个不同的正整数，求最少需要几个正整数，使得与这个整数在非负整数权线性组合下等价。

这题也很显然吧……首先给出的整数本身肯定是能被表示出来的，因此超过最大值的不用管，因为简化后肯定能用这些整数表示出来。

然后从小到大考虑每个整数是否能被原系统表示，如果不能就不管，如果能但可以被之前加入的更小的数表示也不管，否则就将其加入答案。

贪心的正确性是显然的，因为小于可被原系统表示的最小整数的数必然不能选，而该最小整数如果无法被此前选的数表示，就必须选。

考虑完该数后，将递归地得到一个子问题。

实现也很简单，就是一个裸的完全背包。

在具体实现上的分歧给出了三种算法：算法一老老实实跑完全背包时间复杂度，空间复杂度算法二考虑值只有，可以利用压位加速转移，不过每次直接重复移位多遍效率很低，可以再考虑二进制分组，即每次分别移位后与或原状态取或。

时间复杂度（取决于压位用或手写）空间复杂度这两种算法复杂度看上去比较极限，实际上并不会跑满，加之今年评测机性能极其优秀，完全没有压力。

**进阶算法**背包问题本质上是卷积，可以使用多项式理论对其进行优化。

第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共 10 题，每题 1.5 分，共计 15 分。

每题有且仅有一个正确选项）1.与十六进制数A1. 2等值的十进制数是（）。

A．101.2 B. 111.4 C. 161.125 D. 177.252.一个字节（byte）由（）个二进制位组成。

A.8B. 16C. 32D. 以上都有可能3.以下逻辑表达式的值恒为真的是（）。

A. P∨ (﹁P∧ Q)∨ (﹁P∧﹁Q)B. Q∨ (﹁P∧ Q)∨ (P∧﹁Q)C. P∨ Q∨ (P∧﹁Q)∨ (﹁P∧ Q)D. P∨﹁Q∨ (P∧﹁Q)∨ (﹁P∧﹁Q)4.Linux下可执行文件的默认扩展名为（）。

A. exeB. comC. dllD. 以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=( )也成立。

A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。

A. 克劳德·香农B. 戈登·摩尔C. 查尔斯·巴比奇D. 冯·诺伊曼7.前缀表达式“+3 * 2 +5 12”的值是（）。

A. 23B. 25C. 37D. 658.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了（）。

A. 寄存器B. 高速缓存C. 闪存D. 外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右，依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在话，应当存放在数组的（）号位置。

A. 2kB. 2k+1C. k/2下取整D. (k+1)/2下取整10.以下竞赛活动中历史最悠久的是（）。

每个顶点用1个加号’+’表示，长用3个”-“表示，宽用1个”/”表示，高用两个”|”表示。

字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为43，45，47，124。

字符’.’（ASCII码46）需要作为背景输出，即立体图里的空白部分需要用’.’代替。

立体图的画法如下面的规则：若两块积木左右相邻，图示为：
..+---+---+
./ / /|
+---+---+ |
| | | +
| | |/.
+---+---+..
若两块积木上下相邻，图示为：
..+---+
./ /|
+---+ |
| | +
| |/|
+---+ |
| | +
| |/.
+---+..
若两块积木前后相邻，图示为：
….+---+
…/ /|
..+---+ |
./ /| +
+---+ |/.
| | +..
| |/…
+---+….
立体图中，定义位于第(m,1)的格子（即第m行第1列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。

【输入】
输入文件drawing.in第一行有用空格隔开的两个整数m和n，表示有m*n个格子
（1<=m，n<=50）。

接下来的m行，是一个m*n的矩阵，每行有n个用空格隔开的整数，其中第i行第j 列上的整数表示第i行第j列的格子上摞有多少个积木（1<=每个格子上的积木数<=100）。

【输出】
输出文件drawing.out中包含题目要求的立体图，是一个K行L列的字符矩阵，其中
K和L表示最少需要K行L列才能按规定输出立体图。

关于第二十四届全国青少年信息学(计算机)奥林匹克联赛（NOIP2018）获奖情况的通报各镇（街）宣教办（局），松山湖科教局，各中小学，市青少年活动中心：第二十四届全国青少年信息学（计算机）奥林匹克联赛（NOIP2018）顺利结束。

根据全国和省学科竞赛委员会统一划定的获奖分数线，我市学生在高手如林的竞赛中，再创佳绩：获全国一等奖51人、全国二等奖140人、全国三等奖8人，一等奖人数比2017年增加7人，获全国一等奖人数列全省第四名。

根据全国和省组委会划定的初赛和复赛的评奖分数线，本次活动评出了市学校团体奖、市学生个人奖和优秀辅导教师若干名。

现给予通报表彰，并颁发获奖证书以资奖励。

希望获奖的学校和个人戒骄戒躁，再接再厉，进一步提高学习和训练水平，争取在今后的竞赛中取得更好成绩。

也希望其他学校向他们学习，积极开展信息技术教育，大力开展中学生普及计算机基础知识活动，为培养更多的计算机科学与工程领域后备人才作出新的更大的贡献。

附件：第二十四届全国青少年信息学奥林匹克联赛（NOIP2018）获奖名单一、团体奖一等奖东莞市东莞中学松山湖学校、东莞市东华高级中学、东莞市东莞中学、东莞外国语学校、东莞市东华初级中学、东莞市东莞中学南城学校、东莞市东莞中学初中部、东莞市新世纪英才学校二等奖东莞市第一中学、东莞市石龙中学、东莞市莞城少年宫、东莞市可园中学、东莞市望牛墩中学、东莞市石龙第二中学、东莞市石龙第三中学、东莞市南城阳光实验中学、东莞市松山湖实验中学、东莞市东城第一中学三等奖东莞市第六高级中学、东莞市塘厦初级中学、东莞市常平镇振兴中学、东莞市中堂中学、东莞市万江第三中学二、个人奖名单2.提高组获全国一、二、三等奖4、提高组获市一、二、三等奖名单5.优秀辅导教师奖。

NoipXX初赛提高组C试题及答案（完整版）Noipxx初赛提高组试题及答案（完整版）提高组C语言试题一、单项选择题（每题1.5分，共22.5分）。

1. 以下哪个是面向对象的高级语言( ). A. 汇编语言 B. C++ C. FORTRAN D. Basic2. 1TB代表的字节数量是( ). A. 2的10次方B. 2的20次方 C. 2的30次方 D. 2的40次方3. 二进制数00100100和00010101的和是( ). A. 00101000 B. 001010100 C. 01000101 D. 001110014. TCP协议属于哪一层协议( ). A. 应用层 B. 传输层 C. 网络层 D. 数据链路层 5. 以下几个32位IP地址中，书写错误的选项是( ). A. 162.105.128.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.1 6. 在无向图中，所有定点的度数之和是边数的( )倍. A. 0.5 B. 1 C. 2 D. 4 7. 对长度位n的有序单链表，假设检索每个元素的概率相等，那么顺序检索到表中任一元素的平均检索长度为( ). A. n/2 B. (n+1)/2 C. (n-1)/2 D.n/4 8. 编译器的主要功能是( ). A. 将一种高级语言翻译成另一种高级语言 B. 将源程序翻译成指令 C. 将低级语言翻译成高级语言D. 将源程序重新组合 9. 二进制数111.101所对应的十进制数是( ). A. 5.625 B. 5.5 C. 6.125 D. 7.625 10. 假设有变量 int a, float x, y, 且 a=7, x=2.5, y=4.7, 那么表达式x+a%3*(int)(x+y)%2/4的值大约是( ). A. 2.500000 B. 2.750000 C. 3.500000 D. 0.000000 11. 有以下结构体说明和变量定义，如下图，指针p、q、r分别指向一个链表中的三个续结点。

第二十四届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题竞赛时间：2018 年 10 月 13 日 14:30~16:30(WORD重新整理排版)选手注意：●试题纸共有 9 页，答题纸共有 2 页，满分 100 分。

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

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

一、单项选择题（共 10 题，每题 2 分，共计 20 分；每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（）。

A. CB. C++C. PascalD. Python3. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 19864. 设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。

A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1 ) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则该算法的时间复杂度为（）。

A. O(log n)B. O(n log n)C. O(n)D. O(n2 )6. 表达式 a * d - b * c 的前缀形式是（）。

A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。

A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n!，下列说法中错误的是（）。

第二十三届全国青少年信息学奥林匹克联赛初赛提高组 PASCAL语言模拟试题竞赛时间：2017年 10 月 14 日 14:30~16:30选手注意:●试题纸共有 13 页，答题纸共有 2 页，满分 100 分。

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

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

一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）1．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain），以表彰他们对半导体的研究和晶体管效应的发现。

A. 诺贝尔物理学奖B. 约翰·冯·诺依曼奖C. 图灵奖D. 高德纳奖（DonaldE. Knuth Prize）2.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S 和字母键 D 的顺序来回按键，即 CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……，屏幕上输出的第 81 个字符是字母（）。

Ａ. A Ｂ. S Ｃ. D Ｄ. A3.二进制数 00101100 和 01010101 异或的结果是（）。

Ａ. 00101000 Ｂ. 01111001 Ｃ. 01000100 Ｄ. 001110004.与二进制小数 0.1 相等的八进进制数是（）。

Ａ. 0.8 Ｂ. 0.4 Ｃ. 0.2 Ｄ.0.15.以比较作为基本运算，在 N 个数中找最小数的最少运算次数为（）。

Ａ. N Ｂ. N-1 Ｃ. N2 Ｄ. log N6.表达式 a*(b+c)-d 的后缀表达形式为（）。

Ａ. abcd*+- Ｂ. abc+*d- Ｃ. abc*+d- Ｄ. -+*abcd7.一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。