NOIP提高組試題

1、第十五屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時(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ī)是英國(guó)人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2、關(guān)于BIOS下面的說法哪個(gè)是正確的：A）BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱。B）BIOS里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸

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

3、的特點(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(2,n)，最壞情況O(n2)B）平均情況O(n)，最壞情況O(n2)C）平均情況O(n)，最壞情況O(nlog(2,n)D）平均情況O(log(2,n)，最壞情況O(n2)9、左圖給出了一個(gè)加權(quán)無向圖，從頂點(diǎn)V0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點(diǎn)集合的頂點(diǎn)序列為 ： A

4、）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)問全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A）B）C）D）二.不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分，每題正確答案的個(gè)數(shù)不少于1。多選或少選均不得分）。1、關(guān)于CPU下面哪些說法是正確的：A）CPU全稱為中央處理器（或中央處理單元）。B）CPU能直接運(yùn)行機(jī)器語言。C）CPU最早是由Intel公司發(fā)明的。D）同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度

5、快一倍。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、關(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)算能力，為保證

6、每個(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)的升級(jí)與補(bǔ)充。C）TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D）互聯(lián)網(wǎng)上每一臺(tái)入網(wǎng)主機(jī)通常都需要使用一個(gè)唯一的IP地址，否則就必須注冊(cè)一個(gè)固定的域名來標(biāo)明其地址。5、關(guān)于HTML下面哪些說法是正確的：A）HTML全稱超文本標(biāo)記語言，實(shí)現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。B）HTML

7、不單包含有網(wǎng)頁內(nèi)容信息的描述，同時(shí)也包含對(duì)網(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）請(qǐng)求網(wǎng)絡(luò)資源或者網(wǎng)絡(luò)服務(wù)。6、若3個(gè)頂點(diǎn)的無權(quán)圖G的鄰接矩陣用數(shù)組存儲(chǔ)為0，1，11，0，10，1，0，假定在具體存儲(chǔ)中頂點(diǎn)依次為：v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的：A）該圖是有向圖。B）該圖是強(qiáng)聯(lián)通的。C）該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于1。D）從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點(diǎn)序列與廣度優(yōu)先的頂點(diǎn)序列是相同的。7、在帶尾指針（鏈表指針clis

8、t指向尾結(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é)點(diǎn)，在尾部插入一個(gè)元素的語句序列為：p.next:=clist;clist.next:=p;C）在頭部刪除一個(gè)結(jié)點(diǎn)的語句序列為：p:=clist.next;clist.next:=clist.next.next;dispose(p);D）在尾部刪除一個(gè)結(jié)點(diǎn)的語句序列為：p:=clist;clist:=cl

9、ist.next;dispose(p);8、散列表的地址區(qū)間為0-10，散列函數(shù)為H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲(chǔ)到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：A）5 B）7 C）9 D）109、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對(duì)位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：A）插入排序 B）基數(shù)排序 C）歸并排序 D）冒泡排序10、在參加NOI系列競(jìng)賽過程中，下面哪些行為是被嚴(yán)格禁止的：A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入

10、賽場(chǎng)。B）在聯(lián)機(jī)測(cè)試中通過手工計(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è)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若E(G)，則u在線性序列中出現(xiàn)在v之前，這樣的線性序列成為拓?fù)湫蛄小Ｈ缦碌挠邢驘o環(huán)圖，對(duì)其頂點(diǎn)做拓?fù)渑判?，則所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為_。2、某個(gè)國(guó)家的錢幣面值有1，7，72，73共計(jì)四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無限且允許找零，那么交易過程中至少需要流通_張錢幣

11、。四.閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1.vara,b:integer;function work(a,b:integer):integer;beginif a mod b 0 then work := work(b,a mod b)else work := b;end;beginread(a,b);writeln(work(a,b);end.輸入：123 321輸出：_2.vara,b:array0.3of integer;i,j,tmp:integer;beginfor i := 0 to 3 do read(bi);for i := 0 ti 3 do begin ai :

12、= 0; for j := 0 to i do begin inc(ai,bj); inc(bai mod 4,aj); end;end;tmp:=1;for i := 0 to 3 dobegin ai := ai mod 10; bi := bi mod 10; tmp := tmp * (ai + bi);end;writeln(tmp);end.輸入：2 3 5 7輸出：_3.consty = 2009;maxn = 50;varn,i,j,s:longint;c:array0.maxn,0.maxnof longint;begins := 0;read(n);c0,0 := 1;fo

13、r i := 1 to n do begin ci,0 := 1; for j := 1 to i - 1 do ci,j := ci-1,j-1 + ci-1,j; ci,i := 1;end;for i := 0 to n do s := (s + cn,i) mod y;write(s);end.輸入：17輸出：_4.varn,m,i,j,k,p:integer;a,b:array0.100of integer;beginread(n,m);a0 := n;i := 0;p := 0;k := 0;repeat for j := 0 to i - 1 do if ai = aj then

14、 begin p := i; k := j; break; end; if p 0 then break; bi := ai div m; ai+1 := (ai mod m) * 10; inc(i);until ai = 0;write(b0,.);for j := 1 to k - 1 do write(bj);if p 0 then write();for j := k to i - 1 do write(bj);if p 0 then write();writeln;end.輸入：5 13輸出：_五.完善程序（前5空，每空2分，后6空，每空3分，共28分）1.（最大連續(xù)子段和）給出一

15、個(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ù)列為1 2 3 -5 0 7 8時(shí)，輸出16和7。vara:array1.100 of integer;n,i,ans,len,tmp,beg:integer;beginread(n);for i := 1 to n do read(ai);tmp := 0;ans := 0;len := 0;beg :=_;for

16、i := 1 to n dobegin if tmp + ai ans then begin ans := tmp + ai; len := i - beg; end else if (_) and (i - beg len) then len := i - beg; if tmp + ai _ then begin beg := _; tmp := 0; end else _;end;writeln(ans, ,len);end.2.（尋找等差數(shù)列）有一些長(zhǎng)度相等的等差數(shù)列（數(shù)列中每個(gè)數(shù)都為059的整數(shù)），設(shè)長(zhǎng)度均為L(zhǎng)，將等差數(shù)列中的所有數(shù)打亂順序放在一起?，F(xiàn)在給你這些打亂后的數(shù)，問原先，L

17、最大可能為多大？先讀入一個(gè)數(shù)n（1=n maxnum thenbegin work := true; exit;end;first := now;for second := first to maxnum do if hashsecond 0 then begin delta :=_; if first + delta * _ maxnum then break; if delta = 0 then ok := (_) else begin ok := true; for i := 0 to ans - 1 do ok :=_ and (hashfirst+delta*i0); end; if ok then begin for i := 0 to ans - 1 do dec(hashfirst+delta*i); if work(first) then begin work := true; exit; end; for i := 0 to ans - 1 do