第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題解析

第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題

（提高組Pascal語言二小時完成）

○○全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效○○

一、單項選擇題（共10題，每題1.5分，共計15分，每題有且僅有一個正確答案。）

1、關(guān)于圖靈機(jī)下面的說法哪個是正確的：

A）圖靈機(jī)是世界上最早的電子計算機(jī)。

B）由于大量使用磁帶操作，圖靈機(jī)運行速度很慢。

C）圖靈機(jī)只是一個理論上的計算模型。

D）圖靈機(jī)是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。【分析】選擇C

A最早的計算機(jī)是ENIAC

B圖靈機(jī)是計算機(jī)模型，沒有運行速度，更談不上磁帶操作

D圖靈機(jī)是英國人阿蘭圖靈提出的理論，

阿蘭圖靈本人在二戰(zhàn)中破譯德軍密碼系統(tǒng)發(fā)揮重要作用，而不是圖靈機(jī)發(fā)揮作用。

2、關(guān)于BIOS下面的說法哪個是正確的：

A）BIOS是計算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。

B）BIOS里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動程序。

C）BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。

D）BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。【分析】選A

其實bios=BasicInputOutputSystem。但是對于是否是軟件這一說法還存在爭議呢！

B中BIOS只存一些系統(tǒng)啟動的基本信息，這些設(shè)備的驅(qū)動程序是不存的。

C項中BIOS一般是由單獨的芯片廠家生產(chǎn)的，最著名的都是臺灣的三家。

D項中，固件BIOS根本這些功能。

3、已知大寫字母A的ASCII編碼為65（十進(jìn)制），則大寫字母J的十六進(jìn)制ASCII編碼為：

A）48B）49C）50D）以上都不是【分析】選擇D649=74

4、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進(jìn)制補(bǔ)碼為111111*********1。其對應(yīng)的十進(jìn)制整數(shù)應(yīng)該是：

A）19B）-19C）18D）-18【分析】選擇B

111111*********1的原碼為100000000001也就是-19，最高位為符號位。

5、一個包含n個分支結(jié)點（非葉結(jié)點）的非空滿k叉樹，k>=1，它的葉結(jié)點數(shù)目為：

A）nk1B）nk-1C）(k1)n-1D）(k-1)n1【分析】選擇D考多叉樹的性質(zhì)，N0=(K-1)N1，考試的時帶入K=2時候，驗證二叉樹能得到結(jié)果。

6、表達(dá)式a*(bc)-d的后綴表達(dá)式是：

A）abcd*-B）abc*d-C）abc*d-D）-*abcd【分析】選擇B

主要是考樹的遍歷，要明白前綴、中綴和后綴表達(dá)式。

構(gòu)造二叉樹，操作數(shù)做葉子節(jié)點，運算符做非葉節(jié)點。按中序遍歷就可以得到中綴表達(dá)式。

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

0是00的前綴碼，這部分是數(shù)據(jù)結(jié)構(gòu)中哈夫曼編碼處的知識。

8、快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為：

A）平均情況O(nlog(2,n))，最壞情況O(n^2)

B）平均情況O(n)，最壞情況O(n^2)

C）平均情況O(n)，最壞情況O(nlog(2,n))

D）平均情況O(log(2,n))，最壞情況O(n^2)【分析】選擇A

最好的時候是n×log（2，n），最壞情況的是退化成冒泡排序，復(fù)雜度為O（n^2）。

9、左圖給出了一個加權(quán)無向圖，從頂點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【分析】選擇A

加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。10、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：

A）

B）

C）

D）【分析】選擇C

官網(wǎng)

二.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數(shù)不少于1。多選或少選均不得分）。

1、關(guān)于CPU下面哪些說法是正確的：

A）CPU全稱為中央處理器（或中央處理單元）。

B）CPU能直接運行機(jī)器語言。

C）CPU最早是由Intel公司發(fā)明的。

D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍?！痉治觥窟x擇AB

C項中，Intel最早發(fā)明的是微處理器，而CPU之前就由電子管、晶體管實現(xiàn)著呢

D項中，位數(shù)只能說明處理的字長，所在的系統(tǒng)硬件指令不同，速度很難說誰快

。

2、關(guān)于計算機(jī)內(nèi)存下面的說法哪些是正確的：

A）隨機(jī)存儲器（RAM）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。

B）一般的個人計算機(jī)在同一時刻只能存/取一個特定的內(nèi)存單元。

C）計算機(jī)內(nèi)存嚴(yán)格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。

D）1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。【分析】選擇BD

一般是對字節(jié)的一個單元串行操作。1MB=1024KB=1024*1024B

A中RAM不是位置隨機(jī)，而是隨時訪問，所謂“隨機(jī)存取”，指的是當(dāng)存儲器中的消息被讀取或?qū)懭霑r，所需要的時間與這段信息所在的位置無關(guān)。

C中高速緩存和寄存器的物理實現(xiàn)是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。

3、關(guān)于操作系統(tǒng)下面說法哪些是正確的：

A.多任務(wù)操作系統(tǒng)專用于多核心或多個CPU架構(gòu)的計算機(jī)系統(tǒng)的管理。

B.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。

C.分時系統(tǒng)讓多個用戶可以共享一臺主機(jī)的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。

D.為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費開源的?！痉治觥窟x擇BC

A多任務(wù)系統(tǒng)可以是單個CPU構(gòu)架的，普通的PC都是多任務(wù)的。

D操作系統(tǒng)不是都免費開源

4、關(guān)于計算機(jī)網(wǎng)絡(luò)，下面的說法哪些是正確的：

A）網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。

B）新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級與補(bǔ)充。

C）TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。

D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機(jī)通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標(biāo)明其地址?！痉治觥窟x擇C

A網(wǎng)絡(luò)協(xié)議分層不是為了兼容，而是根據(jù)網(wǎng)絡(luò)分層模型來的。

B新的IPv6是IPv4的升級。

D即使注冊了域名也要有IP地址的。

5、關(guān)于HTML下面哪些說法是正確的：

A）HTML全稱超文本標(biāo)記語言，實現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。

B）HTML不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。

C）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實現(xiàn)。

D）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請求網(wǎng)絡(luò)資源或者網(wǎng)絡(luò)服務(wù)。【分析】選擇BD

A沒有都統(tǒng)一編碼

C本網(wǎng)站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。

6、若3個頂點的無權(quán)圖G的鄰接矩陣用數(shù)組存儲為{{0，1，1}{1，0，1}{0，1，0}}，假定在具體存儲中頂點依次為：v1，v2，v3關(guān)于該圖，下面的說法哪些是正確的：

A）該圖是有向圖。

B）該圖是強(qiáng)聯(lián)通的。

C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。

D）從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。【分析】選擇ABD

可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向圖。

C入度之和等于出度之和。

7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有了2個以上的結(jié)點。下面哪些說法是正確的：

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^.next;dispose(p);【分析】選擇AC

B應(yīng)為p^.next:=clist^.next;clist^.next:=p;

D中要循環(huán)找到尾指針的上一個元素才能進(jìn)行刪除

8、散列表的地址區(qū)間為0-10，散列函數(shù)為H(K)=Kmod11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：

A）5B）7C）9D）10【分析】選擇ABCD

哈希函數(shù)的沖突避免

計算各個的散列值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、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：

A）插入排序B）基數(shù)排序C）歸并排序D）冒泡排序【分析】選擇ABCD

在編程實現(xiàn)的時候，只要控制好邊界都是可以達(dá)到穩(wěn)定排序的。

10、在參加NOI系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的：

A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。

B）在聯(lián)機(jī)測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。

C）通過互聯(lián)網(wǎng)搜索取得解題思路。

D）在提交的程序中啟動多個進(jìn)程以提高程序的執(zhí)行效率?！痉治觥窟x擇BCD

都算是違反紀(jì)律的。A有時候是可以的。這里考的是NOI，不是NOIP。三.問題求解（共2題，每空5分，共計10分）

1.拓?fù)渑判蚴侵笇⒂邢驘o環(huán)圖G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v>∈E(G)，則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓?fù)湫蛄?。如下的有向無環(huán)圖，對其頂點做拓?fù)渑判?，則所有可能的拓?fù)湫蛄械膫€數(shù)為______?！痉治觥?32

用排列組合即可，先確定12346的順序，然后將7插入內(nèi)部有兩個位置可選，然后將5插入時候，可以有6個位置選擇。最后，放89的時候，考慮兩種情況，89在一起，有8個位置選；89不在一起，8個位置選2個。

C(2,1)×C(6,1)×[C(8,1)C(8,2)]=2×6×(828)=4322、某個國家的錢幣面值有1，7，7^2，7^3共計四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通______張錢幣。

【分析】35

10015化成7進(jìn)制數(shù)是41125，正常是4×71=29張7^3面額的，1張7^2面額，2張7面額的，5張1面額的。

因為可以無限且找零，并要求最少流通數(shù)量。這樣就把7進(jìn)制上大于等于4的數(shù)a，用找零7-a的方法代替，這樣就能達(dá)到最少。

這里29、1、2、5中只有5是大于4的，所以用一張大額的，并7-5找零的方法計算。這樣，總數(shù)2912(17-5)=35張。四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）

1.3

2.5850

3.487(楊輝三角)

4.0.(384615)（分?jǐn)?shù)變小數(shù)）

五．完善程序(前5空，每空2分，后6空，每空3分，共28分)

（說明：以下各程序填空可能還有一些等價的寫法，