noip初中普及組模擬試卷

1、NOIP考前模擬測(cè)試一、選擇題(每空1.5分，共30分)1、關(guān)于圖靈機(jī)下面的說(shuō)法哪個(gè)是正確的()圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。圖靈機(jī)是英國(guó)人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。2、關(guān)于ASCII,下面哪個(gè)說(shuō)法是正確的()ASCII碼就是鍵盤上所有鍵的唯一編碼。一個(gè)ASCII碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。C)最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語(yǔ)言的編碼。D)ASCII碼是英國(guó)人主持并推廣使用的。3、表達(dá)式a*(b+c)-d的后綴表達(dá)式是()A)abcd*+B)abc+*d-C)abc*+

2、d-D)-+*abcd4、有一個(gè)由4000個(gè)整數(shù)構(gòu)成的順序表,假定表中的元素已經(jīng)按升序排列,采用二分查找定位一個(gè)元素。則最多需要幾次比較就能確定是否存在所查找的元素()A)11次B)12次C)13次D)14次5、2E+03表示()A)2.03B)5C)8D)20006、以下邏輯表達(dá)式的值為真的是()A)PV(-PAQ)V(PAQ)B)QV(-PAQ)V(PAQ)C)PVQV(PAQ)V(-PAQ)D)PVQV(pAQ)V(pAQ)7、設(shè)X、Y、Z分別代表三進(jìn)制下的一位數(shù)字，若等式XY+ZX=XYX在三進(jìn)制下成立，那么同樣在三進(jìn)制下，等式XY*ZX=()也成立。A)YXZB)ZXYC)XYZD)

3、XZY8、主存儲(chǔ)器的存取速度比中央處理器(CPU)的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問(wèn)的存儲(chǔ)單元通常都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了()。A)寄存器B)高速緩存C)內(nèi)存D)外存9、一片容量為8GB的SD卡能存儲(chǔ)大約()張大小為2MB的數(shù)碼相片。A)1600B)2000C4000D)1600010、如果根節(jié)點(diǎn)的深度記為1,則一顆恰有2011個(gè)葉節(jié)點(diǎn)的二叉樹(shù)的深度最少為()A)10B)11C)12D)1311、在含有n個(gè)元素的雙向鏈表中查詢是否存在關(guān)鍵字為k的元素，最壞情況下運(yùn)行的時(shí)間復(fù)雜度為()A)O(1

4、)B)O(logn)C)O(n)D)O(nlogn)12、現(xiàn)有一段文言文,要通過(guò)二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡(jiǎn)單起見(jiàn),假設(shè)這段文言文只有4個(gè)漢字“之”、“乎”、“者”、“也”組成,它們出現(xiàn)的次數(shù)分別為700、600、300、200.那么“也”字的編碼長(zhǎng)度是()A)1B)2C)3D)413、目前計(jì)算機(jī)芯片(集成電路)制造的主要原料是(),它是一種可以在沙子中提煉出的物質(zhì)。A)硅B)銅C)鍺D)鋁14、如果一顆二叉樹(shù)的中序遍歷是BAC,那么它的先序遍歷不可能是()A)ABCB)CBAC)ACBD)BAC15、使用冒泡排序?qū)π蛄羞M(jìn)行升序排列，沒(méi)執(zhí)行一次交換操作，系統(tǒng)將會(huì)減少1個(gè)逆序?qū)?，因此序?，4，

5、3，2，1需要執(zhí)行()次操作，才能完成冒泡排序。A)0B)5C)10D)1516、原字符串中任意一段連續(xù)的字符所組成的新字符串稱為子串，則字符AAABBBCCC”共有()個(gè)不同的非空子串。A)3B)12C)36D)4517、無(wú)向圖G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是()A)a,b,e,c,d,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,e,d,f,c,b18、HTML中，表示()A)正在點(diǎn)擊文字的色彩是紅色；B)可鏈接文字的色彩是

6、紅色；C)非可鏈接文字的色彩是紅色；D)已鏈接文字的色彩是紅色19、以下取自中國(guó)計(jì)算機(jī)學(xué)會(huì)2011年4月14日制定的規(guī)則不正確的是()A)當(dāng)參賽選手對(duì)一道試題提交多份使用不同后綴的源程序文件時(shí)，測(cè)試系統(tǒng)按照.c,.cpp,.pas的順序選取第一份存在的文件進(jìn)行編譯和測(cè)評(píng)，并忽略其他文件。B)除另有規(guī)定外，每道題參賽程序源文件不得大于100KB。C)如果選手目錄下沒(méi)有程序，就會(huì)任意選擇一個(gè)子目錄里的源程序進(jìn)行測(cè)評(píng)。D)對(duì)于Pascal程序禁止使用內(nèi)嵌匯編，并禁止使用任何編譯開(kāi)關(guān)。20、把64位非零浮點(diǎn)數(shù)強(qiáng)制轉(zhuǎn)換為32位浮點(diǎn)數(shù)后，不可能()A)大于原數(shù)B)小于原數(shù)C)等于原數(shù)D)與原數(shù)符號(hào)相反。二

7、、問(wèn)題求解(每題5分，共10分)第一題：5男5女坐成一桌(10個(gè)座位)，同性別不能相鄰的坐法共有種。第二題：小陳現(xiàn)有2個(gè)任務(wù)A,B要完成，每個(gè)任務(wù)分別有若干步驟如下：A=a1-a24a3,B=b1-b24b34b44b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后,切換至另一個(gè)任務(wù),從上次任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如a24b24a34b3是合法的，而a-b3-a34b2是不合法的。小陳從B任務(wù)的b1步驟開(kāi)始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來(lái)時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。

8、試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有種。三、閱讀程序；.constSIZE=100;varn,i,sum,x:integer;a:array1.SIZEofinteger;beginreadln(n);fillchar(a,sizeof(a),0);fori:=1tondobeginread(x);inc(ax);end;i:=0;sum:=0;whilesum(ndiv2+1)dobegininc(i);sum:=sum+ai;end;writeln(i);end.輸入：1145664332321輸出：二、vara,b:integer;functionwork(a,b:integer)

9、:integer;beginifamodb0thenwork:=work(b,amodb)elsework:=b;end;beginread(a,b);writeln(work(a,b);end.輸入：2012輸出：三、varn,i,j:integer;a:array1.100,1.100ofinteger;functionsolve(x,y:integer):integer;varu,v:integer;beginifx=nthenbeginsolve:=ax,y;exit;end;u:=solve(x+1,y);v:=solve(x+1,y+1);ifuvthensolve:=ax,y+u

10、elsesolve:=ax,y+v;end;beginread(n);fori:=1tondoforj:=1toidoread(ai,j);writeln(solve(1,1);end.輸入：52-142-1-2-164032-158輸出：四、vari,a,b,c,x,y:integer;p:array0.4ofinteger;beginy:=20;fori:=0to4doread(p);readln;a:=(p0+p1)+(p2+p3+p4)div7;b:=p0+p1div(p2+p3)divp4);c:=p0*p1divp2;x:=a+b-p(p3+3)mod4;if(x10)theny:

11、=y+(b*100-a)div(pp4mod3*5)elsey:=y+20+(b*100-c)div(pp4mod3*5);writeln(x,x,y);end.注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或數(shù)組元素下標(biāo)越界輸入：66553輸出：四、完善程序（前5空，每空2分，共計(jì)28分）.（子矩陣）輸入一個(gè)n1+m1d哦矩陣a,和n2+m2的矩陣b,問(wèn)a中是否存在子矩陣和b相等。若存在，輸出所有子矩陣左上角的坐標(biāo)；若不存在輸出“Thereisnoanswer”。constSIZE=50;varn1,m1,n2,m2,i,j,k1,k2:integer;a,b:array1.SIZE,1.SIZ

12、Eofinteger;good,haveAns:boolean;beginreadln(n1,m1);fori:=1ton1doforj:=1tom1doread(ai,j);readln(n2,m2);fori:=1ton2doforj:=1tom2dohaveAns:=false;fori:=1ton1-n2+1doforj:=1to_dobeginfork1:=1ton2dofork2:=1to_doifai+k1-1,j+k2-1bk1,k2thengood:=false;ifgoodthenbeginwriteln(i,j);end;end;ifnothaveAnsthenwrite

13、ln(Thereisnoanswer);end.(二叉查找樹(shù))二叉查找樹(shù)具有如下性質(zhì)：每個(gè)節(jié)點(diǎn)的值都大于其左子樹(shù)上所有節(jié)點(diǎn)的值、小于其右子樹(shù)上所有節(jié)點(diǎn)的值。試判斷一棵樹(shù)是否為二叉查找樹(shù)。輸入的第一行包含一個(gè)整數(shù)n,表示這顆樹(shù)有n個(gè)頂點(diǎn)，編號(hào)為1,2,樹(shù)n,其中編號(hào)為1的為根節(jié)點(diǎn)。之后的第i行有三個(gè)數(shù)value，left_child，right_child，分別表示該節(jié)點(diǎn)關(guān)鍵字的值、左子節(jié)點(diǎn)的編號(hào)、右子節(jié)點(diǎn)的編號(hào)；如果不存在左子節(jié)點(diǎn)或右子節(jié)點(diǎn),則用0代替。輸出1表示這顆樹(shù)是二叉查找樹(shù),輸出0則表示不是。programBst;constSIZE=100;constINFINITE=1000000;typenode=recordleft_child,right_child,value:longint;end;vara:array1.SIZEofnode;i,n:longint;functionis_bst(root,lower_bound,upper_bound:longint):longint;varcur:longint;beginifroot=0thenbeginis_bst:=1;exit;end;cur:=aroot.value;if(curlow