第二十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

1、第二十二屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組 C+語(yǔ)言試題競(jìng)賽時(shí)間：2016 年 10 月 22 日 14:3016:30一、單項(xiàng)選擇題（共 20 題，每題 1.5 分，共計(jì) 30 分；每題有且僅有一個(gè)正確選項(xiàng)）1. 以下不是微軟公司出品的軟件是（ ）。A.PowerpointB.WordC.ExcelD.Acrobat Reader2.如果 256 種顏色用二進(jìn)制編碼來(lái)表示，至少需要（）位。A.6B. 7C.8D. 93. 以下不屬于無(wú)線通信技術(shù)的是（ ）。A.藍(lán)牙B.WiFiC.GPRSD.以太網(wǎng)4.以下不是 CPU 生產(chǎn)廠商的是（）。A.IntelB.AMDC.MicrosoftD.

2、IBM5.以下不是存儲(chǔ)設(shè)備的是（）。A.光盤(pán)B.磁盤(pán)C.固態(tài)硬盤(pán)D.鼠標(biāo)6. 如果開(kāi)始時(shí)計(jì)算機(jī)處于小寫(xiě)輸入狀態(tài)，現(xiàn)在有一只小老鼠反復(fù)按照CapsLock、 字母鍵 A、字母鍵 S 和字母鍵 D 的順序循環(huán)按鍵，即 CapsLock、A、S、D、CapsLock、A、S、D、，屏幕上輸出的第 81 個(gè)字符是字母（ ）。A.AB. SC.DD.a7.二進(jìn)制數(shù) 00101100 和 00010101 的和是（ ）。A.00101000B.01000001C.01000100D.001110008.與二進(jìn)制小數(shù) 0.1 相等的八進(jìn)制數(shù)是（）。A.0.8C.0.29.以下是 32 位機(jī)器和 64 位機(jī)器

3、的區(qū)別的是（）。A.顯示器不同B.硬盤(pán)大小不同C.尋址空間不同D.輸入法不同10.以下關(guān)于字符串的判定語(yǔ)句中正確的是（）。A.字符串是一種特殊的線性表B.串的長(zhǎng)度必須大于零C.字符串不可以用數(shù)組來(lái)表示D.空格字符組成的串就是空串11. 一棵二叉樹(shù)如右圖所示，若采用順序存儲(chǔ)結(jié)構(gòu)，即用一 維數(shù)組元素存儲(chǔ)該二叉樹(shù)中的結(jié)點(diǎn)（根結(jié)點(diǎn)的下標(biāo)為 1， 若某結(jié)點(diǎn)的下標(biāo)為 i ，則其左孩子位于下標(biāo) 2i 處、右孩 子位于下標(biāo)(2i+1)處），則圖中所有結(jié)點(diǎn)的最大下標(biāo)為（ ）。A.6B.10C.12D.1512. 若有如下程序段，其中 s、a、b、c 均已定義為整型變量，且 a、c 均已賦值 （c 大于 0）。s

4、 = a;for (b = 1; b = c; b+) s= s + 1;則與上述程序段修改 s 值的功能等價(jià)的賦值語(yǔ)句是（）。A.s = a + b;B.s = a + c;C.s = s + c;D.s = b + c;13. 有以下程序：#include using namespace 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é)果是（）。A.2,2B.2,3C.3,2D.3,314. 給定含有 n 個(gè)不同的數(shù)的數(shù)組

5、L=。如果 L 中存在 x（i1 i n） 使得 x1 x2 . xi -1 xi+1 . xn ， 則稱(chēng) L 是單峰的，并稱(chēng) xi 是 L 的“峰頂”?，F(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 Lk-1 and Lk Lk+13. then _4. else if Lk Lk-1 and Lk Lk+15. then _6. else _正確的填空順序是（）。A.c, a, bB.c, b, aC.a, b, cD.b, a

6、, c15.設(shè)簡(jiǎn)單無(wú)向圖 G 有 16 條邊且每個(gè)頂點(diǎn)的度數(shù)都是 2，則圖 G 有（ ）個(gè)頂點(diǎn)。A.10B.12C.8D.1616.有 7 個(gè)一模一樣的蘋(píng)果，放到 3 個(gè)一樣的盤(pán)子中，一共有（ ）種放法。A.7B.8C.21D.3717. 下圖表示一個(gè)果園灌溉系統(tǒng)，有 A、B、C、D 四個(gè)閥門(mén)，每個(gè)閥門(mén)可以打開(kāi) 或關(guān)上，所有管道粗細(xì)相同，以下設(shè)置閥門(mén)的方法中，可以讓果樹(shù)澆上水的是（ ）。有水有水果樹(shù)A. B 打開(kāi)，其他都關(guān)上B.AB 都打開(kāi)，CD 都關(guān)上C. A 打開(kāi)，其他都關(guān)上D.D 打開(kāi)，其他都關(guān)上18. Lucia 和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊(cè)了賬號(hào)。下圖是他 們之間的關(guān)

7、系圖，兩個(gè)人之間有邊相連代表這兩個(gè)人是朋友，沒(méi)有邊相連代 表不是朋友。這個(gè)社交網(wǎng)站的規(guī)則是：如果某人 A 向他（她）的朋友 B 分 享了某張照片，那么 B 就可以對(duì)該照片進(jìn)行評(píng)論；如果 B 評(píng)論了該照片，那 么他（她）的所有朋友都可以看見(jiàn)這個(gè)評(píng)論以及被評(píng)論的照片，但是不能對(duì) 該照片進(jìn)行評(píng)論（除非 A 也向他（她）分享了該照片）?，F(xiàn)在 Lucia 已經(jīng)上 傳了一張照片，但是她不想讓 Jacob 看見(jiàn)這張照片，那么她可以向以下朋友（ ）分享該照片。A.Dana, Michael, EveB.Dana, Eve, MonicaC.Michael, Eve, JacobD.Micheal, Peter

8、, Monica19. 周末小明和爸爸媽媽三個(gè)人一起想動(dòng)手做三道菜。小明負(fù)責(zé)洗菜、爸爸負(fù)責(zé) 切菜、媽媽負(fù)責(zé)炒菜。假設(shè)做每道菜的順序都是：先洗菜 10 分鐘，然后切 菜 10 分鐘，最后炒菜 10 分鐘。那么做一道菜需要 30 分鐘。注意：兩道不 同的菜的相同步驟不可以同時(shí)進(jìn)行。例如第一道菜和第二道的菜不能同時(shí)洗， 也不能同時(shí)切。那么做完三道菜的最短時(shí)間需要（ ）分鐘。A.90B.60C.50D.4020.參加 NOI 比賽，以下不能帶入考場(chǎng)的是（）。A.鋼筆B.適量的衣服C.U 盤(pán)D.鉛筆二、問(wèn)題求解（共 2 題，每題 5 分，共計(jì) 10 分；第一題全部答對(duì)得 5 分，沒(méi)有 部分分；第二題第一

9、空 2 分，第二空 3 分）1. 從一個(gè) 44 的棋盤(pán)（不可旋轉(zhuǎn)）中選取不在同一行也不在同一列上的兩個(gè) 方格，共有_種方法。2. 約定二叉樹(shù)的根節(jié)點(diǎn)高度為1。一棵結(jié)點(diǎn)數(shù)為 2016的二叉樹(shù)最少有_個(gè)葉子結(jié)點(diǎn)；一棵結(jié)點(diǎn)數(shù)為 2016的二叉樹(shù)最小的高度值是_。三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. #include using namespace std; int main() int max, min, sum, count = 0; int tmp;cin tmp; if (tmp = 0)return 0;max = min = sum = tmp; count+

10、;while (tmp != 0) cin tmp;if (tmp != 0) sum += tmp;count+; if (tmp max) max = tmp; if (tmp min) min = tmp;cout max , min , sum / count endl; return 0;輸入: 1 2 3 4 5 6 0 7 輸出：_ _2. #include using namespace std;int main() int i = 100, x = 0, y = 0; while (i 0) i-;x = i % 8; if (x = 1) y+;cout y endl; r

11、eturn 0;輸出：_ _3. #include 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; api = apj; apj = t; pi+;pj-;for (i = 0; i 6; i+) cout ai ,;cout endl; return 0;輸出：_ _4. #include using namespace std;int main() int i, length1, length2; string

12、s1, s2;s1 = I have a dream.;s2 = I Have A Dream.; length1 = s1.size(); length2 = s2.size();for (i = 0; i = a & s1i = z) s1i -= a - A;for (i = 0; i = a & s2i = z) s2i -= a - A;if (s1 = s2)cout = s2)cout endl; elsecout endl; return 0;輸出：_ _四、完善程序（共 2 題，每題 14 分，共計(jì) 28 分）1. （讀入整數(shù)）請(qǐng)完善下面的程序，使得程序能夠讀入兩個(gè) int

13、范圍內(nèi)的整數(shù)， 并將這兩個(gè)整數(shù)分別輸出，每行一個(gè)。（第一、五空 2.5 分，其余 3 分）輸入的整數(shù)之間和前后只會(huì)出現(xiàn)空格或者回車(chē)。輸入數(shù)據(jù)保證合法。例如：輸入：123 -789輸出：123-789#include using namespace std;int readint() int num = 0;/ 存儲(chǔ)讀取到的整數(shù)int negative = 0;/ 負(fù)數(shù)標(biāo)識(shí)char c;/ 存儲(chǔ)當(dāng)前讀取到的字符c = cin.get();while (c 9) & c != -) c = (1) ;if (c = -) negative = 1; Else (2) ; c = cin.get()

14、; While ( (3) ) (4) ; c = cin.get();if (negative = 1) (5) ; return num;int main() int a, b;a = readint(); b = readint();cout a endl b endl; return 0;2. （郊游活動(dòng)）有 n 名同學(xué)參加學(xué)校組織的郊游活動(dòng)，已知學(xué)校給這 n 名同學(xué) 的郊游總經(jīng)費(fèi)為 A 元，與此同時(shí)第 i 位同學(xué)自己攜帶了 Mi 元。為了方便郊 游，活動(dòng)地點(diǎn)提供 B(n)輛自行車(chē)供人租用，租用第 j 輛自行車(chē)的價(jià)格為 Cj 元，每位同學(xué)可以使用自己攜帶的錢(qián)或者學(xué)校的郊游經(jīng)費(fèi)，為了方便

15、賬務(wù)管 理，每位同學(xué)只能為自己租用自行車(chē)，且不會(huì)借錢(qián)給他人，他們想知道最多 有多少位同學(xué)能夠租用到自行車(chē)。（第四、五空 2.5 分，其余 3 分）本題采用二分法。對(duì)于區(qū)間l, r，我們?nèi)≈虚g點(diǎn) mid 并判斷租用到自行 車(chē)的人數(shù)能否達(dá)到 mid。判斷的過(guò)程是利用貪心算法實(shí)現(xiàn)的。#include using namespace std; #define MAXN 1000000int n, B, A, MMAXN, CMAXN, l, r, ans, mid; bool check(int nn) int count = 0, i, j;i= (1) ;j=1;while (i = n) if ( (2) )count += Cj - Mi; i+; j+; return (3) ;void sort(int a, int l, int r) int i = l, j = r, x = a(l + r) / 2, y; while (i = j) while (ai x) j-; if (i =