全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題2009-2015

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

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

3、。C) 同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。D) CPU最早是由Intel公司創(chuàng)造的。5、關(guān)于ASCII，下面哪個(gè)說法是正確的：A) ASCII碼就是鍵盤上所有鍵的唯一編碼。B) 一個(gè)ASCII碼使用一個(gè)字節(jié)的內(nèi)存空間就能夠存放。C) 最新擴(kuò)展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。D) ASCII碼是英國(guó)人主持制定并推廣使用的。6、以下軟件中不是計(jì)算機(jī)操作系統(tǒng)的是： A) Windows B) Linux C) OS/2 D) WPS7、關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個(gè)是正確的：A) 新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。B) 互聯(lián)網(wǎng)的入網(wǎng)主

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

5、植。D) 以上說法都不對(duì)。10、大寫字母A的ASCII編碼為65十進(jìn)制，那么大寫字母J的十進(jìn)制ASCII編碼為：A) 71 B) 72 C) 73 D) 以上都不是11、十進(jìn)制小數(shù)125.125對(duì)應(yīng)的八進(jìn)制數(shù)是A) 100.1 B) 175.175 C) 175.1 D) 100.17512、有六個(gè)元素FEDCBA 從左至右依次順序進(jìn)棧，在進(jìn)棧過程中會(huì)有元素被彈出棧。問以下哪一個(gè)不可能是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF13、 表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A) abcd*+- B) abc+*d- C) abc*+d-

6、D) -+*abcd14、一個(gè)包含n個(gè)分支結(jié)點(diǎn)非葉結(jié)點(diǎn)的非空二叉樹，它的葉結(jié)點(diǎn)數(shù)目最多為：A) 2n + 1 B) 2n-1 C) n-1 D) n+1 15、快速排序最壞情況下的算法復(fù)雜度為： A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)16. 有一個(gè)由4000個(gè)整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個(gè)元素。那么最多需要幾次比擬就能確定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次17、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對(duì)位置不發(fā)生改變，以下哪種排序算法是不穩(wěn)定的：A) 冒泡排序

7、B) 插入排序 C) 歸并排序 D) 快速排序18、n個(gè)頂點(diǎn)的有向圖，假設(shè)該圖是強(qiáng)連通的從所有頂點(diǎn)都存在路徑到達(dá)其他頂點(diǎn)，那么該圖中最少有多少條有向邊？A) n B) n+1 C) n-1 D) n*(n-1)19、全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A) :/ noi /B) :/ /C) :/ noi /D) :/ xinxixue /20、在參加NOI系列競(jìng)賽過程中，下面哪一種行為是 不 被嚴(yán)格禁止的：A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場(chǎng)。B) 在聯(lián)機(jī)測(cè)試中通過手工計(jì)算出

8、可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。C) 通過互聯(lián)網(wǎng)搜索取得解題思路。D) 在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。二問題求解共2題，每空5分，共計(jì)10分1小陳現(xiàn)有2個(gè)任務(wù)A，B要完成，每個(gè)任務(wù)分別有假設(shè)干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時(shí)候，小陳只能專心做某個(gè)任務(wù)的一個(gè)步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個(gè)任務(wù)，從上次此任務(wù)第一個(gè)未做的步驟繼續(xù)。每個(gè)任務(wù)的步驟順序不能打亂，例如a2->b2->a3->b3是合法的，而a2->b3->

9、a3->b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個(gè)任務(wù)的某個(gè)步驟后，就停工回家吃飯了。當(dāng)他回來時(shí)，只記得自己已經(jīng)完成了整個(gè)任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有 種。2有如下的一段程序：1.a:=1;2.b:=a;3.d:=-a;4.e:=a+d;5.c:=2*d;6.f:=b+e-d;7.g:=a*f+c;現(xiàn)在要把這段程序分配到假設(shè)干臺(tái)數(shù)量充足用電纜連接的PC上做并行執(zhí)行。每臺(tái)PC執(zhí)行其中的某幾個(gè)語句，并可隨時(shí)通過電纜與其他PC通訊，交換一些中間結(jié)果。假設(shè)每臺(tái)PC每單位時(shí)間可以執(zhí)行一個(gè)語句，且通訊花費(fèi)的時(shí)間不計(jì)。那么這段程序最快可以在 單位時(shí)間

10、內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺(tái)PC上已經(jīng)得到，才可以被其他PC引用。例如假設(shè)語句4和6被分別分配到兩臺(tái)PC上執(zhí)行，那么因?yàn)檎Z句6需要引用語句4的計(jì)算結(jié)果，語句6必須在語句4之后執(zhí)行。三閱讀程序?qū)懡Y(jié)果共4題，每題8分，共計(jì)32分1vara, b: integer;function work(a, b: integer): integer;beginif a mod b <> 0 thenwork := work(b, a mod b)elsework := b;end;beginread(a, b);writeln(work(a, b);end.輸入：20 12輸出：_2v

11、ara, b: array0.2 of integer;i, j, tmp: integer;beginfor i := 0 to 2 doread(bi);for i := 0 to 2 dobeginai := 0;for j := 0 to i dobegininc(ai, bj);inc(bai mod 3, aj);end;end;tmp := 1;for i := 0 to 2 dobeginai := ai mod 10;bi := bi mod 10;tmp := tmp * (ai + bi);end;writeln(tmp);end.輸入：2 3 5輸出：_3const c

12、 = 2021;varn, p, s, i, j, t: integer;beginread(n, p);s := 0; t := 1;for i := 1 to n dobegint := t * p mod c;for j := 1 to i dos := (s + t) mod c;end;writeln(s);end.輸入：11 2輸出： 4vara: string;n: integer;procedure getnext(var str: string);varl, i, j, k: integer;temp: char;beginl := length(str);k := l -

13、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;for i := l downto k + 1 dofor j := k + 1 to i - 1 doif strj > strj+1 thenbegintemp := strj;strj := strj+1;strj+1 := temp;end;end;beginread(a);read(n);w

14、hile n > 0 dobegingetnext(a);dec(n);end;write(a);end.輸入：NOIP 3輸出： 四完善程序 (前8空，每空3分，后2空，每空2分，共28分)1最大連續(xù)子段和給出一個(gè)數(shù)列元素個(gè)數(shù)不多于100，數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5，3，2，4時(shí)，輸出9和3；數(shù)列為1 2 3 -5 0 7 8時(shí)，輸出16和7。vara: array1.100 of integer;

15、n, i, ans, len, tmp, beg: integer;beginread(n);for i := 1 to n doread(ai);tmp := 0;ans := 0;len := 0;beg := ;for i := 1 to n dobeginif tmp + ai > ans thenbeginans := tmp + ai;len := i - beg;endelse if ( ) and (i - beg > len) thenlen := i - beg;if tmp + ai thenbeginbeg := ;tmp := 0;endelse ; en

16、d;writeln(ans, ' ', len);end.2. (國(guó)王放置) 在n*m的棋盤上放置k個(gè)國(guó)王，要求k個(gè)國(guó)王互相不攻擊，有多少種不同的放置方法。假設(shè)國(guó)王放置在第(x,y)格，國(guó)王的攻擊的區(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)。讀入三個(gè)數(shù)n,m,k，輸出答案。題目利用回溯法求解。棋盤行標(biāo)號(hào)為0n-1，列標(biāo)號(hào)為0m-1。varn, m, k, ans: integer;hash: array0.4, 0.4 of integer;procedure work

17、(x, y, tot: integer);vari, j: integer;beginif tot = k thenbegininc(ans);exit;end;repeatwhile hashx, y <> 0 dobegininc(y);if y = m thenbegininc(x);y := ;end;if x = n thenexit;end;for i := x - 1 to x + 1 doif (i >= 0) and (i < n) thenfor j := y - 1 to y + 1 doif (j >= 0) and (j < m)

18、then ; ;for i := x - 1 to x + 1 doif (i >= 0) and (i < n) thenfor j := y - 1 to y + 1 doif (j >= 0) and (j < m) then ;inc(y);if y = m thenbegininc(x);y := 0;end;if x = n thenexit;until false;end;beginread(n, m, k);ans := 0;fillchar(hash, sizeof(hash), 0); ;writeln(ans);end.NOIP2021年普及組Pa

19、scal語言參考答案與評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題：每題1.5分 1. D 2. B 3. A 4. A 5. B6. D 7. C 8. B 9. C 10. D11. C 12. C 13. B 14. D 15. D 16. B 17. D 18. A 19. C 20. B二、問題求解：共2題，每空5分，共計(jì)10分170 25三、閱讀程序?qū)懡Y(jié)果共4題，每題8分，共計(jì)32分1. 4 2. 416 3. 782 4. NPOI四完善程序 (前8空，每空3分，后2空，每空2分，共28分) 說明：以下各程序填空可能還有一些等價(jià)的寫法，各省可請(qǐng)本省專家審定和上機(jī)驗(yàn)證，不一定上報(bào)科學(xué)委員會(huì)審查1. 0

20、tmp+ai=ans或者 ai+tmp=ans 或者ans=ai+tmp等 <0 i inc(tmp, ai)或者tmp := tmp+ai2. 0 inc(hashi, j)或者 hashij:= hashij+1 work(x,y,tot+1) dec(hashi, j) 或者 hashij:= hashij-1 work(0,0,0)注意： 兩空，不一定要+1 或者 -1。也可以是 -1 , +1. 也可以是 + k , 也可以 - k, 甚至任何加標(biāo)記的操作(如位運(yùn)算)都可以，只要相互撤銷。所以答案非常多。第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組 Pascal語言 兩小

21、時(shí)完成全部試題答案均要求卸載答卷紙上，寫在試卷上一律無效一、單項(xiàng)選擇題共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。1. 2E+03表示   。A.2.03          B.5          C.8          D.20002.一個(gè)字節(jié)byte由   個(gè)二進(jìn)

22、制組成。A.8         B.16          C.32          D.以上都有可能3.以下邏輯表達(dá)式的值恒為真的是    。A.PPQ(PQ)B.QPQPQC.PQPQPQD.PQPQ(PQ)4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名是(    )。A. exe

23、           B. com         C. dll         D.以上都不是5.如果樹根算第1層，那么一顆n層的二叉樹最多有 個(gè)結(jié)點(diǎn)。A. 2n-1         B. 2n    

24、60;   C.  2n+1        D. 2n+16.提出“存儲(chǔ)程序的計(jì)算機(jī)工作原理的是 。A. 克勞德香農(nóng)    B. 戈登摩爾     C. 查爾斯巴比奇     D.馮諾依曼7.設(shè)X、Y、Z分別代表三進(jìn)制下的一個(gè)數(shù)字，假設(shè)等式XY + ZX = XYX在三進(jìn)制下成立，那么同樣在三進(jìn)制下，等式 XY * ZX = ( )也成立。A. YXZ

25、60;    B. ZXY    C. XYZ      D.XZY8.Pascal語言、C語言和C+語言都屬于 。A. 面向?qū)ο笳Z言  B. 腳本語言   C. 解釋性語言 D.編譯性語言9.前綴表達(dá)式“+ 3 * 2 + 5   12 的值是 。A.     23         B.   &#

26、160; 25         C.     37         D.     6510.主存儲(chǔ)器的存取速度比中央處理器(CPU)的工作速度慢的多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問的存儲(chǔ)單元通常都趨于一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了(   )。A. 存放器 &#

27、160;       B.  高速緩存         C.  閃存         D.  外存11.一個(gè)字長(zhǎng)為8位的整數(shù)的補(bǔ)碼是11111001，那么它的原碼是 。A. 00000111   B. 01111001  C. 11111001      D.1000011112

28、.基于比擬的排序時(shí)間復(fù)雜度的下限是 ，其中n表示待排序的元素個(gè)數(shù)。A. O(n)     B. O(n log n)  C. O(log n)      D. O(n2)13.一個(gè)自然數(shù)在十進(jìn)制下有n位，那么它在二進(jìn)制下的位數(shù)與 最接近。A. 5n      B. n*log210  C. 10*log2 n      D. 10n log2 n14.在以下HTML語句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的

29、是 。A. <a url= :/ noi,cn>歡送訪問NOI網(wǎng)站</a>B. <a href= :/ noi,cn>歡送訪問NOI網(wǎng)站</a>C. <a> :/ noi,cn </a>D. <a name= :/ noi,cn>歡送訪問NOI網(wǎng)站</a>15元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1個(gè)出棧的是R3，那么第5個(gè)出棧的不可能是(   )。A.  R1     

30、0;   B. R2         C. R4         D. R516. 雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均為非空。現(xiàn)要求刪除結(jié)點(diǎn)p，那么以下語句序列中錯(cuò)誤的選項(xiàng)是(    )。Ap.rlink.llink=p.rlink;   p.llink.rlink=p

31、.llink; delete p;Bp.llink.rlink=p.rlink;   p.rlink.llink = p.llink; delete p;Cp.rlink.llink = p.llink;   p.rlink.llink .rlink = p.rlink; delete p;Dp.llink.rlink = p.rlink;   p.llink.rlink.link = p.llink; delete p;17. 一棵二叉樹的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，那么

32、根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是   。A2         B. 3         C. 4         D. 518. 關(guān)于拓?fù)渑判?，以下說法正確的選項(xiàng)是(   )。A所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判駼對(duì)同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的C拓?fù)渑判蛑腥攵葹?的結(jié)點(diǎn)總會(huì)排在入度大

33、于0的結(jié)點(diǎn)的前面D拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度大于0的點(diǎn)19.完全二叉樹的順序存儲(chǔ)方案，是指將完全二叉樹的結(jié)點(diǎn)從上到下、從左到右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號(hào)位置上，那么第k號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的   號(hào)位置。A. 2k         B. 2k+1         C. k/2下取整     

34、0;       D. (k+1)/220. 全國(guó)青少年信息學(xué)奧林匹克系列活動(dòng)的主辦單位是   。A. 教育部      B. 科技部      C. 共青團(tuán)中央         D. 中國(guó)計(jì)算機(jī)學(xué)會(huì) 三、問題求解共2題，每題5分，共計(jì)10分1LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時(shí)只有一部根底構(gòu)造元素的編碼詞典，

35、如果在編碼的過程中遇到一個(gè)新的詞條，那么該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。     舉例說明，考慮一個(gè)待編碼的信息串：“xyx yy yy xyx。初始詞典只有3個(gè)條目，第一個(gè)為x,編碼為1；第二個(gè)為y，編碼為2；第三個(gè)為空格，編碼為3；于是串“xyx的編碼為1-2-1其中-為編碼分隔符，加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx是一個(gè)單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添加到詞典里，編碼為4，然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類推。于是，最后得到編碼：1-2

36、-1-3-2-2-3-5-3-4?，F(xiàn)在初始詞典的3個(gè)條目如上述，那么信息串“yyxy xx yyxy xyx xx xyx的編碼是 2. 隊(duì)列快照是指在某一時(shí)刻隊(duì)列中的元素組成的有序序列?，F(xiàn)有3個(gè)正整數(shù)元素依次入隊(duì)、出隊(duì)。它們的和為8，那么共有_種可能的不同的隊(duì)列快照不同隊(duì)列的相同快照只計(jì)一次。例如，"5 1"、"4 2 2"、""都是可能的隊(duì)列快照；而"7"不是可能的隊(duì)列快照，因?yàn)槭Ｏ碌?個(gè)正整數(shù)的和不可能是1。 四、閱讀程序?qū)懡Y(jié)果共4題，每題8分，其中第4題12各4分，共計(jì)32分1.var a1,a2

37、,a3,x:integer;procedure swap(var a,b:integer);var t:integer;begin t:=a; a:=b; b:=t;end; begin readln(a1,a2,a3); if a1>a2 then swap(a1,a2); if a2>a3 then swap(a2,a3); if a1>a2 then swap(a1,a2); readln(x); if x<a2 then if x<a1 then writeln(x, ,a1, , a3, ,a3) else writeln(a1, ,x, ,

38、a2, ,a3) else if x<a3 then writeln(a1, ,a2, , x, ,a3) else writeln(a1, ,a2, , a3, ,x)end.輸入91 2 2077輸出：_ 2.Var n,m,i:integer;function rSum(j:integer):integer;var sum:integer;begin sum:=0; while j<>0 do begin sum:=sum*10+(j mod 10); j:=j div 10; end; rSum:=sum;end; begin readln(n,m

39、); for i:=n to m do if i=rSum(i) then write(I,);end.輸入：90 120輸出：_ 3.var s:string; i:integer; m1,m2:char;begin readln(s); m1:=; m2:=; for i:=1 to length(s) do if si>m1 then begin m2:=m1; m1:=si; end else if si>m2 then m2:=si; writeln(ord(m1), ,ord(m2);end.輸入：Expo 2021 Shanghai China輸出：提示：字

40、符空格0AaASCII碼324865974.const    num = 5;var    n: integer;function r(n : integer) : integer;var    i : integer;begin    if n <= num then    begin       r := n;     

41、0; exit;    end;    for i :=1 to num do       if r(n-i) < 0 then       begin         r:=i;         exit;    

42、;   end;    r:=-1;end;begin    readln(n);    writeln(r(n);end.(1) 輸入:7輸出：_(4分)(2)輸入 16輸出：_(4分)  五、完善程序1.哥德巴赫猜測(cè)哥德巴赫猜測(cè)是指，任一大于2的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)的和。迄今為止，這仍然是一個(gè)著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編寫程序，驗(yàn)證任一大于2且不超過n的偶數(shù)都能寫成兩個(gè)質(zhì)數(shù)之和。const size=1000;var n,r,I,j,k,ans:

43、integer; p：array1.size of integer; tmp:Boolean;begin readln(n); r:=1; p1:=2; for i:=3 to n do begin ； for j:=1 to r do if I mod =0 thenbegin tmp:=false; break;end;if tmp thenbegin inc(r); ;end; end; ans:=0; for i:=2 to (n div 2) do begin tmp:=false; for j:=1 to r do for k:=j to r do if i+i= then beg

44、in tmp:=true; break; end; if tmp then inc(ans); end; writeln(ans);end.假設(shè)輸入n為2021，那么輸出 時(shí)表示驗(yàn)證成功，即大于2且不超過2021的偶數(shù)都滿足哥德巴赫猜測(cè)。2.(過河問題) 在一個(gè)月黑風(fēng)高的夜晚,有一群人在河的右岸,想通過唯一的一根獨(dú)木橋走到河的左岸.在伸手不見五指的黑夜里,過橋時(shí)必須借照燈光來照明,不幸的是,他們只有一盞燈.另外,獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過,否那么將會(huì)坍塌.每個(gè)人單獨(dú)過獨(dú)木橋都需要一定的時(shí)間,不同的人要的時(shí)間可能不同.兩個(gè)人一起過獨(dú)木橋時(shí),由于只有一盞燈,所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過

45、橋所花費(fèi)的時(shí)間.現(xiàn)在輸入N(2<=N<1000)和這N個(gè)人單獨(dú)過橋需要的時(shí)間,請(qǐng)計(jì)算總共最少需要多少時(shí)間,他們才能全部到達(dá)河左岸.      例如,有3個(gè)人甲、乙、丙,他們單獨(dú)過橋的時(shí)間分別為1   2   4,那么總共最少需要的時(shí)間為7.具體方法是:甲   乙一起過橋到河的左岸,甲單獨(dú)回到河的右岸將燈帶回,然后甲,丙在一起過橋到河的左岸,總時(shí)間為2+1+4=7.CONSTSIZE = 100;     INFINITY = 1000

46、0;     LEFT = true;     RIGHT = false;     LEFT_TO_RIGHT = true;     RIGHT_TO_LEFT = false;var     n, i : integer;     time : array1.Size of integer;     pos :a

47、rray1.Size of Boolean;function max(a, b :integer) : integer;beginif a > b then       max := a     else       max := b;end;function go(stage : boolean) : integer;var     i, j, num, tmp, ans : intege

48、r;beginif   (stage = RIGHT_TO_LEFT)     then begin        num := 0;        ans :=0;        for i := 1 to n do         &#

49、160; if posi = Rignt then           begin              inc(num);              if timei > ans then   &#

50、160;            ans := timei;end;if _ thenbegin   go := ans;   exit;end;ans := INFINITY;for i := 1 to n 1 do    if posi = RIGHT then      for j := i+1 to n do    

51、60;    if posj = RIGHT then         begin            posi := LEFT;            posj := LEFT;       &#

52、160;    tmp := max(timei, timej) + _;            if tmp < ans then              ans := tmp;            posi

53、 := RIGHT;            posj := RIGHT;         end;go := ans;endelse if   (stage = LEFT_TO_RIGHT)then begin   ans := INFINITY;     for i := 1 to n do   

54、   if _ then        begin            posi := RIGHT;           tmp := _;           if tmp < ans then

55、60;            ans := tmp;           _;         end;go := ans;   end   else go := 0;end; begin    readln(n); &

56、#160;  for i := 1 to n do    begin     read(timei);       posi := RIGHT;    end;writeln(go(RIGHT_TO_LEFT);end.一、單項(xiàng)選擇題共20題，每題1.5分，共計(jì)30分1 2 3 4 5 6 7 8 9 10D A A D A D B D C B11 12 13 14 15 16 17 18 19 20D B B B B A A

57、 D C D二、問題求解共2題，每題5分，共計(jì)10分12-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6或22123113431213536249三、閱讀程序?qū)懡Y(jié)果共4題，每題8分，其中第4題1、2各4分，共計(jì)32分12 20 77 91299 101 1113120 11241124四、完善程序前4空，每空2.5分，后6空，每空3分，共計(jì)28分說明：以下各程序填空可能還有一些等價(jià)的寫法，各省可請(qǐng)本省專家審定和上機(jī)驗(yàn)證，不一定上報(bào)科學(xué)委員會(huì)審查1 tmp = 1 pj pr = i pj + pk或pk + pj 10042 num <= 2或num < 3 或nu

58、m = 2 go(LEFT_TO_RIGHT) posi = LEFT或LEFT = posi timei + go(RIGHT_TO_LEFT)或go(RIGHT_TO_LEFT) + timei posi = LEFT本小題中，LEFT可用1代替，LEFT_TO_RIGHT可用1代替，RIGHT_TO_LEFT可用0代替。第十七屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 普及組 Pascal 語言 兩小時(shí)完成 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項(xiàng)選擇題共 20 題，每題 1.5 分，共計(jì) 30 分。每題有且僅有一個(gè)正確選項(xiàng)。1、在二進(jìn)制下，1101001 + = 11

59、10110。A、1011B、1101C、1010D、11112、字符“0的 ASCII 碼為 48，那么字符“9的 ASCII 碼為 。A、39B、57C、120D、視具體的計(jì)算機(jī)而定3、一片容量為 8GB 的 SD 卡能存儲(chǔ)大約 張大小為 2MB 的數(shù)碼照片。A、1600B、2000C、4000D、160004、摩爾定律Moore's law是由英特爾創(chuàng)始人之一戈登·摩爾Gordon Moore提出來的。根據(jù)摩爾定律，在過去幾十年以及在可預(yù)測(cè)的未來幾年，單塊集成電路的集成度大約每 個(gè)月翻一番。A、1B、6C、18D、365、無向完全圖是圖中每對(duì)頂點(diǎn)之間都恰有一條邊的簡(jiǎn)單圖。

60、無向完全圖 G 有 7 個(gè)頂點(diǎn)，那么它共有 條邊。A、7B、21C、42D、496、存放器是 的重要組成局部。A、硬盤B、高速緩存C、內(nèi)存D、中央處理器CPU7、如果根結(jié)點(diǎn)的深度記為 1，那么一棵恰有 2021 個(gè)葉結(jié)點(diǎn)的二叉樹的深度最少是 。A、10B、11C、12D、138、體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場(chǎng)，按老師的要求從高到矮站成一排。每個(gè)同學(xué)按順序來到操場(chǎng)時(shí)，都從排尾走向排頭，找到第一個(gè)比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的方法類似于 算法。A、快速排序B、插入排序C、冒泡排序D、歸并排序9、一個(gè)正整數(shù)在二進(jìn)制下有 100 位，那么它在十六進(jìn)制下有 位。A、7B、13C、25D、不能確定10、有人認(rèn)為，在個(gè)人電腦送修前，將文件放入回收站中就是已經(jīng)將其刪除了。這種想法是 。A、正確的，將文件放入回收站意味著徹底刪除、無法恢復(fù)B、不正確的，只有將回收站清空后，才意味著徹底刪除、無法恢復(fù)C、不正確的，即使將回收站清空，文件只是被標(biāo)記為刪除，仍可能通過恢復(fù)軟件找回D、不正確的，只要在硬盤上出現(xiàn)過的文件，永遠(yuǎn)不可能被徹底刪除11、廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是 。A、鏈表B、隊(duì)列C、棧D、散列表12、在使用高級(jí)語言編寫程序時(shí)，一般提到的“空間復(fù)雜度中的“空間是指 。A、程序運(yùn)行時(shí)理論