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

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

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

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

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

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

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

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

8、效率。三問(wèn)題求解（共三問(wèn)題求解（共2題，每空題，每空5分，共計(jì)分，共計(jì)10分）分）1拓?fù)渑判蚴侵笇⒂邢驘o(wú)環(huán)圖G中的所有頂點(diǎn)排成一個(gè)線(xiàn)性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若∈E(G)，則u在線(xiàn)性序列中出現(xiàn)在v之前，這樣的線(xiàn)性序列成為拓?fù)湫蛄小Ｈ缦碌挠邢驘o(wú)環(huán)圖，對(duì)其頂點(diǎn)做拓?fù)渑判颍瑒t所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為。3215476892某個(gè)國(guó)家的錢(qián)幣面值有177273共計(jì)四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買(mǎi)賣(mài)雙方各種錢(qián)幣的數(shù)量無(wú)限且允