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

2、    A最早的計算機是ENIAC                   B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作                D圖靈機是英國人阿蘭圖靈提出的理論，   &

3、#160;           阿蘭圖靈本人在二戰中破譯德軍密碼系統發揮重要作用，而不是圖靈機發揮作用。    2、關于BIOS下面的說法哪個是正確的：A）BIOS是計算機基本輸入輸出系統軟件的簡稱。B）BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設備的驅動程序。C）BIOS一般由操作系統廠商來開發完成。D）BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。【分析】選A      &#

4、160;  其實bios=Basic Input Output System。但是對于是否是軟件這一說法還存在爭議呢！        B中BIOS只存一些系統啟動的基本信息，這些設備的驅動程序是不存的。        C項中BIOS一般是由單獨的芯片廠家生產的，最著名的都是臺灣的三家。        D項中，固件BIOS根本這些功能。3、已知大寫字母A的ASCII編碼為65（十

5、進制），則大寫字母J的十六進制ASCII編碼為：A）48 B）49 C）50 D）以上都不是【分析】選擇D 64+9=74 【分析】選擇B               5、一個包含n個分支結點（非葉結點）的非空滿k叉樹，k>=1，它的葉結點數目為：A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1【分析】選擇D          &

6、#160;     考多叉樹的性質，N0=(K-1)N+1，考試的時帶入K=2時候，驗證二叉樹能得到結果。6、表達式a*(b+c)-d的后綴表達式是：A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd【分析】選擇B                  主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。     &#

7、160;          構造二叉樹，操作數做葉子節點，運算符做非葉節點。按中序遍歷就可以得到中綴表達式。7、最優前綴編碼，也稱Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼：A）（00，01，10，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）【分析】選擇B         &

8、#160;      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(n2)【分析】選擇A                最好的時候是n

9、5;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                加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、v1v

10、5、v3v4。                10、全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是：【分析】選擇C   官網二.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數不少于1。多選或少選均不得分）。1、關于CPU下面哪些說法是正確的：A）CPU全稱為中央處理器（或中央處理單元）。B）CPU能直接運行機器語言。C）CPU最早是由I

11、ntel公司發明的。D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。【分析】選擇AB                C項中，Intel最早發明的是微處理器，而CPU之前就由電子管、晶體管實現著呢             D項中，位數只能說明處理的字長，所在的系統硬件指令不同，速度很難說誰快。  

12、  2、關于計算機內存下面的說法哪些是正確的：A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。B）一般的個人計算機在同一時刻只能存/取一個特定的內存單元。C）計算機內存嚴格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。D）1MB內存通常是指1024*1024字節大小的內存。【分析】選擇BD             一般是對字節的一個單元串行操作。1MB=1024KB=1024*1

13、024B                A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與這段信息所在的位置無關。              C中高速緩存和寄存器的物理實現是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。3、關于

14、操作系統下面說法哪些是正確的：A.多任務操作系統專用于多核心或多個CPU架構的計算機系統的管理。B.在操作系統的管理下，一個完整的程序在運行過程中可以被部分存放在內存中。C.分時系統讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應通常會采用時間片輪轉調度的策略。D.為了方便上層應用程序的開發，操作系統都是免費開源的。【分析】選擇BC               A多任務系統可以是單個CPU構架的，普通的PC都是多任務的。 &#

15、160;             D操作系統不是都免費開源4、關于計算機網絡，下面的說法哪些是正確的：A）網絡協議之所以有很多層主要是由于新技術需要兼容過去老的實現方案。B）新一代互聯網使用的IPv6標準是IPv5標準的升級與補充。C）TCP/IP是互聯網的基礎協議簇，包含有TCP和IP等網絡與傳輸層的通訊協議。D）互聯網上每一臺入網主機通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標明其地址。【分析】選擇C    &

16、#160;        A網絡協議分層不是為了兼容，而是根據網絡分層模型來的。             B新的IPv6是IPv4的升級。             D即使注冊了域名也要有IP地址的。5、關于HTML下面哪些說法是正確的：A）HTML全稱超文本標記語言，實現了文本、圖形、聲音

17、、乃至視頻信息的統一編碼。B）HTML不單包含有網頁內容信息的描述，同時也包含對網頁格式信息的定義。C）網頁上的超鏈接只能指向外部的網絡資源，本網站網頁間的聯系通過設置標簽來實現。D）點擊網頁上的超鏈接從本質上就是按照該鏈接所隱含的統一資源定位符（URL）請求網絡資源或者網絡服務。【分析】選擇BD                A沒有都統一編碼        

18、0;       C本網站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。                  6、若3個頂點的無權圖G的鄰接矩陣用數組存儲為0，1，11，0，10，1，0，假定在具體存儲中頂點依次為：v1，v2，v3 關于該圖，下面的說法哪些是正確的：A）該圖是有向圖。B）該圖是強聯通的。C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。D）從

19、v1開始的深度優先遍歷所經過的頂點序列與廣度優先的頂點序列是相同的。【分析】選擇ABD                可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向圖。                C入度之和等于出度之和。7、在帶尾指針（鏈表指針clist指向尾結點）的非空循環單鏈表中

20、每個結點都以next字段的指針指向下一個節點。假定其中已經有了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

21、(p);【分析】選擇AC                B應為p.next:=clist.next;clist.next:=p;                D中要循環找到尾指針的上一個元素才能進行刪除8、散列表的地址區間為0-10，散列函數為H(K)=K mod 11。采用開地址法的線性探查法處

22、理沖突，并將關鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：A）5 B）7 C）9 D）10 【分析】選擇ABCD   哈希函數的沖突避免                 計算各個的散列值26   25     72    38 &

23、#160;  8    18    59                                 5     4   &#

24、160;   6       5    8      7      4                這樣就可能5的順序：25、59         

25、                  7的順序：25、26、38、59                           9的順序：25、26、38、

26、18、59                           10的順序：59               上面的順序不是唯一的。9、排序算法是穩定的意思是關鍵碼相同的記錄排序前后相對位置

27、不發生改變，下列哪些排序算法是穩定的：A）插入排序 B）基數排序 C）歸并排序 D）冒泡排序【分析】選擇ABCD                在編程實現的時候，只要控制好邊界都是可以達到穩定排序的。10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B）在聯機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數。C）通過互聯網搜索取得解題思路。D）在提交的程序中啟動多

28、個進程以提高程序的執行效率。【分析】選擇BCD                都算是違反紀律的。A有時候是可以的。這里考的是NOI，不是NOIP。三.問題求解（共2題，每空5分，共計10分）1.拓撲排序是指將有向無環圖G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v>E(G)，則u在線性序列中出現在v之前，這樣的線性序列成為拓撲序列。如下的有向無環圖，對其頂點做拓撲排序，則所有可能的拓撲序列的個數為_。 【分析】432              用排列組合即可，先確定12346的順序，然后將7插入內部有兩個位置可選，然后將5插入時候，可以有6個位置選擇。最后，放89的時候，考慮兩種情況，89在一起，有8個位置選；89不在一起，8個位置選2個。              C(2,1)×C(6,1)×C(8,1)+C(