2018年第二十四屆全國青少年信息學奧林匹克聯賽初賽提高組含答案

1、第二十四屆全國青少年信息學奧林匹克聯賽初賽提高組C+語言試題競賽時間：2018年10月13日14:3016:30(WORD重新整理排版)選手注意：試題紙共有9頁，答題紙共有2頁，滿分100分。請在答題紙上作答，寫在試題紙 上的一律無效。不得使用任何電子設備(如計算器、手機、電子詞典等)或查閱任何書籍資料。一、單項選擇題(共10題，每題2分，共計20分；每題有且僅有一個正確選項)下列四個不同進制的數中，與其它三項數值上不相等的是()。(269)16(617)10(1151)8(1001101011)2下列屬于解釋執(zhí)行的程序設計語言是()。 TOC o 1-5 h z CC+PascalPytho

2、n中國計算機學會于()年創(chuàng)辦全國青少年計算機程序設計競賽。1983198419851986設根節(jié)點深度為0，一棵深度為h的滿k(k1)叉樹，即除最后一層無任何子節(jié)點外， 每一層上的所有結點都有k個子結點的樹，共有()個結點。(kh+1 - 1) / (k - 1)kh-1kh(kh-1 ) / (k - 1)設某算法的時間復雜度函數的遞推方程是T(n) = T(n - 1) + n(n為正整數)及T(0) =1，則該算法的時間復雜度為()。O(log n) B. O(n log n) C. O(n) D. O(n2 )表達式a * d - b * c的前綴形式是()。 TOC o 1-5 h

3、z ad*bc*-*ad*bca*d-b*c- * * a d b c在一條長度為1的線段上隨機取兩個點，則以這兩個點為端點的線段的期望長度是（）。 TOC o 1-5 h z 1 / 21 / 32 / 33 / 5關于Catalan數Cn = （2n）! / （n + 1）! / n!,下列說法中錯誤的是（）。Cn表示有n + 1個結點的不同形態(tài)的二叉樹的個數。Cn表示含n對括號的合法括號序列的個數。Cn表示長度為n的入棧序列對應的合法出棧序列個數。Cn表示通過連接頂點而將n + 2邊的凸多邊形分成三角形的方法個數。假設一臺抽獎機中有紅、藍兩色的球，任意時刻按下抽獎按鈕，都會等概率獲得紅球

4、或 藍球之一。有足夠多的人每人都用這臺抽獎機抽獎，假如他們的策略均為：抽中藍球則繼續(xù) 抽球，抽中紅球則停止。最后每個人都把自己獲得的所有球放到一個大箱子里，最終大箱子 里的紅球與藍球的比例接近于（）。 TOC o 1-5 h z 1 : 22 : 11 : 31 : 1為了統(tǒng)計一個非負整數的二進制形式中1的個數，代碼如下：int CountBit（int x）int ret = 0;while （x）ret+;；return ret;則空格內要填入的語句是（）。x = 1x &= x - 1x | = x 1x = 1二、不定項選擇題（共5題，每題2分，共計10分；每題有一個或多個正確選項，

5、多選或少選均不得分）NOIP初賽中，選手可以帶入考場的有（）。筆橡皮手機（關機）草稿紙2-3樹是一種特殊的樹，它滿足兩個條件：（1）每個內部結點有兩個或三個子結點；（2）所有的葉結點到根的路徑長度相同。如果一棵2-3樹有10個葉結點，那么它可能有（）個非葉結點。 TOC o 1-5 h z 5678下列關于最短路算法的說法正確的有（）。當圖中不存在負權回路但是存在負權邊時,Dijkstra算法不一定能求出源點到所有點的 最短路。當圖中不存在負權邊時，調用多次Dijkstra算法能求出每對頂點間最短路徑。圖中存在負權回路時，調用一次Dijkstra算法也一定能求出源點到所有點的最短路。當圖中不存

6、在負權邊時，調用一次Dijkstra算法不能用于每對頂點間最短路計算。下列說法中，是樹的性質的有（）。無環(huán)任意兩個結點之間有且只有一條簡單路徑有且只有一個簡單環(huán)邊的數目恰是頂點數目減1下列關于圖靈獎的說法中，正確的有（）。圖靈獎是由電氣和電子工程師協(xié)會（IEEE）設立的。目前獲得該獎項的華人學者只有姚期智教授一人。其名稱取自計算機科學的先驅、英國科學家艾倫麥席森圖靈。它是計算機界最負盛名、最崇高的一個獎項，有“計算機界的諾貝爾獎”之稱。三、問題求解（共2題，每題5分，共計10分）甲乙丙丁四人在考慮周末要不要外出郊游。已知如果周末下雨，并且乙不去，則甲一定不去；如果乙去，則丁一定去；如果丙去，

7、則丁一定不去；如果丁不去，而且甲不去，則丙一定不去。如果周末丙去了，則甲（去了/沒去）（1分），乙（去了/沒去）（1分），?。ㄈチ?沒去）（1分）， 周末 （下雨/沒下雨）（2分）。方程a*b = （a or b） * （a and b），在a,b都取0, 31中的整數時，共有 組解。（*表示乘法；or表示按位或運算；and表示按位與運算）四、閱讀程序寫結果(共4題，每題8分，共計32分)1.#include int main() int x; scanf(%d”, &x); int res = 0; for (int i = 0; i x; +i) if (i * i % x = 1) +r

8、es; printf(%d”, res); return 0;輸入：15輸出：2.#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); return 0;輸入：10 7 1 4 3 2 5 9 8 0

9、6輸出：3.#include using namespace std;string s;long long magic(int l, int r) long long ans = 0;for (int i = l; i s;int len = s.length();int ans = 0;for (int l1 = 0; l1 len; +l1) for (int r1 = l1; r1 len; +r1) bool bo = true;for (int l2 = 0; l2 len; +l2) for (int r2 = l2; r2 len; +r2) if (magic(l1, r1)=

10、magic(l2, r2) &(l1!=l2 | r1!=r2) bo = false;if (bo) ans += 1;cout ans endl;return 0;輸入：abacaba輸出：4.#include using namespace std;const int N = 110;bool isUseN;int n, t;int aN, bN;bool isSmall() for (int i = 1; i = n; +i)if (ai != bi) return ai n) return isSmall();for (int i = 1; i = n; +i) if (!isUse

11、i) bpos = i; isUsei = true;if (getPermutation(pos + 1) return true;isUsei = false;return false;void getNext() for (int i = 1; i = n; +i) isUsei = false;getPermutation(1);for (int i = 1; i = n; +i) ai = bi;int main() scanf(%d%d”, &n, &t);for (int i = 1; i = n; +i) scanf(%d”, &ai);for (int i = 1; i =

12、t; +i) getNext();for (int i = 1; i = n; +i) printf(%d”, ai);if (i = n) putchar(n); else putchar();return 0;輸入 1： 6 10 1 6 4 5 3 2輸出1： (3分)輸入2： 6 200 1 5 3 4 2 6輸出2： （5分）五、完善程序（共共2題，每題14分，共計28分）對于一個1到n的排列P （即1到n中每一個數在P中出現了恰好一次），令q為第i個 i位置之后第一個比Pi值更大的位置，如果不存在這樣的位置，則qi=n +1。舉例來說，如果n = 5 且 P 為 1 5 4 2 3

13、，則 P 為 2 6 6 5 6。下列程序讀入了排列P，使用雙向鏈表求解了答案。試補全程序。（第二空2分，其余3分）數據范圍1 W nW 105。#include using namespace std;const int N = 100010;int n;int LN, RN, aN;int main（） cin n;for （int i = 1; i x;；for (int i = 1; i = n; +i) Ri =(2);Li = i - 1;for (int i = 1; i = n; +i) L(3) = Lai;RLai = Rfor (int i = 1; i = n; +i)

14、 cout (5) ;cout endl;return 0;一只小豬要買N件物品（N不超過1000）。它要買的所有物品在兩家商店里都有賣。第i件物品在第一家商店的價格是ai，在第二 家商店的價格是bi，兩個價格都不小于0且不超過10000O如果在第一家商店買的物品 的總額于不少于50000，那么在第一家店買的物品都可以打95折（價格變?yōu)樵瓉淼?.95 倍）。求小豬買齊所有物品所需最少的總額。輸入：第一行一個數N。接下來N行，每行兩個數。第i行的兩個數分別代表ai, bi。輸出：輸出一行一個數，表示最少需要的總額，保留兩位小數。試補全程序。（第一空2分，其余3分） #include #inclu

15、de using namespace std;const int Inf = 1000000000;const int threshold = 50000;const int maxn = 1000;int n, amaxn, bmaxn; bool put_amaxn;int total_a, total_b;double ans;int fthreshold;int main() scanf(%d，&n);total_a = total_b = 0;for (int i = 0; i n; +i) scanf(%d%d，a + i, b + i);if (ai = bi) total_a

16、+= ai;else total_b += bi;ans = total_a + total_b;total_a = total_b = 0;for (int i = 0; i n; +i) if (1) put_ai = true;total_a += ai; else put_ai = false;total_b += bi;if ()printf(.2f，total_a * 0.95 + total_b);return 0;f0 = 0;for (int i = 1; i threshold; +i) fi = Inf;int total_b_prefix = 0;for (int i

17、= 0; i = 0; j) if (3) = threshold & fj != Inf);ans = min(ans, (total_a + j + ai) * 0.95+(4)fj = min(fj + bi, j = ai ?(5 : Inf); printf(%.2f，ans);return 0;第二十四屆全國青少年信息學奧林匹克聯賽初賽提高組參考答案一、單項選擇題（共10題，每題2分，共計20分）12345678910DDBADBBADB二、不定項選擇題（共5題，每題2分，共計10分；每題有一個或多個正確選項，沒有 部分分）12345ABCDABDABDBCD三、問題求解（共2題，每題5分，共計10分）去了沒去沒去 沒下雨（第4空2分，其余1分） TOC o 1-5 h z 454四、閱讀程序寫結果（共4題，每題8分，共計32分） HYPERLINK l bookmark94 o Current Document 4616輸出 1： 2 1 3 5 6 4 （3 分）輸出 2： 3 2 5 6 1 4（5 分）五、完善程序（共計