NOIP2009提高組C++初賽試題與答案

歡迎共閱歡迎共閱第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（提高組語言二小時完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一．單項(xiàng)選擇題（共10題，每題1.分5，共計(jì)15分。每題有且僅有一個正確答案。）1、關(guān)于圖靈機(jī)下面的說法哪個是正確的：圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。圖靈機(jī)只是一個理論上的計(jì)算模型。圖靈機(jī)是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2關(guān)于 下面的說法哪個是正確的：是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動程序。一般由操作系統(tǒng)廠商來開發(fā)完成。能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。3已知大寫字母的編碼為（十進(jìn)制），則大寫字母的十六進(jìn)制 編碼為：以上都不是4在字長為 。其對應(yīng)的十進(jìn)制整數(shù)應(yīng)該是：5一個包含個分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空滿叉樹， ，它的葉結(jié)點(diǎn)數(shù)目為：表達(dá)式 的后綴表達(dá)式是：、最優(yōu)前綴編碼，也稱 編碼。這種編碼組合的特點(diǎn)是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。，，，0，1，0，01，1，011，0，0，100，0、快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為：）平均情況o）平均情況o最壞情況平均情況 ，最壞情況平均情況，最壞情況平均情況 ，最壞情況29、右圖給出了一個加權(quán)無向圖，從頂點(diǎn)開始用算法求最小生成樹0。則依次加入最小生成樹的頂點(diǎn)集合的頂點(diǎn)序列為：、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：二.不定項(xiàng)選擇題（共題，每題分，共計(jì)分。每題正確答案的個數(shù)不少于1多選或少

選均不得分）。1關(guān)于 下面哪些說法是正確的：全稱為中央處理器（或中央處理單元）。能直接運(yùn)行機(jī)器語言。最早是由 公司發(fā)明的。同樣主頻下，位的比位的 運(yùn)行速度快一倍。2關(guān)于計(jì)算機(jī)內(nèi)存下面的說法哪些是正確的：隨機(jī)存儲器（）的意思是當(dāng)程序運(yùn)行時，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。一般的個人計(jì)算機(jī)在同一時刻只能存取一個特定的內(nèi)存單元。計(jì)算機(jī)內(nèi)存嚴(yán)格說來包括主存（ o高速緩存（ ）和寄存器（ ）三個部分。內(nèi)存通常是指 字節(jié)大小的內(nèi)存。3、關(guān)于操作系統(tǒng)下面說法哪些是正確的：多任務(wù)操作系統(tǒng)專用于多核心或多個 架構(gòu)的計(jì)算機(jī)系統(tǒng)的管理。在操作系統(tǒng)的管理下，一個完整的程序在運(yùn)行過程中可以被部分存放在內(nèi)存中。分時系統(tǒng)讓多個用戶可以共享一臺主機(jī)的運(yùn)算能力，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費(fèi)開源的。歡迎共閱歡迎共閱歡迎共閱4、關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)，下面的說法哪些是正確的：網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實(shí)現(xiàn)方案。新一代互聯(lián)網(wǎng)使用的 標(biāo)準(zhǔn)是 標(biāo)準(zhǔn)的升級與補(bǔ)充。是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有 和等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議?；ヂ?lián)網(wǎng)上每一臺入網(wǎng)主機(jī)通常都需要使用一個唯一的地址，否則就必須注冊一個固定的域名來標(biāo)明其地址。5關(guān)于 下面哪些說法是正確的：全稱超文本標(biāo)記語言，實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實(shí)現(xiàn)。點(diǎn)擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（）請求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)服務(wù)。、若個頂點(diǎn)的無權(quán)圖的鄰接矩陣用數(shù)組存儲為 ，，，，，，，，,假定在具體存儲中頂點(diǎn)依次為，，。關(guān)于該圖，下面的說法哪些是正確的：該圖是有向圖。該圖是強(qiáng)連通的。該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于1從開始的深度優(yōu)先遍歷所經(jīng)過的頂點(diǎn)序列與廣度優(yōu)先的頂點(diǎn)序列是相同的。、在帶尾指針（鏈表指針 指向尾結(jié)點(diǎn)）的非空循環(huán)單鏈表中每個結(jié)點(diǎn)都以 字段的指針指向下一個節(jié)點(diǎn)。假定其中已經(jīng)有個以上的結(jié)點(diǎn)。下面哪些說法是正確的：如果指向一個待插入的新結(jié)點(diǎn)，在頭部插入一個元素的語句序列為：如果指向一個待插入的新結(jié)點(diǎn)，在尾部插入一個元素的語句序列為：t在頭部刪除一個結(jié)點(diǎn)的語句序列為：在尾部刪除一個結(jié)點(diǎn)的語句序列為。p=clist;clist=clist->next;de、散列表的地址區(qū)間為 散列函數(shù)為 。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不

確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：插入排序基數(shù)排序歸并排序冒泡排序0在參加 系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的:基攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。基在聯(lián)機(jī)測試中通過手工計(jì)算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)?；ㄟ^互聯(lián)網(wǎng)搜索取得解題思路?；谔峤坏某绦蛑袉佣鄠€進(jìn)程以提高程序的執(zhí)行效率。三.問題求解（共題，每空分，共計(jì)分）.拓?fù)渑判蚴侵笇⒂邢驘o環(huán)圖中的所有頂點(diǎn)排成一個線性序列，使得圖中任意一對頂點(diǎn)若，￡ ，則在線性序列中出現(xiàn)在之前，這樣的線性序列成為拓?fù)湫蛄?。如下的有向無環(huán)圖，對其頂點(diǎn)做拓?fù)渑判颍瑒t所有可能的拓?fù)湫蛄械膫€數(shù)為。.某個國家的錢幣面值有 共計(jì)四種，如果要用現(xiàn)金付清 元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通張錢幣。四.閱讀程序?qū)懡Y(jié)果（共題，每題分，共計(jì)分）輸入:輸出：輸出：輸入：輸入：輸出：歡迎共閱歡迎共閱歡迎共閱輸入：513輸出： 五.完善程序前空，每空分，后空，每空分，共分1（最大連續(xù)子段和）給出一個數(shù)列（元素個數(shù)不多于 ）,數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0請找出數(shù)列中的一個連續(xù)子數(shù)列，使得這個子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個數(shù)最多，并輸出這個最大和以及該連續(xù)子數(shù)列中元素的個數(shù)。例如數(shù)列為4，,,時，輸出和3數(shù)列為 5寸。輸出和7尋找等差數(shù)列有一些長度相等的等差數(shù)列（數(shù)列中每個數(shù)都為的整數(shù)），設(shè)長度均為L將等差數(shù)列中的所有數(shù)打亂順序放在一起?，F(xiàn)在給你這些打亂后的數(shù)，問原先，最大可能為多大？先讀入一個數(shù)（）,再讀入個數(shù)，代表打亂后的數(shù)。輸出等差數(shù)列最大可能長度。歡迎共閱歡迎共閱歡迎共閱0第9十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題參考答案與評分標(biāo)準(zhǔn)一、單項(xiàng)選擇題：（每題1.分5）二、不定項(xiàng)選擇題（共10題，每題1.分5，共計(jì)15分。每題正確答案的個數(shù)大于或等于1。多選

或少選均不得分）。三、問題求解：（共2題，每空