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

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

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

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

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