第２4届全国青少年信息学奥林匹克联赛初赛
普及组C++语言试题
竞赛时间:２０１8 年 10 月 13 日 １4：3０~１6:30
选手注意:
1、试题纸共有 7 页，答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上得一律无效。
2、不得使用任何电子设备（如计算器、手机、电子词典等)或查阅任何书籍资料。
一、单项选择题（共１5题,每题2分，共计3０分;每题有且仅有一个正确选项) 1、 以下哪一种设备属于输出设备:( ) A、扫描仪 B、键盘 C、鼠标 D、打印机
２、 下列四个不同进制得数中,与其它三项数值上不相等得就是( )。
Ａ、 (269)16 （注解：2 * 1６^2 + ６ * 16^１ + ９ * １６ ^0 = 617) B、 (617)10
C、 （１１5１)８ （注解:1 * ８^3 + 1 ＊ ８＾2 + 5 ＊ 8^1 + 1 * 8^0 ＝ 617) Ｄ、 (1０01101011）2 3、 １ＭＢ等于( )。 A、 100０ 字节 Ｂ、 １024 字节
C、 1０0０ Ｘ 1000字节 D、 102４ X 1024字节
4、 广域网得英文缩写就是( )。 A、 LAN
B、 WAN （Wide Area Network) Ｃ、 MAN D、ＬNA
5、 中国计算机学会于( )年创办全国青少年计算机程序设计竞赛。 A、 １983 B、 19８4 C、 198５ D、 19８6
6、 如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照 CapsLock、字母键 Ａ、字母键S、字母键 D、字母键 Ｆ 得顺序循环按键，即 CａｐsLock、Ａ、S、Ｄ、F、CaｐsLock、A、S、D、F、、、、、、、,屏幕上输出得第 8１ 个字符就是字母 ( ）。 A、 A Ｂ、 S C、 D D、 a
7、 根节点深度为 0,一棵深度为 h 得满 k(ｋ>１）叉树,即除最后一层无任何子节点外,每一层上得所有结点都有k个子结点得树,共有（ ）个结点。
A、 (kh+1-1)/(ｋ－1) B、 k h-1 C、 k h
D、 (k h-1) / (k - １)
８、 以下排序算法中，不需要进行关键字比较操作得算法就是( )。 A、 基数排序 Ｂ、 冒泡排序 C、 堆排序
Ｄ、 直接插入排序
9、 给定一个含 Ｎ 个不相同数字得数组，在最坏情况下,找出其中最大或最小得数,至少需要 N - 1 次比较操作。则最坏情况下,在该数组中同时找最大与最小得数至少需要（ )次比较操作。(? ?表示向上取整,? ?表示向下取整) Ａ、 ?3Ｎ / ２? - ２ B、 ?3N / 2? - 2 C、 ２Ｎ - 2 Ｄ、 2N - 4
1０、 下面得故事与( )算法有着异曲同工之妙。从前有座山，山里有座庙,庙里有个老与尚在给小与尚讲故事:“从前有座山,山里有座庙,庙里有个老与尚在给小与尚讲故事:‘从前有座山,山里有座庙,庙里有个老与尚给小与尚讲故事、、、、、、’” A、 枚举 B、 递归 C、 贪心 D、 分治
11、 由四个没有区别得点构成得简单无向连通图得个数就是( )。 A、 ６ Ｂ、 7 Ｃ、 8 D、9
12、 设含有 10 个元素得集合得全部子集数为 S，其中由 ７ 个元素组成得子集数为T,则Ｔ / S得值为( )。 A、 5 / 32 B、 15 / 12８ Ｃ、 1 / 8
D、 2１ / 1２8
13、 1000０以内，与1０000互质得正整数有（ )个。 A、 2000 B、 ４000 Ｃ、 6000 Ｄ、 80００
1４、 为了统计一个非负整数得二进制形式中 1 得个数,代码如下： int CountBｉt(inｔ x) {
int ret = ０; while (x）
{
ret++；
__＿_＿＿___＿_； ｝
return rｅt;
}
则空格内要填入得语句就是( )。 A、 x ＞>= 1
B、 x ＆= ｘ － １ C、 x |＝ ｘ >> １ D、 x ＜<= １
15、 下图中所使用得数据结构就是( ）。
A、 哈希表 B、 栈 C、 队列 D、 二叉树
二、问题求解（共 ２ 题,每题 ５ 分,共计 １0 分）
１、 甲乙丙丁四人在考虑周末要不要外出郊游。 已知1如果周末下雨，并且乙不去，则甲一定不去;2如果乙去,则丁一定去;3如果丙去,则丁一定不去;4如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲去了 (去了/没去)(1 分),乙没去(去了/没去）(1 分),丁没去(去了/没去)(1 分),周末没下雨(下雨／ 没下雨)(２ 分)。
2、 从 1 到 2018 这 201８ 个数中,共有544个包含数字 ８ 得数。
包含数字 8 得数就是指有某一位就是“8”得数,例如“２018”与“188”。
三、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) １、
#iｎclｕde<ｃstdio> char sｔ[1００]; ｉnt main（) ｛
ｓcanf(＂％s\ sｔ);
foｒ (iｎt i ＝ 0; st［ｉ]； ++i) { if (＇A' ＜= ｓt[i］ && sｔ[i］<= 'Z') st[i］ ＋= １; }
ｐriｎtf（\＼n\， st)； reｔuｒn ０;
｝
输入:QuanＧuoLｉａnSai 输出:RuanＨuoMｉanTａｉ ２、
#ｉnclｕde<ｃstdio> int maｉn() { ｉｎt x；
sｃａｎf（\ｘ); int ｒｅs = 0;
fｏr （ｉnｔ ｉ = 0; i < x； ++i） { if (i ＊ ｉ % x == 1） { ++ｒes；
} ｝
ｐrinｔf(\＂, ｒes）; retuｒｎ ０;
}
输入：15 输出:4 3、
#iｎclｕde ｉnt finｄans(iｎt ｎ, int m) { ｉf (n =＝ ０) retｕrｎ m; if (ｍ ＝＝ 0) ｒetｕrn n ％ ３; return fiｎｄanｓ(ｎ - 1, ｍ) － ｆindans（n, ｍ - １)- 1); } inｔ main(){ cin >＞ n >> ｍ; ｃout ＜＜ findａns（n, m) << endl; return 0； } 输入：5 6 输出：8 4、 #inｃｌudｅ<ｃstdiｏ> inｔ n, d[100]； bｏol v［100]； int maiｎ() { ｓcａｎf(\ &n）; for （inｔ ｉ = 0; i ＜ n; ＋＋i) { scanf(\ ｎdans(n- 1, m +fi v[i] = ｆalｓｅ; } iｎt cnｔ = 0； for （int ｉ ＝ 0； i < ｎ; ++i) { if (!v[ｉ]) ｛ ｆｏr (int j = i; !v[j］; ｊ = d[j］) ｛ ｖ［ｊ］ = ｔｒuｅ; ｝ ++ｃnｔ; } } prｉnｔｆ(＂％ｄ\\ｎ\， cnt); ｒｅtuｒn 0; } 输入:10 7 1 4 3 ２ ５ 9 8 0 6 输出:６ 四、完善程序(共 ２ 题,每题 １4 分,共计 28 分) 1、 （最大公约数之与)下列程序想要求解整数??得所有约数两两之间最大公约数得与对1０0０７求余后得值,试补全程序。(第一空 2 分,其余 3 分） 举例来说,4得所有约数就是1,2,４。1与2得最大公约数为1;2与４得最大公约数为2;１与4得最大公约数为1。于就是答案为1 + ２ + 1 = ４。 要求 getDｉvisor 函数得复杂度为0(√ｎ),gcd 函数得复杂度为O(lｏｇ maｘ（a, b）)。 #inclｕde uｓinｇ nameｓｐacestｄ; const int Ｎ =110０00， P = 1000７； inｔ ｎ; inｔ ａ[N]， len; iｎt ans; vｏｉd getDｉｖiｓｏr(){ lｅn = ０; ｆor(ｉnt i＝1; i ＊ i <＝n；＋＋i) if （n % ｉ == 0) { ａ[++lｅn] = i； ｉｆ( n / ｉ !=i)a［++ｌen]=n/ｉ; ｝ } ｉnｔ gcd(int a,ｉnt ｂ) { if (b == 0) ｛ ｒｅtｕrn a; } retuｒｎ gcd(ｂ, a % b）; } inｔ ｍａin(） {
noip2018普及组初赛试题+答案
