NOIP2011普及組初賽試題答案C++

1、第十七屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（普及組C+語言二小時(shí)完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。）1在二進(jìn)制下，1011001+（）=1100110。A1011B1101C1010D1111.字符“0”的ASCII碼為48,則字符“9”的ASCII碼為（）。A.39B.57C.120D.視具體的計(jì)算機(jī)而定.一片容量為8G的SD卡能儲(chǔ)存大約（）張大小為2MB的數(shù)碼照片。A.1600B.2000C.4000D.16000.摩爾定律（Mooreslaw）是由英特爾創(chuàng)始人之一戈登摩爾（Gordon

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

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

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

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

6、全被淘汰，不再使用.（）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。當(dāng)搜索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇。：A.回溯法B.枚舉法C.動(dòng)態(tài)規(guī)劃D.貪心.1956年（）手語肖克利、巴丁和布拉頓，以表彰他們對(duì)半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A.諾貝爾物理學(xué)獎(jiǎng)B.約翰馮諾依曼獎(jiǎng)C.圖靈獎(jiǎng)D.高德納獎(jiǎng).對(duì)一個(gè)有向圖而言，如果每個(gè)節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路徑，那么就稱它是強(qiáng)連通的。例如，有圖就是一個(gè)強(qiáng)連通圖。事實(shí)上，在刪掉邊（）后，它依然是強(qiáng)連通的。AaBAaBbCcDd.從ENIAC到當(dāng)前最先進(jìn)的計(jì)算機(jī)，馮諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié)構(gòu)的核心內(nèi)

7、容是（）。A.采用開關(guān)電路B.采用半導(dǎo)體器件C.采用存儲(chǔ)程序和程序控制原理D.采用鍵盤輸入二.問題求解（共2題，每空5分，共計(jì)10分）.每份考卷都有一個(gè)8位二進(jìn)制序列號(hào)。當(dāng)且僅當(dāng)一個(gè)序列號(hào)含有偶數(shù)個(gè)1時(shí)，它才是有效的。例如,0000000、01010011都是有效的序列號(hào)，而11111110不是。那么，有效的序列號(hào)共有個(gè)。.定義字符串的基本操作為：刪除一個(gè)字符插入一個(gè)字符和將一個(gè)字符修改成另外一個(gè)字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串“ABCDEFG”到字符串“BADECG”的編輯距離為。三.閱讀程序?qū)懡Y(jié)果（共4題,每題8分,共計(jì)32分）

8、#includeusingnamespacestd;intmain（）inti,n,m,ans;cinnm;i=n;ans=0;while（i=m）ans+=i;i+;coutansendl;return0;輸入：1020輸出：#include#includeusingnamespacestd;intmain()stringmap=2223334445556667778889999;stringtel;inti;cintel;for(i=0;i=0)&(teli=9)cout=A)&(teli=Z)coutmapteli-A;coutendl;return0;輸入：輸出：#include#in

9、cludeusingnamespacestd;constintSIZE=100;intmain()intn,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;coutiendl;return0;輸入：1145664332321輸出：#includeusingnamespacestd;intsolve(intn,intm)inti,sum;if(m=1)return1;sum=0;for(i=1;inm;coutsolve(n,m)endl;return0;輸入：

10、74輸出：四完善程序(前11空，每空2分，后2空，每空3分，共28分)1.(子矩陣)給輸入一個(gè)n1*m1的矩陣a,和n2*m2的矩陣b,問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出“Thereisnoanswer”。#includeusingnamespacestd;constintSIZE=50;intn1,m1,n2,m2,aSIZESIZE,bSIZESIZE;NOIP2011NOIP2011初賽普及組C+NOIP2011NOIP2011初賽普及組C+intmain()(inti,j,k1,k2;boolgood,haveAns;cinn1m1;for(

11、i=1;i=n1;i+)for(j=1;jaij;cinn2m2;for(i=1;i=n2;i+)for(j=1;j=m2;j+);haveAns=false;for(i=1;i=n1-n2+1;i+)for(j=1;j=;j+);for(k1=1;k1=n2;k1+)for(k2=1;k2=;k2+)if(ai+k1-1j+k2-1!=bk1k2)good=false;if(good)coutijendl;if(!haveAns)coutThereisnoanswerendl;return0;2.（大整數(shù)開方）輸入一個(gè)正整數(shù)n（1n10100,試用二分法計(jì)算它的平方根的整數(shù)部分。#inclu

12、de#includeusingnamespacestd;constintSIZE=200;structhugeintintlen,numSIZE;/其中l(wèi)en表示大整數(shù)的位數(shù)；num1表示個(gè)位，num2表示十位，以此類推hugeinttimes(hugeinta,hugeintb)/計(jì)算大整數(shù)a和b的乘積inti,j;hugeintans;memset(ans.num,0,sizeof(ans.num);for(i=1;i=a.len;i+)for(j=1;j=b.len;j+)+=a.numi*b.numj;for(i=1;i0)ans.len=a.len+b.len;elseans.len

13、=a.len+b.len-1;returnans;hugeintadd(hugeinta,hugeintb)/計(jì)算大整數(shù)a和b的和inti;hugeintans;memset(ans.num,0,sizeof(ans.num);if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i0)ans.len+;returnans;hugeintaverage(hugeinta,hugeintb)/計(jì)算大整數(shù)a和b的平均數(shù)的整數(shù)部分inti;hugeintans;ans=add(a,b);for(i=ans.len;i=2;i-)*10;ans.n

14、umi-1+=()*10;ans.numi/=2;ans.num1/=2;if(ans.numans.len=0)ans.len-;returnans;hugeintplustwo(hugeinta)/計(jì)算大整數(shù)a加2之后的結(jié)果inti;hugeintans;ans=a;ans.num1+=2;i=1;while(i=10)ans.numi+1+=ans.numi/10;ans.numi%=10;i+;if(ans.numans.len+10);returnans;boolover(hugeinta,hugeintb)/若大整數(shù)ab則返回true,否則返回falseinti;if()returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i-)if(a.numib.numi)returntrue;returnfalse;intmain()strings;inti;hugeinttarget,left,m