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

1、2009第十五屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組C+ 語(yǔ)言二小時(shí)完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效一 單項(xiàng)選擇題（共 10 題，每題分，共計(jì)15 分。每題有且僅有一個(gè)正確答案。）1、關(guān)于圖靈機(jī)下面的說(shuō)法哪個(gè)是正確的：A) 圖靈機(jī)是世界上最早的電子計(jì)算機(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)稱。B) BIOS里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用

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

3、cd*+- B) abc+*d- C) abc*+d- D) -+*abcd7、最優(yōu)前綴編碼，也稱 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(nlog 2n) ，最壞情況 O(n2 )B) 平均情況O(n)，最壞情況O(n2)C) 平均情況O(n)，最壞情況O(nlog2n)D) 平均情況 O(

4、log 2 n) ， 最壞情況 O(n2 )9、右圖給出了一個(gè)加權(quán)無(wú)向圖，從頂點(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、全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：二 不定項(xiàng)選擇題（共10 題，每題分，共計(jì)15 分。每題正確答案的個(gè)數(shù)不少于1。多選或少選均不得分）。1、關(guān)

5、于CPU下面哪些說(shuō)法是正確的：A) CPU全稱為中央處理器（或中央處理單元）。B) CPU能直接運(yùn)行機(jī)器語(yǔ)言。C) CPU最早是由 Intel 公司發(fā)明的。D) 同樣主頻下， 32 位的 CPU比 16 位的 CPU運(yùn)行速度快一倍。2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說(shuō)法哪些是正確的：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)格說(shuō)來(lái)包括主存 （ memory）、高速緩存（cache）和寄存器（register ）三個(gè)部分。D) 1MB內(nèi)存通常是指 1024*1024

6、字節(jié)大小的內(nèi)存。3、關(guān)于操作系統(tǒng)下面說(shuō)法哪些是正確的：A.多任務(wù)操作系統(tǒng)專用于多核心或多個(gè)CPU架構(gòu)的計(jì)算機(jī)系統(tǒng)的管理。B. 在操作系統(tǒng)的管理下， 一個(gè)完整的程序在運(yùn)行過(guò)程中可以被部分存放在內(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ò)，下面的說(shuō)法哪些是正確的：A) 網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過(guò)去老的實(shí)現(xiàn)方案。B) 新一代互聯(lián)網(wǎng)使用的 IPv6 標(biāo)準(zhǔn)是 IPv5 標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。C)TCP/IP 是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含

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

8、，1 ，1 ，0，1 ，0 ， 1， 0 ，假定在具體存儲(chǔ)中頂點(diǎn)依次為 : v 1，v2， v3 。關(guān)于該圖，下面的說(shuō)法哪些是正確的：A) 該圖是有向圖。B) 該圖是強(qiáng)連通的。C) 該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于1。D) 從 v1 開始的深度優(yōu)先遍歷所經(jīng)過(guò)的頂點(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)。下面哪些說(shuō)法是正確的：A) 如果 p 指向一個(gè)待插入的新結(jié)點(diǎn)，在頭部插入一個(gè)元素的語(yǔ)句序列為： p->next = clist-&

9、gt;next; clist->next = p;B) 如果 p 指向一個(gè)待插入的新結(jié)點(diǎn)，在尾部插入一個(gè)元素的語(yǔ)句序列為：p->next = clist；clist->next = p;C) 在頭部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列為：p = clist->next; clist->next = clist->next->next; delete p;D) 在尾部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列為。p = clist; clist = clist ->next; delete p;8、散列表的地址區(qū)間為 0-10, 散列函數(shù)為 H(K)=K mod11。采用開地址法的

10、線性探查法處理沖突，并將關(guān)鍵字序列 26，25， 72，38，8，18， 59 存儲(chǔ)到散列表中，這些元素存入散列表的順序并不確定。 假定之前散列表為空， 則元素 59 存放在散列表中的可能地址有：A)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) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場(chǎng)。B) 在聯(lián)機(jī)測(cè)試中通過(guò)手工計(jì)算出可能的答案并在程序里直接輸出答案來(lái)獲取分?jǐn)?shù)。C) 通過(guò)互聯(lián)網(wǎng)搜索取得解題思

11、路。D) 在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。三問(wèn)題求解（共2 題，每空 5 分，共計(jì) 10 分）1拓?fù)渑判蚴侵笇⒂邢驘o(wú) 環(huán)圖 G中的所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn) u 和 v，若 <u， v> E(G)，則 u 在線性序列中出現(xiàn)在 v 之前，這樣的線性序列成為拓?fù)湫蛄小?如下的有向無(wú)環(huán)圖， 對(duì)其頂點(diǎn)做拓?fù)渑判颍?則所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為。5826147932某個(gè)國(guó)家的錢幣面值有 1, 7, 7 2, 7 3 共計(jì)四種，如果要用現(xiàn)金付清10015 元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無(wú)限且允許找零，那么交易過(guò)程中至少需要流通張錢幣。四閱讀程序?qū)懡Y(jié)果（

12、共4 題，每題 8 分，共計(jì) 32 分）1#include <iostream>using namespace std;int a,b;int work(int a,int b)if (a%b)return work(b,a%b);return b;int main()cin >> a >> b;cout << work(a,b) << endl;return 0;輸入： 123 321輸出： _2#include <iostream>using namespace std;int main()int a4,b4;int

13、i,j,tmp;for (i=0;i<4;i+)cin >> bi;for (i=0;i<4;i+)ai=0;for (j=0;j<=i;j+)ai+=bj;bai%4+=aj;tmp=1;for (i=0;i<4;i+)ai%=10;bi%=10;tmp*=ai+bi;cout << tmp << endl;return 0;輸入：2357輸出： _3#include <iostream>using namespace std;const int maxn=50;const int y=2009;int main()in

14、t n,cmaxnmaxn,i,j,s=0;cin >> n;c00=1;for(i=1;i<=n;i+)ci0=1;for(j=1;j<i;j+)cij=ci-1j-1+ci-1j;cii=1;for(i=0;i<=n;i+)s=(s+cni)%y;cout << s << endl;return 0;輸入： 17輸出：4#include <iostream>using namespace std;int main()int n,m,i,j,p,k;int a100,b100;cin >> n >> m

15、;a0=n;i=0;p=0;k=0;dofor (j=0;j<i;j+)if (ai=aj)p=1;k=j;break;if (p)break;bi=ai/m;ai+1=ai%m*10;i+;while (ai!=0);cout << b0 << "."for (j=1; j<k; j+)cout << bj;if (p)cout << "("for (j=k;j<i;j+)cout << bj;if (p)cout << ")"cout <

16、;< endl;return 0;輸入： 5 13輸出： _五完善程序 ( 前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)1（最大連續(xù)子段和） 給出一個(gè)數(shù)列（元素個(gè)數(shù)不多于 100），數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、 0。請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5 ， 3， 2， 4 時(shí)，輸出 9 和 3；數(shù)列為123-5078時(shí)，輸出 16和7。#include <iostream>using namespace st

17、d;int a101;int n,i,ans,len,tmp,beg,end;int main()cin >> n;for (i=1;i<=n;i+)cin >> ai;tmp=0;ans=0;len=0;beg=;for (i=1;i<=n;i+)if (tmp+ai>ans)ans=tmp+ai;len=i-beg;else if (&&i-beg>len)len=i-beg;if (tmp+ai)beg=;tmp=0;else ;cout << ans << " " <<

18、; len << endl;return 0;2. ( 尋找等差數(shù)列 ) 有一些長(zhǎng)度相等的等差數(shù)列 （數(shù)列中每個(gè)數(shù)都為 059 的整數(shù)），設(shè)長(zhǎng)度均為 L，將等差數(shù)列中的所有數(shù)打亂順序放在一起。現(xiàn)在給你這些打亂后的數(shù)，問(wèn)原先， L 最大可能為多大？先讀入一個(gè)數(shù) n（1<=n<=60），再讀入 n 個(gè)數(shù)，代表打亂后的數(shù)。輸出等差數(shù)列最大可能長(zhǎng)度 L。#include <iostream>using namespace std;int hash60;int n, x, ans, maxnum;int work(int now) int first, second,

19、 delta, i;int ok;while (&& !hashnow)+now;if (now > maxnum)return 1;first = now;for (second = first; second <= maxnum; second+)if (hashsecond) delta =;if (first + delta *> maxnum)break;if (delta = 0)ok = ();elseok = 1;for (i = 0; i < ans; i+)ok =&& (hashfirst+delta*i);if (

20、ok)for (i = 0; i < ans; i+)hashfirst+delta*i-;if (work(first)return 1;for (i = 0; i < ans; i+)hashfirst+delta*i+;return 0;int main()int i;memset(hash, 0, sizeof(hash);cin >> n;maxnum = 0;for (i = 0; i < n; i+)cin >> x;hashx+;if (x > maxnum)maxnum = x;for (ans = n; ans >= 1; ans-)if ( n%ans=0 &&) cout <