NOIP2006初賽試題及答案(提高組)

1、NOIP2006初賽試題(提高組Pascal語言)日期：2006-10-25 來源： 作者： 字體：大 中 小 第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時(shí)完成 ）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、 單項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分。每題有且僅有一個(gè)正確答案.）。1. 在以下各項(xiàng)中。（ ）不是 CPU 的組成部分。A. 控制器 B. 運(yùn)算器 C. 寄存器 D. ALU E. RAM2. BIOS（基本輸入輸出系統(tǒng)）是一組固化在計(jì)算機(jī)內(nèi)（ ）上一個(gè) ROM 芯片上的程序。A. 控制器 B. CPU C. 主板

2、D. 內(nèi)存條 E. 硬盤3.在下面各世界頂級的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（ ）。A. 沃爾夫獎(jiǎng) B. 諾貝爾獎(jiǎng) C. 菲爾茲獎(jiǎng) D. 圖靈獎(jiǎng) E. 南丁格爾獎(jiǎng)4在編程時(shí)（使用任一種高級語言，不一定是Pascal）,如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組（例如1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（ ）。A. 沒有區(qū)別 B. 有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E.取決于數(shù)組的存儲方式。5在 Pascal

3、語言中，表達(dá)式(21 xor 2)的值是（ ）A. 441 B. 42 C.23 D.24 E.256在 Pascal 語言中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是（ ）A. not a=0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and b=0)D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)7某個(gè)車站呈狹長形，寬度只能容下一臺車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛

4、入站的順序?yàn)?1，2，3，則車輛出站的順序?yàn)椋?）。A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6 D.1,4,3,7,2 E.1,4,3,7,58高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ ）。A. 10 B. 11 C. 12 D. 13 E. 21019. 與十進(jìn)制數(shù) 1770.625 對應(yīng)的八進(jìn)制數(shù)是（ ）。由OIF收集A. 3352.5 B. 3350.5 C. 3352.1161D. 335

5、0.1151 E. 前 4 個(gè)答案都不對10將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。A. 6 B. 7 C. 8 D. 9 E. 10二、不定項(xiàng)選擇題（共10 題，每題1.5 分，共計(jì)15 分。每題正確答案的個(gè)數(shù)大于或等于1。多選或少選均不得分）。11. 設(shè)A=B=D=true，C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。A. (AB)(CD)E B.¬(AB)C)DE)C. A(BCDE) D. (A(BC)DE12. (2010)16 + (32)8的結(jié)果是（ ）。A. (8234)10 B. (202A)16 C1

6、3. 設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。A.a,b,c,e,d B.b,c,a,e,d C.a,e,c,b,d D.d,c,e,b,a14. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）由OIF收集A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 515. 在下列各數(shù)據(jù)庫系統(tǒng)軟件中，以關(guān)系型數(shù)據(jù)庫為主體結(jié)構(gòu)的是（ ）。A. ACCESS B. SQL Serve

7、r C. Oracle D. Foxpro16.在下列各軟件中，屬于 NOIP 競賽（復(fù)賽）推薦使用的語言環(huán)境有（ ）。A. gcc/g+ B. Turbo Pascal C. Turbo C D. free pascal17. 以下斷電之后將不能保存數(shù)據(jù)的有（ ）。A. 硬盤 B. ROM C. 顯存 D. RAM18. 在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ ）。A. Pascal和C都是編譯執(zhí)行的高級語言B. 高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D. 高級語言比匯編語言更高級，是因?yàn)樗某绦虻倪\(yùn)行效率更高19

8、. 在下列關(guān)于計(jì)算機(jī)算法的說法中，正確的有（ ）。A. 一個(gè)正確的算法至少要有一個(gè)輸入B. 算法的改進(jìn)，在很大程度上推動了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步由OIF收集C. 判斷一個(gè)算法的好壞，主要依據(jù)它在某臺計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間D. 目前仍然存在許多涉及到國計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法20. 在下列關(guān)于青少年信息學(xué)競賽的說法中，你贊成的是（ ）（本題不回答為0分，答題一律滿分）。A. 舉行信息學(xué)競賽的目的，是為了帶動廣大青少年學(xué)科學(xué)、愛科學(xué)，為造就一大批優(yōu)秀的計(jì)算機(jī)科學(xué)與技術(shù)人才奠定良好的基礎(chǔ)B. 如果競賽優(yōu)勝者不能直接保送上大學(xué)，我今后就不再參與這項(xiàng)活動了C. 準(zhǔn)備

9、競賽無非要靠題海戰(zhàn)術(shù)，為了取得好成績，就得拼時(shí)間、拼體力D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優(yōu)秀選手應(yīng)該有堅(jiān)韌不拔的意志，有嚴(yán)謹(jǐn)求實(shí)的作風(fēng)，既要努力奮進(jìn)，又要?jiǎng)俨或湐〔火H三問題求解（共 2 題，每題 5 分，共計(jì) 10 分）1將 2006 個(gè)人分成若干不相交的子集，每個(gè)子集至少有 3 個(gè)人，并且：（1）在每個(gè)子集中，沒有人認(rèn)識該子集的所有人。（2）同一子集的任何 3 個(gè)人中，至少有 2 個(gè)人互不認(rèn)識。（3）對同一子集中任何2個(gè)不相識的人，在該子集中恰好只有1個(gè)人認(rèn)識這兩個(gè)人。 則滿足上述條件的子集最多能有_ _個(gè)？2將邊長為 n 的正三角形每邊 n 等分，過每個(gè)分點(diǎn)分別做

10、另外兩邊的平行線，得到若干個(gè)正三角形， 我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同 一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上（圖中是 n=5 時(shí)一條通路的例 子）。設(shè) n=10，則該正三角形的不同的通路的總數(shù)為_ _。四閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. Program ex401;varu,v:array0.3 of integer;i,x,y:integer;beginx:=10; y:=10;for i

11、:=0 to 3 doread(ui);v0:=(u0+u1+u2+u3) div 7; v1:=u0 div (u1-u2) div u3); v2:=u0*u1 div u2*u3; v3:=v0*v1;x:=(v0+v1+2)-u(v3+3) mod 4;if (x>10) theny:=y+(v2*100-v3) div (uu0 mod 3*5)由OIF收集elsey:=y+20+(v2*100-v3) div (uv0 mod 3*5);writeln (x,',',y);end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0 或下標(biāo)越界。輸入：9 3 9

12、4輸出： 2.Program ex402;constm:array0.4 of integer=(2,3,5,7,13);var i,j:integer; t: longint;beginfor i:=0 to 4 dobegint:=1;for j:=1 to mi-1 do t:=t*2;t:=(t*2-1)*t; write (t,' ');end;writeln;end.輸出:_ 3. Program ex403;Const NN=7;Type Arr1=array0.30 of char;var s:arr1; k,p:integer;function fun1(s:

13、arr1; a:char;n:integer):integer;var j:integer;beginj:=n;while (a<sj)and(j>0) do dec(j);fun1:=j;end;Function fun2(s:arr1; a:char; n:integer):integer;var j:integer;beginj:=1;while (a>sj)and(j<n) do inc(j);fun2:=j;end;beginfor k:=1 to NN dosk:=chr(ord('A')+2*k+1);k:=fun1(s,'M

14、9;,NN)+fun2(s,'M',NN);writeln(k);end.輸出： 4. program ex404;var x,x2:longint; procedure digit(n,m:longint);var n2:integer;beginif(m>0) thenbeginn2:=n mod 10;write(n2:2);if(m>1) then digit(n div 10,m div 10);n2:=n mod 10;write(n2:2);end;end;beginwriteln('Input a number:');readln(x

15、);x2:=1;while(x2<x) do x2:=x2*10;x2:=x2 div 10;digit(x,x2);writeln;end.輸入：9734526輸出： 五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)1（選排列）下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個(gè)數(shù)中取k(1<=k<=n)個(gè)數(shù)的全部可能的排列（不一定按升序輸出）。例如，當(dāng)n=3，k=2時(shí)，應(yīng)該輸出（每行輸出5個(gè)排列）：12 13 21 23 3231程序：Program ex501;Var i,n,k:integer;a:array1.10 of

16、integer;count:longint;Procedure perm2(j:integer);var i,p,t:integer;beginif thenbeginfor i:=k to n dobegin inc(count);t:=ak; ak:=ai; ai:=t;for do write(ap:1);write(' ');t:=ak;ak:=ai;ai:=t;if (count mod 5=0) then writeln;end;exit;end;for i:=j to n dobegint:=aj;aj:=ai;ai:=t; ;t:=aj; ;endend;beg

17、inwriteln('Entry n,k (k<=n):'); read(n,k);count:=0;for i:=1 to n do ai:=i; ;end.2（TSP 問題的交叉算子）TSP 問題(Traveling Salesman Problem)描述如下：給定n個(gè)城市，構(gòu)成一個(gè)完全圖，任何兩城市之間都有一個(gè)代價(jià)（例如路程、旅費(fèi)等），現(xiàn)要構(gòu)造遍歷所有城市的環(huán) 路，每個(gè)城市恰好經(jīng)過一次，求使總代價(jià)達(dá)到最小的一條環(huán)路。遺傳算法是求解該問題的一個(gè)很有效的近似算法。在該算法中，一個(gè)個(gè)體為一條環(huán)路，其編碼方法 之一是1到n這n個(gè)數(shù)字的一個(gè)排列，每個(gè)數(shù)字為一個(gè)城市的編號。例如

18、當(dāng)n=5時(shí)，“3 4 2 1 5” 表示該方案實(shí)施的路線為 3->4->2->1->5->3。遺傳算法的核心是通過兩個(gè)個(gè)體的交叉操作，產(chǎn)生兩個(gè)新的個(gè)體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：(1)選定中間一段作為互換段，該段的起止下標(biāo)為t1，t2，隨機(jī)生成t1，t2后，互換兩段。(2)互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩步處理：(2.1) 將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為 0，表示已處理完。(2.2) 將兩個(gè)互換段中其余數(shù)字標(biāo)記為 1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。 例如：n=12，兩個(gè)個(gè)體分別是：a1:

19、 1 3 5 4 * 2 6 7 9 * 10 12 8 11a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9t1=5，t2=8。上述每一行中，兩個(gè)星號間的部分為互換段。假定數(shù)組的下標(biāo)從1開始，互換后有：a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9然后，將數(shù)字 6,7 對應(yīng)的項(xiàng)標(biāo)記為 0，星號內(nèi)數(shù)字 2,9,10,11 對應(yīng)的項(xiàng)標(biāo)記為 1，并且按順序?qū)?應(yīng)關(guān)系為:10<->2，11<->9。于是，將 a19=10 替換為 a19=2，將 a22=2 替換為 a

20、22=10， 類似再做第 2 組替換。這樣處理后，就得到了兩個(gè)新個(gè)體：a1: 1 3 5 4 6 7 10 11 2 12 8 9a2: 3 10 1 12 2 6 7 9 8 5 4 11（3）輸出兩個(gè)新個(gè)體的編碼。程序：program ex502;type arr1=array1.20 of integer;var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;function rand1(k:integer):integer;var t:integer;begint:=0;while (t<2) or(t>k) dot:=random(k+1)-

21、2;rand1:=t;end;procedure read1(var a:arr1;m:integer);讀入數(shù)組元素 a1至 am，a0=0，略。procedure wrt1(var a:arr1;m:integer);輸出數(shù)組元素 a1至 am，略。procedure cross(var a1,a2:arr1;t1,t2,n:integer);由OIF收集var i,j,t,kj:integer;beginfor i:=t1 to t2 dobegint:=a1i; ;end;for i:=1 to n doif (i<t1)or(i>t2) thenbeginkz1i:=-1

22、;kz2i:=-1;endelsebegin ; end;for i:=t1 to t2 dofor j:=t1 to t2 doif(a1i=a2j) thenbegin ; break; end;for i:=t1 to t2 doif(kz1i=1) thenbeginfor j:=t1 to t2 doif(kz2j=1) thenbegin kj:=j; break; end;for j:=1 to n doif thenbegin a1j:=a2kj;break; end;for j:=1 to n doif thenbegin a2j:=a1i; break; end;kz1i:

23、=0;kz2kj:=0;end;end;beginwriteln('input (n>5):');readln(n);writeln('input array 1:'); read1(a1,n);writeln('input array 2:'); read1(a2,n);t1:=rand1(n-1);repeatt2:=rand1(n-1);until(t1<>t2);if(t1>t2) thenbegin k:=t1; t1:=t2; t2:=k; end; ;wrt1(a1,n); wrt1(a2,n);endPas

24、cal語言)日期：2006-10-25 來源： 作者： 字體：大 中 小 第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時(shí)完成 ）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、 單項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分。每題有且僅有一個(gè)正確答案.）。1. 在以下各項(xiàng)中。（ ）不是 CPU 的組成部分。A. 控制器 B. 運(yùn)算器 C. 寄存器 D. ALU E. RAM2. BIOS（基本輸入輸出系統(tǒng)）是一組固化在計(jì)算機(jī)內(nèi)（ ）上一個(gè) ROM 芯片上的程序。A. 控制器 B. CPU C. 主板 D. 內(nèi)存條 E. 硬盤3.在下面各世

25、界頂級的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（ ）。A. 沃爾夫獎(jiǎng) B. 諾貝爾獎(jiǎng) C. 菲爾茲獎(jiǎng) D. 圖靈獎(jiǎng) E. 南丁格爾獎(jiǎng)4在編程時(shí)（使用任一種高級語言，不一定是Pascal）,如果需要從磁盤文件中輸入一個(gè)很大的二維數(shù)組（例如1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循環(huán)是關(guān)于列的）相比，在輸入效率上（ ）。A. 沒有區(qū)別 B. 有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì)C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E.取決于數(shù)組的存儲方式。5在 Pascal 語言中，表達(dá)式(21 xor 2)的值

26、是（ ）A. 441 B. 42 C.23 D.24 E.256在 Pascal 語言中，判斷a不等于0且b不等于0的正確的條件表達(dá)式是（ ）A. not a=0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and b=0)D. (a<>0)or(b<>0) E. (a<>0)and (b<>0)7某個(gè)車站呈狹長形，寬度只能容下一臺車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從 這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的順序?yàn)?1，2，3，則車輛出站的

27、順序?yàn)椋?）。A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6 D.1,4,3,7,2 E.1,4,3,7,58高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ ）。A. 10 B. 11 C. 12 D. 13 E. 21019. 與十進(jìn)制數(shù) 1770.625 對應(yīng)的八進(jìn)制數(shù)是（ ）。由OIF收集A. 3352.5 B. 3350.5 C. 3352.1161D. 3350.1151 E. 前 4 個(gè)答案都不

28、對10將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（ ）次比較，完成從小到大的排序。A. 6 B. 7 C. 8 D. 9 E. 10二、不定項(xiàng)選擇題（共10 題，每題1.5 分，共計(jì)15 分。每題正確答案的個(gè)數(shù)大于或等于1。多選或少選均不得分）。11. 設(shè)A=B=D=true，C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。A. (AB)(CD)E B.¬(AB)C)DE)C. A(BCDE) D. (A(BC)DE12. (2010)16 + (32)8的結(jié)果是（ ）。A. (8234)10 B. (202A)16 C13. 設(shè)棧S的初始狀態(tài)為空，元素a,b

29、,c,d,e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。A.a,b,c,e,d B.b,c,a,e,d C.a,e,c,b,d D.d,c,e,b,a14. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號，以下同），后根遍歷是3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）由OIF收集A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 515. 在下列各數(shù)據(jù)庫系統(tǒng)軟件中，以關(guān)系型數(shù)據(jù)庫為主體結(jié)構(gòu)的是（ ）。A. ACCESS B. SQL Server C. Oracle D. Foxp

30、ro16.在下列各軟件中，屬于 NOIP 競賽（復(fù)賽）推薦使用的語言環(huán)境有（ ）。A. gcc/g+ B. Turbo Pascal C. Turbo C D. free pascal17. 以下斷電之后將不能保存數(shù)據(jù)的有（ ）。A. 硬盤 B. ROM C. 顯存 D. RAM18. 在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ ）。A. Pascal和C都是編譯執(zhí)行的高級語言B. 高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言D. 高級語言比匯編語言更高級，是因?yàn)樗某绦虻倪\(yùn)行效率更高19. 在下列關(guān)于計(jì)算機(jī)算法的說法中，正確

31、的有（ ）。A. 一個(gè)正確的算法至少要有一個(gè)輸入B. 算法的改進(jìn)，在很大程度上推動了計(jì)算機(jī)科學(xué)與技術(shù)的進(jìn)步由OIF收集C. 判斷一個(gè)算法的好壞，主要依據(jù)它在某臺計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間D. 目前仍然存在許多涉及到國計(jì)民生的重大課題，還沒有找到能夠在計(jì)算機(jī)上實(shí)施的有效算法20. 在下列關(guān)于青少年信息學(xué)競賽的說法中，你贊成的是（ ）（本題不回答為0分，答題一律滿分）。A. 舉行信息學(xué)競賽的目的，是為了帶動廣大青少年學(xué)科學(xué)、愛科學(xué)，為造就一大批優(yōu)秀的計(jì)算機(jī)科學(xué)與技術(shù)人才奠定良好的基礎(chǔ)B. 如果競賽優(yōu)勝者不能直接保送上大學(xué)，我今后就不再參與這項(xiàng)活動了C. 準(zhǔn)備競賽無非要靠題海戰(zhàn)術(shù)，為了取得好成績，

32、就得拼時(shí)間、拼體力D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優(yōu)秀選手應(yīng)該有堅(jiān)韌不拔的意志，有嚴(yán)謹(jǐn)求實(shí)的作風(fēng)，既要努力奮進(jìn)，又要?jiǎng)俨或湐〔火H三問題求解（共 2 題，每題 5 分，共計(jì) 10 分）1將 2006 個(gè)人分成若干不相交的子集，每個(gè)子集至少有 3 個(gè)人，并且：（1）在每個(gè)子集中，沒有人認(rèn)識該子集的所有人。（2）同一子集的任何 3 個(gè)人中，至少有 2 個(gè)人互不認(rèn)識。（3）對同一子集中任何2個(gè)不相識的人，在該子集中恰好只有1個(gè)人認(rèn)識這兩個(gè)人。 則滿足上述條件的子集最多能有_ _個(gè)？2將邊長為 n 的正三角形每邊 n 等分，過每個(gè)分點(diǎn)分別做另外兩邊的平行線，得到若干個(gè)正三角形，

33、 我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同 一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上（圖中是 n=5 時(shí)一條通路的例 子）。設(shè) n=10，則該正三角形的不同的通路的總數(shù)為_ _。四閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. Program ex401;varu,v:array0.3 of integer;i,x,y:integer;beginx:=10; y:=10;for i:=0 to 3 doread(ui)

34、;v0:=(u0+u1+u2+u3) div 7; v1:=u0 div (u1-u2) div u3); v2:=u0*u1 div u2*u3; v3:=v0*v1;x:=(v0+v1+2)-u(v3+3) mod 4;if (x>10) theny:=y+(v2*100-v3) div (uu0 mod 3*5)由OIF收集elsey:=y+20+(v2*100-v3) div (uv0 mod 3*5);writeln (x,',',y);end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0 或下標(biāo)越界。輸入：9 3 9 4輸出： 2.Program ex40

35、2;constm:array0.4 of integer=(2,3,5,7,13);var i,j:integer; t: longint;beginfor i:=0 to 4 dobegint:=1;for j:=1 to mi-1 do t:=t*2;t:=(t*2-1)*t; write (t,' ');end;writeln;end.輸出:_ 3. Program ex403;Const NN=7;Type Arr1=array0.30 of char;var s:arr1; k,p:integer;function fun1(s:arr1; a:char;n:inte

36、ger):integer;var j:integer;beginj:=n;while (a<sj)and(j>0) do dec(j);fun1:=j;end;Function fun2(s:arr1; a:char; n:integer):integer;var j:integer;beginj:=1;while (a>sj)and(j<n) do inc(j);fun2:=j;end;beginfor k:=1 to NN dosk:=chr(ord('A')+2*k+1);k:=fun1(s,'M',NN)+fun2(s,'

37、M',NN);writeln(k);end.輸出： 4. program ex404;var x,x2:longint; procedure digit(n,m:longint);var n2:integer;beginif(m>0) thenbeginn2:=n mod 10;write(n2:2);if(m>1) then digit(n div 10,m div 10);n2:=n mod 10;write(n2:2);end;end;beginwriteln('Input a number:');readln(x);x2:=1;while(x2<

38、;x) do x2:=x2*10;x2:=x2 div 10;digit(x,x2);writeln;end.輸入：9734526輸出： 五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)1（選排列）下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個(gè)數(shù)中取k(1<=k<=n)個(gè)數(shù)的全部可能的排列（不一定按升序輸出）。例如，當(dāng)n=3，k=2時(shí)，應(yīng)該輸出（每行輸出5個(gè)排列）：12 13 21 23 3231程序：Program ex501;Var i,n,k:integer;a:array1.10 of integer;count:longi

39、nt;Procedure perm2(j:integer);var i,p,t:integer;beginif thenbeginfor i:=k to n dobegin inc(count);t:=ak; ak:=ai; ai:=t;for do write(ap:1);write(' ');t:=ak;ak:=ai;ai:=t;if (count mod 5=0) then writeln;end;exit;end;for i:=j to n dobegint:=aj;aj:=ai;ai:=t; ;t:=aj; ;endend;beginwriteln('Entr

40、y n,k (k<=n):'); read(n,k);count:=0;for i:=1 to n do ai:=i; ;end.2（TSP 問題的交叉算子）TSP 問題(Traveling Salesman Problem)描述如下：給定n個(gè)城市，構(gòu)成一個(gè)完全圖，任何兩城市之間都有一個(gè)代價(jià)（例如路程、旅費(fèi)等），現(xiàn)要構(gòu)造遍歷所有城市的環(huán) 路，每個(gè)城市恰好經(jīng)過一次，求使總代價(jià)達(dá)到最小的一條環(huán)路。遺傳算法是求解該問題的一個(gè)很有效的近似算法。在該算法中，一個(gè)個(gè)體為一條環(huán)路，其編碼方法 之一是1到n這n個(gè)數(shù)字的一個(gè)排列，每個(gè)數(shù)字為一個(gè)城市的編號。例如當(dāng)n=5時(shí)，“3 4 2 1 5” 表

41、示該方案實(shí)施的路線為 3->4->2->1->5->3。遺傳算法的核心是通過兩個(gè)個(gè)體的交叉操作，產(chǎn)生兩個(gè)新的個(gè)體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：(1)選定中間一段作為互換段，該段的起止下標(biāo)為t1，t2，隨機(jī)生成t1，t2后，互換兩段。(2)互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩步處理：(2.1) 將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為 0，表示已處理完。(2.2) 將兩個(gè)互換段中其余數(shù)字標(biāo)記為 1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。 例如：n=12，兩個(gè)個(gè)體分別是：a1: 1 3 5 4 * 2 6 7 9

42、* 10 12 8 11a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9t1=5，t2=8。上述每一行中，兩個(gè)星號間的部分為互換段。假定數(shù)組的下標(biāo)從1開始，互換后有：a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9然后，將數(shù)字 6,7 對應(yīng)的項(xiàng)標(biāo)記為 0，星號內(nèi)數(shù)字 2,9,10,11 對應(yīng)的項(xiàng)標(biāo)記為 1，并且按順序?qū)?應(yīng)關(guān)系為:10<->2，11<->9。于是，將 a19=10 替換為 a19=2，將 a22=2 替換為 a22=10， 類似再做第 2 組替換。

43、這樣處理后，就得到了兩個(gè)新個(gè)體：a1: 1 3 5 4 6 7 10 11 2 12 8 9a2: 3 10 1 12 2 6 7 9 8 5 4 11（3）輸出兩個(gè)新個(gè)體的編碼。程序：program ex502;type arr1=array1.20 of integer;var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;function rand1(k:integer):integer;var t:integer;begint:=0;while (t<2) or(t>k) dot:=random(k+1)-2;rand1:=t;end;procedure read1(var a:arr1;m:integer