NOIP2013初賽普及組C++題目及答案

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

2、尚講故事：從前有座山，山里有座廟，廟里有個(gè)老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個(gè)老和尚給小和尚講故事'枚舉B.遞歸C.貪心D.分治邏輯表達(dá)式（）的值與變量A的真假無(wú)關(guān)。4. A.（AVB）人円AB.（AVB）人円BC.（AAB）V（円AAB）D.（AVB）人円AAB將（2,6,10,17）分別存儲(chǔ)到某個(gè)地址區(qū)間為010的哈希表中，如果哈希函數(shù)h（x）=（），將不會(huì)產(chǎn)生沖突，其中ab表示a除以b的余數(shù)。A.x11B. x2115. 2x11D.|V2|11，其中"X表示"X下取整在十六進(jìn)制表示法中，字母A相當(dāng)于十進(jìn)制中的（）A.9B.10C.15D.

3、16下圖中所使用的數(shù)據(jù)結(jié)構(gòu)是（）。A.哈希表B.棧C.隊(duì)列D.二叉樹在資源管理器中，用鼠標(biāo)右鍵單擊一個(gè)文件時(shí)，會(huì)出現(xiàn)一個(gè)名為“復(fù)制”的操作選項(xiàng)，它的意思是（）。6. 用剪切板中的文件替換該文件在該文件所在文件夾中，將該文件克隆一份將該文件復(fù)制到剪切板，并保留原文件將該文件復(fù)制到剪切板，并刪除原文件已知一棵二叉樹有10個(gè)節(jié)點(diǎn)，則其中至多有（）個(gè)節(jié)點(diǎn)有2個(gè)子節(jié)點(diǎn)。7. A.4B.5C.6D.7在一個(gè)無(wú)向圖中，如果任意兩點(diǎn)之間都存在路徑相連，則稱其為連通圖。下圖是一個(gè)有4個(gè)頂點(diǎn)、6條邊的連通圖。若要使它不再是連通圖，至少要?jiǎng)h去其中的（）條邊。A.1B.2D.4C.38. 二叉樹的（）第一個(gè)訪問的節(jié)點(diǎn)

4、是根節(jié)點(diǎn)。A.先序遍歷B.中序遍歷C.后序遍歷D.以上都是以A0作為起點(diǎn)，對(duì)下面的無(wú)向圖進(jìn)行深度優(yōu)先遍歷時(shí)，遍歷順序不可能是（）?！?A.AO,A1,A2,A3B.AO,A1,A3,A2C.AO,A2,A1,A3D.9. AO,A3,A1,A24協(xié)議使用32位地址，隨著其不斷被分配，地址資源日趨枯竭。因此，它正逐漸被使用（）位地址的6協(xié)議所取代。A.40B.48C.64D.128（）的平均時(shí)間復(fù)雜度為O（nn），其中n是待排序的元素個(gè)數(shù)。A.快速排序B.插入排序C.冒泡排序D.基數(shù)排序下面是根據(jù)歐幾里得算法編寫的函數(shù)，它所計(jì)算的是a和b的（）。（a,b）（b0）a;(b,a%b);10. C.

5、最大公約數(shù)D.最小公倍數(shù)通常在搜索引擎中，對(duì)某個(gè)關(guān)鍵詞加上雙引號(hào)表示（）。11. 排除關(guān)鍵詞，不顯示任何包含該關(guān)鍵詞的結(jié)果將關(guān)鍵詞分解，在搜索結(jié)果中必須包含其中的一部分精確搜索，只顯示包含整個(gè)關(guān)鍵詞的結(jié)果站內(nèi)搜索，只顯示關(guān)鍵詞所指向網(wǎng)站的內(nèi)容中國(guó)的國(guó)家頂級(jí)域名是（）。A.B.C.D.12. 把64位非零浮點(diǎn)數(shù)強(qiáng)制轉(zhuǎn)換成32位浮點(diǎn)數(shù)后，不可能（）。A.大于原數(shù)B.小于原數(shù)C.等于原數(shù)D.與原數(shù)符號(hào)相反下列程序中，正確計(jì)算1,2,?,100這100個(gè)自然數(shù)之和（初始值為0）的是（）A.i=1;B.i=1;dcsum+-i;sum+=i;I+：i+;while(i<=100);while(1&

6、gt;100；C.i=1;D.while(i<100)while(i100)sum4=i;sum+=i;i+:4；20.復(fù)賽全國(guó)統(tǒng)一評(píng)測(cè)時(shí)使用的系統(tǒng)軟件是（）A.B.C.D.二、問題求解（共2題，每題5分，共計(jì)10分；每題全部答對(duì)得1. 5分，沒有部分分）7個(gè)同學(xué)圍坐一圈，要選2個(gè)不相鄰的作為代表，有種不同的選法。某系統(tǒng)自稱使用了一種防竊聽的方式驗(yàn)證用戶密碼。密碼是n個(gè)數(shù)s1,s2,?,，均為0或1。該系統(tǒng)每次隨機(jī)生成n個(gè)數(shù)a1,a2,?,，均為0或1，請(qǐng)用戶回答（sial+s2a2+?+）除以2的余數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為，即使問答的過(guò)程被泄露，也無(wú)助于破

7、解密碼一一因?yàn)橛脩舨]有直接發(fā)送密碼。然而，事與愿違。例如，當(dāng)n=4時(shí)，有人竊聽了以下5次問答：惡統(tǒng)主或的n個(gè)數(shù)攀性密碼的用戶的回答ai34111001200110301100411100510000就破解出了密碼s1=，s2=，s3=，s4=。三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）<>()a,b;>>a>>b;<<a<<"+"<<b<<"="<<<<輸入：35輸出：1. <>J()a,b,u,i,;>>a>

8、;>b>>u;=0;(i=a;i<=b;)(i%u)0)J<<<<0;輸入：110015輸出：2. <>J()=100;n,f,i,a;>>n>>f;(i=1;i<=n;)>>ai;=1;=n;=(+)/2;(f<=a)一J=+1;(<);<<<<0;輸入：121724691115171819202125輸出：4.<>()=100;,n,;>>n;(i=0;i<n;)>>i;i=1;(j=0;j<i;)(j&l

9、t;i)(j>=i)i=j+1;=0;(i=0;i<n;)(i>)=i;<<<<輸入：625311124輸出：四、完善程序(共2題，每題14分，共計(jì)28分)1.(序列重排)全局?jǐn)?shù)組變量a定義如下：=100;a,n;它記錄著一個(gè)長(zhǎng)度為n的序列a1,a2,?,an。現(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ì)位置。例如，長(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)

10、、空間復(fù)雜度為O(n)：1(p)i,j,b;(i=1;i<=p;)b(1)=ai;(3分)(i=p+1;i<=n;)bi-p=(2);(3分)(i=1;i<=(3);)(2分)ai=bi;我們也可以用時(shí)間換空間，使用時(shí)間復(fù)雜度為O(n2)、空間復(fù)雜度為O(1)的算法：2(p)i,j,;(i=p+1;i<=n;)=ai;(j=i;j>=(4);)(3分)aj=aj-1;(5)=;(3分)2.(二叉查找樹)二叉查找樹具有如下性質(zhì)：每個(gè)節(jié)點(diǎn)的值都大于其左子樹上所有節(jié)點(diǎn)的值、小于其右子樹上所有節(jié)點(diǎn)的值。試判斷一棵樹是否為二叉查找樹。輸入的第一行包含一個(gè)整數(shù)n，表示這棵樹有

11、n個(gè)頂點(diǎn)，編號(hào)分別為1,2,?,n，其中編號(hào)為1的為根結(jié)點(diǎn)。之后的第i行有三個(gè)數(shù),，分別表示該節(jié)點(diǎn)關(guān)鍵字的值、左子節(jié)點(diǎn)的編號(hào)、右子節(jié)點(diǎn)的編號(hào)；如果不存在左子節(jié)點(diǎn)或右子節(jié)點(diǎn)，則用0代替。輸出1表示這棵樹是二叉查找樹，輸出0則表示不是。<>=100;=1000000;JJa;(,)(0)1;=a;(>)(1)(a,)1)(2),(3),(4)1)1;0;()i,n;>>n;(i=1;i<=n;)>>ai>>ai>>ai;<<(5),)<<0;第十九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組參考答案一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分）12345678910AABCDBBCAC11121314151617181920AADACCADAB二、問題求解（共2題，每題5分，共計(jì)10分；每題全部答對(duì)得5分，沒有部分分）1.14