2013noip初賽提高組試題解析

1、省淳中信息學奧賽輔導 奧賽試題解析19.2 十九屆提高組一、單項選擇題（共15題，每題1.5分，共計22.5分；每題有且僅有一個正確選項）1一個32位整型變量占用（ A ）個字節(jié)。A4B8C32D1282二進制數(shù)11.01在十進制下是（ A ）。A3.25B4.125C6.25D11.1253下面的故事與（ B ）算法有著異曲同工之妙。從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：“從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事：從前有座山，山里有座廟，廟里有個老和尚在給小和尚講故事”A枚舉B遞歸C貪心D分治41948年，（ D ）將熱力學中的熵引入信息通信領(lǐng)域，標志著信息論

2、研究的開端。A馮諾伊曼(John von Neumann)B圖靈（Alan Turing）C歐拉（Leonhard Euler） D克勞德香農(nóng)（Claude Shannon）【分析】 香農(nóng)信息論鼻祖5已知一棵二叉樹有2013個節(jié)點，則其中至多有（ A ）個節(jié)點有2個子節(jié)點。A1006B1007C1023D1024【分析】（1）樹根深度為0，深度為10的滿二叉樹節(jié)點總數(shù)2047； （2）本題樹深為10的完全二叉樹，與滿二叉樹相比少了34個節(jié)點，（3）深度為9的滿二叉樹節(jié)點總數(shù)量為1023；（4）1023-（34/2）=10066在一個有向圖中，如果任意兩點之間都存在路徑相連，則稱其為連通圖。右圖

3、是一個有5個頂點、8條邊的連通圖。若要使它不再是連通圖，至少要刪去其中的（ B ）條邊。A2B3C4D5【分析】要使圖不聯(lián)通，只要其中某一個節(jié)點不連通即可，所有頂點度最少是3，所以最少需要刪除3條邊7斐波那契數(shù)列的定義如下：F1=1，F(xiàn)2=1，F(xiàn)n=Fn-1+Fn-2（n3）。如果用下面的函數(shù)計算斐波那契數(shù)列的第n項，則其時間復雜度為（ D ）。function F(n:longint):longint;beginif n=2 thenF:=1elseF:=F(n-1)+F(n-2);end;AO(1)BO(n)CO(n2)DO(Fn)【分析】計算F1需要1次，計算F2需要一次，計算Fn需要計

4、算F(n-1)的次數(shù)加上F（n-2）的次數(shù)，所以其實就是計算Fn次，于是答案選擇D，至于這個Fn到底是多大，數(shù)學上可以計算，它等于O(（1+sqrt(5)）/2)n).8二叉查找樹具有如下性質(zhì)：每個節(jié)點的值都大于其左子樹上所有節(jié)點的值、小于其右子樹上所有節(jié)點的值。那么，二叉查找樹的（ B ）是一個有序序列。A先序遍歷 B中序遍歷 C后序遍歷 D寬度優(yōu)先遍歷9將（2，6，10，17）分別存儲到某個地址區(qū)間為010的哈希表中，如果哈希函數(shù)h(x)=（ D ），將不會產(chǎn)生沖突，其中a mod b表示a除以b的余數(shù)。Ax mod 11Bx2 mod 11C2x mod 11Dmod 11，其中表示下取

5、整【分析】A項6和17對11取余都是6發(fā)生沖突，B項10的平方和17的平方對11取余都是1發(fā)生沖突，C項6的兩倍和17的兩倍對11取余都是1發(fā)生沖突，D項分別為1，2，3，4，不沖突10IPv4協(xié)議使用32位地址，隨著其不斷被分配，地址資源日趨枯竭。因此，它正逐漸被使用（ D ）位地址的IPv6協(xié)議所取代。A40B48C64D12811二分圖是指能將頂點劃分成兩個部分，每一部分內(nèi)的頂點間沒有邊相連的簡單無向圖。那么12個頂點的二分圖至多有（ C ）條邊。A18B24C36D66【分析】二分為6個和6個的頂點，此時邊最多，有36條邊。12（ B ）是一種通用的字符編碼，它為世界上絕大部分語言設定

6、了統(tǒng)一并且唯一的二進制編碼，以滿足跨語言、跨平臺的文本交換。目前它已經(jīng)收錄了超過十萬個不同字符。AASCIIBUnicodeCGBK2312DBIG5【分析】UNICODE與ASCII的區(qū)別 .1.ASCII的特點（1）ASCII 是用來表示英文字符的一種編碼規(guī)范。每個ASCII字符占用1 個字節(jié)，因此，ASCII 編碼可以表示的最大字符數(shù)是255（00HFFH）。這對于英文而言，是沒有問題的，一般只什么用到前128個(00H-7FH,最高位為0)。而最高位為1 的另128 個字符（80HFFH）被稱為“擴展ASCII”，一般用來存放英文的制表符、部分音標字符等等的一些其它符號。（2）但是對于

7、中文等比較復雜的語言，255個字符顯然不夠用。于是，各個國家紛紛制定了自己的文字編碼規(guī)范，其中中文的文字編碼規(guī)范叫做“GB231280”， 它是和ASCII 兼容的一種編碼規(guī)范， 其實就是利用擴展ASCII沒有真正標準化這一點，把一個中文字符用兩個擴展ASCII 字符來表示，以區(qū)分ASCII 碼部分。 但是這個方法有問題，最大的問題就是中文的文字編碼和擴展ASCII 碼有重疊。而很多軟件利用擴展ASCII 碼的英文制表符來畫表格，這樣的軟件用到中文系統(tǒng)中，這些表格就會被誤認作中文字符，出現(xiàn)亂碼。另外，由于各國和各地區(qū)都有自己的文字編碼規(guī)則，它們互相沖突，這給各國和各地區(qū)交換信息帶來了很大的麻煩

8、。2.UNICODE的產(chǎn)生（1）要真正解決這個問題，不能從擴展ASCII 的角度入手，UNICODE作為一個全新的編碼系統(tǒng)應運而生，它可以將中文、法文、德文等等所有的文字統(tǒng)一起來考慮，為每一個文字都分配一個單獨的編碼。3.什么是UNICODEUnicode與ASCII一樣也是一種字符編碼方法，它占用兩個字節(jié)（0000HFFFFH）,容納65536 個字符，這完全可以容納全世界所有語言文字的編碼。在Unicode 里，所有的字符都按一個字符來處理， 它們都有一個唯一的Unicode 碼。13把64位非零浮點數(shù)強制轉(zhuǎn)換成32位浮點數(shù)后，不可能（ D ）。A大于原數(shù)B小于原數(shù) C等于原數(shù) D與原數(shù)符

9、號相反【分析】64位非零浮點數(shù)強制轉(zhuǎn)換成32位浮點數(shù)，兩個數(shù)會有大小上的細微差別，但不會發(fā)生符號變化，因為有專門的符號位14對一個n個頂點、m條邊的帶權(quán)有向簡單圖用Dijkstr算法計算單源最短路時，如果不使用堆或其它優(yōu)先隊列進行優(yōu)化，則其時間復雜度為（ B ）。AO(mn+n3) BO(n2) CO(m+n)log n) DO(m+n2)log n)【分析】Dijkstra算法（雙重for 循環(huán)）計算單源最短路時間復雜度如果不借助堆或優(yōu)先隊列優(yōu)化，是O（n2）.15T(n)表示某個算法輸入規(guī)模為n時的運算次數(shù)。如果T(1)為常數(shù)，且有遞歸式T(n)=2*T(n / 2)+2n，那么T(n)

10、= （ B ）。A(n) B(n log n) C(n2) D(n2log n)【分析】的含義和“等于”類似，而大O的含義和“小于等于”類似設 N(1 / 2) X=1 ,X=log2NT(n)=2*T(n / 2)+2n=2(2（T（n / 4）+2(n / 2)+2n=22T（n / 4）+(2n) 2=2XT（1）+(2n) X =2 log2N T（1）+(2N) log2N =N +(2N) log2N= O(N log2N)二、不定項選擇題（共5題，每題1.5分，共計7.5分；每題有一個或多個正確選項，多選或少選均不得分）1下列程序中，正確計算1，2，100這100個自然數(shù)之和su

11、m（初始值為0）的是（ AC ）。2（ AD ）的平均時間復雜度為O(n log n)，其中n是待排序的元素個數(shù)。A快速排序B插入排序C冒泡排序D歸并排序【分析】只有快速排序和歸并排序是n log n的，冒泡和插入都是n2的時間復雜度。3以A0作為起點，對下面的無向圖進行深度優(yōu)先遍歷時（遍歷的順序與頂點字母的下標無關(guān)），最后一個遍歷到的頂點可能是（ CD ）。AA1 BA2 CA3 DA44（ AB ）屬于NP類問題。A存在一個P類問題 B任何一個P類問題C任何一個不屬于P類的問題 D任何一個在（輸入規(guī)模的）指數(shù)時間內(nèi)能夠解決的問題【分析】1. 時間復雜度：（1）時間復雜度：是指執(zhí)行算法所需要

12、的計算工作量。 時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規(guī)模擴大后，程序需要的時間長度增長得有多快。 （2）多項式時間算法：如果一個算法，它能在以輸入規(guī)模為參變量的某個多項式的時間內(nèi)給出答案，則稱它為多項式時間算法。2. P類、NP類問題（1）P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。 （2）NP類問題：NP（Non-deterministic Polynomial）問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。 （3）所有的P類問題都是NP問題。 NP問

13、題不是非P類問題3. NPC問題（NP完全問題）：Cook 在1971年給出并證明了有一類問題具有下述性質(zhì)：（1）這類問題中任何一個問題至今未找到多項式時間算法；（2）如果這類問題中存在一個問題有多項式時間算法，則這類問題都有多項式時間算法這類問題就是所謂的NP完全問題。 （3）NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。5CCF NOIP復賽考試結(jié)束后，因（ ABCD ）提出的申訴將不會被受理。A源程序文件名大小寫錯誤B源程序保存在指定文件夾以外的位置C輸出文件的文件名錯誤D只提交了可執(zhí)行文件，未提交源程序

14、三、問題求解（共2題，每題5分，共計10分；每題全部答對得5分，沒有部分分）1 某系統(tǒng)自稱使用了一種防竊聽的方式驗證用戶密碼。密碼是n個數(shù)s1，s2，sn，均為0或1。該系統(tǒng)每次隨機生成n個數(shù)a1，a2，an，均為0或1，請用戶回答（s1a1+s2a2+snan）除以2的余數(shù)。如果多次的回答總是正確，即認為掌握密碼。該系統(tǒng)認為，即使問答的過程被泄露，也無助于破解密碼因為用戶并沒有直接發(fā)送密碼。然而，事與愿違。例如，當n=4時，有人竊聽了以下5次問答：就破解出了密碼s1= 0 ，s2= 1 ，s3= 1 ，s4= 1 ?！痉治觥浚?）由第5組得到s1=0；（2）由第1組、第5組得到s2=1；（3

15、）由第1組、第3組得到s3=1；（3）由第2組、第3組得到s4=1；2 現(xiàn)有一只青蛙，初始時在n號荷葉上。當它某一時刻在k號荷葉上時，下一時刻將等概率地隨機跳到1，2，k號荷爾蒙葉之一上，直至跳到1號荷葉為止。當n=2時，平均一共跳2次；當n=3時，平均一共跳2.5次。則當n=5時，平均一共跳 37/12 次?！痉治鲞f推】（1）由n=2時，跳法22，21共2次，平均跳的次數(shù)f2=2次，說明在求平均時編號1不統(tǒng)計在內(nèi)。（2）由n=3時，跳法33，32，31，再從2號跳跳法22，21共5次，平均跳的次數(shù)f3=2.5次；f3=(3+f2)/2=2.5（3）由n=4時，跳法分別是落在1號、2號、3號、

16、4號；平均跳的次數(shù)f4=（4+f2+f3）/3=（4+2+2.5）/3 = 8.5/3（4）由n=5時，跳法分別是落在1號、2號、3號、4號、5號；平均跳的次數(shù)f5=（5+f2+f3+f4）/4=（5+2+2.5+8.5/3）/4= 37/12四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1【字符串判定輸入的字符串是否是回文串】varn,i:integer;str:string;isPlalindrome:Boolean;beginreadln(str);n:=Length(str);isPlalindrome:=true;for i:=1 to (n idv 2) dobeginif (

17、stristrn-i+1) thenisPlalindrome:=false;end;if (isPlalindrome) thenwriteln(Yes)elsewriteln(No);end.輸入：abceecba輸出： Yes 【分析】 str1str8、str2str7 、 str3str6 、str4str5這4對字符相同則返回true2【數(shù)學到1000中是或的倍數(shù)的數(shù)的個數(shù)】Var a,b,u,v,I,num:integer;beginreadln(a,b,u,v);num:=0;for i:=a to b dobegin if (I mod u=0)or(I mod v=0) t

18、hen inc(num);end;writeln(num);end.輸入：1 1000 10 15輸出： 133 【分析】此題計數(shù)1-1000范圍內(nèi)能夠整除10或15的數(shù)有多少個，使用容斥原理或者集合求并很容易可以得到1000/10+1000/15-1000/30=133.3【動態(tài)規(guī)劃最長上升子序列的長度】const SIZE=100;var n,ans,I,j:integer;height,num:array1.SIZE of integer; beginread(n);for i:=1 to n dobegin read(heighti); numi:=1; for j:=1 to i-1

19、 do beginif (heightj=numi) then numi:=numj+1; end;end;ans:=0;for i:=1 to n dobeginif (numians) then ans:=ans+numi;end;writeln(ans);end.輸入：83 2 5 11 12 7 4 10輸出： 4 【分析】【1.狀態(tài)描述】 （1）heighti存放的數(shù)組（2）numi：數(shù)組height1heighti中中包含heighti上升序列長度【2.狀態(tài)轉(zhuǎn)移】 1. 初始狀態(tài)：numi:=1; num1:=1; 2. 狀態(tài)轉(zhuǎn)移：從下標1逐步遞推到n，求解numi numi=Ma

20、x numj, (1= j= i-1, heightj height3=5，num4= num3+1=3【4.算法設計】 1. 初始狀態(tài)：numi:=1; num1:=1; 求解numi的最優(yōu)解2. 狀態(tài)前驅(qū)： numi的前驅(qū)狀態(tài)numj：num1 numi-13. 狀態(tài)轉(zhuǎn)移： （1）條件：if (heightj=numi) （2）轉(zhuǎn)移方程：numi:=numj+1;4【深度優(yōu)先搜索上下左右找棋盤數(shù)字為0的連續(xù)單元格數(shù)量】const SIZE=100;varn,m,p,count,ans,x,y,I,j:integer;a:array1.SIZE,1.SIZE of integer;proce

21、dure colour(x,y:integer);begininc(count);axy:=1;if (x1)and(ax-1y=0) then colour(x-1,y); /上if (y1)and(axy-1=0) thencolour(x,y-1); /左if (xn)and(ax+1y=0) thencolour(x+1,y); /下if (ym)and(axy+1=0) thencolour(x,y+1); /右end;beginfillchar(a,sizeof(a),0);readln(n,m,p);for i:=1 to p dobegin read(x,y); axy:=1;

22、end;ans:=0;for i:=1 to n dofor j:=1 to m do if aij=0 then begincount:=0; colour(i,j);if (anscount) then ans:=count;end;writeln(ans);end.輸入：6 5 91 42 32 43 24 14 34 55 46 4輸出： 7 【分析】【1.狀態(tài)描述】 （1）棋盤狀態(tài)：axy:=1或0（2）count,ans：數(shù)字為0的連續(xù)單元格數(shù)量，count當前解,ans當前最優(yōu)解【2.狀態(tài)轉(zhuǎn)移】 1. 初始狀態(tài)：查找棋盤每個值為0的單元格 aij=0 2. 狀態(tài)轉(zhuǎn)移：如果aij=

23、0則 （1）：狀態(tài)修改 inc(count); aij:=1;（2）：按上下左右4個方向深度搜索下一單元格【3.算法分析】分上下左右找數(shù)字為0的連續(xù)單元格數(shù)量【4.算法設計】 1. 初始狀態(tài)：查找棋盤每個值為0的單元格 ，并以它為起點查找數(shù)字為0的連續(xù)單元格數(shù)量count,初始count:=02. 父狀態(tài)axy=0 procedure colour(x,y:integer);begin 1. 計算新狀態(tài)：inc(count); 2. 父狀態(tài)訪問過標志：axy:=1; 3. 試探各種子狀態(tài)可能按上下左右4個方向深度搜索下一單元格 4. 下一單元格值為0，則深度搜索colour(x-1,y) en

24、d;五、完善程序（第1題15分，第2題13分，共計28分）1（序列重排）全局數(shù)組變量a定義如下：const int SIZE=100;int aSIZE,n;它記錄著一個長度為n的序列a1，a2，an。現(xiàn)在需要一個函數(shù)，以整數(shù)p(1pn)為參數(shù)，實現(xiàn)如下功能：將序列a的前p個數(shù)與后n-p個數(shù)對調(diào)，且不改變這p個數(shù)（或n-p個數(shù)）之間的相對位置。例如，長度為5的序列1，2，3，4，5，當p=2時重排結(jié)果為3，4，5，1，2。有一種樸素的算法可以實現(xiàn)這一需求，其時間復雜度為O(n)、空間復雜度為O(n)：procedure swap1(p:longint);varI,j:longint;b:arr

25、ay1.SIZE of longint;begin for i:=1 to p do b（1） n-p+i :=ai;/（2分） for i:=p+1 to n do bi-p:=ai; for i:=1 to n do ai:=bi;end;【分析】【算法設計】1. 第一種方法是通過開一個b數(shù)組，然后先將a數(shù)組中1到p的數(shù)復制到b數(shù)組中后p個位置：n-p+1到n。2. 將a數(shù)組p+1到n區(qū)間的數(shù)復制到b數(shù)組前段1n-p。3. 最后再將b數(shù)組元素復制回a數(shù)組中；顯然第一空是n-p+i。以p=3為例我們也可以用時間換空間，使用時間復雜度為O(n2)、空間復雜度為O(1)的算法：procedure

26、 swap2(p:longint);var I,j,temp:longint;beginfor i:=p+1 to n dobegintemp:=ai;for j:=I downto (2) i+1-p do aj:=aj-1; /（2分） (3) ai-p :=temp; /（2分）end;end;【分析】【1.算法分析】前P個數(shù)逐漸往后移動【2.算法設計】1.初始狀態(tài)：將第p+1位置空出temp:=ai;，將前p個數(shù)后移 2.空出位置i從p+1一直到n，移動的數(shù)就是i左邊的p個數(shù) 3.將空出位置i原來的數(shù)temp放到i的前面空出的位置i-pai-p:=temp;事實上，還有一種更好的算法，

27、時間復雜度為O(n)、空間復雜度為O(1);procedure swap3(p:longint);varstart1,end1,start2,end2,I,j,temp:longint;beginstart1:=1; end1:=p;start2:=p+1; end2:=n;while true dobegin i:=star1; j:=start2; while (i=end1)and(j=end2) do begin temp:=ai;ai:=aj; aj:=temp;inc(i); inc(j);end;if i=end1 then start1:=ielse if (4) jend1)

28、 and( jend2) then 則交換的兩段需要進行調(diào)整 （1）第一段start1、end1右移，應該在當前i、j之間： start1:=i ; end1:=J-1 （2）第二段start2右移、end2不變 start2:=j; 3. 狀態(tài)轉(zhuǎn)移2：第二段數(shù)組全部交換結(jié)束，第一段尚有部分數(shù)組沒有移動，即 if (iend2) then （1）第一段的起始位置 需要調(diào)整i，結(jié)束位置不變start1:=i （2）第二段調(diào)整的數(shù)改變，但位置不變即start2、end2不調(diào)整【2.算法設計】 1.初始狀態(tài)：設置要調(diào)整兩段的起訖下標；兩段數(shù)組進行交換 start1:=1; end1:=p; star

29、t2:=p+1; end2:=n; 2. 狀態(tài)轉(zhuǎn)移1：第一段數(shù)組全部交換結(jié)束，第二段尚有部分數(shù)組沒有移動， if (iend1) and( jend2) then 調(diào)整第一段、第二段的起訖下標 3. 狀態(tài)轉(zhuǎn)移2：第二段數(shù)組全部交換結(jié)束，第一段尚有部分數(shù)組沒有移動，只要調(diào)整第一段的起始下標，第二段的起訖下標不需調(diào)整 4.結(jié)束條件：兩段的前交換數(shù)組的下標i,j均大于兩段結(jié)束下標。2（兩元序列）試求一個整數(shù)序列中，最長的僅包含兩個不同整數(shù)的連續(xù)子序列。如有多個子序列并列最長，輸出任意一個即可。例如，序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中，有兩段滿足條件的最長子序列，長度均為

30、7，分別用下劃線和上劃線標出。program two;const SIZE=100;var n,I,j,cur1,cur2,count1,count2, ans_length,ans_start,ans_end:longint; /cur1,cur2分別表示當前子序列中的兩個不同整數(shù) /count1,count2分別表示cur1，cur2在當前子序列中出現(xiàn)的次數(shù) /ans_length連續(xù)子序列最大長度，ans_start,ans_end記錄子序列的是開始結(jié)束下標 a:array1.SIZE of longint;begin readln(n); for i:=1 to n do read(ai); i:=1; j:=1; /i，j分別表示當前子序列的首尾，并保證其中至多有兩個不同整數(shù) while (j=n)and(aj=ai) do inc(j); cur1:=ai; cur2:=aj; count1:= (1) j-1 ; /（3分） count2:=1; ans_length:=j-i+1; while j0 do begin if ai=cur1 then dec(count1) else dec(count2); inc(i); end; cur2:=aj; count2:=1; end else begin while count10 d