1、第二十四屆全國青少年信息學奧林匹克聯賽初賽普及組 C+語言試題競賽時間：2018 年 10 月 13 日 14:3016:30(WORD重新整理排版)選手注意：l 試題紙共有 7 頁，答題紙共有 2 頁，滿分 100 分。請在答題紙上作答，寫在試題紙上的一律無效。l 不得使用任何電子設備（如計算器、手機、電子詞典等）或查閱任何書籍資料。一、單項選擇題（共 15 題，每題 2 分，共計 30 分 ； 每題有且僅有一個正確選項）1. 以下哪一種設備屬于輸出設備：（ ）A. 掃描儀 B. 鍵盤 C. 鼠標 D. 打印機2. 下列四個不同進制的數中，與其它三項數值上不相等的是（ ）。A. (269)1

2、6B. (617)10C. (1151)8D. (1001101011)23. 1MB 等于（ ）。A. 1000 字節 B. 1024 字節C. 1000 1000 字節 D. 1024 1024 字節4. 廣域網的英文縮寫是（ ）。A. LANB. WANC. MAND. LNA5. 中國計算機學會于（ ）年創辦全國青少年計算機程序設計競賽。A. 1983B. 1984C. 1985D. 19866. 如果開始時計算機處于小寫輸入狀態，現在有一只小老鼠反復按照CapsLock、字母鍵 A、字母鍵 S、字母鍵 D、字母鍵 F 的順序循環按鍵，即 CapsLock、A、S、D、F、CapsLo

3、ck、A、S、D、F、，屏幕上輸出的第 81 個字符是字母（ ）。A. A B. S C. D D. a7. 根節點深度為 0，一棵深度為 h 的滿 k（k1）叉樹，即除最后一層無任何子節點外，每一層上的所有結點都有 k 個子結點的樹，共有（ ）個結點。A. (kh+1 - 1) / (k - 1)B. kh-1C. khD. (kh-1 ) / (k - 1)8. 以下排序算法中，不需要進行關鍵字比較操作的算法是（ ）。A. 基數排序B. 冒泡排序C. 堆排序D. 直接插入排序9. 給定一個含 N 個不相同數字的數組，在最壞情況下，找出其中最大或最小的數，至少需要 N - 1 次比較操作。則

4、最壞情況下，在該數組中同時找最大與最小的數至少需要（ ）次比較操作。（ 表示向上取整， 表示向下取整）A. 3N/2 - 2B. 3N/2 - 2C. 2N - 2D. 2N 410. 下面的故事與（ ）算法有著異曲同工之妙。從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：“從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事”A. 枚舉 B. 遞歸 C. 貪心 D. 分治11. 由四個沒有區別的點構成的簡單無向連通圖的個數是（ ）。A. 6B. 7C. 8D. 912. 設含有 10 個元素的集合的全部子集數為 S，其中由 7

5、個元素組成的子集數為T，則 T / S 的值為（ ）。A. 5 / 32B. 15 / 128C. 1 / 8D. 21 / 12813. 10000 以內，與 10000 互質的正整數有（ ）個。A. 2000B. 4000C. 6000D. 800014. 為了統計一個非負整數的二進制形式中 1 的個數，代碼如下：int CountBit(int x)int ret = 0;while (x)ret+;_;return ret;則空格內要填入的語句是（ ）。A. x = 1B. x &= x - 1C. x |= x 1D. x = 115. 下圖中所使用的數據結構是（ ）。A. 哈希表

6、B. 棧 C. 隊列 D. 二叉樹二、 問題求解（共 2 題，每題 5 分，共計 10 分）1. 甲乙丙丁四人在考慮周末要不要外出郊游。已知如果周末下雨，并且乙不去，則甲一定不去；如果乙去，則丁一定去；如果丙去，則丁一定不去；如果丁不去，而且甲不去，則丙一定不去。如果周末丙去了，則甲_（去了/沒去）(1 分)，乙_（去了/沒去）(1 分)，丁_（去了/沒去）(1 分)，周末_（下雨/沒下雨）(2 分)。2. 從 1 到 2018 這 2018 個數中，共有_個包含數字 8 的數。包含數字 8 的數是指有某一位是“8”的數， 例如“2018”與“188”。三 、閱讀程序寫結果（共 4 題，每題

7、8 分，共計 32 分）1.#include char 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輸出：_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.

8、 #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 findans(n, m) endl;return 0;輸入：5 6輸出：_4.#include int n, d100;bool v100;int main() scanf(%d, &n);for

9、 (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輸出：_四、完善程序 （共 共 2 題，每題 14 分 ， 共計 28 分 ）1.（最大公約數之和）下列程序想要求解整數n的所有約數兩兩之間最大公約數的和對10007求余后的值，試補全程序。（第一空 2 分，其余 3

10、 分）舉例來說，4的所有約數是1,2,4。1和2的最大公約數為1；2和4的最大公約數為2；1和4的最大公約數為1。于是答案為1 + 2 + 1 = 4。要求 getDivisor 函數的復雜度為O(n)，gcd 函數的復雜度為O(logmax(a,b)。#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

11、 = len; +i) for (int j = i + 1; j = len; +j) ans = ( (5) ) % P;cout ans endl;return 0;2. 對于一個1到n的排列P（即1到n中每一個數在P中出現了恰好一次），令qi為第個位置之后第一個比Pi 值更大的位置，如果不存在這樣的位置，則qi=n +1。舉例來說，如果n = 5且P為1 5 4 2 3，則P為2 6 6 5 6。下列程序讀入了排列P，使用雙向鏈表求解了答案。試補全程序。（第二空2 分，其余 3 分）數據范圍 1 n 105 。#include using namespace std;const int

12、 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 (int i = 1; i = n; +i) cout (5) ;cout endl;return 0;第二十四屆全國青少年信息學奧林匹克聯賽初賽普及組參考答案一、單項選擇題（共15 題，每題2 分，共計30 分）12345678910DDDBBAAAAB1112131415ABBBB二、問題求解（共2題，每題5分，共計10分）1. 去了 沒去 沒去 沒下雨 （第4 空2分，其余1分）2. 544三、閱讀程序寫結果（共4題，每題8分，共計32 分）1. RuanHuoMianTai2. 43. 84. 6四、完善程序（共計28分，以下各程序填空