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.(
2、1151)8 D.(1001101011)2 3.1MB 等于（） 。 A.1000 字节B.1024 字节 C. 1000 X 1000 字节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、
3、 A、S、D、F、，屏幕上输出的第81 个字符是字母 （） 。 A.AB. SC.DD.a 7.根节点深度为0，一棵深度为h 的满k（k1）叉树，即除最后一层无任何子节点 外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。 A.(k h+1-1) / (k -1) h-1 B.k h C.k 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 个元素组成的子集
5、数为 T，则T/ S 的值为（） 。 A.5/ 32 B.15 /128 C.1 / 8 D.21 / 128 13. 10000 以内，与 10000 互质的正整数有（）个。 A.2000 B.4000 C.6000 D.8000 14.为了统计 一 个 非 负整数的二进制形式中1 的个数，代码如下：intCountBit(int x) int ret= 0;while(x) ret+; _; returnret; 则空格内要填入的语句是（） 。 A.x=1 B.xintmain() scanf(%s,st);for (inti=0;sti;+i) if(A =sti printf(%sn,
6、st);return0; 输入：QuanGuoLianSai 输出：_ 2.#include int main() intx; scanf(%d, int res =0; for (int i =0; i x;+i) if(i * i %x = 1) +res; printf(%d,res); return0; 输入：15 输出：_ 3.#includeusing namespace std;int n, m; intfindans(intn, intm) if(n = 0) returnm;if(m= 0) return n% 3; returnfindans(n -1,m) -findan
7、s(n, m -1)+ findans(n -1, m -1); intmain()cin nm;cout findans(n,m) endl; return0; 输入：56输出：_ 4. #includeintn,d100;bool v100; int main() scanf(%d, for(inti=0;in;+i) scanf(%d,d +i);vi= false; intcnt = 0; for(inti = 0; i n; +i)if(!vi) for (int j= i;!vj;j =dj) vj = true; +cnt; printf(%dn,cnt); return 0;
8、输入：10 71 43 25 98 06 输出：_ 四、完善程序（共 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 函数的复杂度为函数的复杂度为(log max(, )。 #includeusing namespace std; const intN
9、 = 110000, P = 10007; intn;intaN, len; intans; voidgetDivisor()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;return0; 2.对于一个 1 到 的排列（即 1 到 中每一个数在中出现了恰好一次），令为 第 个 位置之后第一个比值更大的位置，如果不存在这样 的 位 置 ， 则=+1。举例来 说 ， 如 果=5
10、且为15 4 23，则为2 66 56。 下列程序读入了排列，使用双向链表求解了答案。试补 全 程 序 。（第二空2 分，其 余 3 分） 数据范围1 105。 #includeusingnamespace std;const intN = 100010; intn;intLN,RN,aN; intmain() cinn; for(int i = 1; ix; (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(int i = 1; i=n; +i) cout (5) ; cout endl; return0;
