普及組初賽試題+答案

1、第24屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組C+語言試題競賽時(shí)間：2018 年 10 月 13 日 14:3016:30選手注意：1、試題紙共有 7 頁，答題紙共有 2 頁，滿分 100 分。請?jiān)诖痤}紙上作答，寫在試題紙上的一律無效。2、不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共15題，每題2分，共計(jì)30分；每題有且僅有一個(gè)正確選項(xiàng)）1. 以下哪一種設(shè)備屬于輸出設(shè)備:( )A.掃描儀 B.鍵盤 C.鼠標(biāo) D.打印機(jī)2. 下列四個(gè)不同進(jìn)制的數(shù)中，與其它三項(xiàng)數(shù)值上不相等的是( )。A. (269)16 (注解：2 * 162 + 6 * 161 +

2、9 * 16 0 = 617)B. (617)10C. (1151)8 （注解：1 * 83 + 1 * 82 + 5 * 81 + 1 * 80 = 617）D. (1001101011)23. 1MB等于( )。A. 1000 字節(jié)B. 1024 字節(jié)C. 1000 X 1000字節(jié)D. 1024 X 1024字節(jié)4. 廣域網(wǎng)的英文縮寫是( )。A. LANB. WAN (Wide Area Network)C. MAN D.LNA5. 中國計(jì)算機(jī)學(xué)會于( )年創(chuàng)辦全國青少年計(jì)算機(jī)程序設(shè)計(jì)競賽。A. 1983B. 1984C. 1985 D. 19866. 如果開始時(shí)計(jì)算機(jī)處于小寫輸入狀態(tài)

3、，現(xiàn)在有一只小老鼠反復(fù)按照 CapsLock、字母鍵 A、字母鍵S、字母鍵 D、字母鍵 F 的順序循環(huán)按鍵，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、.，屏幕上輸出的第 81 個(gè)字符是字母 ( )。A. AB. S C. D D. a7. 根節(jié)點(diǎn)深度為 0，一棵深度為 h 的滿 k(k1)叉樹，即除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有k個(gè)子結(jié)點(diǎn)的樹，共有( )個(gè)結(jié)點(diǎn)。A. (kh+1-1)/(k-1)B. kh-1C. khD. (kh-1) / (k - 1)8. 以下排序算法中，不需要進(jìn)行關(guān)鍵字比較操作的算法是( )。A. 基數(shù)排序B. 冒泡排序C.

4、 堆排序D. 直接插入排序9. 給定一個(gè)含 N 個(gè)不相同數(shù)字的數(shù)組，在最壞情況下，找出其中最大或最小的數(shù)，至少需要 N - 1 次比較操作。則最壞情況下，在該數(shù)組中同時(shí)找最大與最小的數(shù)至少需要( )次比較操作。( 表示向上取整， 表示向下取整)A. 3N / 2 - 2B. 3N / 2 - 2C. 2N - 2D. 2N - 410. 下面的故事與( )算法有著異曲同工之妙。從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事:“從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事:從前有座山，山里有座廟，廟里有個(gè)老和尚給小和尚講故事.”A. 枚舉B. 遞歸C. 貪心D. 分治11. 由

5、四個(gè)沒有區(qū)別的點(diǎn)構(gòu)成的簡單無向連通圖的個(gè)數(shù)是( )。A. 6B. 7 C. 8 D.912. 設(shè)含有 10 個(gè)元素的集合的全部子集數(shù)為 S，其中由 7 個(gè)元素組成的子集數(shù)為T，則T / S的值為( )。A. 5 / 32B. 15 / 128C. 1 / 8D. 21 / 12813. 10000以內(nèi)，與10000互質(zhì)的正整數(shù)有( )個(gè)。A. 2000B. 4000C. 6000D. 800014. 為了統(tǒng)計(jì)一個(gè)非負(fù)整數(shù)的二進(jìn)制形式中 1 的個(gè)數(shù)，代碼如下:int CountBit(int x)int ret = 0;while (x)ret+;_;return ret;則空格內(nèi)要填入的語句是

6、( )。A. x = 1B. x &= x - 1C. x |= x 1D. x = 115. 下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是( )。A. 哈希表 B. 棧C. 隊(duì)列 D. 二叉樹二、問題求解（共 2 題，每題 5 分，共計(jì) 10 分）1. 甲乙丙丁四人在考慮周末要不要外出郊游。 已知1如果周末下雨，并且乙不去，則甲一定不去；2如果乙去，則丁一定去；3如果丙去，則丁一定不去；4如果丁不去，而且甲不去，則丙一定不去。如果周末丙去了，則甲去了(去了/沒去)(1 分)，乙沒去(去了/沒去)(1 分)，丁沒去(去了/沒去)(1 分)，周末沒下雨(下雨/ 沒下雨)(2 分)。2. 從 1 到 2018 這 2

7、018 個(gè)數(shù)中，共有544個(gè)包含數(shù)字 8 的數(shù)。包含數(shù)字 8 的數(shù)是指有某一位是“8”的數(shù)，例如“2018”與“188”。三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1.#includechar st100;int main() scanf(%s, st); for (int i = 0; sti; +i) if (A = sti & sti= Z) sti += 1; printf(%sn, st); return 0;輸入：QuanGuoLianSai輸出：RuanHuoMianTai2.#includeint main() int x; scanf(%d, &x); i

8、nt res = 0; for (int i = 0; i x; +i) if (i * i % x = 1) +res; printf(%d, res);return 0;輸入：15輸出：43.#includeusing namespacestd;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 finda

9、ns(n, m) endl;return 0;輸入：5 6輸出：84.#includeint 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 (int j = i; !vj; j = dj) vj = true;+cnt; printf(%dn, cnt); return 0;輸入：10 7 1 4 3 2 5 9 8 0 6輸出：6四、完善程序

10、（共 2 題，每題 14 分，共計(jì) 28 分）1. （最大公約數(shù)之和）下列程序想要求解整數(shù)的所有約數(shù)兩兩之間最大公約數(shù)的和對10007求余后的值，試補(bǔ)全程序。（第一空 2 分，其余 3 分）舉例來說，4的所有約數(shù)是1,2,4。1和2的最大公約數(shù)為1；2和4的最大公約數(shù)為2；1和4的最大公約數(shù)為1。于是答案為1 + 2 + 1 = 4。要求 getDivisor 函數(shù)的復(fù)雜度為0(n)，gcd 函數(shù)的復(fù)雜度為O(log max(a, b)。#includeusing namespacestd;const int N =110000, P = 10007;int n;int aN, len;int

11、 ans;void getDivisor()len = 0;for(int i=1;i * i n;getDivisor();ans = 0;for (int i = 1; i = len; +i) for (int j = i + 1; j = len; +j) ans=(ans + gcd(ai, aj)%P;cout ans endl;return 0;2. 對于一個(gè)1到n的排列p(即1到n中每一個(gè)數(shù)在p中出現(xiàn)了恰好一次)，令qi為第i個(gè)位置之后第一個(gè)比pi值更大的位置，如果不存在這樣的位置，則qi=n+1。舉例來說，如果n=5且p為1 5 4 2 3，則q為2 6 6 5 6。下列程序讀入了排列p，使用雙向鏈表求解了答案。試補(bǔ)全程序。（第二空2分，其余3分）數(shù)據(jù)范圍 1 n 105。#includeusing namespace std;const int N =100010;int n;int LN, RN,aN;int main() cin