第十六屆全國青少年信息學奧林匹克聯(lián)賽初賽試題及答案(Pascal普及組)

1、第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（普及組Pascal語言二小時完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一.單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。）1、關(guān)于圖靈機下面的說法哪個是正確的：A）圖靈機是世界上最早的電子計算機。B）由于大量使用磁帶操作，圖靈機運行速度很慢。C）圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。D）圖靈機只是一個理論上的計算模型。2、關(guān)于計算機內(nèi)存下面的說法哪個是正確的：A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B）1MB內(nèi)存通常是指102

2、4*1024字節(jié)大小的內(nèi)存。C）計算機內(nèi)存嚴格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。D）一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個小時以上。3、關(guān)于BIOS下面說法哪個是正確的：A） BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B） BIOS里包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設(shè)備的驅(qū)動程序。C） BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D） BIOS能供提各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。4、關(guān)于CPU下面哪個說法是正確的：A） CPU全稱為中央處理器（或中央處理單元）。B） CPU可以直接運行匯編語言。

3、C）同樣主頻下，32位的CPU比16位白CPU運行速度快一倍。D）CPU最早是由Intel公司發(fā)明的。5、關(guān)于ASCII,下面哪個說法是正確的：A） ASCII碼就是鍵盤上所有鍵的唯一編碼。B） 一個ASCII碼使用一個字節(jié)的內(nèi)存空間就能夠存放。C）最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。D）ASCII碼是英國人主持制定并推廣使用的。6、下列軟件中不是計算機操作系統(tǒng)的是：A）WindowsB）LinuxC）OS/2D）WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個是正確的：A）新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。B)互聯(lián)網(wǎng)的入網(wǎng)主機如果有了域名就不再需要IP地

4、址。C)互聯(lián)網(wǎng)的基石協(xié)議為TCP/IP協(xié)議。D)互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費使用的。8、關(guān)于HTML下面哪種說法是正確的：A) HTML實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B) HTML全稱為超文本標記語言。C)網(wǎng)上廣泛使用的Flash動畫都是由HTML編寫的。D)HTML也是一種高級程序設(shè)計語言。9、關(guān)于程序設(shè)計語言，下面哪個說法是正確的：A)加了注釋的程序一般會比同樣的沒有加注釋的程序運行速度慢。B)高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)(如：自控機床)或低端手機上。C)高級語言相對于低級語言更容易實現(xiàn)跨平臺的移植。D)以上說法都不對。10、已知大寫字

5、母A的ASCII編碼為65(十進制)，則大寫字母J的十進制ASCII編碼為：A)71B)72C)73D)以上都不是11、十進制小數(shù)125.125對應的八進制數(shù)是A)100.1B)175.175C)175.1D)100.17512、有六個元素FEDCBA從左至右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可能是合法的出棧序列？A)EDCFABB)DECABFC)CDFEBAD)BCDAEF13、表達式a*(b+c)-d的后綴表達式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd14、一個包含n個分支結(jié)點(非葉結(jié)點)的非空二叉樹，它的葉結(jié)點數(shù)目最多為：A)

6、2n+1B)2n-1C)n-1D)n+115、快速排序最壞情況下的算法復雜度為：A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)16.有一個由4000個整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素：A)11次B)12次C)13次D)14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的：A)冒泡排序B)插入排序C)歸并排序D)快速排序18、已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？A）nB

7、）n+1C）n-1D）n*（n-1）19、全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關(guān)的信息和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是：A）C）20、在參加NOI系列競賽過程中，下面哪一種行為是不被嚴格禁止的：A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B）在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。C）通過互聯(lián)網(wǎng)搜索取得解題思路。D）在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。2 .問題求解（共2題，每空5分，共計10分）1 .小陳現(xiàn)有2個任務(wù)A,B要完成，每個任務(wù)分別有若干步驟如下：A=a1->a2->a3,B

8、=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如a2->b2->a3->b3是合法的，而a2->b3->a3->b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整個任務(wù)A,其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有種。2 .有如下的一段程序：1. a:=1;2. b:=a;3.

9、 d:=-a;4. e:=a+d;5. c:=2*d;6. f:=b+e-d;7. g:=a*f+c;現(xiàn)在要把這段程序分配到若干臺（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺PC每單位時間可以執(zhí)行一個語句，且通訊花費的時間不計。則這段程序最快可以在單位時間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺PC上已經(jīng)得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執(zhí)行，則因為語句6需要引用語句4的計算結(jié)果，語句6必須在語句4之后執(zhí)行。3 .閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1.vara,b:

10、integer;functionwork(a,b:integer):integer;beginifamodb<>0thenwork:=work(b,amodb)elsework:=b;end;beginread(a,b);writeln(work(a,b);end.輸入：2012輸出：2.vara,b:array0.2ofinteger;1, j,tmp:integer;beginfori:=0to2doread(bi);fori:=0to2dobeginai:=0;forj:=0toidobegininc(ai,bj);inc(baimod3,aj);end;end;tmp:=1

11、;fori:=0to2dobeginai:=aimod10;bi:=bimod10;tmp:=tmp*(ai+bi);end;writeln(tmp);end.輸入：235輸出：3.constc=2009;varn,p,s,i,j,t:integer;beginread(n,p);s:=0;t:=1;fori:=1tondobegint:=t*pmodc;forj:=1toidos:=(s+t)modc;end;writeln(s);end.輸入：112輸出：4.vara:string;n:integer;proceduregetnext(varstr:string);varl,i,j,k:i

12、nteger;temp:char;begin1 :=length(str);k:=l-1;while(k>=1)and(strk>strk+1)dodec(k);i:=k+1;while(i<=l)and(stri>strk)doinc(i);temp:=strk;strk:=stri-1;stri-1:=temp;fori:=ldowntok+1doforj:=k+1toi-1doifstrj>strj+1thenbegintemp:=strj;strj:=strj+1;strj+1:=temp;end;end;beginread(a);read(n);whil

13、en>0dobegingetnext(a);dec(n);end;write(a);end.輸入：NOIP3輸出：四.完善程序（前8空，每空3分，后2空，每空2分，共28分）1 .（最大連續(xù)子段和）給出一個數(shù)列（元素個數(shù)不多于100）,數(shù)列元素均為負整數(shù)、正整數(shù)、0。請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4,-5,3,2,4時，輸出9和3;數(shù)列為123-5078時，輸出16和7。vara:array1.100ofinteger;n,i,ans,len,

14、tmp,beg:integer;beginread(n);fori:=1tondoread(ai);tmp:=0;NOIP2009初賽普及組Pascal6ans:=0;len:=0;beg:=；fori:=1tondobeginiftmp+ai>ansthenbeginans:=tmp+ai;len:=i-beg;endelseif()and(i-beg>len)thenlen:=i-beg;iftmp+aithenbeginbeg:=；tmp:=0;endelse；end;writeln(ans,'',len);end.2.(國王放置)在n*m的棋盤上放置k個國王

15、，要求k個國王互相不攻擊，有多少種不同的放置方法。假設(shè)國王放置在第(x,y)格，國王的攻擊的區(qū)域是：(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。讀入三個數(shù)n,m,k,輸出答案。題目利用回溯法求解。棋盤行標號為0n-1,列標號為0m-1。varh, m,k,ans:integer;hash:array0.4,0.4ofinteger;procedurework(x,y,tot:integer);vari, j：integer;beginiftot=kthenbegininc(ans);exit;e

16、nd;repeatwhilehashx,y<>0dobegininc(y);ify=mthenbegininc(x);y：=；end;ifx=nthenexit;end;fori:=x-1tox+1doif(i>=0)and(i<n)thenforj:=y-1toy+1doif(j>=0)and(j<m)then；fori:=x-1tox+1doif(i>=0)and(i<n)thenforj:=y-1toy+1doif(j>=0)and(j<m)then；inc(y);ify=mthenbegininc(x);y：=0;end;if

17、x=nthenexit;untilfalse;end;beginread(n,m,k);ans:=0;f川char(hash,sizeof(hash),0);writeln(ans);end.NOIP2009年普及組（Pascal語言）參考答案與評分標準一、單項選擇題：（每題1.5分）1.D2.B3.A4.A5.B6.D7.C8.B9.C10.D11.C12.C13.B14.D15.D16.B17.D18.A19.C20.B二、問題求解：（共2題，每空5分，共計10分）1 .702 .5三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）3 .42. 4163. 7824. NPOI四.完善程序（前8空，每空3分，后2空，每空2分，共28分）（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機驗證