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

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

2、尚講故事：從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事'枚舉B.遞歸C.貪心D.分治邏輯表達(dá)式（）的值與變量A的真假無關(guān)。4. A.（AVB）人円AB.（AVB）人円BC.（AAB）V（円AAB）D.（AVB）人円AAB將（2,6,10,17）分別存儲到某個地址區(qū)間為010的哈希表中，如果哈希函數(shù)h（x）=（），將不會產(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.隊列D.二叉樹在資源管理器中，用鼠標(biāo)右鍵單擊一個文件時，會出現(xiàn)一個名為“復(fù)制”的操作選項，它的意思是（）。6. 用剪切板中的文件替換該文件在該文件所在文件夾中，將該文件克隆一份將該文件復(fù)制到剪切板，并保留原文件將該文件復(fù)制到剪切板，并刪除原文件已知一棵二叉樹有10個節(jié)點，則其中至多有（）個節(jié)點有2個子節(jié)點。7. A.4B.5C.6D.7在一個無向圖中，如果任意兩點之間都存在路徑相連，則稱其為連通圖。下圖是一個有4個頂點、6條邊的連通圖。若要使它不再是連通圖，至少要刪去其中的（）條邊。A.1B.2D.4C.38. 二叉樹的（）第一個訪問的節(jié)點

4、是根節(jié)點。A.先序遍歷B.中序遍歷C.后序遍歷D.以上都是以A0作為起點，對下面的無向圖進(jìn)行深度優(yōu)先遍歷時，遍歷順序不可能是（）?！?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（）的平均時間復(fù)雜度為O（nn），其中n是待排序的元素個數(shù)。A.快速排序B.插入排序C.冒泡排序D.基數(shù)排序下面是根據(jù)歐幾里得算法編寫的函數(shù)，它所計算的是a和b的（）。（a,b）（b0）a;(b,a%b);10. C.

5、最大公約數(shù)D.最小公倍數(shù)通常在搜索引擎中，對某個關(guān)鍵詞加上雙引號表示（）。11. 排除關(guān)鍵詞，不顯示任何包含該關(guān)鍵詞的結(jié)果將關(guān)鍵詞分解，在搜索結(jié)果中必須包含其中的一部分精確搜索，只顯示包含整個關(guān)鍵詞的結(jié)果站內(nèi)搜索，只顯示關(guān)鍵詞所指向網(wǎng)站的內(nèi)容中國的國家頂級域名是（）。A.B.C.D.12. 把64位非零浮點數(shù)強制轉(zhuǎn)換成32位浮點數(shù)后，不可能（）。A.大于原數(shù)B.小于原數(shù)C.等于原數(shù)D.與原數(shù)符號相反下列程序中，正確計算1,2,?,100這100個自然數(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ù)賽全國統(tǒng)一評測時使用的系統(tǒng)軟件是（）A.B.C.D.二、問題求解（共2題，每題5分，共計10分；每題全部答對得1. 5分，沒有部分分）7個同學(xué)圍坐一圈，要選2個不相鄰的作為代表，有種不同的選法。某系統(tǒng)自稱使用了一種防竊聽的方式驗證用戶密碼。密碼是n個數(shù)s1,s2,?,，均為0或1。該系統(tǒng)每次隨機生成n個數(shù)a1,a2,?,，均為0或1，請用戶回答（sial+s2a2+?+）除以2的余數(shù)。如果多次的回答總是正確，即認(rèn)為掌握密碼。該系統(tǒng)認(rèn)為，即使問答的過程被泄露，也無助于破

7、解密碼一一因為用戶并沒有直接發(fā)送密碼。然而，事與愿違。例如，當(dāng)n=4時，有人竊聽了以下5次問答：惡統(tǒng)主或的n個數(shù)攀性密碼的用戶的回答ai34111001200110301100411100510000就破解出了密碼s1=，s2=，s3=，s4=。三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計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分，共計28分)1.(序列重排)全局?jǐn)?shù)組變量a定義如下：=100;a,n;它記錄著一個長度為n的序列a1,a2,?,an?，F(xiàn)在需要一個函數(shù)，以整數(shù)p(1<p<n)為參數(shù)，實現(xiàn)如下功能：將序列a的前p個數(shù)與后n-p個數(shù)對調(diào)，且不改變這p個數(shù)(或n-p個數(shù))之間的相對位置。例如，長度為5的序列1,2,3,4,5，當(dāng)p=2時重排結(jié)果為3,4,5,1,2。有一種樸素的算法可以實現(xiàn)這一需求，其時間復(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;我們也可以用時間換空間，使用時間復(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ì)：每個節(jié)點的值都大于其左子樹上所有節(jié)點的值、小于其右子樹上所有節(jié)點的值。試判斷一棵樹是否為二叉查找樹。輸入的第一行包含一個整數(shù)n，表示這棵樹有

11、n個頂點，編號分別為1,2,?,n，其中編號為1的為根結(jié)點。之后的第i行有三個數(shù),，分別表示該節(jié)點關(guān)鍵字的值、左子節(jié)點的編號、右子節(jié)點的編號；如果不存在左子節(jié)點或右子節(jié)點，則用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;第十九屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽普及組參考答案一、單項選擇題（共20題，每題1.5分，共計30分）12345678910AABCDBBCAC11121314151617181920AADACCADAB二、問題求解（共2題，每題5分，共計10分；每題全部答對得5分，沒有部分分）1.14