今天下午2：30——4：30是信息學奧賽的初賽。
因為我在等C語言的試卷出來，現在沒有事，就把pascal語言已經出來的選擇題和問題求解部分，分析壹下，因為C語言也是壹樣的題目。有興趣的可以看看吧，自己的答案，歡迎探討。
普及組和提高組的選擇題和問題求解題。
第十五屆全國青少年信息學奧林匹克聯賽初賽試題
（ 普及組 Pascal 語言 二小時完成）
●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上壹律無效 ●●
壹. 單項選擇題（***20題，每題1.5分，***計30分。每題有且僅有壹個正確答案。）
1、 關於圖靈機下面的說法哪個是正確的：
A) 圖靈機是世界上最早的電子計算機
B) 由於大量使用磁帶操作，圖靈機運行速度很慢。
C) 圖靈機是英國人圖靈發明的，在二戰中為破譯德軍的密碼發揮了重要作用。
D) 圖靈機只是壹個理論上的計算模型。
分析選擇D
A最早的計算機是ENIAC B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作
C圖靈機是英國人阿蘭圖靈提出的理論，
阿蘭圖靈本人在二戰中破譯德軍密碼系統發揮重要作用，而不是圖靈機發揮作用。
2、 關於計算機內存，下列說法哪個是正確的：
A) 隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。
B) 1MB內存通常是指1024*1024字節大小的內存。
C) 計算機內存嚴格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。
D) 壹般內存中的數據即使在斷電的情況下也能保留2個小時以上。
分析選擇B 1MB=1024KB=1024*1024B
A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與這段信息所在的位置無關。
C中高速緩存和寄存器的物理實現是集成在CPU中，這兩部分不屬於馮諾依曼體系中的五大部分的任意壹個部分。
D中2秒都保留不住 馬上丟失
3、 下列關於BIOS的說法哪個是正確的：
A) BIOS是計算機基本輸入輸出系統軟件的簡稱。
B) BIOS包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅動程序。
C) BIOS壹般由操作系統廠商來開發完成。
D) BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。
分析選A 其實bios=Basic Input Output System。但是對於是否是軟件這壹說法還存在爭議呢！
B中BIOS只存壹些系統啟動的基本信息，這些設備的驅動程序是不存的。
C項中BIOS壹般是由單獨的芯片廠家生產的，最著名的都是臺灣的三家。
D項中，固件BIOS根本這些功能。
4、 關於CPU下面那個說法是正確的：
A) CPU全稱為中央處理器（或中央處理單元）。
B) CPU可以直接運行匯編語言。
C) 同樣主頻下，32位的CPU比16位的CPU運行速度快壹倍。
D) CPU最早是由Intel公司發明的。
分析選擇A CPU=Central Processing Unit
B項中，CPU只能執行機器指令，也就是二進制的代碼
C項中，位數只能說明處理的字長，所在的系統硬件指令不同，速度很難說誰快
D項中，Intel最早發明的是微處理器，而CPU之前就由電子管、晶體管實現著呢。
5、 關於ASCII，下面哪個說法是正確的：
A) ASCII碼就是鍵盤上所有鍵的唯壹編碼。
B) 壹個ASCII碼使用壹個字節的內存空間就能夠存放。
C) 最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。
D) ASCII碼是英國人主持制定並推廣使用的。
分析選擇B ASCII碼是用壹個字節保存的，八位二進制0～127編碼。
A項，和鍵盤沒有對應關系
C項，擴展的ASCII碼用兩個字節，漢字編碼不是擴展ASCII的內容。
D項，美國標準信息交換碼，美國
6、 下列軟件中不是計算機操作系統的是：
A) Windows B) Linux C) OS/2 D) WPS
分析選D WPS=Word Processing System(金山公司的文字處理系統)
B是開源Linux系統 C是蘋果公司的系統
7、 關於互聯網，下面的說法哪壹個是正確的：
A) 新壹代互聯網使用的IPv6標準是IPv5標準的升級與補充。
B) 互聯網的入網主機如果有了域名就不再需要IP地址。
C) 互聯網的基礎協議為TCP/IP協議。
D) 互聯網上所有可下載的軟件及數據資源都是可以合法免費使用的。
分析選擇C 主要互聯網的協議是TCP/IP，TCP是傳輸層的文件傳輸協議，IP是網絡層的網際協議。
A中IPv6是IPv4的升級
B中必須有IP，域名是為了好記的
D中盜版非法
8、 關於HTML語言下面哪種說法是正確的：
A) HTML實現了文本、圖形、聲音乃至視頻信息的統壹編碼。
B) HTML全稱為超文本標記語言。
C) 網上廣泛使用的Flash動畫都是由HTML編寫的。
D) HTML也是壹種高級程序設計語言。
分析選擇B HTML(HyperText Mark-up Language)即超文本標記語言，是構成網頁文檔的主要語言。
A文本、圖形、聲音和視頻都是有各自的編碼，沒有統壹。
C中Flash是由專門的軟件Adobe公司的Flash軟件制作。
D是壹種標記語言，可以說類似於腳本，不是高級編程語言。
9、 關於程序設計語言，下面哪種說法是正確的：
A) 加了註釋的程序壹般會比同樣的沒有加註釋的程序運行速度慢。
B) 高級語言開發的程序不能使用在低層次的硬件系統（如：自控機床）或低端手機上。
C) 高級語言相對於低級語言更容易實現跨平臺的移植。
D) 以上說法都不對。
分析選擇C 以前的真題中出現過該選項，高級語言的特點
A註釋會在編譯的時候被忽視的，不影響程序運行
B高級語言可以使用底層硬件，編譯後生成目標代碼，可以在硬件系統上執行
10、 已知大寫字母A的ASCII編碼為65（十進制），則大寫字母J的十進制ASCII編碼為：
A) 71 B) 72 C) 73 D) 以上都不是
分析選擇D 64+9=74
11、 十進制小數125.125對應的八進制數是
A) 100.1 B) 175.175 C) 175.1 D) 100.175
分析選擇C
整數部分除以8取余數，結果反敘寫 小數部分乘以8取整數，正序寫。
12、 有六個元素FEDCBA 從左到右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪壹個不可能是合法的出棧序列？
A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF
分析選擇C
註意入棧順序是F～A
當CD出棧後，棧頂為E，F是出不來的，故C不合法。
13、 表達式 a*(b+c)-d 的後綴表達式是
A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd
分析選擇B
主要是考樹的遍歷，要明白前綴、中綴和後綴表達式。
構造二叉樹，操作數做葉子節點，運算符做非葉節點。按中序遍歷就可以得到中綴表達式。
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 (nlog2n) D) O (n2)
分析選擇D 最壞情況時間復雜度，每次選擇的數都是最靠邊的數。
16、 又壹個由4000個整數構成的順序表，假定表中的元素已經按升序排列，采用二分查找定位壹個元素。則最多需要幾次比較就能確定是否存在所查找的元素：
A) 11次 B) 12次 C) 13次 D) 14次
分析選擇B
2^11-1=2047 2^12-1=4095 2047<4000<4095 故樹的高度為12
17、 排序算法是穩定的意思是關鍵碼相同的記錄排序前後相對位置不發生改變，下列哪種排序算法是不穩定的：
A) 冒泡排序 B) 插入排序 C) 歸並排序 D) 快速排序
分析選擇D
快排會造成數據左右位置的調換
其它排序可以編程時註意邊界條件就可以達到穩定。
18、 已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？
A) n B) n + 1 C) n - 1 D) n* (n - 1)
分析選擇A
構成壹個有向的圈（環），所有節點都在圈的上面。
19、 全國信息學奧林匹克的官方網站為參與信息學競賽的老師同學們提供相關的信息和資源，請問全國信息學奧林匹克官方網站的網址是：
A) / D) /
D）/
分析選擇C 官網
二.不定項選擇題（***10題，每題1.5分，***計15分，每題正確答案的個數不少於1。多選或少選均不得分）。
1、關於CPU下面哪些說法是正確的：
A）CPU全稱為中央處理器（或中央處理單元）。
B）CPU能直接運行機器語言。
C）CPU最早是由Intel公司發明的。
D）同樣主頻下，32位的CPU比16位的CPU運行速度快壹倍。
分析選擇AB
C項中，Intel最早發明的是微處理器，而CPU之前就由電子管、晶體管實現著呢 D項中，位數只能說明處理的字長，所在的系統硬件指令不同，速度很難說誰快
2、關於計算機內存下面的說法哪些是正確的：
A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內存位置是隨機而不確定的。
B）壹般的個人計算機在同壹時刻只能存/取壹個特定的內存單元。
C）計算機內存嚴格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。
D）1MB內存通常是指1024*1024字節大小的內存。
分析選擇BD 壹般是對字節的壹個單元串行操作。1MB=1024KB=1024*1024B
A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或寫入時，所需要的時間與這段信息所在的位置無關。
C中高速緩存和寄存器的物理實現是集成在CPU中，這兩部分不屬於馮諾依曼體系中的五大部分的任意壹個部分。
3、關於操作系統下面說法哪些是正確的：
A.多任務操作系統專用於多核心或多個CPU架構的計算機系統的管理。
B.在操作系統的管理下，壹個完整的程序在運行過程中可以被部分存放在內存中。
C.分時系統讓多個用戶可以***享壹臺主機的運算能力，為保證每個用戶都得到及時的響應通常會采用時間片輪轉調度的策略。
D.為了方便上層應用程序的開發，操作系統都是免費開源的。
分析選擇BC
A多任務系統可以是單個CPU構架的，普通的PC都是多任務的。
D操作系統不是都免費開源
4、關於計算機網絡，下面的說法哪些是正確的：
A）網絡協議之所以有很多層主要是由於新技術需要兼容過去老的實現方案。
B）新壹代互聯網使用的IPv6標準是IPv5標準的升級與補充。
C）TCP/IP是互聯網的基礎協議簇，包含有TCP和IP等網絡與傳輸層的通訊協議。
D）互聯網上每壹臺入網主機通常都需要使用壹個唯壹的IP地址，否則就必須註冊壹個固定的域名來標明其地址。
分析選擇C
A網絡協議分層不是為了兼容，而是根據網絡分層模型來的。
B新的IPv6是IPv4的升級。
D即使註冊了域名也要有IP地址的。
5、關於HTML下面哪些說法是正確的：
A）HTML全稱超文本標記語言，實現了文本、圖形、聲音、乃至視頻信息的統壹編碼。
B）HTML不單包含有網頁內容信息的描述，同時也包含對網頁格式信息的定義。
C）網頁上的超鏈接只能指向外部的網絡資源，本網站網頁間的聯系通過設置標簽來實現。
D）點擊網頁上的超鏈接從本質上就是按照該鏈接所隱含的統壹資源定位符（URL）請求網絡資源或者網絡服務。
分析選擇BD
A沒有都統壹編碼
C本網站頁面也可以用超鏈接
6、若3個頂點的無權圖G的鄰接矩陣用數組存儲為{{0，1，1}{1，0，1}{0，1，0}}，假定在具體存儲中頂點依次為：v1，v2，v3 關於該圖，下面的說法哪些是正確的：
A）該圖是有向圖。
B）該圖是強聯通的。
C）該圖所有頂點的入度之和減所有頂點的出度之和等於1。
D）從v1開始的深度優先遍歷所經過的頂點序列與廣度優先的頂點序列是相同的。
分析選擇ABD
可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向圖。
C入度之和等於出度之盒。
7、在帶尾指針（鏈表指針clist指向尾結點）的非空循環單鏈表中每個結點都以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(p);
分析選擇AC
B應為p^.next:=clist^.next;clist^.next:=p;
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
分析選擇ABCD 哈希函數的沖突避免
計算各個的散列值26 25 72 38 8 18 59
5 4 6 5 8 7 4
這樣就可能5的順序：25、59……
7的順序：25、26、38、59……
9的順序：25、26、38、18、59……
10的順序：……59
上面的順序不是唯壹的。
9、排序算法是穩定的意思是關鍵碼相同的記錄排序前後相對位置不發生改變，下列哪些排序算法是穩定的：
A）插入排序 B）基數排序 C）歸並排序 D）冒泡排序
分析選擇ABCD
在編程實現的時候，只要控制好邊界都是可以達到穩定排序的。
10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：
A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。
B）在聯機測試中通過手工計算出可能的答案並在程序裏直接輸出答案來獲取分數。
C）通過互聯網搜索取得解題思路。
D）在提交的程序中啟動多個進程以提高程序的執行效率。
分析選擇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(8,2)]=2×6×(8+28)=432
2、某個國家的錢幣面值有1，7，7^2，7^3***計四種，如果要用現金付清10015元的貨物，假設買賣雙方各種錢幣的數量無限且允許找零，那麽交易過程中至少需要流通______張錢幣。
分析35
10015化成7進制數是41125，正常是4×7+1=29張7^3面額的，1張7^2面額，2張7面額的，5張1面額的。
因為可以無限且找零，並要求最少流通數量。這樣就把7進制上大於等於4的數a，用找零7-a的方法代替，這樣就能達到最少。
這裏29、1、2、5中只有5是大於4的，所以用壹張大額的，並7-5找零的方法計算。這樣，總數29+1+2+(1+7-5)=35張。
因為是做C的，所以讀程序和完善的部分就沒有分析了。呵呵～～