




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第二十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組C+語(yǔ)言試題競(jìng)賽時(shí)間:2018年10月13日14:3016:30(WORD重新整理排版)選手注意:試題紙共有9頁(yè),答題紙共有2頁(yè),滿分100分。請(qǐng)?jiān)诖痤}紙上作答,寫在試題紙 上的一律無(wú)效。不得使用任何電子設(shè)備(如計(jì)算器、手機(jī)、電子詞典等)或查閱任何書籍資料。一、單項(xiàng)選擇題(共10題,每題2分,共計(jì)20分;每題有且僅有一個(gè)正確選項(xiàng))下列四個(gè)不同進(jìn)制的數(shù)中,與其它三項(xiàng)數(shù)值上不相等的是()。(269)16(617)10(1151)8(1001101011)2下列屬于解釋執(zhí)行的程序設(shè)計(jì)語(yǔ)言是()。 TOC o 1-5 h z CC+PascalPytho
2、n中國(guó)計(jì)算機(jī)學(xué)會(huì)于()年創(chuàng)辦全國(guó)青少年計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽。1983198419851986設(shè)根節(jié)點(diǎn)深度為0,一棵深度為h的滿k(k1)叉樹,即除最后一層無(wú)任何子節(jié)點(diǎn)外, 每一層上的所有結(jié)點(diǎn)都有k個(gè)子結(jié)點(diǎn)的樹,共有()個(gè)結(jié)點(diǎn)。(kh+1 - 1) / (k - 1)kh-1kh(kh-1 ) / (k - 1)設(shè)某算法的時(shí)間復(fù)雜度函數(shù)的遞推方程是T(n) = T(n - 1) + n(n為正整數(shù))及T(0) =1,則該算法的時(shí)間復(fù)雜度為()。O(log n) B. O(n log n) C. O(n) D. O(n2 )表達(dá)式a * d - b * c的前綴形式是()。 TOC o 1-5 h
3、z ad*bc*-*ad*bca*d-b*c- * * a d b c在一條長(zhǎng)度為1的線段上隨機(jī)取兩個(gè)點(diǎn),則以這兩個(gè)點(diǎn)為端點(diǎn)的線段的期望長(zhǎng)度是()。 TOC o 1-5 h z 1 / 21 / 32 / 33 / 5關(guān)于Catalan數(shù)Cn = (2n)! / (n + 1)! / n!,下列說(shuō)法中錯(cuò)誤的是()。Cn表示有n + 1個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹的個(gè)數(shù)。Cn表示含n對(duì)括號(hào)的合法括號(hào)序列的個(gè)數(shù)。Cn表示長(zhǎng)度為n的入棧序列對(duì)應(yīng)的合法出棧序列個(gè)數(shù)。Cn表示通過(guò)連接頂點(diǎn)而將n + 2邊的凸多邊形分成三角形的方法個(gè)數(shù)。假設(shè)一臺(tái)抽獎(jiǎng)機(jī)中有紅、藍(lán)兩色的球,任意時(shí)刻按下抽獎(jiǎng)按鈕,都會(huì)等概率獲得紅球
4、或 藍(lán)球之一。有足夠多的人每人都用這臺(tái)抽獎(jiǎng)機(jī)抽獎(jiǎng),假如他們的策略均為:抽中藍(lán)球則繼續(xù) 抽球,抽中紅球則停止。最后每個(gè)人都把自己獲得的所有球放到一個(gè)大箱子里,最終大箱子 里的紅球與藍(lán)球的比例接近于()。 TOC o 1-5 h z 1 : 22 : 11 : 31 : 1為了統(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)要填入的語(yǔ)句是()。x = 1x &= x - 1x | = x 1x = 1二、不定項(xiàng)選擇題(共5題,每題2分,共計(jì)10分;每題有一個(gè)或多個(gè)正確選項(xiàng),
5、多選或少選均不得分)NOIP初賽中,選手可以帶入考場(chǎng)的有()。筆橡皮手機(jī)(關(guān)機(jī))草稿紙2-3樹是一種特殊的樹,它滿足兩個(gè)條件:(1)每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)或三個(gè)子結(jié)點(diǎn);(2)所有的葉結(jié)點(diǎn)到根的路徑長(zhǎng)度相同。如果一棵2-3樹有10個(gè)葉結(jié)點(diǎn),那么它可能有()個(gè)非葉結(jié)點(diǎn)。 TOC o 1-5 h z 5678下列關(guān)于最短路算法的說(shuō)法正確的有()。當(dāng)圖中不存在負(fù)權(quán)回路但是存在負(fù)權(quán)邊時(shí),Dijkstra算法不一定能求出源點(diǎn)到所有點(diǎn)的 最短路。當(dāng)圖中不存在負(fù)權(quán)邊時(shí),調(diào)用多次Dijkstra算法能求出每對(duì)頂點(diǎn)間最短路徑。圖中存在負(fù)權(quán)回路時(shí),調(diào)用一次Dijkstra算法也一定能求出源點(diǎn)到所有點(diǎn)的最短路。當(dāng)圖中不存
6、在負(fù)權(quán)邊時(shí),調(diào)用一次Dijkstra算法不能用于每對(duì)頂點(diǎn)間最短路計(jì)算。下列說(shuō)法中,是樹的性質(zhì)的有()。無(wú)環(huán)任意兩個(gè)結(jié)點(diǎn)之間有且只有一條簡(jiǎn)單路徑有且只有一個(gè)簡(jiǎn)單環(huán)邊的數(shù)目恰是頂點(diǎn)數(shù)目減1下列關(guān)于圖靈獎(jiǎng)的說(shuō)法中,正確的有()。圖靈獎(jiǎng)是由電氣和電子工程師協(xié)會(huì)(IEEE)設(shè)立的。目前獲得該獎(jiǎng)項(xiàng)的華人學(xué)者只有姚期智教授一人。其名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國(guó)科學(xué)家艾倫麥席森圖靈。它是計(jì)算機(jī)界最負(fù)盛名、最崇高的一個(gè)獎(jiǎng)項(xiàng),有“計(jì)算機(jī)界的諾貝爾獎(jiǎng)”之稱。三、問(wèn)題求解(共2題,每題5分,共計(jì)10分)甲乙丙丁四人在考慮周末要不要外出郊游。已知如果周末下雨,并且乙不去,則甲一定不去;如果乙去,則丁一定去;如果丙去,
7、則丁一定不去;如果丁不去,而且甲不去,則丙一定不去。如果周末丙去了,則甲(去了/沒(méi)去)(1分),乙(去了/沒(méi)去)(1分),?。ㄈチ?沒(méi)去)(1分), 周末 (下雨/沒(méi)下雨)(2分)。方程a*b = (a or b) * (a and b),在a,b都取0, 31中的整數(shù)時(shí),共有 組解。(*表示乘法;or表示按位或運(yùn)算;and表示按位與運(yùn)算)四、閱讀程序?qū)懡Y(jié)果(共4題,每題8分,共計(jì)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分,共計(jì)28分)對(duì)于一個(gè)1到n的排列P (即1到n中每一個(gè)數(shù)在P中出現(xiàn)了恰好一次),令q為第i個(gè) i位置之后第一個(gè)比Pi值更大的位置,如果不存在這樣的位置,則qi=n +1。舉例來(lái)說(shuō),如果n = 5 且 P 為 1 5 4 2 3
13、,則 P 為 2 6 6 5 6。下列程序讀入了排列P,使用雙向鏈表求解了答案。試補(bǔ)全程序。(第二空2分,其余3分)數(shù)據(jù)范圍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不超過(guò)1000)。它要買的所有物品在兩家商店里都有賣。第i件物品在第一家商店的價(jià)格是ai,在第二 家商店的價(jià)格是bi,兩個(gè)價(jià)格都不小于0且不超過(guò)10000O如果在第一家商店買的物品 的總額于不少于50000,那么在第一家店買的物品都可以打95折(價(jià)格變?yōu)樵瓉?lái)的0.95 倍)。求小豬買齊所有物品所需最少的總額。輸入:第一行一個(gè)數(shù)N。接下來(lái)N行,每行兩個(gè)數(shù)。第i行的兩個(gè)數(shù)分別代表ai, bi。輸出:輸出一行一個(gè)數(shù),表示最少需要的總額,保留兩位小數(shù)。試補(bǔ)全程序。(第一空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;第二十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組參考答案一、單項(xiàng)選擇題(共10題,每題2分,共計(jì)20分)12345678910DDBADBBADB二、不定項(xiàng)選擇題(共5題,每題2分,共計(jì)10分;每題有一個(gè)或多個(gè)正確選項(xiàng),沒(méi)有 部分分)12345ABCDABDABDBCD三、問(wèn)題求解(共2題,每題5分,共計(jì)10分)去了沒(méi)去沒(méi)去 沒(méi)下雨(第4空2分,其余1分) TOC o 1-5 h z 454四、閱讀程序?qū)懡Y(jié)果(共4題,每題8分,共計(jì)32分) HYPERLINK l bookmark94 o Current Document 4616輸出 1: 2 1 3 5 6 4 (3 分)輸出 2: 3 2 5 6 1 4(5 分)五、完善程序(共計(jì)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 四川省綿陽(yáng)市三臺(tái)中學(xué)2024-2025學(xué)年高二(上)期末生物試卷(含解析)
- 溝槽開挖支護(hù)施工方案
- 橋架鋼結(jié)構(gòu)施工方案
- 導(dǎo)管室裝修施工方案
- 深圳燈光秀施工方案
- 反光涂料施工方案
- 防滑混凝土泳池施工方案
- 5以內(nèi)的3個(gè)數(shù)加減混合題
- 等效電路模型、單顆粒模型、均質(zhì)多孔模型、異構(gòu)模型等
- 地暖加壓泵換向閥工作原理
- 人教版PEP小學(xué)五年級(jí)英語(yǔ)下冊(cè)全冊(cè)教案(含計(jì)劃)
- 《公路工程造價(jià)標(biāo)準(zhǔn)高海拔高寒地區(qū)補(bǔ)充規(guī)定》
- 2024-2030年中國(guó)工控機(jī)行業(yè)發(fā)展?fàn)顩r及營(yíng)銷戰(zhàn)略研究報(bào)告
- 臨床護(hù)理實(shí)踐指南2024版
- 貴州省獸藥經(jīng)營(yíng)質(zhì)量管理規(guī)范實(shí)施細(xì)則
- 常規(guī)弱電系統(tǒng)施工單價(jià)表純勞務(wù)
- 勞動(dòng)合同(模版)4篇
- 2024-2025學(xué)年小學(xué)信息技術(shù)(信息科技)五年級(jí)下冊(cè)人教版教學(xué)設(shè)計(jì)合集
- 2024年大學(xué)試題(林學(xué))-森林經(jīng)理學(xué)考試近5年真題集錦(頻考類試題)帶答案
- 醫(yī)學(xué)教材 《婦產(chǎn)科學(xué)》第9版課件-胎兒異常與多胎妊娠
- 2025年國(guó)家公務(wù)員考試行測(cè)(地市級(jí))行政職業(yè)能力測(cè)驗(yàn)試卷與參考答案
評(píng)論
0/150
提交評(píng)論