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

1、NOIP2011第十七屆信息學(xué)奧林匹克競賽初賽（普及組C+語言二小時完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分。每題有且僅有一個正確選項(xiàng)。）1 在二進(jìn)制下，1011001 +（）= 1100110。A 1011B 1101C 1010D 11112.字符“ 0”的ASCII碼為48，則字符“ 9”的ASCII碼為（）。A 39B 57C 120D 視具體的計(jì)算機(jī)而定3 一片容量為8G的SD卡能儲存大約（ ）張大小為2MB的數(shù)碼照片。A 1600B 2000C 4000D 160004 摩爾定律（Moores law）是由英特爾

2、創(chuàng)始人之一戈登摩爾（Gordon Moor）提出來的。根據(jù)摩爾定律，在過去幾十年一級在可預(yù)測的未來紀(jì)念，單塊集成電驢的集成度大約每（）個月翻一番。A 1B 6C 18D .365 無向完全圖是圖中每對頂點(diǎn)之間都恰好有一條邊的簡單圖。已知無向完全圖G有7個頂點(diǎn)，則它共有（）條邊。A 7B 21C 42D 496 寄存器是（）的重要組成部分。A 硬盤B 高速緩存C 內(nèi)存D 中央處理器（CPU）7 如果根結(jié)點(diǎn)的深度記為1,則一棵恰有2011個葉結(jié)點(diǎn)的二叉樹的深度最少是（）。A 10B 11C 12D 13&體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個同學(xué)按 順序來到操

3、場時，都從排尾走到排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的 方法類似于（）算法。A 快速排序B 插入排序C 冒泡排序D 歸并排序9 一個正整數(shù)在二進(jìn)制下有 100位，則它在十六進(jìn)制下有（）位。A 7B 13C 25D 不能確定10 有人認(rèn)為，在個人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（ ）。A正確的，將文件放入回收站以為著徹底刪除、無法恢復(fù)B 不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復(fù)C 不正確的，即使回收站清空，文件只是被標(biāo)記為刪除，仍可能通過回復(fù)軟件找回D 不正確的，只要在硬盤上出現(xiàn)過的文件，永遠(yuǎn)不可能被徹底刪除11. 廣度優(yōu)先搜索時

4、，需要用到的數(shù)據(jù)結(jié)構(gòu)是（）。A 鏈表B.隊(duì)列C.棧D.散列表12. 在使用高級語言編寫程序時，一般提到的“空間復(fù)雜度”中的“空間”是指（）。A .程序運(yùn)行時理論上所占的內(nèi)存空間B. 程序運(yùn)行時理論上所占的數(shù)組空間C. 程序運(yùn)行時理論上所占的硬盤空間D .程序源文件理論上所占的硬盤空間13. 在含有n個元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最快情況下運(yùn)行的時間復(fù)雜度 是（ ）。A . 0（1 ）B . 0（ log n ）C . 0（ n ）D . 0（ n log n ）14. 生物特征識別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜 識別、人臉識別等技術(shù)已廣

5、泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。一下不屬于生物特征識別技術(shù) 及其應(yīng)用的是（）。B.步態(tài)驗(yàn)證A.指靜脈驗(yàn)證C . ATM機(jī)密碼驗(yàn)證D .聲音驗(yàn)證15 .現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個漢M “之”、“呼”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、200。那么,“也”字的編碼長度是（）。A . 1B . 2C . 3D . 416 .關(guān)于匯編語言，下列說法錯誤的是（）A .是一種與具體硬件相關(guān)的程序設(shè)計(jì)語言B.在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試C .可以直接反問寄存器、內(nèi)存單元、以及I/O端口D .

6、隨著高級語言的誕生，如今已完全被淘汰，不再使用17 .（）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。當(dāng)搜索到某一步時，發(fā)現(xiàn)原 先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇。：A .回溯法B .枚舉法C.動態(tài)規(guī)劃D .貪心A .諾貝爾物理學(xué)獎D.高德納獎B .約翰馮諾依曼獎C .圖靈獎18. 1956年（ ）手語肖克利、巴丁和布拉頓，以表彰他們對半導(dǎo)體的 研究和晶體管效應(yīng)的發(fā)現(xiàn)。19 .對一個有向圖而言，如果每個節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路徑，那NOIP2011 初賽普及組C+ 2么就稱它是強(qiáng)連通的。例如，有圖就是一個強(qiáng)連通圖。事實(shí)上，在刪掉邊（）后，它依然是強(qiáng)連通的。A. aB. b

7、C. c D. d20.從ENIAC到當(dāng)前最先進(jìn)的計(jì)算機(jī)，馮諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié) 構(gòu)的核心內(nèi)容是（）。A .采用開關(guān)電路B .采用半導(dǎo)體器件C .采用存儲程序和程序控制原理D .采用鍵盤輸入二問題求解（共 2題，每空5分，共計(jì)10分）1. 每份考卷都有一個8位二進(jìn)制序列號。當(dāng)且僅當(dāng)一個序列號含有偶數(shù)個1時，它才是有效的。例如，0000000、01010011都是有效的序列號，而11111110不是。那么，有效的序列號共有個。2. 定義字符串的基本操作為：刪除一個字符插入一個字符和將一個字符修改成另外一個字符這三種操作。將字符串A變成字符串E的最少操作步數(shù)，稱為字符串A

8、到字符串E的編輯距離。字符 串“ ABCDEFG ”到字符串“ BADECG ”的編輯距離為 。三閱讀程序?qū)懡Y(jié)果（共 4題，每題8分，共計(jì)32分）1 .#in cludeusing n amespace std;int mai n（）int i,n, m,a ns;cinnm;i=n;an s=0;while（i=m）an s+=i;i+;couta nse ndl;return 0;輸入：10 20輸出：2 .#in clude#in clude using n amespace std;int mai n()string map= 2223334445556667778889999; st

9、ring tel;int i;cin tel;for(i=0;i=0) & (teli=9) cout=A) & (teli=Z) coutmapteli-A;coute ndl;return 0;輸入：CCF-NOIP-2011輸出： 3.#in clude #in clude using n amespace std;con st int SIZE = 100;int mai n()int n ,i,sum,x,aSIZE;cinn; memset(a,0,sizeof(a);for(i=1;ix; ax+;i=0;sum=0;while(sum( n/2+1) i+;sum+=ai;co

10、utie ndl;return 0;輸入：114 5 6 6 4 3 3 2 3 2 1輸出：4.#in cludeusing n amespace std;int solve(i nt n ,i nt m)int i,sum;if(m=1) return 1;sum=0;for(i=1;i n ;i+)sum+= solve(i,m-1);return sum;int mai n()int n,m;cinnm;coutsolve (n,m) e ndl;return 0;輸入：7 4輸出：四.完善程序(前11空，每空2分，后2空，每空3分，共28分)1 .(子矩陣)給輸入一個n1*m1的矩陣

11、a，和n2*m2的矩陣b，問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出There isno an swer ”。#in cludeusing n amespace std;const int SIZE = 50;int n1,m1, n2,m2,aSIZESIZE,bSIZESIZE;int mai n()int i,j,k1,k2;bool good ,haveA ns;cinn 1m1;for(i=1;i=n 1;i+)for(j=1;jaij;cinn 2m2;for(i=1;i=n 2;i+)for(j=1;j=m2;j+)haveA ns=false

12、;for(i=1;i=n1-n 2+1;i+)for(j=1;j=;j+) ；for(k 1=1;k1=n2;k1+)for(k2=1;k2=;k2+)if(ai+k1-1j+k2-1!=bk1k2) good=false;if(good)couti je ndl; ;if(!haveA ns)coutThere is no an swere ndl;return 0;2.(大整數(shù)開方)輸入一個正整數(shù)n (1竊10100)，試用二分法計(jì)算它的平方根的整數(shù)部分。#in clude#in cludeusing n amespace std;const int SIZE=200;struct hug

13、e intint len,n umSIZE;/其中l(wèi)en表示大整數(shù)的位數(shù)；num1表示個位，num2表示十位，以此類推huge int times(huge int a,huge int b)/計(jì)算大整數(shù)a和b的乘積int i,j;huge int ans;memset(a ns. num,O,sizeof(a ns. num);for(i=1;i=a.le n;i+)for(j=1;jv=b .len ;j+)_+=a .n umi*b. numj;for(i=1;i0)ans.len=a.len+b.len;elsean s.le n=a.le n+b.le n-1;return ans;

14、huge int add(huge int a,huge int b)/計(jì)算大整數(shù)a和b的和int i;huge int ans;memset(a ns. num,0,sizeof(a ns. num);if(a.le n b.le n)ans.len=a.len;elseans.len=b.len;for(i=1;i0)ans.len+;return ans;huge int average(huge int a,huge int b)/計(jì)算大整數(shù)a和b的平均數(shù)的整數(shù)部分int i;huge int ans;an s=add(a,b);for(i=a ns.le n;i=2;i-)ans.n

15、u mi-1+=()*10;an s. numi/=2;ans.n um1/=2;if(ans.n uma ns.len=0)ans.len-;return ans;huge int plustwo(huge int a)/計(jì)算大整數(shù)a加2之后的結(jié)果int i;huge int ans;an s=a;ans.n um1+=2;i=1;while( (i=10) )ans.n umi+1+=a ns.n umi/10;ans.n umi%=10;i+;if(ans.n uma ns.len+10) ;return ans;bool over(huge int a,huge int b)II若大整

16、數(shù)ab則返回true ，否則返回falseint i;if()return false;if( a.lenb.len )return true;for(i=a.le n;i=1;i-)if(a. numib .n umi)return true;return false;int mai n()stri ng s;int i;huge int target,left,middle,right;cin s;memset(target. num,0,sizeof(target. num);target.le n=s.le ngth();for(i=1;i=1;i-)coutleft .n umi;return 0;NOIP2011年普及組（C+語言）參考答案與評分標(biāo)準(zhǔn)、單項(xiàng)選擇題：（每題1.5分）1. B2. B3. C4. C5. B6. D7. B8. B9. C10. C11. B12. A13. C14. C15. C16. D17. A18. A19. A20. C二、問題求解：（