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

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

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

4、表.在使用高級語言編寫程序時,一般提到的“空間復(fù)雜度”中的“空間”是指()。A.程序運(yùn)行時理論上所占的內(nèi)存空間B.程序運(yùn)行時理論上所占的數(shù)組空間C.程序運(yùn)行時理論上所占的硬盤空間D.程序源文件理論上所占的硬盤空間.在含有n個元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最快情況下運(yùn)行的時間復(fù)雜度是（）。A.O（1）B.O（logn）C.O（n）D.O（nlogn）.生物特征識別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識別、虹膜識別、人臉識別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。一下不屬于生物特征識別技術(shù)及其應(yīng)用的是（）。A.指靜脈驗(yàn)證B.步態(tài)驗(yàn)證C.ATM機(jī)密碼驗(yàn)證

5、D.聲音驗(yàn)證.現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個漢字“之”、“呼”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、200。那么，“也”字的編碼長度是（）。A.1B.2C.3D.4.關(guān)于匯編語言，下列說法錯誤的是（）A.是一種與具體硬件相關(guān)的程序設(shè)計語言B.在編寫復(fù)雜程序時，相對于高級語言而言代碼量較大，且不易調(diào)試C.可以直接反問寄存器、內(nèi)存單元、以及I/O端口D.隨著高級語言的誕生，如今已完全被淘汰，不再使用.（）是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。當(dāng)搜索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇

6、。：A.回溯法B.枚舉法C.動態(tài)規(guī)劃D.貪心.1956年（）手語肖克利、巴丁和布拉頓，以表彰他們對半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A.諾貝爾物理學(xué)獎B.約翰馮諾依曼獎C.圖靈獎D.高德納獎.對一個有向圖而言，如果每個節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路徑，那么就稱它是強(qiáng)連通的。例如，有圖就是一個強(qiáng)連通圖。事實(shí)上，在刪掉邊（）后，它依然是強(qiáng)連通的。A.aB.bC.cD.d.從ENIAC到當(dāng)前最先進(jìn)的計算機(jī)，馮諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié)構(gòu)的核心內(nèi)容是（）。A.采用開關(guān)電路B.采用半導(dǎo)體器件C.采用存儲程序和程序控制原理D.采用鍵盤輸入二.問題求解（共2題，每空5分，共計10分）.一個。.定義字符串的基本操作為：刪除一個字符插入一個字符和將一個字符修改成另外一個字符這三種操作。將字符串A變成字符串B的最少操作步數(shù)，稱為字符串A到字符串B的編輯距離。字符串“ABCDEFG”到字符串“BADECG”的編輯距離為。三