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

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

2、級在可預(yù)測的未來紀(jì)念，單塊集成電驢的集成度大約每（）個月翻一番。A.1B.6C.18D.36無向完全圖是圖中每對頂點之間都恰好有一條邊的簡單圖。已知無向完全圖G有7個頂點，則它共有（）條邊。A.7B.21C.42D.49A硬盤B高速緩存C內(nèi)存D中央處理器（）7如果根結(jié)點的深度記為1，則一棵恰有2011個葉結(jié)點的二叉樹的深度最少是（）。A10B11C12D138體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場，按老師的要求從高到矮站成一排。每個同學(xué)按順序來到操場時，都從排尾走到排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊的方法類似于（）算法。A快速排序B插入排序C冒泡排序D歸并排序9一個正整

3、數(shù)在二進(jìn)制下有100位，則它在十六進(jìn)制下有（）位。A7B13C25D不能確定10有人認(rèn)為，在個人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是（）。A正確的，將文件放入回收站以為著徹底刪除、無法恢復(fù)B不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復(fù)C不正確的，即使回收站清空，文件只是被標(biāo)記為刪除，仍可能通過回復(fù)軟件找回D不正確的，只要在硬盤上出現(xiàn)過的文件，永遠(yuǎn)不可能被徹底刪除11廣度優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是()。A鏈表B隊列C棧D散列表12在使用高級語言編寫程序時，一般提到的“空間復(fù)雜度”中的“空間”是指()。A程序運行時理論上所占的內(nèi)存空間B程序運行時理論上所占

4、的數(shù)組空間C程序運行時理論上所占的硬盤空間D程序源文件理論上所占的硬盤空間13.在含有n個元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最快情況下運行的時間復(fù)雜度是()。AO(1)BO(n)CO(n)DO(nn)14生物特征識別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。一下不屬于生物特征識別技術(shù)及其應(yīng)用的是A.指靜脈驗證C.機(jī)密碼驗證D.聲音驗證現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個漢字“之”、“呼”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、

5、200。那么，“也”字的編碼長度是（）。A.1B.2C.3D.415. 關(guān)于匯編語言，下列說法錯誤的是（）A.是一種與具體硬件相關(guān)的程序設(shè)計語言B.在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試C.可以直接反問寄存器、內(nèi)存單元、以及端口D.隨著高級語言的誕生，如今已完全被淘汰，不再使用16. （）是一種選優(yōu)搜索法，按選優(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.

6、圖靈獎D.高德納獎對一個有向圖而言，如果每個節(jié)點都存在到達(dá)其他任何節(jié)點的路徑，那么就稱它是強(qiáng)連通的。例如，有圖就是一個強(qiáng)連通圖。事實上，在刪掉邊（）后，它依然是強(qiáng)連通的。A.aB.bC.cD.d從到當(dāng)前最先進(jìn)的計算機(jī)，馮諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié)構(gòu)的核心內(nèi)容是（）。A.采用開關(guān)電路B.采用半導(dǎo)體器件C.采用存儲程序和程序控制原理D.采用鍵盤輸入二.問題求解（共2題，每空5分，共計10分）每份考卷都有一個8位二進(jìn)制序列號。當(dāng)且僅當(dāng)一個序列號含有偶數(shù)個1時，它才是有效的。例如，0000000、01010011都是有效的序列號，而11111110不是。那么，有效的序列號共有個。定

7、義字符串的基本操作為：刪除一個字符插入一個字符和將一個O字符修改成另外一個字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串“”到字符串“”的編輯距離為三閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計32分)1<>J()J>>n>>m;J0;(i<)JJ<<<<0;輸入：1020輸出：<><>J()"2223334445556667778889999"Ji;>>(0<()(i>='0')(i<='

8、9')<<i;(i>='A')(i<='Z')<<i-'A'<<0;輸入：2011輸出：<><>=100;();>>n;(a,0(a);(1<)>>x;ax;0;0;(<(2+1)i;<<i<<0;輸入：1145664332321輸出：4.<>(m)1;0;(1<)；()>>n>>m;<<（）<<0;輸入：74輸出：四完善程序（前11空，每空2

9、分，后2空，每空3分，共28分）1.（子矩陣）給輸入一個n1*m1的矩陣a，和n2*m2的矩陣b,問a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出“”。<>=50;n1122;()12;>>n1>>m1;(1<1)(1<1)>>aij;>>n2>>m2;(1<2)(1<2)(1<12+1)(1<=)；(k1=11<21)(k2=12<=2)(a1-12-1k1k2)()vvjvv''vvjvv；()vv""vv

10、；0;2.(大整數(shù)開方)輸入一個正整數(shù)n(KnW10100),試用二分法計算它的平方根的整數(shù)部分。v>v>200;；其中表示大整數(shù)的位數(shù)；1表示個位，2表示十位，以此類推(b)計算大整數(shù)a和b的乘積(,0()；(1<) (1<)i*il；(1<) 1i/10；(>0)(b)計算大整數(shù)a和b的和i；(,0();(>)(1<)i1i/10；i10；(1>0)(b)計算大整數(shù)a和b的平均數(shù)的整數(shù)部分i；();)*10；(>=2)1(i2；12；(0)(a)計算大整數(shù)a加2之后的結(jié)果i；12；(i<)(i>=10)1i/10；i10；(1>0)(b)若大整數(shù)a>b則返回，否則返回i；()(>)(>=1)(i<i)(i>i)()s；i；>>s；(,0()；()；(1<)i卜(,0()；1；1=1；)();();(>=1)<<i;0;2011年普及組（語言）參考答案與評分標(biāo)準(zhǔn)一、單項選擇題：（每題1.5分）1.B2.B3.C4.C5.B6.D7.B8.B9.C10.C14.C15.C11.B12.A13.C16.D17.A18.A19.A20.