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

1、NOIP2009初賽提高組C1第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（提高組提高組C語言語言二小時完成二小時完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一一單項選擇題單項選擇題（共（共10題，每題題，每題1.5分，共計分，共計15分。每題有且僅有一個正確答案。分。每題有且僅有一個正確答案。）1、關于圖靈機下面的說法哪個是正確的：A)圖靈機是世界上最早的電子計

2、算機。B)由于大量使用磁帶操作，圖靈機運行速度很慢。C)圖靈機只是一個理論上的計算模型。D)圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2、關于BIOS下面的說法哪個是正確的：A)BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B)BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設備的驅動程序。C)BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D)BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。3

3、、已知大寫字母A的II編碼為65（十進制），則大寫字母J的十六進制II編碼為：A)48B)49C)50D)以上都不是4、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為1111111111101101。其對應的十進制整數(shù)應該是：A)19B)19C)18D)185、一個包含n個分支結點（非葉結點）的非空滿k叉樹，k=1，它的葉結點數(shù)目為：A)nk1B)nk1C)(k1)n1D.(k1)n16.表達式a(bc)d的后綴表達式是

4、：A)abcdB)abcdC)abcdD)abcd7、最優(yōu)前綴編碼，也稱Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）8、快速排序平均情況和最壞情況下的算法時間復雜度分別為：A)平均情況O(nlog2n)，最壞情況O(n2)B)平

5、均情況O(n)，最壞情況O(n2)C)平均情況O(n)，最壞情況O(nlog2n)D)平均情況O(log2n)，最壞情況O(n2)9、左圖給出了一個加權無向圖，從頂點V0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點集合的頂點序列為：A)V0V1V2V3V5V4B)V0V1V5V4V3V3C)V1V2V3V0V5V4D)V1V2V3V0V4V5NOIP2009初賽提高組C3pnext=clist；clistnext=pC)在

6、頭部刪除一個結點的語句序列為：p=clistnextclistnext=clistnextnextpD)在尾部刪除一個結點的語句序列為。p=clistclist=clistnextp8、散列表的地址區(qū)間為010散列函數(shù)為H(K)=Kmod11。采用開地址法的線性探查法處理沖突，并將關鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：A

7、)5B)7C)9D)109、排序算法是穩(wěn)定的意思是關鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：A)插入排序B)基數(shù)排序C)歸并排序D)冒泡排序10、在參加NOI系列競賽過程中，下面哪些行為是被嚴格禁止的：A)攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。B)在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。C)通過互聯(lián)網(wǎng)搜索取得解題思路。D)在提交的程序中啟動多個進程以提高程序的執(zhí)行

8、效率。三問題求解（共三問題求解（共2題，每空題，每空5分，共計分，共計10分）分）1拓撲排序是指將有向無環(huán)圖G中的所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若∈E(G)，則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓撲序列。如下的有向無環(huán)圖，對其頂點做拓撲排序，則所有可能的拓撲序列的個數(shù)為。3215476892某個國家的錢幣面值有177273共計四種，如果要用現(xiàn)金付清10015元的貨物，假設買賣雙方各種錢幣的數(shù)量無限且允