1、NOIP2009普及組和提高組初賽試題和答案分析（選擇題和問題求解題部分） -chu2009-10-17 23:58      今天下午2：304：30是信息學奧賽的初賽。      因為我在等C語言的試卷出來，現在沒有事，就把pascal語言已經出來的選擇題和問題求解部分，分析一下，因為C語言也是一樣的題目。有興趣的可以看看吧，自己做的答案，歡迎探討。     普及組和提高組的選擇題和問題求解題。     第十五屆

2、全國青少年信息學奧林匹克聯賽初賽試題 （ 普及組 Pascal 語言 二小時完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一. 單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。） 1、 關于圖靈機下面的說法哪個是正確的： A) 圖靈機是世界上最早的電子計算機 B) 由于大量使用磁帶操作，圖靈機運行速度很慢。 C) 圖靈機是英國人圖靈發明的，在二戰中為破譯德軍的密碼發揮了重要作用。 D) 圖靈機只是一個理論上的計算模型。 【分析】選擇D        A最早的計算機是ENIAC

3、0;  B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作        C圖靈機是英國人阿蘭圖靈提出的理論，         阿蘭圖靈本人在二戰中破譯德軍密碼系統發揮重要作用，而不是圖靈機發揮作用。2、 關于計算機內存，下列說法哪個是正確的： A) 隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。 B) 1MB內存通常是指1024*1024字節大小的內存。 C) 計算機內存嚴格說來包括主存（m

4、emory）、高速緩存（cache）和寄存器（register）三個部分。 D) 一般內存中的數據即使在斷電的情況下也能保留2個小時以上。 【分析】選擇B 1MB=1024KB=1024*1024B        A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與信息所在的位置無關。        C中高速緩存和寄存器的物理實現是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。

5、        D中2秒都保留不住 馬上丟失3、 下列關于BIOS的說法哪個是正確的： A) BIOS是計算機基本輸入輸出系統軟件的簡稱。 B) BIOS包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。 C) BIOS一般由操作系統廠商來開發完成。 D) BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。 【分析】選A 其實bios=Basic Input Output System。但是對于是否是軟件這一說法還存在爭議呢！     

6、0;  B中BIOS只存一些系統啟動的基本信息，這些設備的驅動程序是不存的。        C項中BIOS一般是由單獨的芯片廠家生產的，最著名的都是臺灣的三家BIOS芯片廠家。        D項中，固件BIOS根本沒有這些功能。4、 關于CPU下面那個說法是正確的： A) CPU全稱為中央處理器（或中央處理單元）。 B) CPU可以直接運行匯編語言。 C) 同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。 D) CPU最早是由Inte

7、l公司發明的。 【分析】選擇A CPU=Central Processing Unit                B項中，CPU只能執行機器指令，也就是二進制的代碼                C項中，位數只能說明處理的字長，所在的系統硬件指令不同，速度很難說誰快  

8、60;             D項中，Intel最早發明的是微處理器，而CPU之前就由電子管、晶體管實現著呢。5、 關于ASCII，下面哪個說法是正確的： A) ASCII碼就是鍵盤上所有鍵的唯一編碼。 B) 一個ASCII碼使用一個字節的內存空間就能夠存放。 C) 最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。 D) ASCII碼是英國人主持制定并推廣使用的。 【分析】選擇B ASCII碼是用一個字節保存的，八位二進制0127編碼。  &

9、#160;     A項，和鍵盤沒有對應關系        C項，擴展的ASCII碼用兩個字節，漢字編碼不是擴展ASCII的內容。        D項，美國標準信息交換碼，美國6、 下列軟件中不是計算機操作系統的是： A) Windows B) Linux C) OS/2 D) WPS 【分析】選D   WPS=Word Processing System(金山公司的文字處理系統) &#

10、160;              B是開源Linux系統 C是蘋果公司的系統7、 關于互聯網，下面的說法哪一個是正確的： A) 新一代互聯網使用的IPv6標準是IPv5標準的升級與補充。 B) 互聯網的入網主機如果有了域名就不再需要IP地址。 C) 互聯網的基礎協議為TCP/IP協議。 D) 互聯網上所有可下載的軟件及數據資源都是可以合法免費使用的。 【分析】選擇C 主要互聯網的協議是TCP/IP，TCP是傳輸層的文件傳輸協議，IP是網絡層的網際協議。 

11、       A中IPv6是IPv4的升級        B中必須有IP，域名是為了好記的        D中盜版非法8、 關于HTML語言下面哪種說法是正確的： A) HTML實現了文本、圖形、聲音乃至視頻信息的統一編碼。 B) HTML全稱為超文本標記語言。 C) 網上廣泛使用的Flash動畫都是由HTML編寫的。 D) HTML也是一種高級程序設計語言。 【分析】選擇B HTML(Hyper

12、Text Mark-up Language)即超文本標記語言，是構成網頁文檔的主要語言。        A文本、圖形、聲音和視頻都是有各自的編碼，沒有統一。        C中Flash是由專門的軟件Adobe公司的Flash軟件制作。        D是一種標記語言，可以說類似于腳本，不是高級編程語言。9、 關于程序設計語言，下面哪種說法是正確的： A) 加了注釋的程序一般會比同樣的沒

13、有加注釋的程序運行速度慢。 B) 高級語言開發的程序不能使用在低層次的硬件系統（如：自控機床）或低端手機上。 C) 高級語言相對于低級語言更容易實現跨平臺的移植。 D) 以上說法都不對。 【分析】選擇C 以前的真題中出現過該選項，高級語言的特點        A注釋會在編譯的時候被忽視的，不影響程序運行        B高級語言可以使用底層硬件，編譯后生成目標代碼，可以在硬件系統上執行10、 已知大寫字母A的ASCII編碼為65（十進制），則大寫字母J的十

14、進制ASCII編碼為： A) 71 B) 72 C) 73 D) 以上都不是 【分析】選擇D 64+9=7411、 十進制小數125.125對應的八進制數是 A) 100.1 B) 175.175 C) 175.1 D) 100.175 【分析】選擇C                 整數部分除以8取余數，結果反序寫；小數部分乘以8取整數，正序寫。12、 有六個元素FEDCBA 從左到右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可

15、能是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF 【分析】選擇C                       注意入棧順序是FA                當CD出棧后，棧頂為E，F是

16、出不來的，故C不合法。13、 表達式 a*(b+c)-d 的后綴表達式是 A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 【分析】選擇B                  主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。              &

17、#160; 構造二叉樹，操作數做葉子節點，運算符做非葉節點。按中序遍歷就可以得到中綴表達式。14、 一個包含n個分支節點（非葉節點）的非空二叉樹，它的葉節點數目最多為： A) 2n + 1 B) 2n - 1 C) n - 1 D) n + 1 【分析】選擇D                考二叉樹的性質：N0=N2+1 即葉子節點比二叉節點數多一個。15、 快速排序最壞情況下的算法復雜度為： A) O (log2n) B) O (n) C) O

18、 (nlog2n) D) O (n2) 【分析】選擇D    最壞情況時間復雜度，每次選擇的數都是最靠邊的數。16、 又一個由4000個整數構成的順序表，假定表中的元素已經按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次 【分析】選擇B         211-1=2047   212-1=4095      2047<4000

19、<4095 故樹的高度為12 17、 排序算法是穩定的意思是關鍵碼相同的記錄排序前后相對位置不發生改變，下列哪種排序算法是不穩定的： A) 冒泡排序 B) 插入排序 C) 歸并排序 D) 快速排序 【分析】選擇D        快排會造成數據左右位置的調換        其它排序可以編程時注意邊界條件就可以達到穩定。18、 已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？ A) n B) n + 1 C)

20、 n - 1 D) n* (n - 1)【分析】選擇A                    構成一個有向的圈（環），所有節點都在圈的上面。19、 全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是： A) B) / C) D) 【分析】選擇C   官網20、 在參加NOI系列競賽過程中，下面哪一種

21、行為是 不 被嚴格禁止的： A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。 B) 在聯機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數。 C) 通過互聯網搜索取得解題思路。 D) 在提交的程序中啟動多個進程以提高程序的執行效果。 【分析】選擇A                 B某種意義上這是一種作弊行為        C當然不行，一般不

22、會連外部網絡         D造成服務器宕機，影響賽事二. 問題求解（共2題，每空5分，共10分） 1. 小陳現有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續。每個任務的步驟順序不能打亂，例如a2->b2->a3->b3是合法的，而 a2->b3-&

23、gt;a3->b2是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經完成了整個任務A，其他的都忘了。使計算小陳飯前已做的可能的任務步驟序列共有 _ 種。 【分析】70解法一：   相當于以前的A到B路程的問題，呵呵a3 0    1    4    10   20   35 a2 0    1    3 &

24、#160;  6    10   15a1 0    1    2    3    4    5     0    1    1    1    1    1   

25、60;      b1   b2   b3   b4   b5看懂了嗎？學過奧數的應該能明白吧。然后把a3那一行加起來1+4+10+20+35=70。解法二：排列組合+加法原理B任務中的b1一定做，而且肯定是第一個做的。除了b1外，第一類：完成A任務               只有1種。第二類：完成A任務和b2 &#

26、160;         有C(4,1)=4種。第三類：完成A任務和b2、b3       有C(5,2)=10種。第四類：完成A任務和b2、b3、b4   有C(6,3)=20種。第五類：完成A任務和b2、b3、b4、b5有C(7,4)=35種。加起來1+4+10+20+35=70。2. 有如下的一段程序： 1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7

27、. g:=a*f+c; 現在要把這段程序分配到若干臺（數量充足）用電纜連接的PC上做并行執行。每臺PC執行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結果。假設每臺PC每單位時間可以執行一個語句，且通訊花費的時間不計。則這段程序最快可以在_單位時間內執行完畢。注意：任意中間結果只有在某臺PC上已經得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執行，則因為語句6需要引用語句4的計算結果，語句6必須在語句4之后執行。 【分析】5可以畫出一個拓撲圖1>2>467   >3/    &#

28、160;             /               5/第一時間1，第二時間2和3，第三時間4和5，第四時間6，第五時間7。|第十五屆全國青少年信息學奧林匹克聯賽初賽試題（ 提高組 Pascal 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項選擇題 （共10題，每題1.5分，共計15分，

29、每題有且僅有一個正確答案。）1、關于圖靈機下面的說法哪個是正確的：A）圖靈機是世界上最早的電子計算機。B）由于大量使用磁帶操作，圖靈機運行速度很慢。C）圖靈機只是一個理論上的計算模型。D）圖靈機是英國人圖靈發明的，在二戰中為破譯德軍的密碼發揮了重要作用。【分析】選擇C               A最早的計算機是ENIAC          

30、60;        B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作                D圖靈機是英國人阿蘭圖靈提出的理論，               阿蘭圖靈本人在二戰中破譯德軍密碼系統發揮重要作用，而不是圖靈機發揮作

31、用。    2、關于BIOS下面的說法哪個是正確的：A）BIOS是計算機基本輸入輸出系統軟件的簡稱。B）BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設備的驅動程序。C）BIOS一般由操作系統廠商來開發完成。D）BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能?！痉治觥窟xA         其實bios=Basic Input Output System。但是對于是否是軟件這一說法還存在爭議呢！      

32、  B中BIOS只存一些系統啟動的基本信息，這些設備的驅動程序是不存的。        C項中BIOS一般是由單獨的芯片廠家生產的，最著名的都是臺灣的三家。        D項中，固件BIOS根本這些功能。3、已知大寫字母A的ASCII編碼為41（十六進制），則大寫字母J的十六進制ASCII編碼為：A）48 B）49 C）50 D）以上都不是【分析】選擇D   41+9=4A    這道題目網上的

33、不一致，我問過我參加考試的學生，應該是這樣的。 考的是十六進制加法和細心。4、在字長為16位的系統環境下，一個16位帶符號整數的二進制補碼為1111111111101101。其對應的十進制整數應該是：A）19 B）-19 C）18 D）-18【分析】選擇B               1111111111101101的原碼為1000000000010011 也就是-19，最高位為符號位。5、一個包含n個分支結點（非葉結點）的非空滿k叉樹，k>=1，它

34、的葉結點數目為：A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1【分析】選擇D                考多叉樹的性質，N0=(K-1)N+1，考試的時帶入K=2時候，驗證二叉樹能得到結果。6、表達式a*(b+c)-d的后綴表達式是：A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd【分析】選擇B        

35、          主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。                構造二叉樹，操作數做葉子節點，運算符做非葉節點。按中序遍歷就可以得到中綴表達式。7、最優前綴編碼，也稱Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼：A）（00，01，10

36、，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）【分析】選擇B                0是00的前綴碼，這部分是數據結構中哈夫曼編碼處的知識。8、快速排序平均情況和最壞情況下的算法時間復雜度分別為：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(n

37、2)【分析】選擇A                最好的時候是n×log（2，n），最壞情況的是退化成冒泡排序，復雜度為O（n2）。9、左圖給出了一個加權無向圖，從頂點V0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點集合的頂點序列為：A）V0，V1，V2，V3，V5，V4B）V0，V1，V5，V4，V3，V3C）V1，V2，V3，V0，V5，V4D）V1，V2，V3，V0，V4，V5 【分析】選擇A  

38、              加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。                10、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是：A）B）/C）D）【分析

39、】選擇C   官網二.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數不少于1。多選或少選均不得分）。1、關于CPU下面哪些說法是正確的：A）CPU全稱為中央處理器（或中央處理單元）。B）CPU能直接運行機器語言。C）CPU最早是由Intel公司發明的。D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。【分析】選擇AB                C項中，Intel最早發明的是微處理器，而CP

40、U之前就由電子管、晶體管實現著呢             D項中，位數只能說明處理的字長，所在的系統硬件指令不同，速度很難說誰快。    2、關于計算機內存下面的說法哪些是正確的：A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。B）一般的個人計算機在同一時刻只能存/取一個特定的內存單元。C）計算機內存嚴格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。D）1MB

41、內存通常是指1024*1024字節大小的內存?！痉治觥窟x擇BD             一般是對字節的一個單元串行操作。1MB=1024KB=1024*1024B                A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與這段信息所在的位置

42、無關。              C中高速緩存和寄存器的物理實現是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。3、關于操作系統下面說法哪些是正確的：A.多任務操作系統專用于多核心或多個CPU架構的計算機系統的管理。B.在操作系統的管理下，一個完整的程序在運行過程中可以被部分存放在內存中。C.分時系統讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應通常會采用時間片輪轉調度的策略。D.為了方便上層應用程序的開發，操作系統都是

43、免費開源的。【分析】選擇BC               A多任務系統可以是單個CPU構架的，普通的PC都是多任務的。               D操作系統不是都免費開源4、關于計算機網絡，下面的說法哪些是正確的：A）網絡協議之所以有很多層主要是由于新技術需要兼容過去老的實現方案。B）新一代互聯網使用的IPv6標準是

44、IPv5標準的升級與補充。C）TCP/IP是互聯網的基礎協議簇，包含有TCP和IP等網絡與傳輸層的通訊協議。D）互聯網上每一臺入網主機通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標明其地址。【分析】選擇C             A網絡協議分層不是為了兼容，而是根據網絡分層模型來的。             B新的IPv6是IPv4的升級

45、。             D即使注冊了域名也要有IP地址的。5、關于HTML下面哪些說法是正確的：A）HTML全稱超文本標記語言，實現了文本、圖形、聲音、乃至視頻信息的統一編碼。B）HTML不單包含有網頁內容信息的描述，同時也包含對網頁格式信息的定義。C）網頁上的超鏈接只能指向外部的網絡資源，本網站網頁間的聯系通過設置標簽來實現。D）點擊網頁上的超鏈接從本質上就是按照該鏈接所隱含的統一資源定位符（URL）請求網絡資源或者網絡服務。【分析】選擇BD  &#

46、160;             A沒有都統一編碼                C本網站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。               

47、60; 6、若3個頂點的無權圖G的鄰接矩陣用數組存儲為0，1，11，0，10，1，0，假定在具體存儲中頂點依次為：v1，v2，v3 關于該圖，下面的說法哪些是正確的：A）該圖是有向圖。B）該圖是強聯通的。C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。D）從v1開始的深度優先遍歷所經過的頂點序列與廣度優先的頂點序列是相同的?！痉治觥窟x擇ABD                可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向

48、圖。                C入度之和等于出度之和。7、在帶尾指針（鏈表指針clist指向尾結點）的非空循環單鏈表中每個結點都以next字段的指針指向下一個節點。假定其中已經有了2個以上的結點。下面哪些說法是正確的：A）如果p指向一個待插入的新結點，在頭部插入一個元素的語句序列為：p.next:=clist.next;clist.next:=p;B）如果p指向一個待插入的新結點，在尾部插入一個元素的語句序列為：p.next:=clist;

49、clist.next:=p;C）在頭部刪除一個結點的語句序列為：p:=clist.next;clist.next:=clist.next.next;dispose(p);D）在尾部刪除一個結點的語句序列為：p:=clist;clist:=clist.next;dispose(p);【分析】選擇AC                B應為p.next:=clist.next;clist.next:=p;    

50、            D中要循環找到尾指針的上一個元素才能進行刪除8、散列表的地址區間為0-10，散列函數為H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：A）5 B）7 C）9 D）10 【分析】選擇ABC   哈希函數的沖突避免      

51、           計算各個的散列值26   25    72    38    8    18    59                  &#

52、160;                           4     3     6        5     8   7 &

53、#160;  4                這樣就可能5的順序：25、59                                    7的順序：25、26、38、59   &