全國青少年信息學(xué)奧賽試題及答案

1、.第十五屆（2009年）信息學(xué)奧賽初賽試題及答案 一.單項選擇題 （共10題，每題1.5分，共計15分，每題有且僅有一個正確答案。） 1 、關(guān)于圖靈機下面的說法哪個是正確的： 圖靈機是世界上最早的電子計算機。 由于大量使用磁帶操作，圖靈機運行速度很慢。 圖靈機只是一個理論上的計算模型。 圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。 答案（c） 2、關(guān)于bios下面的說法哪個是正確的： bios是計算機基本輸入輸出系統(tǒng)軟件的簡稱。 bios里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動程序。 bios一般由操作系統(tǒng)廠商來開發(fā)完成。 bios能提供各種文件拷貝

2、、復(fù)制、刪除以及目錄維護等文件管理功能。 答案（a） 3 、已知大寫字母a的ascii編碼為65（十進制），則大寫字母j的十六進制ascii編碼 為： a）48 b）49 c）50 d）以上都不是 答案（d） 4 、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為1111111111101101。其對應(yīng)的十進制整數(shù)應(yīng)該是： a）19 b）-19 c）18 d）-18 答案（b） 5 、一個包含n個分支結(jié)點（非葉結(jié)點）的非空滿k叉樹，k=1，它的葉結(jié)點數(shù)目為： nk+1 b）nk-1 c）(k+1)n-1 d）(k-1)n+1 答案（d） 6 、表達(dá)式a*(b+c)-d的后綴表達(dá)式

3、是： abcd*+- b）abc+*d- c）abc*+d- d）-+*abcd 答案（b） 7 、最優(yōu)前綴編碼，也稱huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼： a）（00，01，10，11） b）（0，1，00，11） c）（0，10，110，111） d）（1，01，000，001） 答案（b） 8 、快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為： 平均情況o(nlog(2,n)，最壞情況o(n2) 平均情況o(n)，最壞情況o(n2) 平均情況o(n)，最壞情況o(nlog(2,n) 平均

4、情況o(log(2,n)，最壞情況o(n2) 答案（a） 9 、左圖給出了一個加權(quán)無向圖，從頂點v0開始用prim算法求最小生成樹。則依次加 入最小生成樹的頂點集合的頂點序列為： v0，v1，v2，v3，v5，v4 v0，v1，v5，v4，v3，v3 v1，v2，v3，v0，v5，v4 v1，v2，v3，v0，v4，v5 答案（a） 10、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息 和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是： / / / http:/www.xi

5、/ 答案（c） 精品.精品.二、.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數(shù)不少于1。多選或少選均不得分）。 1、關(guān)于cpu下面哪些說法是正確的： a）cpu全稱為中央處理器（或中央處理單元）。 b）cpu能直接運行機器語言。 c）cpu最早是由intel公司發(fā)明的。 d）同樣主頻下，32位的cpu比16位的cpu運行速度快一倍。 答案（ab） 2、關(guān)于計算機內(nèi)存下面的說法哪些是正確的： a）隨機存儲器（ram）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。 b）一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。 c）計

6、算機內(nèi)存嚴(yán)格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。 d）1mb內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。 答案（bd） 3、關(guān)于操作系統(tǒng)下面說法哪些是正確的： a.多任務(wù)操作系統(tǒng)專用于多核心或多個cpu架構(gòu)的計算機系統(tǒng)的管理。 b.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。 c.分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。 d.為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費開源的。 答案（bc） 4、關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的： a）網(wǎng)絡(luò)

7、協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。 b）新一代互聯(lián)網(wǎng)使用的ipv6標(biāo)準(zhǔn)是ipv5標(biāo)準(zhǔn)的升級與補充。 c）tcp/ip是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有tcp和ip等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。 d）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的ip地址，否則就必須注冊一個固定的域名來標(biāo)明其地址。 答案（c） 5、關(guān)于html下面哪些說法是正確的： a）html全稱超文本標(biāo)記語言，實現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。 b）html不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。 c）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實

8、現(xiàn)。 d）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（url）請求網(wǎng)絡(luò)資源或者網(wǎng)絡(luò)服務(wù)。 答案（bd） 6、若3個頂點的無權(quán)圖g的鄰接矩陣用數(shù)組存儲為0，1，11，0，10，1，0，假定在具體存儲中頂點依次為：v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的： a）該圖是有向圖。 b）該圖是強聯(lián)通的。 c）該圖所有頂點的入度之和減所有頂點的出度之和等于1。 d）從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。 答案（abd） 7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有了

9、2個以上的結(jié)點。下面哪些說法是正確的： a）如果p指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為： p.next:=clist.next;clist.next:=p; b）如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為： p.next:=clist;clist.next:=p; c）在頭部刪除一個結(jié)點的語句序列為： p:=clist.next;clist.next:=clist.next.next;dispose(p); d）在尾部刪除一個結(jié)點的語句序列為： p:=clist;clist:=clist.next;dispose(p); 答案（ac） 8、散列表的地址區(qū)間為

10、0-10，散列函數(shù)為h(k)=k mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假 定之前散列表為空，則元素59存放在散列表中的可能地址有： a）5 b）7 c）9 d）10 答案（abc） 9、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的： a）插入排序 b）基數(shù)排序 c）歸并排序 d）冒泡排序 答案（abcd） 10、在參加noi系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的： a）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。 b）在聯(lián)

11、機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。 c）通過互聯(lián)網(wǎng)搜索取得解題思路。 d）在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。 三.、問題求解（共2題，每空5分，共計10分） 1.拓?fù)渑判蚴侵笇⒂邢驘o環(huán)圖g中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若e(g)，則u在線性序列 中出現(xiàn)在v之前，這樣的線性序列成為拓?fù)湫蛄?。如下的有向無環(huán)圖，對其頂點做拓?fù)渑判?，則所有可能的拓?fù)湫蛄械膫€數(shù)為_432_。 2、某個國家的錢幣面值有1，7，72，73共計四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通

12、_35_張錢幣。 四、.閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分） 1. var a,b:integer; function work(a,b:integer):integer; begin if a mod b 0 then work := work(b,a mod b) else work := b; end; begin read(a,b); writeln(work(a,b); end. 輸入：123 321 輸出：_3_ 精品.2. var a,b:array0.3of integer; i,j,tmp:integer; begin for i := 0 to 3 do read

13、(bi); for i := 0 to 3 do begin ai := 0; for j := 0 to i do begin inc(ai,bj); inc(bai mod 4,aj); end; end; tmp:=1; for i := 0 to 3 do begin ai := ai mod 10; bi := bi mod 10; tmp := tmp * (ai + bi); end; writeln(tmp); end. 輸入：2 3 5 7 輸出：_5850_ 精品.3. const y = 2009; maxn = 50; var n,i,j,s:longint; c:ar

14、ray0.maxn,0.maxnof longint; begin s := 0; read(n); c0,0 := 1; for i := 1 to n do begin ci,0 := 1; for j := 1 to i - 1 do ci,j := ci-1,j-1 + ci-1,j; ci,i := 1; end; for i := 0 to n do s := (s + cn,i) mod y; write(s); end. 輸入：17 輸出：_487_ 4. var n,m,i,j,k,p:integer; a,b:array0.100of integer; begin read

15、(n,m); a0 := n; i := 0; p := 0; k := 0; repeat for j := 0 to i - 1 do if ai = aj then begin p := i; k := j; break; end; if p 0 then break; bi := ai div m; ai+1 := (ai mod m) * 10; inc(i); until ai = 0精品.noip2009初賽普及組（pascal語言）參考答案與評分標(biāo)準(zhǔn)一、單項選擇題：（每題1.5分） 1. d 2. b 3. a 4. a 5. b6. d 7. c 8. b 9. c 10.

16、d11. c 12. c13. b 14. d 15. d 16. b 17. d 18. a 19. c 20. b二、問題求解：（共2題，每空5分，共計10分）17025三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1. 42. 4163. 7824. npoi四完善程序 (前8空，每空3分，后2空，每空2分，共28分)1. 0 tmp+ai=ans或者 ai+tmp=ans 或者ans=ai+tmp等 =1，它的葉結(jié)點數(shù)目為： a) nk + 1 b) nk-1 c) (k+1)n-1 d. (k-1)n+1 6. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是： a) abcd*+- b)

17、 abc+*d- c) abc*+d- d) -+*abcd 7、最優(yōu)前綴編碼，也稱huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。 a)（00，01，10，11） b)（0，1，00，11） c)（0，10，110，111） d)（1，01，000，001） 8、快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為： a) 平均情況 o(nlog2n)，最壞情況o(n2) b) 平均情況 o(n)， 最壞情況o(n2) c) 平均情況 o(n)， 最壞情況o(nlog2n) d) 平均情況 o(log2n)

18、， 最壞情況o(n2) 9、左圖給出了一個加權(quán)無向圖，從頂點v0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點集合的頂點序列為： a) v0, v1, v2, v3, v5, v4 b) v0, v1, v5, v4, v3, v3 c) v1, v2, v3, v0, v5, v4 d) v1, v2, v3, v0, v4, v5 10、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是： a) / b) / )

19、/ d) / 二 不定項選擇題 （共10題，每題1.5分，共計15分。每題正確答案的個數(shù)不少于1。多選或少選均不得分）。 1、關(guān)于cpu下面哪些說法是正確的： a) cpu全稱為中央處理器（或中央處理單元）。 b) cpu能直接運行機器語言。 c) cpu最早是由intel公司發(fā)明的。 d) 同樣主頻下，32位的cpu比16位的cpu運行速度快一倍。 2、關(guān)于計算機內(nèi)存下面的說法哪些是正確的： a) 隨機存儲器（ram）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。 b) 一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。

20、 c) 計算機內(nèi)存嚴(yán)格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。 d) 1mb內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。 3、關(guān)于操作系統(tǒng)下面說法哪些是正確的： a. 多任務(wù)操作系統(tǒng)專用于多核心或多個cpu架構(gòu)的計算機系統(tǒng)的管理。 b. 在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。 c. 分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。 d. 為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費開源的。 4、關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的： a) 網(wǎng)絡(luò)協(xié)議之

21、所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。 b) 新一代互聯(lián)網(wǎng)使用的ipv6標(biāo)準(zhǔn)是ipv5標(biāo)準(zhǔn)的升級與補充。 c) tcp/ip是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有tcp和ip等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。 d) 互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的ip地址，否則就必須注冊一個固定的域名來標(biāo)明其地址。 5、關(guān)于html下面哪些說法是正確的： a) html全稱超文本標(biāo)記語言，實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。 b) html不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。 c) 網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實現(xiàn)。 d

22、) 點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（url）請求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)服務(wù)。 6、若3個頂點的無權(quán)圖g的鄰接矩陣用數(shù)組存儲為0，1，1，1，0，1，0，1，0，假定在具體存儲中頂點依次為: v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的： a) 該圖是有向圖。 b) 該圖是強連通的。 c) 該圖所有頂點的入度之和減所有頂點的出度之和等于1。 d) 從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。 7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有2個以上的結(jié)點。下面哪些說

23、法是正確的： a) 如果p指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為： p.next:= clist.next; clist.next:= p; b) 如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為： p.next:= clist; clist.next:= p; c) 在頭部刪除一個結(jié)點的語句序列為： p:= clist.next; clist.next:= clist.next.next; dispose(p); d) 在尾部刪除一個結(jié)點的語句序列為。 p:= clist; clist:= clist .next; dispose(p); 8、散列表的地址區(qū)間為0

24、-10,散列函數(shù)為h(k)=k mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有： 精品.a) 5 b) 7 c) 9 d) 10 9、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的： a) 插入排序 b) 基數(shù)排序 c) 歸并排序 d) 冒泡排序 10、在參加noi系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的： a) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。 b) 在聯(lián)機測試中通過

25、手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。 c) 通過互聯(lián)網(wǎng)搜索取得解題思路。 d) 在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。 三問題求解（共2題，每空5分，共計10分） 1拓?fù)渑判蚴侵笇⒂邢驘o環(huán)圖g中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若 e(g)，則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓?fù)湫蛄?。如下的有向無環(huán)圖，對其頂點做拓?fù)渑判?，則所有可能的拓?fù)湫蛄械膫€數(shù)為 。 2某個國家的錢幣面值有1, 7, 72, 73共計四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通 張錢幣。 四閱讀

26、程序?qū)懡Y(jié)果（共4題，每題8分，共計32分） 1 var a, b: integer; function work(a, b: integer): integer; begin if a mod b 0 then work := work(b, a mod b) else work := b; end; begin read(a, b); writeln(work(a, b); end. 輸入：123 321 輸出：_ 2 var a, b: array0.3 of integer; i, j, tmp: integer; begin for i := 0 to 3 do read(bi); f

27、or i := 0 to 3 do begin ai := 0; for j := 0 to i do begin inc(ai, bj); inc(bai mod 4, aj); end; end; tmp := 1; for i := 0 to 3 do begin ai := ai mod 10; bi := bi mod 10; tmp := tmp * (ai + bi); end; writeln(tmp); end. 輸入：2 3 5 7 輸出：_ 3 const y = 2009; maxn = 50; var n, i, j, s: longint; c: array0.ma

28、xn, 0.maxn of longint; begin s := 0; read(n); c0, 0 := 1; for i := 1 to n do begin ci, 0 := 1; for j := 1 to i - 1 do ci, j := ci-1, j-1 + ci-1, j; ci, i := 1; end; for i := 0 to n do s := (s + cn, i) mod y; write(s); end. 輸入：17 輸出： 4 var n, m, i, j, k, p: integer; a, b: array0.100 of integer; begin

29、 read(n, m); a0 := n; i := 0; p := 0; k := 0; repeat for j := 0 to i - 1 do if ai = aj then begin p := 1; k := j; break; end; if p 0 then break; bi := ai div m; ai+1 := (ai mod m) * 10; inc(i); until ai = 0; write(b0, .); for j := 1 to k - 1 do write(bj); if p 0 then write(); for j := k to i - 1 do

30、write(bj); if p 0 then write(); writeln; end. 輸入：5 13 輸出：_ 五完善程序 (前5空，每空2分，后6空，每空3分，共28分) 1（最大連續(xù)子段和）給出一個數(shù)列（元素個數(shù)不多于100），數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4，-5，3，2，4時，輸出9和3；數(shù)列為1 2 3 -5 0 7 8時，輸出16和7。 var a: array1.100 of integer; n, i, ans, len, tmp, beg: integer; begin read(n); for i := 1 to n do read(ai); tmp := 0; ans := 0; len := 0; beg := ; for i := 1 to n do begin if tmp + ai ans th