第十五屆（2009年）信息學奧賽初賽試題答案

1、第十五屆（2009年）信息學奧賽初賽試題答案一. 單項選擇題 （共10題，每題1.5分，共計15分，每題有且僅有一個正確答案。） 1 、關于圖靈機下面的說法哪個是正確的：答案（C） A）圖靈機是世界上最早的電子計算機。B）由于大量使用磁帶操作，圖靈機運行速度很慢。 C）圖靈機只是一個理論上的計算模型。 D）圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。最早的計算機是ENIAC    圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作圖靈機是英國人阿蘭圖靈提出的理論，阿蘭圖靈本人在二戰(zhàn)中破譯德軍密碼系統(tǒng)發(fā)揮重要作用，而不是圖靈機發(fā)揮作用。圖靈是英

2、國著名的數(shù)學家和邏輯學家，被稱為計算機科學之父、人工智能之父，是計算機邏輯的奠基者，提出了“圖靈機”和“圖靈測試”等重要概念。人們?yōu)榧o念其在計算機領域的卓越貢獻而設立“圖靈獎”。1936年，阿蘭.圖靈提出了一種抽象的計算模型 圖靈機 (Turing Machine)。圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學運算的過程，他把這樣的過程看作下列兩種簡單的動作： 在紙上寫上或擦除某個符號； 把注意力從紙的一個位置移動到另一個位置；“圖靈機”不是一種具體的機器，而是一種思想模型，可制造一種十分簡單但運算能力極強的計算機裝置，用來計算所有能想像得到的可計算函數(shù)。裝置由一個控制器和一根假設兩端無界的

3、工作帶（起存儲器的作用）組成。工作帶被劃分為大小相同的方格，每一格上可書寫一個給定字母表上的符號?？刂破骺梢栽趲献笥乙苿?，它帶有一個讀寫出一個你期待的結(jié)果。外行人看了會墜入云里霧里，而內(nèi)行人則稱它是“闡明現(xiàn)代電腦原理的開山之作”，并冠以“理想計算機”的名稱?！皥D靈機”更在電腦史上與“馮·諾依曼機”齊名，被永遠載入計算機的發(fā)展史中。回顧20世紀科學技術的輝煌發(fā)展時，不能不提及20世紀最杰出的數(shù)學家之一的馮·諾依曼（美籍匈牙利人）。20世紀40年代，馮·諾依曼在參與世界上第一臺計算機-ENIAC的研制小組工作時，發(fā)現(xiàn)ENIAC有兩個致命的缺陷：一是采用十進制運算，邏

4、輯元件多，結(jié)構(gòu)復雜，可靠性低；二是沒有內(nèi)部存貯器，操縱運算的指令分散存貯在許多電路部件內(nèi)，這些運算部件如同一副積木，解題時必須像搭積木一樣用人工把大量運算部件搭配成各種解題的布局，每算一題都要搭配一次，非常麻煩且費時。 針對這兩個問題，諾依曼和其他合作者一起嘔心瀝血地進行了半年多時間的改革性研究，結(jié)果取得了令人滿意的成果。但是，由于ENIAC的制造已接近尾聲，因此它未能采用諾依曼的改進意見。 諾依曼的研究成果得到了ENIAC研制小組專家的青睞，他們在ENIAC尚未竣工之前，就著手計劃一個結(jié)構(gòu)全新的電子計算機EDVAC方案。1945年6月底，由諾依曼執(zhí)筆寫出了EDVAC計劃草案。在這個方案中，諾

5、依曼提出了在計算機中采用二進制算法和設置內(nèi)存貯器的理論，并明確規(guī)定了電子計算機必須由運算器、控制器、存貯器、輸入設備和輸出設備等五大部分構(gòu)成的基本結(jié)構(gòu)形式。他認為，計算機采用二進制算法和內(nèi)存貯器后，指令和數(shù)據(jù)便可以一起存放在存貯器中，并可作同樣處理，這樣，不僅可以使計算機的結(jié)構(gòu)大大簡化，而且為實現(xiàn)運算控制自動化和提高運算速度提供了良好的條件。EDVAC于1952年建成，它的運算速度與ENIAC相似，而使用的電子管卻只有5900多個，比ENIAC少得多。EDVAC的誕生，使計算機技術出現(xiàn)了一個新的飛躍。它奠定了現(xiàn)代電子計算機的基本結(jié)構(gòu)，標志著電子計算機時代的真正開始。 根據(jù)馮·諾依曼提

6、出的原理制造的計算機被稱為馮·諾依曼結(jié)構(gòu)計算機，現(xiàn)代計算機雖然結(jié)構(gòu)更加復雜，計算能力更加強大，但仍然是基于這一原理設計的，也是馮諾依曼機。最簡單的來說，他的精髓貢獻是2點：2進制思想與程序內(nèi)存思想。2、關于BIOS下面的說法哪個是正確的：答案（A）A）BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。 B）BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設備的驅(qū)動程序。C）BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。 D）BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。其實bios=Basic Input Output System。但

7、是對于是否是軟件這一說法還存在爭議呢！  BIOS只存一些系統(tǒng)啟動的基本信息，這些設備的驅(qū)動程序是不存的。    BIOS一般是由單獨的芯片廠家生產(chǎn)的，最著名的都是臺灣的三家。  固件BIOS根本這些功能。BIOS是"基本輸入輸出系統(tǒng)"。其實，它是一組固化到計算機內(nèi)主板上一個ROM芯片上的程序，它保存著計算機最重要的基本輸入輸出的程序、系統(tǒng)設置信息、開機后自檢程序和系統(tǒng)自啟動程序。 其主要功能是為計算機提供最底層的、最直接的硬件設置和控制。3 、已知大寫字母A的ASCII編碼為65（十進制），則大寫字母J的十六進制ASCII

8、編碼 為：答案（D）A）48 B）49 C）50 D）以上都不是 “0”的ASCII編碼為48“A”的ASCII編碼為65“a”的ASCII編碼為974 、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為。其對應的十進制整數(shù)應該是：答案（B）A）19 B）-19 C）18 D）-18 最高位為符號位補碼 1再取反原碼：1000000000010011十進制整數(shù)：-195 、一個包含n個分支結(jié)點（非葉結(jié)點）的非空滿k叉樹，k>=1，它的葉結(jié)點數(shù)目為：答案（D）A)nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1 多叉樹的性質(zhì)，N0=(K-1)N+1，考試的時

9、帶入K=2時候，驗證二叉樹能得到結(jié)果。二叉樹的性質(zhì)：N0=N2+1 即葉子節(jié)點比二叉節(jié)點數(shù)多一個。（1）完全二叉樹的定義：深度為k，有n個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應時，稱為完全二叉樹。特點：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)；對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l 或l+1（2）滿二叉樹：一棵深度為k，且有2的(k)次方1個節(jié)點的二叉樹特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)滿二叉樹肯定是完全二叉樹完全二叉樹不一定是滿二叉樹一棵深度為K且有2的K次方減1個結(jié)點的二叉樹稱為滿二叉樹。深度為K的，

10、有N個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至N的結(jié)點一一對應，稱之為完全二叉樹。            0                  0            &

11、#160;   0          /                  /               /     

12、       0     0             0     0          0     0      

13、60;  /     /           /                      /        0   0 0  &

14、#160;0     0                      0   0           (1)        

15、0;        (2)             (3)1、是滿二叉樹，也是完全二叉樹。2、是完全二叉樹。3、非完全二叉樹。簡單的講，將節(jié)點按層次從1-n編號：             1         &

16、#160;/             2      3        /     /       4   5 6   7  . . . .缺少的節(jié)點只能是大號的，即：如果n號節(jié)點存在，則1到

17、n-1號節(jié)點必定存在， 同樣，若n號節(jié)點不存在，則n+1號及更大號的節(jié)點也必定不存在可以根據(jù)公式進行推導，假設n0是度為0的結(jié)點總數(shù)（即葉子結(jié)點數(shù)），n1是度為1的結(jié)點總數(shù)，n2是度為2的結(jié)點總數(shù)，由二叉樹的性質(zhì)可知：n0n21，則n= n0n1n2（其中n為完全二叉樹的結(jié)點總數(shù)），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉樹中度為1的結(jié)點數(shù)只有兩種可能0或1，由此得到n0（n1）/2或n0n/2，合并成一個公式：n0（n1）/2，就可根據(jù)完全二叉樹的結(jié)點總數(shù)計算出葉子結(jié)點數(shù)。6 、表達式a*(b+c)-d的后綴表達式是：答案（B）A)abcd*+- B）abc+*d

18、- C）abc*+d- D）-+*abcd   主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。  構(gòu)造二叉樹，操作數(shù)做葉子節(jié)點，運算符做非葉節(jié)點。按中序遍歷就可以得到中綴表達式。根據(jù)所給表達式（其實正常的都是中綴表達式）可以構(gòu)造二叉樹 * d a + b c中綴表達式就是中序遍歷a*(b+c)-d后綴表達式就是后續(xù)遍歷abc+*d-前綴表達式就是前序遍歷-*a+bcd7 、最優(yōu)前綴編碼，也稱Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼：答案（B）A）（00，01，10，11

19、）B）（0，1，00，11） C）（0，10，110，111） D）（1，01，000，001） 0是00的前綴碼，這部分是數(shù)據(jù)結(jié)構(gòu)中哈夫曼編碼處的知識。哈夫曼編碼從哈夫曼樹根結(jié)點開始，對左子樹分配代碼“0”，右子樹分配代碼“1”，一直到達葉子結(jié)點為止，然后將從樹根沿每條路徑到達葉子結(jié)點的代碼排列起來，便得到了哈夫曼編碼。例，對電文 EMCAD 編碼。若等長編碼，則 EMCAD => 000001010011100 共15位設各字母的使用頻度為 E,M,C,A,D=1,2,3,3,4。用頻度為權值生成哈夫曼樹，并在葉子上標注對應的字母，樹枝分配代碼“0”或“1”:各字母的編碼即為哈夫曼編

20、碼： EMCAD => 000001011011 共12位8 、快速排序平均情況和最壞情況下的算法時間復雜度分別為：答案（A）A）平均情況O(nlog(2,n)，最壞情況O(n2) B）平均情況O(n)，最壞情況O(n2) C）平均情況O(n)，最壞情況O(nlog(2,n) D）平均情況O(log(2,n)，最壞情況O(n2) 最好的時候是n×log（2，n），最壞情況的是退化成冒泡排序，復雜度為O（n2）。選擇排序：O(n2)冒泡排序：O(n2)計數(shù)排序：O(n2)比較排序：O(log(2,n)-1.44n)堆排序： O(log(2,n)9 、左圖給出了一個加權無向圖，從頂

21、點V0開始用prim算法求最小生成樹。則依次加 入最小生成樹的頂點集合的頂點序列為：答案（A）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 加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。Prim算法用于求無向圖的最小生成樹。假設V是圖中頂點的集合,E是圖中邊的集合,設圖G =（V，E），其生成樹的頂點集合為U。、把v0放入U。、在所有uU，vV-U的邊(u，v)E中找一條最小權值的邊，加入生成樹。、把找到的邊的v加入U集合。如果U集合已有n個元素，則

22、結(jié)束，否則繼續(xù)執(zhí)行。其算法的時間復雜度為O(n2) 做法：任取一個頂點加入生成樹，然后對那些一個端點在生成樹中，而另一個端點不在生成樹中的邊進行排序，取權值最小的邊，將它和另一個端點加進生成樹中。重復步驟直到所有頂點都加進了生成樹。加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、Prim算法實現(xiàn)： （1）集合：設置一個數(shù)組set(i=0,1,.,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1） （2）圖用鄰接矩陣或鄰接表表示，路徑不通用無窮大表示，在計算機中可用一個大整數(shù)（如 1 << 30）代替。 10、全國信息學奧林匹克的官方網(wǎng)站為

23、參與信息學競賽的老師同學們提供相關的信息 和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是：答案（C）A）w.noi / B）C）D） 二、.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數(shù)不少于1。多選或少選均不得分）。答案（AB）1、關于CPU下面哪些說法是正確的： A）CPU全稱為中央處理器（或中央處理單元）。 B）CPU能直接運行機器語言。 C）CPU最早是由Intel公司發(fā)明的。 D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。 Intel最早發(fā)明的是微處理器，而CPU之前就由電子管、晶體管實現(xiàn) 位數(shù)只能說明處理的字長，所在的系統(tǒng)硬

24、件指令不同，速度很難說誰快。1、64bit CPU擁有更大的尋址能力，最大支持到16GB內(nèi)存， 32bit支持4G內(nèi)存，而16bit只支持64K內(nèi)存（1M）。2、64位CPU一次可提取64位數(shù)據(jù)，比32位提高了一倍，理論上性能會提升1倍。但這是建立在64bit操作系統(tǒng)，64bit軟件的基礎上的（30%）。WindowsXP 64位2、關于計算機內(nèi)存下面的說法哪些是正確的：答案（BD） A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B）一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。C）計算機內(nèi)存嚴格來說包括主存（memory）、高速緩存（c

25、ache）和寄存器（register）三個部分。D）1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。 一般是對字節(jié)的一個單元串行操作。1MB=1024KB=1024*1024BRAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或?qū)懭霑r，所需要的時間與這段信息所在的位置無關。 高速緩存和寄存器的物理實現(xiàn)是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。3、關于操作系統(tǒng)下面說法哪些是正確的：答案（BC）A.多任務操作系統(tǒng)專用于多核心或多個CPU架構(gòu)的計算機系統(tǒng)的管理。 B.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。

26、 C.分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。 D.為了方便上層應用程序的開發(fā)，操作系統(tǒng)都是免費開源的。 多任務系統(tǒng)可以是單個CPU構(gòu)架的，普通的PC都是多任務的。 操作系統(tǒng)不是都免費開源4、關于計算機網(wǎng)絡，下面的說法哪些是正確的：答案（C）A）網(wǎng)絡協(xié)議之所以有很多層主要是由于新技術需要兼容過去老的實現(xiàn)方案。 B）新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。 C）TCP/IP是互聯(lián)網(wǎng)的基礎協(xié)議簇，包含有TCP和IP等網(wǎng)絡與傳輸層的通訊協(xié)議。 D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的IP地址，否則就必須注

27、冊一個固定的域名來標明其地址。網(wǎng)絡協(xié)議分層不是為了兼容，而是根據(jù)網(wǎng)絡分層模型來的。 新的IPv6是IPv4的升級。 即使注冊了域名也要有IP地址的。5、關于HTML下面哪些說法是正確的：答案（BD）A）HTML全稱超文本標記語言，實現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。 B）HTML不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。 C）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設置標簽來實現(xiàn)。 D）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請求網(wǎng)絡資源或者網(wǎng)絡服務。 沒有都統(tǒng)一編碼本網(wǎng)站頁面也可以用超鏈接，就是絕對路徑。也可

28、以用相對路徑。6、若3個頂點的無權圖G的鄰接矩陣用數(shù)組存儲為0，1，11，0，10，1，0，假定在具體存儲中頂點依次為：v1，v2，v3 關于該圖，下面的說法哪些是正確的：答案（ABD）A）該圖是有向圖。 B）該圖是強聯(lián)通的。 C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。 D）從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。 可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向圖。        入度之和等于出度之和。7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)

29、點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有了2個以上的結(jié)點。下面哪些說法是正確的：答案（AC）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.ne

30、xt;dispose(p);  B應為p.next:=clist.next;clist.next:=p;  D中要循環(huán)找到尾指針的上一個元素才能進行刪除8、散列表的地址區(qū)間為0-10，散列函數(shù)為H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假 定之前散列表為空，則元素59存放在散列表中的可能地址有：答案（ABC）A）5 B）7 C）9 D）10 選擇ABCD   哈希函數(shù)的沖突避免  計算各個的散列值26&#

31、160;  25    72    38    8    18    59                  5     4   

32、    6       5    8      7      4 這樣就可能5的順序：25、59          7的順序：25、26、38、59        

33、60; 9的順序：25、26、38、18、59 10的順序：59 上面的順序不是唯一的。9、排序算法是穩(wěn)定的意思是關鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：答案（ABCD）A）插入排序 B）基數(shù)排序 C）歸并排序 D）冒泡排序            在編程實現(xiàn)的時候，只要控制好邊界都是可以達到穩(wěn)定排序的。10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：答案（BCD）A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B）在聯(lián)機測

34、試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。 C）通過互聯(lián)網(wǎng)搜索取得解題思路。D）在提交的程序中啟動多個進程以提高程序的執(zhí)行效率。     A有時候是可以的。這里考的是NOI，不是NOIP。三.、問題求解（共2題，每空5分，共計10分） 1.拓撲排序是指將有向無環(huán)圖G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v>E(G)，則u在線性序列 中出現(xiàn)在v之前，這樣的線性序列成為拓撲序列。如下的有向無環(huán)圖，對其頂點做拓撲排序，則所有可能的拓撲序列的個數(shù)為_432_。用排列組合，先確定12346的順序，然后將7

35、插入內(nèi)部有兩個位置可選（可將7放在4錢前或4后），然后將5插入時候（如在123476中插入5，五應在1的后面就可以，則有6種情況，當然在123746中也一樣），可以有6個位置選擇。最后，放89的時候，考慮兩種情況，89在一起，有8個位置選（可放在1前或者1的后面都可以）；89不在一起，8個位置選2個。              C(2,1)×C(6,1)×C(8,1)+C(8,2)=2×6×(8+28)=4322、某個國家的錢

36、幣面值有1，7，72，73共計四種，如果要用現(xiàn)金付清10015元的貨物，假設買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通_35_張錢幣?？梢耘袛嘤?9張73的錢，用一張72的錢，此時還剩余19元，可用2張7元的和五張一元的解決，但這時一元用的太多我們可以給對方一張七元的讓對方找兩張一元的就可以，這樣只用到29+1+2（七元）+1（七元）+2（一元）共35張，而第一種方法需要更多一些    10015化成7進制數(shù)是41125，正常是4×7+1=29張73面額的，1張72面額，2張7面額的，5張1面額的。     因為可以無限且找零，并要求最少流通數(shù)量。這樣就把7進制上大于等于4的數(shù)a，用找零