《2018NOIP普及组初赛试题_中学教育-竞赛题.pdf》由会员分享，可在线阅读，更多相关《2018NOIP普及组初赛试题_中学教育-竞赛题.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二十四届全国青少年信息学奥林匹克联赛初赛 普及组 C+语言试题 竞赛时间：2018 年 10 月 13 日 14:3016:30 选手注意：试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在 试题纸上的一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资 料。一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）1、以下哪一种设备属于输出设备：（）A.扫描仪 B.键盘 C.鼠标 D.打印机 2、下列四个不同进制的数中，与其它三项数值上不相等的是（）。A.(269)16 B.(617)10 C.(1151)8
2、 D.(1001101011)2 3、1MB 等于（）。A.1000 字节 B.B.1024 字节 C.1000 X 1000 字节 D.D.1024 X 1024 字节 4、广域网的英文缩写是（）。A.LAN B.WAN C.MAN D.LNA 5、中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。A.1983 B.1984 C.1985 D.1986 6、如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、，屏幕上输出的第
3、81 个字符是字母 欢迎下载 2（）。A.A B.S C.D D.a 7、根节点深度为 0，一棵深度为 h 的满 k（k1）叉树，即除最后一层无任何子 节点外，每一层上的所有结点都有 k 个子结点的树，共有（）个结点。A.(k h+1-1)/(k-1)B.k h-1 C.k h D.(k h-1)/(k-1)8、以下排序算法中，不需要进行关键字比较操作的算法是（）。A.基数排序 B.冒泡排序 C.堆排序 D.直接插入排序 9、给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的 数，至少需要 N-1 次比较操作。则最坏情况下，在该数组中同时找最大与 最小的数至少需要（）次比较
4、操作。（表示向上取整，表示向下取整）A.3N/2-2 B.3N/2-2 C.2N-2 D.2N-4 10、下面的故事与（）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座 山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里 有座庙，庙里有个老和尚给小和尚讲故事”A.枚举 B.递归 C.贪心 D.分治 11、由四个没有区别的点构成的简单无向连通图的个数是（）。A.6 B.7 C.8 D.9 12、设含有 10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T/S 的值为（）。A.5/32 B.15/128 C.1/
5、8 D.21/128 13、10000 以内，与 10000 互质的正整数有（）个。有页满分分请在答题纸上作答写在试题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其中最大或最小的数至少需要
6、次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取整表示向下 欢迎下载 3 A.2000 B.4000 C.6000 D.8000 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 15、下图中所使用的数据结构是（）。压入 A 压入 B 弹出 B 压 A.哈希表 B.栈 C.队列 D.二叉树 二、问题求解（共 2 题，每题 5 分，共计 10 分）1、甲乙
7、丙丁四人在考虑周末要不要外出郊游。已知如果周末下雨，并且乙不去，则甲一定不去；如果乙去，则丁一定 去；如果丙去，则丁一定不去；如果丁不去，而且甲不去，则丙一定不 去。如果周末丙去了，则甲_（去了/没去）(1 分)，乙_（去 了/没去）(1 分)，丁_（去了/没去）(1 分)，周末_（下雨/没下雨）(2 分)。2、从 1 到 2018 这 2018 个数中，共有_个包含数字 8 的数。包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1、#include B A A A C A 有页满分分请在答题纸上作答写在试
8、题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其中最大或最小的数至少需要次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取整表示向下 欢迎下载 4 char
9、st100;int main()scanf(%s,st);f or(int i=0;sti;+i)if(A=sti&sti=Z)sti+=1;printf(%sn,st);r eturn 0;输入：QuanGuoLianSai 输出：_ 2、#include int main()int x;scanf(%d,&x);int res=0;for(int i=0;i x;+i)if(i*i%x=1)+res;printf(%d,res);return 0;输入：15 输出：_ 3、#include using namespace std;int n,m;int findans(int n,int
10、m)有页满分分请在答题纸上作答写在试题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其中最大或最小的数至少需要次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取
11、整表示向下 欢迎下载 5 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 findans(n,m)endl;return 0;输入：5 6 输出：_ 4、#include int n,d100;bool v100;int main()scanf(%d,&n);for(int i=0;i n;+i)scanf(%d,d+i);vi=false;int cnt=0;for(int i=0;i n;+i)if(!vi)for(i
12、nt j=i;!vj;j=dj)vj=true;+cnt;printf(%dn,cnt);return 0;有页满分分请在答题纸上作答写在试题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其
13、中最大或最小的数至少需要次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取整表示向下 欢迎下载 6 输入：10 7 1 4 3 2 5 9 8 0 6 输出：_ 四、完善程序（共 2 题，每题 14 分，共计 28 分）1、（最大公约数之和）下列程序想要求解整数 的所有约数两两之间最大公约 数的和对 10007 求余后的值，试补全程序。（第一空 2 分，其余 3 分）举例来说，4 的所有约数是 1,2,4。1 和 2 的最大公约数为 1；2 和 4 的最大公约 数为 2；1 和 4 的最大公约数为 1。于是答案为 1+2+1=4。要求 getDivisor 函数的
14、复杂度为函数的复杂度为(log max(,)。#include using namespace std;const int N=110000,P=10007;int n;int aN,len;int ans;void getDivisor()len=0;for(int i=1;(1)n;getDivisor();ans=0;for(int i=1;i=len;+i)for(int j=i+1;j=len;+j)ans=(5)%P;cout ans endl;return 0;有页满分分请在答题纸上作答写在试题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题
15、共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其中最大或最小的数至少需要次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取整表示向下 欢迎下载 7 2、对于一个 1 到 的排列（即 1 到 中每一个数在 中出现了恰好一次），令为 第 个位置之后第
16、一个比值更大的位置，如果不存在这样的位置，则 =+1。举例来说，如果 =5 且 为 1 5 4 2 3，则 为 2 6 6 5 6。下列程序读入了排列，使用双向链表求解了答案。试补全程序。（第二空 2 分，其余 3 分）数据范围 1 105。#include using namespace std;const int N=100010;int n;int LN,RN,aN;int main()cin n;for(int i=1;i x;(1);for(int i=1;i=n;+i)Ri=(2);Li=i-1;for(int i=1;i=n;+i)L (3)=Lai;RLai=R (4);for
17、(int i=1;i=n;+i)cout (5);cout endl;return 0;有页满分分请在答题纸上作答写在试题纸上的一律无效不得使用任何电子设备如计算器手机电子词典等或查阅任何书籍资料一单项选择题共题每题分共计分每题有且仅有一个正确选项以下哪一种设备属于输出设备扫描仪键盘鼠标打学会于年创办全国青少年计算机程序设计竞赛如果开始时计算机处于小写输入状态现在有一只小老鼠反复按照字母键字母键字母键字母键的顺序循环按键即屏幕上输出的第个字符是字母根节点深度为一棵深度为的满叉树即除最后一的算法是基数排序冒泡排序堆排序直接插入排序给定一个含个不相同数字的数组在最坏情况下找出其中最大或最小的数至少需要次比较操作则最坏情况下在该数组中同时找最大与最小的数至少需要次比较操作表示向上取整表示向下