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

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

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

3、的區(qū)別的是（）。A.顯示器不同B.硬盤大小不同C.尋址空間不同D.輸入法不同10.以下關于字符串的判定語句中正確的是（）。A.字符串是一種特殊的線性表B.串的長度必須大于零C.字符串不可以用數(shù)組來表示D.空格字符組成的串就是空串11. 一棵二叉樹如右圖所示，若采用順序存儲結構，即用一 維數(shù)組元素存儲該二叉樹中的結點（根結點的下標為 1， 若某結點的下標為 i ，則其左孩子位于下標 2i 處、右孩 子位于下標(2i+1)處），則圖中所有結點的最大下標為（ ）。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 值的功能等價的賦值語句是（）。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;程序運行后的輸出結果是（）。A.2,2B.2,3C.3,2D.3,314. 給定含有 n 個不同的數(shù)的數(shù)組

5、L=。如果 L 中存在 x（i1 i n） 使得 x1 x2 . xi -1 xi+1 . xn ， 則稱 L 是單峰的，并稱 xi 是 L 的“峰頂”?，F(xiàn)在已知 L 是單峰的，請把 a-c 三行代碼補全到算法中使得算法 正確找到 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.設簡單無向圖 G 有 16 條邊且每個頂點的度數(shù)都是 2，則圖 G 有（ ）個頂點。A.10B.12C.8D.1616.有 7 個一模一樣的蘋果，放到 3 個一樣的盤子中，一共有（ ）種放法。A.7B.8C.21D.3717. 下圖表示一個果園灌溉系統(tǒng)，有 A、B、C、D 四個閥門，每個閥門可以打開 或關上，所有管道粗細相同，以下設置閥門的方法中，可以讓果樹澆上水的是（ ）。有水有水果樹A. B 打開，其他都關上B.AB 都打開，CD 都關上C. A 打開，其他都關上D.D 打開，其他都關上18. Lucia 和她的朋友以及朋友的朋友都在某社交網(wǎng)站上注冊了賬號。下圖是他 們之間的關

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

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

9、空 2 分，第二空 3 分）1. 從一個 44 的棋盤（不可旋轉）中選取不在同一行也不在同一列上的兩個 方格，共有_種方法。2. 約定二叉樹的根節(jié)點高度為1。一棵結點數(shù)為 2016的二叉樹最少有_個葉子結點；一棵結點數(shù)為 2016的二叉樹最小的高度值是_。三、閱讀程序寫結果（共 4 題，每題 8 分，共計 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 分，共計 28 分）1. （讀入整數(shù)）請完善下面的程序，使得程序能夠讀入兩個 int

13、范圍內的整數(shù)， 并將這兩個整數(shù)分別輸出，每行一個。（第一、五空 2.5 分，其余 3 分）輸入的整數(shù)之間和前后只會出現(xiàn)空格或者回車。輸入數(shù)據(jù)保證合法。例如：輸入：123 -789輸出：123-789#include using namespace std;int readint() int num = 0;/ 存儲讀取到的整數(shù)int negative = 0;/ 負數(shù)標識char c;/ 存儲當前讀取到的字符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. （郊游活動）有 n 名同學參加學校組織的郊游活動，已知學校給這 n 名同學 的郊游總經費為 A 元，與此同時第 i 位同學自己攜帶了 Mi 元。為了方便郊 游，活動地點提供 B(n)輛自行車供人租用，租用第 j 輛自行車的價格為 Cj 元，每位同學可以使用自己攜帶的錢或者學校的郊游經費，為了方便

15、賬務管 理，每位同學只能為自己租用自行車，且不會借錢給他人，他們想知道最多 有多少位同學能夠租用到自行車。（第四、五空 2.5 分，其余 3 分）本題采用二分法。對于區(qū)間l, r，我們取中間點 mid 并判斷租用到自行 車的人數(shù)能否達到 mid。判斷的過程是利用貪心算法實現(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 =