2011第17屆NOIP試題及解析

第十七屆NOIP2011提高組初賽試題+答案+解析（pascal）一、單項(xiàng)選擇題（共10題，每題1.5分，共15分，每題有且僅有一個(gè)正確選項(xiàng)。）在二進(jìn)制下，1011010+（）=1100111。1011 B.1101C.1010D.1111答案：B解析：簡單的二進(jìn)制運(yùn)算，炮灰都會(huì)。字符“A”的ASCII碼為十六進(jìn)制41，則字符“Z^的ASCII碼為十六進(jìn)制的（）。A.66B.5AC.50 D.視具體的計(jì)算機(jī)而定答案：B解析：每年必考進(jìn)制轉(zhuǎn)換題。背得ASCII碼的可以直接算出Z的碼然后轉(zhuǎn)回16進(jìn)制。像我不背得的就把十六進(jìn)制的41轉(zhuǎn)回十進(jìn)制，4*16+1=65，然后+25得90，再轉(zhuǎn)成16進(jìn)制得5A。右圖是一棵二叉樹，它的先序遍歷是（）。（我就不畫圖了==帶魚語口述一下：根是A，左右子樹分別為B和C，B的左右子樹分別為D和E，E的右子樹為F）ABDEFCB.DBEFACC.DFEBCAD.ABCDEF答案：A解析：每年必考樹的遍歷題。先序遍歷就是先根遍歷，就是先根，再左右子樹的遍歷。然后就ABDEFC出來了。從這個(gè)解析可以看出這個(gè)解析是新手向的解析-。-寄存器是（）的重要組成部分。硬盤高速緩存內(nèi)存中央處理器（CPU）答案：D解析：每年必考硬件知識(shí)題。寄存器在CPU里。廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（）。鏈表隊(duì)列棧散列表答案：B解析：數(shù)據(jù)結(jié)構(gòu)題。廣搜需要存每一層的一大堆東西，繼續(xù)向下一層搜時(shí)需要用到，所以要用存取方便的隊(duì)列。鏈表取數(shù)不便，棧是深搜用的，散列表就是hash表，和寬搜沒啥必然聯(lián)系。在使用高級(jí)語言編寫程序時(shí)，一般提到的“空間復(fù)雜度”中的“空間”是指（）程序運(yùn)行時(shí)理論上所占的內(nèi)存空間程序運(yùn)行時(shí)理論上所占的數(shù)組空間程序運(yùn)行時(shí)理論上所占的硬盤空間程序源文件理論上所占的硬盤空間答案：A解析：常識(shí)題。BCD均明顯錯(cuò)。應(yīng)用快速排序的分治思想，可以實(shí)現(xiàn)一個(gè)求第K大數(shù)的程序。假定不考慮極端的最壞情況，理論上可以實(shí)現(xiàn)的最低的算法時(shí)間復(fù)雜度為（）。O （nA2）O （nlogn）O （n）O （1）答案：C解析：快排思想找第K大的數(shù)以前初賽就出過，那時(shí)是個(gè)補(bǔ)完程序題?？炫诺臅r(shí)間復(fù)雜度是O（nlogn），這題我費(fèi)解了一下，我認(rèn)為是O（logn），不過沒這個(gè)選項(xiàng)，于是我猜是O（n）。剛才上網(wǎng)查，這個(gè)方法找第K大的數(shù)時(shí)間復(fù)雜度的確是O（n）。為解決Web應(yīng)用中的不兼容問題，保障信息的順利流通，（）制定了一系列標(biāo)準(zhǔn)，涉及HTML、XML、CSS等，并建議開發(fā)者遵循。微軟美國計(jì)算機(jī)協(xié)會(huì)（ACM）聯(lián)合國教科文組織萬維網(wǎng)聯(lián)盟（W3C）答案：D解析：姿勢題，我承認(rèn)我不會(huì)，不過我根據(jù)豐富的經(jīng)驗(yàn)，猜對(duì)了。雖然微軟很流弊，但是這種標(biāo)準(zhǔn)一般不是微軟定制的；聯(lián)合國教科文組織總部設(shè)在法國巴黎。其宗旨是促進(jìn)教育、科學(xué)及文化方面的國際合作，以利于各國人民之間的相互了解，維護(hù)世界和平。所以就是D了。體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場，按老師的要求從高道矮站成一排。每個(gè)同學(xué)按順序來到操場時(shí)，都從排尾走到排頭，找到第一個(gè)比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的方法類似于（）算法?？焖倥判虿迦肱判蛎芭菖判驓w并排序答案：B解析：排序問題。這個(gè)站隊(duì)方法與插排相同，找個(gè)位置插進(jìn)去！1956年（）授予肖克利（WilliamShockley）（帶魚：“有沒有一種‘Youareshock!’的感覺啊?”）、巴?。↗ohnBardeen）和布拉頓（WalterBrattain），以表彰他們對(duì)半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。諾貝爾物理學(xué)獎(jiǎng)約翰?馮?諾依曼獎(jiǎng)圖靈獎(jiǎng)D. 高德納獎(jiǎng)（DonaldE.KnuthPrize）答案：A解析：超級(jí)姿勢題，沒啥人做得對(duì)，我也錯(cuò)了…我看D標(biāo)了英文，很犀利的樣子，我就選D了，結(jié)果竟然是A。D的那個(gè)也是計(jì)算機(jī)的獎(jiǎng)，始于1996年。1996年姚期智得了高德納獎(jiǎng)，2000年姚期智得了圖靈獎(jiǎng)，不過姚期智太不注重名利了，沒啥人知道，搜狗拼音都打不出來。1997年萊斯利得了高德納獎(jiǎng)，2010年得了圖靈獎(jiǎng)，我以為會(huì)考最新的圖靈獎(jiǎng)得主，背了這人名字，結(jié)果沒考，考的是幾十年前的人……冏二、不定項(xiàng)選擇題（共10題，每題1.5分，共15分。每題有一個(gè)或多個(gè)正確選項(xiàng)。多選或少選均不得分。）（這部分較難得分，我錯(cuò)了很多題）如果根節(jié)點(diǎn)的深度記為1，則一棵恰有2011個(gè)葉子結(jié)點(diǎn)的二叉樹的深度可能是（）。TOC\o"1-5"\h\z1011122011答案：CD解析：可以自己推出，深度為n的滿二叉樹葉子結(jié)點(diǎn)數(shù)為2A（n-1），2人10=1024,2人11=2048,深度為11的數(shù)怎么搞都搞不出2011個(gè)結(jié)點(diǎn)，所以10和11不選。深度為n的一根蛋疼樹也可以有n個(gè)葉子結(jié)點(diǎn)…這個(gè)我沒考慮到，果斷錯(cuò)了。在布爾邏輯中，邏輯“或”的性質(zhì)有（）。（原題ABCD選項(xiàng)里的或是個(gè)類似V的表示或的符號(hào)，為了該文檔流通方便我都改成了“V”）交換律：PVq=qVp結(jié)合律：PV（QVR）=（PVQ）VR幕等律：PVP=P有界率：PV1=1（1表示邏輯真）答案：ABCD解析：基礎(chǔ)題。雖然我不知道or是否有什么交換律結(jié)合律，思考一下就行了。A，位置交換肯定不影響結(jié)果；B，不管怎么括，都是其中有1就是1，都為0才為0,；C肯定，D更不用說。一個(gè)正整數(shù)在十六進(jìn)制下有100位，則它在二進(jìn)制下可能有（）位。TOC\o"1-5"\h\z399400401404答案：AB解析：一個(gè)十六進(jìn)制數(shù)字可用4個(gè)二進(jìn)制數(shù)字表示，100位的十六進(jìn)制可以用400位二進(jìn)制表示，當(dāng)然剛開始那幾位可能是0，所以也可能是399、398、397位二進(jìn)制表示。匯編語言（）。A. 是一種與硬件無關(guān)的程序設(shè)計(jì)語言在編寫復(fù)雜程序時(shí)，相對(duì)于高級(jí)語言而言代碼量較大，且不易調(diào)試可以直接訪問寄存器、內(nèi)存單元、I/O端口隨著高級(jí)語言的誕生，如今已完全被淘汰，不再使用答案：BC解析：姿勢題，我姿勢不夠沒做對(duì)。A，與硬件有關(guān)；B，這是肯定的；C，百度說匯編語言能夠直接訪問與硬件相關(guān)的存儲(chǔ)器或I/O端口。D，百度說匯編語言是一種功能很強(qiáng)的程序設(shè)計(jì)語言，也是利用計(jì)算機(jī)所有硬件特性并能直接控制硬件的語言。匯編語言是比較底層的語言，不會(huì)不再使用，只是不用來直接編程而已?，F(xiàn)有一段文言文，要通過二進(jìn)制哈弗曼編碼進(jìn)行壓縮。簡單起見，假設(shè)這段文言文只由4個(gè)漢字“之”、“乎”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、400。那么，“也”字的編碼長度可能是（）。TOC\o"1-5"\h\z1234答案：BC解析：初賽常考的哈夫曼編碼。哈夫曼編碼是一種很犀利的編碼，按那啥的使用頻率，把使用頻率高的那啥編為短一點(diǎn)的編碼，使用頻率高的長一點(diǎn)。一般方法是建一棵哈弗曼樹，然后左子樹為0右子樹為1，從上到下的一條路為這個(gè)葉子結(jié)點(diǎn)的編碼。百度說把所有東西放到一個(gè)集合F中，在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。這樣，從這題來看，先弄300和400的兩個(gè)，變成一個(gè)根為700的樹。然后現(xiàn)在就有600,700,700，選600和其中一個(gè)700再做一顆樹。這樣就會(huì)有兩種情況，“也”可能是2位也可能是3位，所以選BC。生物特征識(shí)別是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識(shí)別、虹膜識(shí)別、人臉識(shí)別等技術(shù)已廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。以下屬于生物特征識(shí)別技術(shù)及其應(yīng)用的是（）。指靜脈驗(yàn)證步態(tài)驗(yàn)證ATM機(jī)密碼驗(yàn)證聲音驗(yàn)證答案：ABD解析：蛋疼題。主要糾結(jié)于選不選D，你需要一定的考試經(jīng)驗(yàn)和對(duì)出題老師的心理分析，得出D這個(gè)選項(xiàng)就是特指生物的聲音而不是各種聲音，選上D。對(duì)于序列“7、5、1、9、3、6、8、4”，在不改變順序的情況下，去掉（）會(huì)使逆序?qū)Φ膫€(gè)數(shù)減少3.TOC\o"1-5"\h\z7536答案：CD解析:姿勢題，我沒姿勢我不自豪，做錯(cuò)。百度說，對(duì)于一個(gè)包含N個(gè)非負(fù)整數(shù)的數(shù)組A[1..n],如果有i<j，且A[i]>A[j]，則稱（A[i],A[j]）為數(shù)組A中的一個(gè)逆序?qū)Α，F(xiàn)在知道逆序?qū)κ巧读?，就容易做了，?shù)字這么少，窮舉兩個(gè)數(shù)只需C（2,8）=28次，找到所有的逆序?qū)?，自己在草稿紙上開個(gè)數(shù)組，每找到一個(gè)就在這個(gè)數(shù)下面加一，然后看哪個(gè)數(shù)在數(shù)組里等于3的就選它。計(jì)算機(jī)中的數(shù)值信息分為整數(shù)和實(shí)數(shù)（浮點(diǎn)數(shù)）。實(shí)屬之所以能表示很大或者很小的數(shù)是由于使用了（）。階碼補(bǔ)碼反碼較長的位數(shù)答案：A解析：姿勢題，我略看了一點(diǎn)這方面的姿勢，我有姿勢我自豪。對(duì)右圖使用Dijkstra算法計(jì)算S點(diǎn)到其余各點(diǎn)的最短路徑長度時(shí)，到B點(diǎn)的距離【B】初始時(shí)賦值為8,在算法的執(zhí)行過程中還會(huì)出現(xiàn)的值有（）。（原試題右圖，為照顧手機(jī)黨我字述邊集（（a,b,c）代表a到b有條長c的邊）：（S,A,2），（S,B,8），（S,D,3），（A,B,5），（B,C,1），（B,D,3），（C,D,1）TOC\o"1-5"\h\z3765答案：BCD解析：學(xué)過Dijkstra就知道，我是太久沒用這個(gè)忘記了冏?Dijkstra的思想是建個(gè)一維數(shù)組記錄起點(diǎn)到其他各點(diǎn)的距離（沒路為無限大），然后找一個(gè)這個(gè)距起點(diǎn)最近的點(diǎn)作為中間結(jié)點(diǎn)，更新起點(diǎn)到各個(gè)點(diǎn)的距離，然后把中心結(jié)點(diǎn)加個(gè)用過的標(biāo)記，繼續(xù)找下一個(gè)距離起點(diǎn)最近的點(diǎn)為中心結(jié)點(diǎn)，直到所有的點(diǎn)都當(dāng)過中心結(jié)點(diǎn)就結(jié)束。這題中，第一個(gè)找到的中間結(jié)點(diǎn)是A，這時(shí)把SB更新為7，然后找到的中心結(jié)點(diǎn)為D，這時(shí)把SB更新為6，把SC更新為4；下一個(gè)找到的中心結(jié)點(diǎn)為C，這時(shí)把SB更新為5。所以選BCD。為計(jì)算機(jī)網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定的集合稱為（原題寫的是“成為”）網(wǎng)絡(luò)協(xié)議。下列英文縮寫中，（）是網(wǎng)絡(luò)協(xié)議。HTTPTCP/IPFTPWWW答案：ABC解析：網(wǎng)絡(luò)協(xié)議不單指某一協(xié)議，而是指各種為計(jì)算機(jī)網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定的集合。所以HTTP（超文本傳輸協(xié)議）、TCP/IP、FTP（文件傳輸協(xié)議）都屬于網(wǎng)絡(luò)協(xié)議。WWW是萬維網(wǎng)，不是協(xié)議。三、問題求解（共2題，每題5分，共計(jì)10分）平面圖是可以畫在平面上，且它的邊僅在頂點(diǎn)上才能相交的簡單無向圖。4個(gè)頂點(diǎn)的平面圖至多有6條邊，如右圖所示。那么，5個(gè)頂點(diǎn)的平面圖至多有―條邊。(圖我就不畫了，比較簡單，是一個(gè)口畫一條對(duì)角線，然后沒有對(duì)角線的那2個(gè)點(diǎn)從口外面連了一條曲線)答案：9解析：手畫，怎么畫最多都只能畫9條，所以……定義一種字符串操作，一次可以將其中一個(gè)元素移到任意位置。舉例說明，對(duì)于字符串“BCA”，可以將A移到B之前，變成字符串“ABC”。如果要將字符串"DACHEBGIF”變成“ABCDEFGHI”，最少需要次操作。答案：4解析：這個(gè)不是交換位置喔，是取出再插入。先在原序列中找個(gè)最長上升子序列(除去某些元素，但不影響相對(duì)位置的序列稱為子序列)，發(fā)現(xiàn)是ACEGI，長度為5,最長了，剩下4個(gè)移動(dòng)一下就能成有序的ABCDEFGHI了。四、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分)1.constSIZE=100;varn,i,sum,x:integer;A:array[1..SIZE]ofinteger;beginreadln(n);fillchar(a,sizeof(a),0);fori:=1tondobeginread(x);inc(a[x]);end;i:=0;sum:=0;whilesum<(ndiv2+1)dobegininc(i);sum:=sum+a[i];end;writeln(i);end.輸入：1145664332321輸出： 答案：3解析：這是個(gè)求中位數(shù)的程序。注意讀入的時(shí)候不是把數(shù)讀進(jìn)a[i],而是讓a[x]+1。簡單模擬也可以。啊varn:ineger;proceduref2(x,y:integer);forward;proceduref1(x,y:integer);beginifx<nthenf2(y,x+y);end;proceduref2(x,y:integer);beginwrite(x,’‘)；f1(y,x+y);end;beginreadln(n);f1(0,1);end.輸入：30輸出： 答案：1251334解析：模擬一下，發(fā)現(xiàn)是隔一個(gè)輸出一個(gè)的斐波那契數(shù)列，注意主程序調(diào)用的是^1而不是f2,我沒注意看以為是f2結(jié)果整個(gè)都錯(cuò)位了冏。啊constv=100;varvisited:array[1..v]ofboolean;e:array[1..v,1..v]ofinteger;n,m,ans,i,j,a,b,c:integer;proceduredfs(x,len:integer);vari:integer;beginvisited[x]:=true;iflen>ansthenans:=len;fori:=1tondoif(notvisited(i))and(e[x,i]<>-1)thendfs(I,len+e[x,i]);visited[x]:=false;end;beginreadln(n,m);fori:=1tondoforj:=1tondoe[i][j]:=-1;fori:=1tomdobeginreadln(a,b,c);e[a][b]:=c;e[b][a]:=c;end;fori:=1tondovisited[i]:=false;ans:=0;fori:=1tondodfs(i,0);writeln(ans);end.輸入：46TOC\o"1-5"\h\z2103204301402460輸出： 答案：150解析：一眼看去，過程名叫DFS,輸入是個(gè)無向圖，len>ans的話ans:=len，可以得知這是個(gè)在圖中用DFS找最長的路徑的程序。DFS以任意點(diǎn)作為起點(diǎn)，找一條路徑，本次走過的點(diǎn)不走，找到?jīng)]路走為止。由于就4個(gè)點(diǎn)，最多就走3條邊，看看最長的那3條，605040,可以一次走完，即走2-4-1-3可以走完這3條邊，所以ans是150。4.啊constSIZE=10000;LENGTH=10;varsum:longint;n,m,I,j:integer;a:array[1..SIZE,