全國青少年信息學奧賽試題及答案

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

2、、復制、刪除以及目錄維護等文件管理功能。 答案（a） 3 、已知大寫字母a的ascii編碼為65（十進制），則大寫字母j的十六進制ascii編碼 為： a）48 b）49 c）50 d）以上都不是 答案（d） 4 、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為1111111111101101。其對應的十進制整數(shù)應該是： a）19 b）-19 c）18 d）-18 答案（b） 5 、一個包含n個分支結點（非葉結點）的非空滿k叉樹，k=1，它的葉結點數(shù)目為： nk+1 b）nk-1 c）(k+1)n-1 d）(k-1)n+1 答案（d） 6 、表達式a*(b+c)-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 、快速排序平均情況和最壞情況下的算法時間復雜度分別為： 平均情況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 、左圖給出了一個加權無向圖，從頂點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、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息 和資源，請問全國信息學奧林匹克官方網站的網址是： / / / http:/www.xi

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

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

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

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

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

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

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

12、_35_張錢幣。 四、.閱讀程序寫結果（共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語言）參考答案與評分標準一、單項選擇題：（每題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三、閱讀程序寫結果（共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，它的葉結點數(shù)目為： a) nk + 1 b) nk-1 c) (k+1)n-1 d. (k-1)n+1 6. 表達式a*(b+c)-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、快速排序平均情況和最壞情況下的算法時間復雜度分別為： a) 平均情況 o(nlog2n)，最壞情況o(n2) b) 平均情況 o(n)， 最壞情況o(n2) c) 平均情況 o(n)， 最壞情況o(nlog2n) d) 平均情況 o(log2n)

18、， 最壞情況o(n2) 9、左圖給出了一個加權無向圖，從頂點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、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是： a) / b) / )

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

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

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

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

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

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

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

26、程序寫結果（共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ù)列元素均為負整數(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