noip2018普及組初賽試題c

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

2、6 B. (617)10 C. (1151)8 D. (1001101011)2 3. 1MB 等于（ ）。 A. 1000 字節(jié) B. 1024 字節(jié) C. 1000 X 1000 字節(jié) D. 1024 X 1024 字節(jié) 4. 廣域網(wǎng)的英文縮寫是（ ）。 A. LAN B. WAN C. MAN D. LNA 5. 中國計算機學(xué)會于（ ）年創(chuàng)辦全國青少年計算機程序設(shè)計競賽。 A. 1983 B. 1984 C. 1985 D. 1986 6. 如果開始時計算機處于小寫輸入狀態(tài)，現(xiàn)在有一只小老鼠反復(fù)按照CapsLock、字母鍵 A、字母鍵 S、字母鍵 D、字母鍵 F 的順序循環(huán)按鍵，即 Ca

3、psLock、A、 S、D、F、CapsLock、A、S、D、F、，屏幕上輸出的第 81 個字符是字母（ ）。 A. A B. S C. D D. a 7. 根節(jié)點深度為 0，一棵深度為 h 的滿 k（k1）叉樹，即除最后一層無任何子 節(jié)點外，每一層上的所有結(jié)點都有 k 個子結(jié)點的樹，共有（ ）個結(jié)點。 A. (k h+1 - 1) / (k - 1) B. k h-1 C. k h D. (k h-1) / (k - 1) 8. 以下排序算法中，不需要進行關(guān)鍵字比較操作的算法是（ ）。 A. 基數(shù)排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序 9. 給定一個含 N 個不相同數(shù)字的數(shù)組

4、，在最壞情況下，找出其中最大或最小的數(shù)，至少需要 N - 1 次比較操作。則最壞情況下，在該數(shù)組中同時找最大與最小的數(shù)至少需要（ ）次比較操作。（ 表示向上取整， 表示向下取整） A. 3N / 2 - 2 B. 3N / 2 - 2 C. 2N - 2 D. 2N - 4 10. 下面的故事與（ ）算法有著異曲同工之妙。 從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：“從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事” A. 枚舉 B. 遞歸 C. 貪心 D. 分治 11. 由四個沒有區(qū)別的點構(gòu)成的簡單無向連通圖的個數(shù)是（

5、 ）。 A. 6 B. 7 C. 8 D. 9 12. 設(shè)含有 10 個元素的集合的全部子集數(shù)為 S，其中由 7 個元素組成的子集數(shù)為T，則 T / S 的值為（ ）。 A. 5 / 32 B. 15 / 128 C. 1 / 8 D. 21 / 128 13. 10000 以內(nèi)，與 10000 互質(zhì)的正整數(shù)有（ ）個。 A. 2000 B. 4000 C. 6000 D. 8000 14. 為了統(tǒng)計一個非負(fù)整數(shù)的二進制形式中 1 的個數(shù)，代碼如下： int CountBit(int x) int ret = 0; while (x) ret+; _; return ret; 則空格內(nèi)要填入的

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

7、（下雨/ 沒下雨）(2分)。 2. 從1到2018這2018個數(shù)中，共有_個包含數(shù)字8的數(shù)。包含數(shù)字8的數(shù)是指有某一位是“8”的數(shù)， 例如“2018”與“188”。 三 、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 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

8、 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 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 -

9、 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 (int j = i; !vj; j = dj) vj = true; +cnt; printf(%dn, cnt);

10、return 0; 輸入：10 7 1 4 3 2 5 9 8 0 6 輸出：_ 四、完善程序（ 共 2 題，每題 14 分，共計 28 分） 1. （最大公約數(shù)之和）下列程序想要求解整數(shù)的所有約數(shù)兩兩之間最大公約 數(shù)的和對10007求余后的值，試補全程序。（第一空 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ù)雜度為函數(shù)的復(fù)雜度為(log max(, )。 #include using namespace std; const i

11、nt 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; 2. 對于一個1到的排列（即1到中每一個數(shù)在中出現(xiàn)了恰好一次），令為 第個位置之后第一個比值更大的位置，如果不存在這樣的位置，則 = + 1。 舉例來說，如果 = 5且為1 5 4 2 3，則為2 6 6 5 6。 下列程序讀入了排列，使用雙向鏈表求解了答案。試補全程序。（第二空 2 分，其余 3 分） 數(shù)據(jù)范圍 1 105。 #include using namespace std; const int N = 100010; int n; int LN, RN, aN; int main() cin n; for (in