NOIP提高組初賽C基礎(chǔ)教學(xué)

1、第二十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組 c+語言試題（2小時(shí)）選手注意: 不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共 15 題，每題 1.5 分，共計(jì) 22.5 分；每題有且僅有一個(gè)正確 選項(xiàng)）1.以下不是微軟公司出品的軟件是（ ）。. powerpoint. word . excel. acrobat reader2.如果開始時(shí)計(jì)算機(jī)處于小寫輸入狀態(tài)，現(xiàn)在有一只小老鼠反復(fù)按照 capslock、字母鍵 a、字母鍵 s 和字母鍵 d 的順序來回按鍵，即 capslock、a、s、d、s、a、capslock、a、s、d、s、a、capsl

2、ock、a、s、d、s、a、，屏幕上輸出的第 81 個(gè)字符是字母（ ）。. a . s . d . a3.二進(jìn)制數(shù) 00101100 和 01010101 異或的結(jié)果是（ ）。. 00101000 . 01111001 . 01000100 . 001110004. 與二進(jìn)制小數(shù) 0.1 相等的八進(jìn)進(jìn)制數(shù)是（ ）。. 0.8 . 0.4 . 0.2 . 0.15. 以比較作為基本運(yùn)算，在 n 個(gè)數(shù)中找最小數(shù)的最少運(yùn)算次數(shù)為（ ）。. n . n-1 . n2 . log n6. 表達(dá)式 a*(b+c)-d 的后綴表達(dá)形式為（ ）。. abcd*+- . abc+*d- . abc*+d- .

3、-+*abcd7. 一棵二叉樹如右圖所示，若采用二叉樹鏈表存儲(chǔ)該二叉 樹（各個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)的數(shù)據(jù)、左孩子指針、右孩子指針）。如果沒有左孩子或者右孩子，則對(duì)應(yīng)的為空指針。那么該鏈表中空指針的數(shù)目為（ ）。a. 6 b. 7 c. 12 . 148.g 是一個(gè)非連通簡單無向圖，共有 28 條邊，則該圖至少有（ ）個(gè)頂點(diǎn)。. 10 . 9 .8 .7 9.某計(jì)算機(jī)的 cpu 和內(nèi)存之間的地址總線寬度是 32 位（bit），這臺(tái)計(jì)算機(jī)最多可以使用（ ）的內(nèi)存。a.2gbb.4gbc.8gbd.16gb10.有以下程序：#include <iostream> using namespace

4、std;int main() int k = 4, n = 0; while (n < k) n+;if (n % 3 != 0) continue;k-;cout << k << "," << n << endl; return 0;程序運(yùn)行后的輸出結(jié)果是（ ）。. 2,2 . 2,3 . 3,2 . 3,311. 有 7 個(gè)一模一樣的蘋果，放到 3 個(gè)一樣的盤子中，一共有（ ）種放法。. 7 . 8 . 21 . 3712.lucia 和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊(cè)了賬號(hào)。下圖是他們 之間的關(guān)系圖，兩個(gè)

5、人之間有邊相連代表這兩個(gè)人是朋友，沒有邊相連代表不是朋友。這個(gè)社交網(wǎng)站的規(guī)則是：如果某人 a 向他（她）的朋友 b 分享了 某張照片，那么 b 就可以對(duì)該照片進(jìn)行評(píng)論；如果 b 評(píng)論了該照片，那么他 （她）的所有朋友都可以看見這個(gè)評(píng)論以及被評(píng)論的照片，但是不能對(duì)該照片進(jìn)行評(píng)論（除非 a 也向他（她）分享了該照片）?，F(xiàn)在 lucia 已經(jīng)上傳了一張照片，但是她不想讓 jacob 看見這張照片，那么她可以向以下朋友（ ）分享該照片。. dana, michael, eve . dana, eve, monica. michael, eve, jacob . micheal, peter, moni

6、ca13.周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé) 切菜、媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜 10 分鐘，然后切 菜 10 分鐘，最后炒菜 10 分鐘。那么做一道菜需要 30 分鐘。注意：兩道不 同的菜的相同步驟不可以同時(shí)進(jìn)行。例如第一道菜和第二道的菜不能同時(shí)洗，也不能同時(shí)切。那么做完三道菜的最短時(shí)間需要（）分鐘。a.90b.60c.50d.4014. 假設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式t(n) = 2t()+t(1) = 1則算法的時(shí)間復(fù)雜度為（ ）。a.o(n)b. o()c. o( logn)d.o(n2)1.給定含有 n 個(gè)不同的數(shù)的數(shù)組 l=&l

7、t;x1, x2, .,xn>。如果 l 中存在 xi（1 < i < n） 使得 x1 <x2 < . < xi-1 <xi > xi+1 > . >xn， 則稱 l 是單峰的，并稱 xi 是 l 的“峰頂”。現(xiàn)在已知 l 是單峰的，請(qǐng)把 a-c 三行代碼補(bǔ)全到算法中使得算法 正確找到 l 的峰頂。a.search(k+1, n)b.search(1, k-1)c.return lksearch(1, n)1.k n/22.if lk > lk-1 and lk > lk+13.then _4.else if lk &g

8、t; lk-1 and lk < lk+15.then _6.else _正確的填空順序是（）。a.c, a, bb.c, b, ac.a, b, cd.b, a, c二、不定項(xiàng)選擇題（共 5 題，每題 1.5 分，共計(jì) 7.5 分；每題有一個(gè)或多個(gè)正確 選項(xiàng)，多選或少選均不得分）1.以下屬于無線通信技術(shù)的有（ ）。a.藍(lán)牙b.wific.gprsd.以太網(wǎng)2.可以將單個(gè)計(jì)算機(jī)接入到計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)接入通訊設(shè)備有（ ）。a.網(wǎng)卡b.光驅(qū)c.鼠標(biāo)d.顯卡3.下列算法中運(yùn)用分治思想的有（ ）。a.快速排序b.歸并排序c.冒泡排序d.計(jì)數(shù)排序4.下圖表示一個(gè)果園灌溉系統(tǒng)，有 a、b、c、d

9、四個(gè)閥門，每個(gè)閥門可以打開 或關(guān)上，所有管道粗細(xì)相同，以下設(shè)置閥門的方法中，可以讓果樹澆上水的有（ ）。 有水 有水果樹a.b 打開，其他都關(guān)上 b.ab 都打開，cd 都關(guān)上c.a 打開，其他都關(guān)上 d.d 打開，其他都關(guān)上5. 參加 noi 比賽，以下能帶入考場(chǎng)的有（ ）。a.鋼筆 b.適量的衣服c.u 盤 d.鉛筆三、問題求解（共 2 題，每題 5 分，共計(jì) 10 分；每題全部答對(duì)得 5 分，沒有部分分）1.一個(gè) 1×8 的方格圖形（不可旋轉(zhuǎn)）用黑、白兩種顏色填涂每個(gè)方格。如果 每個(gè)方格只能填涂一種顏色，且不允許兩個(gè)黑格相鄰，共有_種填 涂方案。2.某中學(xué)在安排期末考試時(shí)發(fā)現(xiàn)，

10、有 7 個(gè)學(xué)生要參加 7 門課程的考試，下表列 出了哪些學(xué)生參加哪些考試（用表示要參加相應(yīng)的考試）。 最少要安排_(tái)個(gè)不同的考試時(shí)間段才能避免沖突？考試學(xué)生 1學(xué)生 2學(xué)生 3學(xué)生 4學(xué)生 5學(xué)生 6學(xué)生 7通用技術(shù)物理化學(xué)生物歷史地理政治四、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1.#include <iostream> using namespace std;int main() int a6 = 1, 2, 3, 4, 5, 6; int pi = 0; int pj = 5; int t , i;while (pi < pj) t = api; ap

11、i = apj; apj = t; pi+; pj-;for (i = 0; i < 6; i+) cout << ai << ","cout << endl; return 0;輸出：_2.#include <iostream> using namespace std;int main() char a100100, b100100; string c100; string tmp;int n, i = 0, j = 0, k = 0, total_len100, length1003;cin >> n;g

12、etline(cin, tmp);for (i = 0; i < n; i+) getline(cin, ci);total_leni = ci.size();for (i = 0; i < n; i+) j = 0;while (cij != ':') aik = cij;k = k + 1; j+;lengthi1 = k - 1; aik = 0;k = 0;for (j = j + 1; j < total_leni; j+) bik = cij;k = k + 1;lengthi2 = k - 1; bik = 0;k = 0;for (i = 0;

13、 i < n; i+) if (lengthi1 >= lengthi2) cout << "no,"else k = 0;for (j = 0; j < lengthi2; j+) if (aik = bij) k = k + 1;if (k > lengthi1) break;if (j = lengthi2) cout << "no,"else cout << "yes,"cout << endl;return 0;輸入：3 ab:acdebfbkbd ar

14、:acdbrtsars:severe atypical respiratory syndrome 輸出：_（注：輸入各行前后均無空格）3.#include<iostream> using namespace std;int lps(string seq, int i, int j) int len1, len2;if (i = j) return 1;if (i > j) return 0;if (seqi = seqj)return lps(seq, i + 1, j - 1) + 2; len1 = lps(seq, i, j - 1);len2 = lps(seq, i

15、 + 1, j); if (len1 > len2) return len1; return len2;int main() string seq = "acmerandacm" int n = seq.size();cout << lps(seq, 0, n - 1) << endl; return 0;輸出：_4.#include <iostream> #include <cstring> using namespace std;int map100100;int sum100, weight100; int vis

16、it100;int n;void dfs(int node) visitnode = 1; sumnode = 1; int v, maxw = 0;for (v = 1; v <= n; v+) if (!mapnodev | visitv) continue;dfs(v);sumnode += sumv; if (sumv > maxw) maxw = sumv;if (n - sumnode > maxw) maxw = n - sumnode;weightnode = maxw;int main() memset(map, 0, sizeof(map); memset

17、(sum, 0, sizeof(sum); memset(weight, 0, sizeof(weight); memset(visit, 0, sizeof(visit); cin >> n;int i, x, y;for (i = 1; i < n; i+) cin >> x >> y; mapxy = 1; mapyx = 1;dfs(1);int ans = n, ansn = 0; for (i = 1; i <= n; i+)if (weighti < ans) ans = weighti; ansn = i;cout <

18、< ansn << " " << ans << endl; return 0;輸入：111 21 32 42 52 63 77 87 116 99 10輸出：_五、完善程序（共 2 題，每題 14 分，共計(jì) 28 分）1.（交朋友）根據(jù)社會(huì)學(xué)研究表明，人們都喜歡找和自己身高相近的人做朋友?，F(xiàn)在有 n 名身高兩兩不相同的同學(xué)依次走入教室，調(diào)查人員想預(yù)測(cè)每個(gè)人在走入教室的瞬間最想和已經(jīng)進(jìn)入教室的哪個(gè)人做朋友。當(dāng)有兩名同學(xué)和這名 同學(xué)的身高差一樣時(shí)，這名同學(xué)會(huì)更想和高的那個(gè)人做朋友。比如一名身高為1.80 米的同學(xué)進(jìn)入教室時(shí)，有一名身高為

19、 1.79 米的同學(xué)和一名身高為1.81米的同學(xué)在教室里，那么這名身高為 1.80 米的同學(xué)會(huì)更想和身高為 1.81 米的同學(xué)做朋友。對(duì)于第一個(gè)走入教室的同學(xué)我們不做預(yù)測(cè)。由于我們知道所有人的身高和走進(jìn)教室的次序，所以我們可以采用離線的做法來解決這樣的問題，我們用排序加鏈表的方式幫助每一個(gè)人找到在他 之前進(jìn)入教室的并且和他身高最相近的人。（第一空 2 分，其余 3 分）#include <iostream> using namespace std; #define maxn 200000#define infinity 2147483647int answermaxn, heigh

20、tmaxn, previousmaxn, nextmaxn; int rankmaxn;int n;void sort(int l, int r) int x = heightrank(l + r) / 2, i = l, j = r, temp; while (i <= j)while (heightranki < x) i+; while (heightrankj > x) j-;if ( (1) ) temp = ranki; ranki = rankj;rankj = temp;i+; j-; if (i < r) sort(i, r); if (l <

21、j) sort(l, j);int main()cin >> n;int i, higher, shorter; for (i = 1; i <= n; i+) cin >> heighti; ranki = i;sort(1, n);for (i = 1; i <= n; i+) previousranki = ranki - 1; (2) ;for (i = n; i >= 2; i-) higher = shorter = infinity; if (previousi !=0)shorter = heighti - heightprevious

22、i;if (nexti != 0) (3) ;if ( (4) )answeri = previousi;elseansweri = nexti;nextpreviousi = nexti; (5) ;for (i = 2; i <= n; i+)cout << i << ":" << answeri; return 0; 2. (交通中斷）有一個(gè)小國家，國家內(nèi)有 n 座城市和 m 條雙向的道路，每條道路連接著兩座不同的城市。其中 1 號(hào)城市為國家的首都。由于地震頻繁可能導(dǎo)致某一個(gè)城市與外界交通全部中斷。這個(gè)國家的首腦想知道，如果只

23、有第i(i>1)個(gè)城市因地震而導(dǎo)致交通中斷時(shí)，首都到多少個(gè)城市的最短路徑長度會(huì)發(fā)生改變。如果因?yàn)闊o法通過第 i 個(gè)城市而導(dǎo)致從首都出發(fā)無法到達(dá)某個(gè)城市，也認(rèn)為到達(dá)該城市的最短路徑長度改變。對(duì)于每一個(gè)城市 i，假定只有第 i 個(gè)城市與外界交通中斷，輸出有多少個(gè)城市會(huì)因此導(dǎo)致到首都的最短路徑長度改變。我們采用鄰接表的方式存儲(chǔ)圖的信息，其中 headx表示頂點(diǎn) x 的第一條 邊的編號(hào)，nexti表示第 i 條邊的下一條邊的編號(hào)，pointi表示第 i 條邊的終點(diǎn)，weighti表示第 i 條邊的長度。（第一空 2 分，其余 3 分）#include <iostream>#inclu

24、de <cstring>using namespace std; #define maxn 6000 #define maxm 100000#define infinity 2147483647int headmaxn, nextmaxm, pointmaxm, weightmaxm;int queuemaxn, distmaxn, visitmaxn;int n, m, x, y, z, total = 0, answer;void link(int x,int y,int z) total+;nexttotal = headx; headx = total; pointtota

25、l = y; weighttotal = z; total+;nexttotal = heady; heady = total; pointtotal = x; weighttotal = z;int main() int i, j, s, t; cin >> n >> m;for (i = 1; i <= m; i+) cin >> x >> y >> z; link(x, y, z);for (i = 1; i <= n; i+) disti = infinity; (1) ;queue1 = 1; visit1 = 1; s = 1;t = 1;/ 使用 spfa 求出第一個(gè)點(diǎn)到其余各點(diǎn)的最短路長度while (s <= t) x = queues % maxn;j = headx