noip2初賽普及組c++題目及答案

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

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

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

4、廣度優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是（）。A鏈表 B 隊列 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 O(1)B O(logn)C O(n)D O(nlogn)14生物特征識別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。

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

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

7、A 采用開關(guān)電路B 采用半導(dǎo)體器件C 采用存儲程序和程序控制原理D 采用鍵盤輸入二問題求解（共2 題，每空5 分，共計 10 分）1個。2 定義字符串的基本操作為：刪除一個字符插入一個字符和將一個字符修改成另外一個字符這三種操作。將字符串變成字符串的最少操作步數(shù)，稱為字符串到字符串的編輯距離。字符串“ ABCDEFG ”到字符串“ BADECG ”的編輯距離為。三閱讀程序?qū)懡Y(jié)果（共4 題，每題8 分，共計32 分）1#includeusingnamespacestd;intmain()inti,n,m,ans;cinnm;i=n;ans=0;while(i=m)ans+=i;i+;coutan

8、sendl;return0;輸入： 1020輸出： _2#include#includeusingnamespacestd;intmain()stringmap=stringtel;inti;cintel;for(i=0;i=0)&(teli=9)cout=A)&(teli=Z)coutmapteli-A;coutendl;return0;輸入： CCF-NOIP-2011輸出： _3#include#includeusingnamespacestd;constintSIZE=100;intmain()intn,i,sum,x,aSIZE;cinn;memset(a,0,sizeof(a);f

9、or(i=1;ix;ax+;i=0;sum=0;while(sum(n/2+1)i+;sum+=ai;coutiendl;return0;輸入：1145664332321輸出：4#includeusingnamespacestd;intsolve(intn,intm)inti,sum;if(m=1)return1;sum=0;for(i=1;inm;coutsolve(n,m)endl;return0;輸入：74輸出：_四完善程序( 前 11 空，每空2 分，后 2 空，每空3 分，共 28 分 )1 （子矩陣） 給輸入一個n1*m1的矩陣 a ，和 n2*m2 的矩陣 b ，問 a 中是否存

10、在子矩陣和等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出“Thereisnoanswer”。b 相#includeusingnamespacestd;constintSIZE=50;intn1,m1,n2,m2,aSIZESIZE,bSIZESIZE;intmain()inti,j,k1,k2;boolgood,haveAns;cinn1m1;for(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+) ;f

11、or(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ù)開方 ) 輸入一個正整數(shù) n （ 1 n10100 ），試用二分法計算它的平方根的整數(shù)部分。#include#includeusingnamespacestd;constintSIZE=200;structhugeintintlen,numSIZE;/ 其中 len 表示大整數(shù)的位數(shù)； num1 表示個位，

12、 num2 表示十位，以此類推hugeinttimes(hugeinta,hugeintb)/ 計算大整數(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=a.len+b.len-1;returnans;hugeintadd(hugeinta,hugeintb)/ 計算大整數(shù) a 和 b 的和inti;hugeintans;mem

13、set(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)/ 計算大整數(shù) a 和 b 的平均數(shù)的整數(shù)部分inti;hugeintans;ans=add(a,b);for(i=ans.len;i=2;i-)ans.numi-1+=()*10;ans.numi/=2;ans.num1/=2;if(ans.numans.len=0)ans.len-;returnans;hugeint

14、plustwo(hugeinta)/ 計算大整數(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ù)inti;ab則返回true，否則返回falseif()returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i-)if(a.numib.numi)returntrue;returnfalse;intmain()strings;inti;hugeinttarget,left,middle,right;cins