第十七屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(普及組c).

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

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

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

4、能被徹底刪除11 廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（A鏈表B隊(duì)列C棧）。D 散列表12 在使用高級(jí)語言編寫程序時(shí)，一般提到的“空間復(fù)雜度”中的“空間”是指（A 程序運(yùn)行時(shí)理論上所占的內(nèi)存空間B 程序運(yùn)行時(shí)理論上所占的數(shù)組空間C 程序運(yùn)行時(shí)理論上所占的硬盤空間D 程序源文件理論上所占的硬盤空間）。13 在含有 n 個(gè)元素的雙向鏈表中查詢是否存在關(guān)鍵字為是（）。k 的元素，最快情況下運(yùn)行的時(shí)間復(fù)雜度AO(1 )B O( log n )C O( n )D O( n log n )14生物特征識(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)證15 現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由 4 個(gè)漢字“之”、 “呼”、 “者”、 “也”組成，它們出現(xiàn)的次數(shù)分別為 700、600、300、200。那么， “也”字的編碼長度是（）。A 1B 2C 3D 416 關(guān)于匯編語言，下列說法錯(cuò)誤的是（）A 是一種與具體硬件相關(guān)的程序設(shè)計(jì)語言B 在編寫復(fù)雜程序時(shí)，相對于高級(jí)語言而言代碼量較大，且不易調(diào)試C 可以直接訪問寄存器、內(nèi)存單元、以及I/O 端口D 隨著高級(jí)語言的誕生，如今已完

6、全被淘汰，不再使用17（）是一種選優(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 貪心18 1956 年（）手語肖克利、巴丁和布拉頓，以表彰他們對半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A B CD德納獎(jiǎng)19對一個(gè)有向圖而言， 如果每個(gè)節(jié)點(diǎn)都存在到達(dá)其他任何節(jié)點(diǎn)的路徑， 那么就稱它是強(qiáng)連通的。 例如，有圖就是一個(gè)強(qiáng)連通圖。 事實(shí)上，在刪掉邊（ ）后，它依然是強(qiáng)連通的。A aB bC cD d20從 ENIAC 到當(dāng)前最先進(jìn)的計(jì)算機(jī)，馮諾依曼體系結(jié)構(gòu)始終占有重要地位。馮諾依曼提醒結(jié)構(gòu)的核心內(nèi)容是（）。A

7、 采用開關(guān)電路B 采用半導(dǎo)體器件C 采用存儲(chǔ)程序和程序控制原理D 采用鍵盤輸入二問題求解（共2 題，每空5 分，共計(jì)10 分）1每份考卷都有一個(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è)。2定義字符串的基本操作為： 刪除一個(gè)字符插入一個(gè)字符和將一個(gè)字符修改成另外一個(gè)字符這三種操作。將字符串變成字符串的最少操作步數(shù)，稱為字符串到字符串的編輯距離。字符串“ ABCDEFG ”到字符串“BADECG ”的編輯距離為。三閱讀程序?qū)懡Y(jié)果（共4 題，每題8 分，

8、共計(jì)32 分）1#includeusing namespace std;int main()int i,n,m,ans;cinnm;i=n;ans=0;while(i=m)ans+=i;i+;coutansendl;return 0;輸入： 10 20輸出： _2#include#includeusing namespace std;int main()string map= 2223334445556667778889999;string tel;int i;cintel;for(i=0;i=0) & (teli=9) )cout=A) & (teli=Z)coutmapteli-A;cou

9、tendl;return 0;輸入： CCF-NOIP-2011輸出： _3#include#includeusing namespace std;const int SIZE = 100;int main()int n,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;return 0;輸入：1145664332321輸出：4#includeusing namespace std;int solve(int n,int m)int i,su

10、m;if(m=1) return 1;sum=0;for(i=1;inm;coutsolve(n,m)endl;return 0;輸入： 74輸出： _四完善程序( 前 11 空，每空 2 分，后 2 空，每空3 分，共 28 分 )1 （子矩陣） 給輸入一個(gè)n1*m1的矩陣 a，和 n2*m2 的矩陣 b ，問 a 中是否存在子矩陣和b 相等。若存在，輸出所有子矩陣左上角的坐標(biāo)：若不存在輸出“There isno answer”。#includeusing namespace std;const int SIZE = 50;int n1,m1,n2,m2,aSIZESIZE,bSIZESIZ

11、E;int main()int i,j,k1,k2;bool good ,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+) ;for(k1=1;k1=n2;k1+)for(k2=1;k2=;k2+)if(ai+k1-1j+k2-1!=bk1k2)good=false;if(good)couti jendl; ;if(!haveAns)coutThere is no answ

12、erendl;return 0;2.( 大整數(shù)開方 )輸入一個(gè)正整數(shù)n （ 1 n10100），試用二分法計(jì)算它的平方根的整數(shù)部分。#include#includeusing namespace std;const int SIZE=200;struct hugeintint len,numSIZE;/ 其中 len 表示大整數(shù)的位數(shù)； num1 表示個(gè)位， num2 表示十位，以此類推hugeint times(hugeint a,hugeint b)/ 計(jì)算大整數(shù) a 和 b 的乘積int i,j;hugeint ans;memset(ans.num,0,sizeof(ans.num);f

13、or(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;return ans;hugeint add(hugeint a,hugeint b)/ 計(jì)算大整數(shù) a 和 b 的和int i;hugeint ans;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+;return ans;hu

14、geint average(hugeint a,hugeint b)/ 計(jì)算大整數(shù) a 和 b 的平均數(shù)的整數(shù)部分int i;hugeint ans;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-;return ans;hugeint plustwo(hugeint a)/ 計(jì)算大整數(shù) a 加 2 之后的結(jié)果int i;hugeint ans;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) ;return ans;bool over(hugeint a,hugeint b)/若大整數(shù)ab 則返回 true，否則返回falseint i;if()return false;if( a.lenb.len )return true;for(i=a.len;i=1;i-)if(a.numib.numi)return true;return false;int main()string s;int i;hugeint target,left,middle,r