NOIP2018普及组初赛题解 | 您所在的位置:网站首页 › 全国信息学奥林匹克联赛真题 › NOIP2018普及组初赛题解 |
第24届全国青少年信息学奥林匹克联赛初赛 普及组C++语言试题 竞赛时间:2018 年 10 月 13 日 14:30~16:30 选手注意: 1、试题纸共有 7 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上的一律无效。 2、不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项) 1. 以下哪一种设备属于输出设备:( ) A.扫描仪 B.键盘 C.鼠标 D.打印机 解析:D,其他三项都属于输入设备。 扩展: 输入设备(Input Device )是把数据、指令及某些标志信息等输送到计算机中去。键盘、鼠标、摄像头、扫描仪、光笔、手写输入板、游戏杆、语音输入装置等都属于输入设备。 输出设备(Output Device)是把计算或处理的结果或中间结果以人能识别的各种形式,如数字、符号、字母等表示出来,因此输入输出设备起了人与机器之间进行联系的作用。常见的有显示器、打印机、绘图仪、影像输出系统、语音输出系统、磁记录设备等。 控制台打字机、光笔、显示器等既可作输入设备、也可作输出设备。 2. 下列四个不同进制的数中,与其它三项数值上不相等的是( )。 A. (269)16 B. (617)10 C. (1151)8 D. (1001101011)2 解析:D A选项:2 * 16^2 + 6 * 16^1 + 9 * 16 ^0 = 617 C选项:1 * 8^3 + 1 * 8^2 + 5 * 8^1 + 1 * 8^0 = 617 D选项:1*2^9+1*2^6+1*2^5+1*2^3+1*2^1+1^0=621 扩展: 进制也就是进制位,对于接触过电脑的人来说应该都不陌生,我们常用的进制包括:二进制、八进制、十进制与十六进制,它们之间区别在于数运算时是逢几进一位。比如二进制是逢2进一位,十进制也就是我们常用的0-9是逢10进一位。 进制转换总结: 1)十进制转二进制 方法为:十进制数除2取余法,即十进制数除2,余数为权位上的数,得到的商值继续除2,依此步骤继续向下运算直到商为0为止。(除2取余倒序法) 2)二进制转十进制 方法为:把二进制数按权展开、相加即得十进制数。 例如:10010110 = 1*27+0*26+0*25+1*24+0*23+1*22+1*21+0*20=150 3)二进制转八进制 方法为:3位二进制数按权展开相加得到1位八进制数。(注意事项,3位二进制转成八进制是从右到左开始转换,不足时补0)。 例如:10010110 = 010 010 110 = 226 4)八进制转成二进制 方法为:八进制数通过除2取余法,得到二进制数,对每个八进制为3个二进制,不足时在最左边补零。 5)二进制转十六进制 方法为:与二进制转八进制方法近似,八进制是取三合一,十六进制是取四合一。(注意事项,4位二进制转成十六进制是从右到左开始转换,不足时补0)。 6)十六进制转二进制 方法为:十六进制数通过除2取余法,得到二进制数,对每个十六进制为4个二进制,不足时在最左边补零。 7)十进制转八进制或者十六进制有两种方法 第一:间接法—把十进制转成二进制,然后再由二进制转成八进制或者十六进制。 第二:直接法—把十进制转八进制或者十六进制按照除8或者16取余,直到商为0为止。 8)八进制或者十六进制转成十进制 方法为:把八进制、十六进制数按权展开、相加即得十进制数。 9)八进制与十六进制之间的转换有两种方法 第一种:他们之间的转换可以先转成二进制然后再相互转换。 第二种:他们之间的转换可以先转成十进制然后再相互转换。 3. 1MB等于( )。 A. 1000 字节 B. 1024 字节 C. 1000 X 1000字节 D. 1024 X 1024字节 解析:D 1TB等于1024GB; 1GB等于1024MB; 1MB等于1024KB; 1KB等于1024Byte(字节); 1Byte等于8bit(位); 4. 广域网的英文缩写是( )。 A. LAN B. WAN (Wide Area Network) C. MAN D.LNA 解析:B 局域网(Local Area Network)英文缩写:LAN。通常只范围在几百米到几十千米的网络。城域网(Metropolitan Area Network)简称MAN。是在一个城市范围内所建立的计算机通信网。广域网(Wide Area Network)英文缩写:WAN。通常跨接很大范围如一个国家。 5. 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。 A. 1983 B. 1984 C. 1985 D. 1986 解析:B 1984年邓小平指出:“计算机的普及要从娃娃做起。”中国计算机学会于1984年创办全国青少年计算机程序设计竞赛(简称:NOI),当年参加竞赛的有8000多人。竞赛旨在向中学阶段学习的青少年普及计算机科学知识;给学校的信息技术教育课程提供动力和新的思路;给有才华的学生提供相互交流和学习的机会;通过竞赛和相关的活动培养和选拔优秀计算机人才。 6. 如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键S、字母键 D、字母键 F 的顺序循环按键,即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、......,屏幕上输出的第 81 个字符是字母 ( )。 A. A B. S C. D D. A 解析:A ASDFasdf八个字符一循环,81/8=10......1,所以是第一个字符。 7. 根节点深度为 0,一棵深度为 h 的满 k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有k个子结点的树,共有( )个结点。 A. (kh+1-1)/(k-1) B. kh-1 C. k h D. (kh-1) / (k - 1) 解析:A S=k0+k1+k2+k3+k4+....+kh-1+kh kS=k1+k2+k3+k4+....+kh-1+kh+kh+1=(S-1)+kh+1 (k-1)S = kh+1-1 S=(kh+1-1)/(k-1) 8. 以下排序算法中,不需要进行关键字比较操作的算法是( )。 A. 基数排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序 解析:A 基数排序,属于“分配式排序”,又称“桶子法”或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些桶中,藉以达到排序的作用。 冒泡排序,它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 堆排序,是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。 直接插入排序,基本思想是:当插入第i(i >= 1)时,前面的V[0],V[1],……,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的元素向后顺移。 9. 给定一个含 N 个不相同数字的数组,在最坏情况下,找出其中最大或最小的数,至少需要 N - 1 次比较操作。则最坏情况下,在该数组中同时找最大与最小的数至少需要( )次比较操作。(⌈ ⌉表示向上取整,⌊ ⌋表示向下取整) A. ⌈3N / 2⌉ - 2 B. ⌊3N / 2⌋ - 2 C. 2N - 2 D. 2N - 4 解析:A 如果分别找最大值、最小值,则至少都需要N-1次操作。 同时找最大最小值,按照下面的优化算法: 初始值: N为奇数,最大值、最小值的初始值都设为第一个元素。 N为偶数,将前两个元素比较,最大值初始值为大的元素,最小值初始值为小的元素。 枚举,每次两个元素(循环步长为2) 比较两个元素,分出大小。 大的元素与最大值比较,比最大值大则设为该元素。 小的元素与最小值比较,比最小值小则设为该元素。 循环结束,得到最大、最小值。 N为奇数时,比较次数为3*(N-1)/2 =(3N+1)/2 - 2 N为偶数时,比较次数为1 +3*(N-2)/2 = 3N/2 – 2 综合奇偶,显然答案为A。 10. 下面的故事与( )算法有着异曲同工之妙。从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事......’” A. 枚举 B. 递归 C. 贪心 D. 分治 解析:B 枚举:把所有元素一个一个拿出来进行操作。 递归:自己调用自己。 贪心:总是做出在当前看来是最好的选择。 分治:将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。 11. 由四个没有区别的点构成的简单无向连通图的个数是( )。 A. 6 B. 7 C. 8 D.9 解析:A 1) 四个区别的点,意味着以下的图形为相同形状。 用d=[1, 2, 2,1]表示对应点的度,则以上的图的d数组都是一样的。 2)而以下的图形则是不同的另外一个形状,其d=[1, 3, 1, 1]。 题目要求,实际就是找出不同的d数组的个数。 3)根据边数来分类判断: 小于3条边,不构成连通,排除掉。 3条边:d=[1, 2, 2, 1]和[1, 3,1,1]两种 4条边:d=[2,2,2,2]和[1,3,2,2]两种 5条边:d=[2,2,3,3]一种 6条边:d=[3,3,3,3]一种 一共6种不同的图形,答案是A。 12. 设含有 10 个元素的集合的全部子集数为 S,其中由 7 个元素组成的子集数为T,则T / S的值为( )。 A. 5 / 32 B. 15 / 128 C. 1 / 8 D. 21 / 128 解析:B 因为含有10个元素的集合的全部子集数为210=1024,又因为其中由7个元素组成的子集数为120。 则: 13. 10000以内,与10000互质的正整数有( )个。 A. 2000 B. 4000 C. 6000 D. 8000 解析:B 互质的意思,与10000没有公约数,也即不能被10000的质因子整除。 10000=104=24×54,10000÷2=5000,10000以内有质因数2的数有5000个,10000÷5=2000,10000以内有质因数5的数有2000个,10000÷10=1000,同时有质因数2和5的数有1000个, 5000 +2000 – 1000 =6000,被2或5整除的数有6000个,互质的数有:10000 - 6000 = 4000个。 14. 为了统计一个非负整数的二进制形式中 1 的个数,代码如下: int CountBit(int x) { int ret = 0; while (x) { ret++; ___________; } return ret; } 则空格内要填入的语句是( )。 A. x >>= 1 B. x &= x - 1 C. x |= x >> 1 D. x =1等价于x=x>>1 如果知道x = x&(x-1)是二进制从后往前去掉1个1的话,答案B自然知道。 如果不知道的话,就自己模拟一下吧,比如用一个数5=(101)2 A选项模拟,结果为3(101,10,1,0) B选项模拟,结果为2(101,100,0) C选项模拟,死循环 D选项模拟,死循环 15. 下图中所使用的数据结构是( )。 A. 哈希表 B. 栈 C. 队列 D. 二叉树 解析:B 先入后出,栈的性质 先入先出,队列 二、问题求解(共 2 题,每题 5 分,共计 10 分) 1. 甲乙丙丁四人在考虑周末要不要外出郊游。已知1如果周末下雨,并且乙不去,则甲一定不去;2如果乙去,则丁一定去;3如果丙去,则丁一定不去;4如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲_____ (去了/没去)(1 分),乙_____(去了/没去)(1 分),丁_____(去了/没去)(1 分),周末______(下雨/ 没下雨)(2 分)。 解析: 首先,丙是要去的。 那么根据(4)可以得知丁、甲中一定有一个或两个去。 而又根据(3)可以得知丁不去,所以甲去。 又根据(2),因为前面已经提到:丁不去。所以证明乙也不去。 最后根据(1)得知,周末一定不下雨,如果下雨,那么甲也不去,就和之前的矛盾了。 所以答案: 甲(去了) 乙(没去) 丁(没去) 周末(没下雨) 2. 从 1 到 2018 这 2018 个数中,共有_____个包含数字 8 的数。 解析: 包含数字 8 的数是指有某一位是“8”的数,例如“2018”与“188”。 100内:个位是8,十位是8:共:10+9=19 每1到100一百个数字里有19个,80到89是10个,在加上8、18、28到98的9个(因为80到89中的88算过了,所以要去掉一个) 2000里面有20个一百,再去掉800到899和1800到1899这两个整百,最后再加上2008和2018这两个, 综合列式是200+19×18+2=200+342+2=544一共有544个含8的数。 三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. #include char st[100]; int main() { scanf('%s', st); for (int i = 0; st[i]; ++i) { if ('A' if (i * i % x == 1) { ++res; } } printf('%d', res); return 0; } 输入:15 输出:4 3. #include using namespace std; int n, m; int findans(int n, int m) { if (n == 0) return m; if (m == 0) return n % 3; return findans(n - 1, m) - findans(n, m - 1) +findans(n - 1, m - 1); } int main(){ cin >> n >> m; cout scanf('%d', d + i); v[i] = false; } int cnt = 0; for (int i = 0; i < n; ++i) { if (!v[i]) { for (int j = i; !v[j]; j = d[j]) { v[j] = true; } ++cnt; } } printf('%d\n', cnt); return 0; } 输入:10 7 1 4 3 2 5 9 8 0 6 输出:6 四、完善程序(共 2 题,每题 14 分,共计 28 分) 1. (最大公约数之和)下列程序想要求解整数 举例来说,4的所有约数是1,2,4。1和2的最大公约数为1;2和4的最大公约数为2;1和4的最大公约数为1。于是答案为1 + 2 + 1 = 4。 要求 getDivisor 函数的复杂度为0(√n),gcd 函数的复杂度为O(log max(a, b))。 #include using namespace std; const int N =110000, P = 10007; int n; int a[N], len; int ans; //计算出所有公约数,并存储在a数组中 void getDivisor(){ len = 0; for(int i=1; i * i if (b == 0) { return a ; } return gcd(b, a % b ); } int main() { cin >> n; getDivisor(); ans = 0; for (int i = 1; i ans=( ans + gcd(a[i], a[j]) )%P; } } cout int x; cin >> x; a[x] = i ; } for (int i = 1; i L[ R[a[i]] ]= L[a[i]]; R[L[a[i]]] = R[ a[i] ]; } for (int i = 1; i |
CopyRight 2018-2019 实验室设备网 版权所有 |