NOIP初賽普及組C題目及答案

1、第十九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組C+語言試題競(jìng)賽時(shí)間： 2013 年 10 月 13 日 14:3016:30 選手注意：試題紙共有 9 頁，答題紙共有 2 頁，滿分 100 分。請(qǐng)?jiān)诖痤}紙上作 答，寫在試題紙上的一律無效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、 電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共 20 題，每題 1.5 分，共計(jì) 30 分；每題有且僅有一 個(gè)正確選項(xiàng)）1. 一個(gè) 32 位整型變量占用（ ） 個(gè)字節(jié)。A. 4 B. 8 C. 32 D. 1282. 二進(jìn)制數(shù) 11.01 在十進(jìn)制下是（ ）。A. 3.25 B. 4.125 C. 6.25 D. 1

2、1.1253. 下面的故事與（ ）算法有著異曲同工之妙。 從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：從前有座 山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：從前有座山，山里 有座廟，廟里有個(gè)老和尚給小和尚講故事 A.枚舉 B. 遞歸C. 貪心D. 分治4.邏輯表達(dá)式（）的值與變量A 的真假無關(guān)。A.(AV B) AB. (A V B) A BC.(A A B) V (円A A B)D. (A V B) A A A B5.將( 2, 6, 10, 17）分別存儲(chǔ)到某個(gè)地址區(qū)間為 010 的哈希表中，如果哈希函數(shù) h（x） =（ ），將不會(huì)產(chǎn)生沖突，其中 a mod b 表示 a

3、除以b 的余數(shù)。C.2x mod 11 D. | V2| mod 11，其中V X表示V X下取整6.在十六進(jìn)制表示法中，字母A 相當(dāng)于十進(jìn)制中的（）。A.9 B. 10 C. 15 D. 167.下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是（）。A.哈希表 B. 棧 C. 隊(duì)列 D.二叉樹8.在 Windows 資源管理器中，用鼠標(biāo)右鍵單擊一個(gè)文件時(shí)，會(huì)出現(xiàn)一個(gè)名A. x mod 11B. x2 mod 11為“復(fù)制”的操作選項(xiàng)，它的意思是（ ）。A. 用剪切板中的文件替換該文件B. 在該文件所在文件夾中，將該文件克隆一份C. 將該文件復(fù)制到剪切板，并保留原文件D. 將該文件復(fù)制到剪切板，并刪除原文件9. 已知

4、一棵二叉樹有 10 個(gè)節(jié)點(diǎn)，則其中至多有（ ）個(gè)節(jié)點(diǎn)有 2 個(gè)子節(jié) 點(diǎn)。A. 4 B. 5 C. 6 D. 710. 在一個(gè)無向圖中，如果任意兩點(diǎn)之間都存在路徑相連，則稱其為連通 圖。下圖是一個(gè)有 4 個(gè)頂點(diǎn)、 6 條邊的連通圖。若要使它不再是連通圖， 至少要?jiǎng)h去其中的（ ）條邊。A. 1 B. 2 C. 3 D. 411. 二叉樹的（ ）第一個(gè)訪問的節(jié)點(diǎn)是根節(jié)點(diǎn)。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 以上都是12. 以 A0 作為起點(diǎn)，對(duì)下面的無向圖進(jìn)行深度優(yōu)先遍歷時(shí)，遍歷順序不可 能是（ ）。A. A0, A1 , A2, A3 B.A0, A1, A3, A2 C. A0

5、, A2, A1, A3D. A0,A3, A1, A213. IPv4 協(xié)議使用 32 位地址，隨著其不斷被分配，地址資源日趨枯竭。因 此，它正逐漸被使用（ ）位地址的 IPv6 協(xié)議所取代。A. 40 B. 48 C. 64 D. 12814. （ ）的 平均時(shí)間復(fù)雜度為 O（n log n） ，其中 n 是待排序的元 素個(gè)數(shù)。A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基數(shù)排序15. 下面是根據(jù)歐幾里得算法編寫的函數(shù)，它所計(jì)算的是 a 和 b 的 （ ）。int euclid（int a, int b）if （b = 0） return a;elsereturn euclid（

6、b, a % b）;A. 最大公共質(zhì)因子 B. 最小公共質(zhì)因子C. 最大公約數(shù) D. 最小公倍數(shù)16. 通常在搜索引擎中，對(duì)某個(gè)關(guān)鍵詞加上雙引號(hào)表示（ ）。A. 排除關(guān)鍵詞，不顯示任何包含該關(guān)鍵詞的結(jié)果B. 將關(guān)鍵詞分解，在搜索結(jié)果中必須包含其中的一部分C. 精確搜索，只顯示包含整個(gè)關(guān)鍵詞的結(jié)果D. 站內(nèi)搜索，只顯示關(guān)鍵詞所指向網(wǎng)站的內(nèi)容17. 中國(guó)的國(guó)家頂級(jí)域名是（ ）A. .cnB. .chC. .chnD. .china18. 把 64 位非零浮點(diǎn)數(shù)強(qiáng)制轉(zhuǎn)換成 32 位浮點(diǎn)數(shù)后， 不可能 （）。A. 大于原數(shù) B. 小于原數(shù)C. 等于原數(shù) D. 與原數(shù)符號(hào)相反19. 下列程序中，正確計(jì)算

7、 1, 2, ?, 100 這 100 個(gè)自然數(shù)之和sum（ 初始值為 0）的是（ ）。20. CCF NOIP 復(fù)賽全國(guó)統(tǒng)一評(píng)測(cè)時(shí)使用的系統(tǒng)軟件是（ ）。A. NOI Windows B. NOI Linux C. NOI Mac OS D. NOI DOS二、問題求解（共 2 題，每題 5 分，共計(jì) 10 分；每題全部答對(duì)得 5 分，沒有部分分）1. 7 個(gè)同學(xué)圍坐一圈，要選 2 個(gè)不相鄰的作為代表，有 種不同的選法。2. 某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是 n 個(gè)數(shù) s1, s2, ? , sn ，均為 0 或 1 。該系統(tǒng)每次隨機(jī)生成 n 個(gè)數(shù) a1, a2, ? ,

8、 an，均為0 或1，請(qǐng)用戶回答 （sial + s2a2 +?+ snan） 除以2 的余數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為，即使問答的 過程被泄露，也無助于破解密碼因?yàn)橛脩舨]有直接發(fā)送密碼。 然而，事與愿違。例如，當(dāng) n = 4 時(shí)，有人竊聽了以下 5 次問答： 就破解出了密碼 s1 = ， s2 = ，s3= ， s4 = 。三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. #include using namespace std;int a, b;cinab; couta+b=a+bendl; 輸入： 3 5 輸出： 2. #include us

9、ing namespace std; int main() int a, b, u, i, num; cinabu; num = 0;for (i = a; i = b; i+) if (i % u) = 0) num+;coutnumendl; return 0; 輸入： 1 100 15 輸出： 3. #include using namespace std; int main() int n, f, i, left, right, middle, aSIZE; cinnf;for (i = 1; i ai; left = 1;right = n;do middle = (left + r

10、ight) / 2;if (f = amiddle) right = middle;elseleft = middle + 1; while (left right);coutleftendl;return 0;輸入：12 172 4 6 9 11 15 17 18 19 20 21 25 輸出： #include using namespace std;int main()int heightSIZE, numSIZE, n, ans;cinn;for (int i = 0; i heighti; numi = 1;for (int j = 0; j i; j+)if (heightj =

11、numi) numi = numj+1;ans = 0;for (int i = 0; i ans) ans = numi;coutansendl;輸入：62 5 3 11 12 4輸出： 四、完善程序(共 2 題，每題 14 分，共計(jì) 28 分)1. (序列重排) 全局?jǐn)?shù)組變量 a 定義如下：const int SIZE = 100;int aSIZE, n;它記錄著一個(gè)長(zhǎng)度為 n 的序列 a1, a2, ? , an ?，F(xiàn)在需要一個(gè)函數(shù)，以整數(shù) p (1 p n)為參數(shù)，實(shí)現(xiàn)如下功能：將序列a的前p個(gè)數(shù)與后n - p個(gè)數(shù)對(duì)調(diào)，且不改變這 p個(gè)數(shù)(或 n - p個(gè) 數(shù))之間的相對(duì)位置。例如，

12、長(zhǎng)度為 5 的序列 1, 2, 3, 4, 5 ，當(dāng) p = 2 時(shí)重排結(jié)果為 3, 4, 5, 1, 2。有一種樸素的算法可以實(shí)現(xiàn)這一需求，其時(shí)間復(fù)雜度為 O( n) 、空間復(fù)雜度 為 O(n)：void swap1(int p)int i, j, bSIZE;for (i =1; i =p; i+)b(1) = ai;/ ( 3分)for (i =p + 1;= n; i+)bi- p =(2) ; /( 3 分)for (i =1; i =(3) ; i+)/ ( 2分)ai = bi;我們也可以用時(shí)間換空間，使用時(shí)間復(fù)雜度為0(n2)、空間復(fù)雜度為 0(1)的算法：void swap2

13、(int p)for (i = p + 1; i =(4) ; j-) / ( 3 分)aj = aj - 1;(5) = temp; / ( 3 分)2. (二叉查找樹) 二叉查找樹具有如下性質(zhì)： 每個(gè)節(jié)點(diǎn)的值都大于其左 子樹上所有節(jié)點(diǎn)的 值、小于其右子樹上所有節(jié)點(diǎn)的值。試判斷一棵樹是否 為二叉查找樹。輸入的第一行包含一個(gè)整數(shù) n ，表示這棵樹有 n 個(gè)頂點(diǎn)， 編號(hào)分別為 1, 2, ? , n ，其 中編號(hào)為 1 的為根結(jié)點(diǎn)。之后的第 i 行有三個(gè)數(shù) value, left_child , right_child ，分別表示該節(jié)點(diǎn)關(guān)鍵字的值、左子節(jié)點(diǎn)的編 號(hào)、右子節(jié)點(diǎn)的編號(hào)；如果不存在左子

14、節(jié)點(diǎn)或右子節(jié)點(diǎn)，則用 0 代替。輸 出 1 表示這棵樹是二叉查找樹，輸出 0 則表示不是。#include using namespace std;const int SIZE = 100;const int INFINITE = 1000000;struct nodeint left_child, right_child, value;node aSIZE;int is_bst(int root, int lower_bound, int upper_bound)int cur;if (root = 0)return 1;cur = aroot.value;&1) &if (cur lowe

15、r_bound) & ( (1) )(is_bst(aroot.left_child, lower_bound, cur)(is_bst( (2) , (3) , (4) ) = 1)return 1;return 0;int main()int i, n; cinn;for (i = 1; i ai.valueai.left_childai.right_child;coutis_bst( (5) , -INFINITE, INFINITE)endl;return 0;第十九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組參考答案一、單項(xiàng)選擇題(共 20 題，每題 1.5 分，共計(jì) 30 分)1 234567 8910A ABCDBB CAC11 121314151617 181920A A D A C C A D A B二、問題求解（共 2 題，每題 5 分，共計(jì) 10 分；每題全部答對(duì)得 5 分，沒有 部分分）1. 142. s1 = 0 ，s2 = 1 ， s3 = 1