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

1、2 0 0 9 第 十 五 屆 全 國 青 少 年 信 息 學(xué) 奧 林 匹 克 聯(lián) 賽 初 賽 試 題(提咼組C+語言二小時(shí)完成)全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一單項(xiàng)選擇題(共 10 題，每題 1.5 分，共計(jì) 15分。每題有且僅有一個(gè)正確答案。)1、關(guān)于圖靈機(jī)下面的說法哪個(gè)是正確的：A) 圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。B) 由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。C) 圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。D) 圖靈機(jī)是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2、關(guān)于BIOS下面的說法哪個(gè)是正確的：A) BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡稱。B)

2、BIOS里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C) BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D) BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。3、已知大寫字母A的ASCII編碼為65 (十進(jìn)制)，則大寫字母J的十六進(jìn)制ASCII編碼為:A) 48B)49C)50D) 以上都不是4、在字長為。其對應(yīng)的十進(jìn)制整數(shù)應(yīng)該是：A) 19B)-19 C)18D)-185、 一個(gè)包含n個(gè)分支結(jié)點(diǎn)(非葉結(jié)點(diǎn))的非空滿k叉樹，k=1，它的葉結(jié)點(diǎn)數(shù)目為：A) nk+1B)nk-1 C)(k+1)n-1D.(k-1)n+16、表達(dá)式 a*(b+c)-d 的后綴表達(dá)式

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

4、平均情況0(log 2n)，最壞情況0(n2)9、右圖給出了一個(gè)加權(quán)無向圖， 從頂點(diǎn) V0 開始用 prim 算法求最 小生成樹。則依次加入最小生成 樹的頂點(diǎn)集合的頂點(diǎn)序列為：A) V0,V1,V2,V3,V5,V4B) V0,V1,V5,V4,V3,V3C) V1,V2,V3,V0,V5,V4D) V1,V2,V3,V0,V4,V510、全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息和資 源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A) httB)C)D)二不定項(xiàng)選擇題(共 10題，每題 1.5 分，共計(jì) 15 分。每題正確答案的個(gè)數(shù)不少于 1。 多選或少選均不得分)

5、。1、關(guān)于CPUF面哪些說法是正確的：A) CPU全稱為中央處理器(或中央處理單元)。B) CPU能直接運(yùn)行機(jī)器語言。C) CPU最早是由In tel公司發(fā)明的。D) 同樣主頻下，32位的CPU比 16位的CPU運(yùn)行速度快一倍。2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說法哪些是正確的：A) 隨機(jī)存儲(chǔ)器(RAM的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨 機(jī)而不確定的。B) 一般的個(gè)人計(jì)算機(jī)在同一時(shí)刻只能存 /取一個(gè)特定的內(nèi)存單元。C) 計(jì)算機(jī)內(nèi)存嚴(yán)格說來包括主存(memory、高速緩存(cache)和寄存器(register ) 三個(gè)部分。D) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。3

6、、關(guān)于操作系統(tǒng)下面說法哪些是正確的：A. 多任務(wù)操作系統(tǒng)專用于多核心或多個(gè) CPU架構(gòu)的計(jì)算機(jī)系統(tǒng)的管理。B. 在操作系統(tǒng)的管理下，一個(gè)完整的程序在運(yùn)行過程中可以被部分存放在內(nèi)存中。C. 分時(shí)系統(tǒng)讓多個(gè)用戶可以共享一臺(tái)主機(jī)的運(yùn)算能力，為保證每個(gè)用戶都得到及時(shí)的 響應(yīng)通常會(huì)采用時(shí)間片輪轉(zhuǎn)調(diào)度的策略。D. 為了方便上層應(yīng)用程序的開發(fā)，操作系統(tǒng)都是免費(fèi)開源的。4、關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)，下面的說法哪些是正確的：A) 網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實(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和I

7、P等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D) 互聯(lián)網(wǎng)上每一臺(tái)入網(wǎng)主機(jī)通常都需要使用一個(gè)唯一的 IP 地址，否則就必須注冊一 個(gè)固定的域名來標(biāo)明其地址。5、關(guān)于HTM下面哪些說法是正確的：A) HTM全稱超文本標(biāo)記語言，實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B) HTMI不單包含有網(wǎng)頁內(nèi)容信息的描述，同時(shí)也包含對網(wǎng)頁格式信息的定義。C) 網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實(shí) 現(xiàn)。D) 點(diǎn)擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符(URL請求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)服務(wù)。6若3個(gè)頂點(diǎn)的無權(quán)圖G的鄰接矩陣用數(shù)組存儲(chǔ)為0，1，1，1，0，1，0,1, 0， 假定

8、在具體存儲(chǔ)中頂點(diǎn)依次為：V1, V2, V3。關(guān)于該圖，下面的說法哪些是正確的：A) 該圖是有向圖。B) 該圖是強(qiáng)連通的。C) 該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于 1。D) 從V1開始的深度優(yōu)先遍歷所經(jīng)過的頂點(diǎn)序列與廣度優(yōu)先的頂點(diǎn)序列是相同的。7、在帶尾指針(鏈表指針 clist 指向尾結(jié)點(diǎn))的非空循環(huán)單鏈表中每個(gè)結(jié)點(diǎn)都以 next 字 段的指針指向下一個(gè)節(jié)點(diǎn)。假定其中已經(jīng)有 2個(gè)以上的結(jié)點(diǎn)。下面哪些說法是正確的：A) 如果 p 指向一個(gè)待插入的新結(jié)點(diǎn)，在頭部插入一個(gè)元素的語句序列為：p-next=clist-next;clist-next=p;B) 如果 p 指向一個(gè)待插入的新結(jié)

9、點(diǎn)，在尾部插入一個(gè)元素的語句序列為：p-next=clist ；clist-next=p;C) 在頭部刪除一個(gè)結(jié)點(diǎn)的語句序列為：p=clist-next;clist-next=clist-next-next;deletep;D) 在尾部刪除一個(gè)結(jié)點(diǎn)的語句序列為。p=clist;clist=clist- n ext;deletep;8、散列表的地址區(qū)間為0-10,散列函數(shù)為H（K）=Kmod11采用開地址法的線性探查法處理 沖突，并將關(guān)鍵字序列26, 25，72, 38, 8，18, 59存儲(chǔ)到散列表中，這些元素存入散 列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有

10、：A）5B）7C）9D）109、 排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排 序算法是穩(wěn)定的：A）插入排序B）基數(shù)排序C）歸并排序D）冒泡排序10、在參加NOI系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的：A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。B）在聯(lián)機(jī)測試中通過手工計(jì)算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。C）通過互聯(lián)網(wǎng)搜索取得解題思路。D）在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。三問題求解（共2題，每空5分，共計(jì)10分）1 拓?fù)渑判蚴侵笇⒂邢驘o 環(huán)圖G中的所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對 頂點(diǎn)u和v,若 E（G）

11、，則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓 撲序列。如下的有向無環(huán)圖，對其頂點(diǎn)做拓?fù)渑判?，則所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為。2某個(gè)國家的錢幣面值有1,7,7 2,7 3共計(jì)四種，如果要用現(xiàn)金付清10015元的貨物，假 設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通張錢幣。四閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）#in clude usingn amespacestd; in ta,b;in twork(i nta,i ntb) if(a%b)1.returnwork(b,a%b);returnb;intmain()cinab;coutwork(a,b)endl

12、;return0;輸入： 123321輸出： 2#include usingnamespacestd; intmain()inta4,b4;inti,j,tmp; for(i=0;ibi;for(i=0;i4;i+)ai=0;for(j=0;j=i;j+)ai+=bj; bai%4+=aj;tmp=1;for(i=0;i4;i+)ai%=10;bi%=10;tmp*=ai+bi;couttmpendl;return0;輸入： 2357輸出： 3#include usingnamespacestd; constintmaxn=50;constinty=2009;intmain() intn,cm

13、axnmaxn,i,j,s=0; cinn;c00=1;for(i=1;i=n;i+)ci0=1;for(j=1;ji;j+)cij=ci-1j-1+ci-1j;cii=1;for(i=0;i=n;i+) s=(s+cni)%y;coutsendl;return0;輸入： 17輸出：4#include usingnamespacestd; intmain()intn,m,i,j,p,k; inta100,b100;cinnm;a0=n;i=0;p=0;k=0;dofor(j=0;ji;j+)if(ai=aj)p=1;k=j; break;if(p)break; bi=ai/m; ai+1=ai

14、%m*10; i+;while(ai!=0);coutb0.;for(j=1;jk;j+)coutbj;if(p)cout(;for(j=k;ji;j+)coutbj;if(p)cout);coutendl;return0;輸入： 513輸出： 五完善程序 (前 5 空，每空 2分，后 6 空，每空 3分，共 28分)1(最大連續(xù)子段和) 給出一個(gè)數(shù)列(元素個(gè)數(shù)不多于 100)，數(shù)列元素均為負(fù)整數(shù)、 正整數(shù)、0。請找出數(shù)列中的一個(gè)連續(xù)子數(shù)列， 使得這個(gè)子數(shù)列中包含的所有元素之和最大， 在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子 數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為

15、4，-5，3，2，4時(shí)，輸出 9和3；數(shù)列為 123-5078時(shí)， 輸出 16和 7。#includeusingnamespacestd;inta101;intn,i,ans,len,tmp,beg,end;intmain()cinn;for(i=1;iai;tmp=0;ans=0;len=0;begg;for(i=1;ia ns) an s=tmp+ai; len=i-beg;elseif( &i-begle n)len=i-beg; if(tmp+ai)beg=;tmp=0;elsecouta nsvvvle nen dl;return。；2.(尋找等差數(shù)列)有一些長度相等的等差數(shù)列(數(shù)列

16、中每個(gè)數(shù)都為059的整數(shù))，設(shè)長度均為L,將等差數(shù)列中的所有數(shù)打亂順序放在一起?，F(xiàn)在給你這些打亂后的數(shù)，問原 先，L最大可能為多大？先讀入一個(gè)數(shù) n (1=*=60，再讀入n個(gè)數(shù)，代表打亂后的數(shù)。 輸出等差數(shù)列最大可能長度L。#in cludeusingn amespacestd;in thash60;intn, x,a ns,max num;in twork(i ntno w)in tfirst,secon d,delta,i;in tok;while(&!hashnow)+now;if(no wmax num)returnl;first=now;for(sec on d=first;sec

17、 on dmax num)break;if(delta=0)ok=()；elseok=1;for(i=0;ia ns;i+)ok=&(hashfirst+delta*i);if(ok)for(i=0;ia ns;i+)hashfirst+delta*i-; if(work(first)return1;for(i=0;in;maxnum=O;for(i=0;i x; hashx+; if(xmax num) max num=x;for(ans=n;an s=1;a ns-) if(n %a ns=O&) couta nse ndl; break;return。；2009 第十五屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題參考答案與評分標(biāo)準(zhǔn) 一、單項(xiàng)選擇題：（每題 1.5 分）二、不定項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分。每題正確答案的個(gè)數(shù)大于或等于 1。多選或少選均不得分）。三、問題求解：（共 2 題，每空 5 分，共計(jì) 10分）1432235四、閱讀程序?qū)懡Y(jié)果（共 4題，每題 8分，共計(jì) 32 分）1.32.58503.487（ 楊輝三角 ）4.0.（384615） （分?jǐn)?shù)變小數(shù)）五完善程序 （