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

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

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

3、操場時，都從排尾走到排頭，找到第一個比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的方法類似于（ ）算法。A 快速排序 B 插入排序 C 冒泡排序D 歸并排序9一個正整數(shù)在二進(jìn)制下有100 位，則它在十六進(jìn)制下有（ ）位。A 7 B 13 C 25 D 不能確定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 隊(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 O(1 ) B O( n ) C O( n ) D O( n n )14 生物特征識別， 是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用

5、于政府、銀行、安全防衛(wèi)等領(lǐng)域。一下不屬于生物特征識別技術(shù)及其應(yīng)用的是()。D .聲A .指靜脈驗(yàn)證B .步態(tài)驗(yàn)證 C.機(jī)密碼驗(yàn)證 音驗(yàn)證15 .現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個漢字“之”、“呼”、"者”、“也”組成，它們出現(xiàn)的次數(shù)分別為 700、600、300、200。那么，“也”字的編碼長度是（）。A.1 B . 2 C . 3 D . 416 .關(guān)于匯編語言，下列說法錯誤的是（）A .是一種與具體硬件相關(guān)的程序設(shè)計語言B .在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試C .可以直接反問寄存器、內(nèi)存單元、以及端口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 .貪18 . 1956年（）手語肖克利、巴丁和布拉頓，以表彰他們對半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A .諾貝爾物理學(xué)獎B .約翰馮諾依曼獎 C .圖靈獎D.高德納獎19 .對一個有向圖而言，如果每個節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路 徑，那么就稱它是強(qiáng)連通的。例如，有圖就是一個強(qiáng)連通圖。事實(shí) 上，在刪掉邊（）后，它依然是強(qiáng)連通的。A . a B . b C . c D.d20

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

8、2X編輯距離。字符串""到字符串“"的編輯距離為 o5 / 18三閱讀程序?qū)懡Y(jié)果(共4 題，每題 8 分，共計 32 分)1<>();>>n>>m;0;(i<);<<<<0;輸入： 10 20輸出：26 / 18<><>J0("2223334445556667778889999"Ji；»；(0<0)(i>=<0') (i<=<9')«i；(i>='A') (i<=

9、'Z')«iJA'；«；0；)輸入：2011輸出：3.<>=100;0;»n;(a,0(a);(1<)»x;ax；)0；0；(<(2+1)Ji；)«i«0;8/18輸入：114 5 6 6 4 3 3 2 3 2 1輸出：4.<>；(m)；(1) 1；0；(1<)(1)；()>>n>>m;<<()<<0;輸入： 7 4輸出：四完善程序( 前 11 空，每空 2 分，后 2 空，每空 3 分，共 28 分 )1 .(子矩陣)

10、給輸入一個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)()<<i<<' '<<j<<；®)()&l

11、t;<""<<；0;)2 .(大整數(shù)開方)輸入一個正整數(shù)n (1WnW1010°),試用二分法計算 它的平方根的整數(shù)部分。<><>200;； )；其中表示大整數(shù)的位數(shù)；1表示個位，2表示十位，以此類推(b)計算大整數(shù)a和b的乘積；(,0()；(1<)(1<)i*j(1<)1i/10；(口>0)；1；(b)計算大整數(shù)a和b的和i；(,0()；(>)；(1<)i；1 i/10；i10；(1>0)；(b)計算大整數(shù)a和b的平均數(shù)的整數(shù)部分13 / 18i；()；(>=2)1()*1

12、0；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<)加-；(,0()；1；1=1；()；()J_J() );(>=1)<<i;0;2011 年普及組（語言）參考答案與評分標(biāo)準(zhǔn)一、單項(xiàng)選擇題：（每題 1.5 分）I. B 2. B 3. C 4. C 5. B6. D 7. B 8. B 9. C 10. CII. B 12. A 13. C 14. C 15. C16. D 17. A 18. A 19. A 20. C二、問題求解：（共2 題，每空