noip2010提高組初賽試題解析

（C++語(yǔ)言二小時(shí)完成●●全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效與16進(jìn)制數(shù)A1.2等值的10進(jìn)制數(shù)是 ） ） ） 到影響。而根據(jù)局部性原理，CPU所的單元通常都趨于在一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了（ 一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號(hào)位置，則第K號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)如果 C.k/2下取 ）二.選擇題（共10題，每題1.5分，共計(jì)15分。每題有一個(gè)或多個(gè)正確選項(xiàng)。多選元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第一個(gè)出棧的是R3，那么第五個(gè)出棧的可能是（ C.0只有唯一的一個(gè)編碼一顆二叉樹(shù)的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點(diǎn)的左 在下列HTML語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向NOI的超的是 <a ">歡迎NOI<a ">歡迎NOI <a ">歡迎NOI （1,1,1（1,1,1（0,3,0（2,0,0雙向鏈表中有兩個(gè)指針域llink和rlinkp指向鏈表中P,則下面語(yǔ)句序列中正確的是 ）A.p->rlink->llink=p-p->llink->rlink=p->llink;deleteB.P->llink->rlink=p-p->rlink->llnik=p->llink;deleteC.p->rlink->llink=p-p->rlink->llink->rlink=p->rlink;deleteD.p->llink->rlink=p-p->llink->rlink->llink=p->llink;delete 蘋(píng)果公司發(fā)布4三、問(wèn)題求解（3515分LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過(guò)程中，開(kāi)始時(shí)只有一部基礎(chǔ)構(gòu)造元素的舉例說(shuō)明，考慮一個(gè)待編碼的信息串：“xyxyyyyxyx”3個(gè)條目，第x,1y23；于是串“xyx”的編碼1-2-1（其中-為編碼分隔符），1-2-1-3。但由于有了一個(gè)空4，然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類(lèi) 無(wú)向圖G有7個(gè)頂點(diǎn)，若不存在由奇數(shù)條邊構(gòu)成的簡(jiǎn)單回路，則它至多有 記T為一隊(duì)列，初始時(shí)為空，現(xiàn)有n個(gè)總和不超過(guò)32的正整數(shù)依次入列。如果無(wú)論這些數(shù)具體為何值，都能找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列T中的數(shù)之和恰好為9，那么n的最小值是 四.閱讀程序?qū)懡Y(jié)果（4728分#include<iostream>usingnamespacestd;intmain()constintSIZEintdata[SIZE],i,j,cnt,n,m;for(i=1;i<=n;i++)for(i=1;i<=n;i++){cnt=0;for(j=1;j<=n;if((data[i]<data[j])||(data[j]==data[i]&&j<i))if(cnt==m)}return}596-8016#include<iostream>usingnamespacestd;int{constintintna,nb,a[SIZE],b[SIZE],i,j,k;for(i=1;i<=na;i++)for(i=1;i<=nb;i++)while((i<=na)&&(j<=nb)){if(a[i]<=b[j]){cout<<a[i]<<’‘;}elsecout<<b[j]<<’‘;}}if(i<=for(k=i;k<=na;k++)cout<<a[k]<<’‘;if(j<=for(k=j;k<=nb;k++)cout<<b[k]<<’‘;return}5135742610#include<iostream>usingnamespaceconstintNUM=5;intr(intn){inti;returnn;returni;return-}int{intn;return0;}#include<iostream>usingnamespacestd;constintsize=100;intboolbool{inti;returnfalse;return}voidswap(int*a,int{intt;}voidperm(intleft,int{inti;{{cout<<r[i]<<'}}{}}int{intx,y,i;{}cout<<"Nosoloution!"<<endl;return0;}91234569五、完善程序（12102.527分1.(過(guò)河問(wèn)題)在一個(gè)月黑風(fēng)高的夜晚,的左岸.在伸手不見(jiàn)五指的黑夜里,過(guò)橋時(shí)必須借照燈光來(lái)照明,不幸的是,他們只有一盞燈.另外,獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過(guò),否則將會(huì)坍塌.每個(gè)人單獨(dú)過(guò)獨(dú)木橋都需要一定的時(shí)間,不同的人要的時(shí)間可能不同.兩個(gè)人一起過(guò)獨(dú)木橋時(shí),由于只有一盞燈,所以需要的時(shí)間(<=N1000和這N的時(shí)間,,例如,3個(gè)人甲、乙、丙,124,則總共最少需要的時(shí)間為7.具體方法是:甲乙一起過(guò)橋到河的左岸,甲單獨(dú)回到河的右岸將燈帶回,然后甲,丙在一起過(guò)橋到河的左岸,2+1+4=7。#include<iostream>usingnamespaceconstintsize=100;constintinfinity=10000;constboolLeft=true;constboolRight=false;constboolleft_to_right=true;constboolright_to_left=false;intn,hour[size];boolpos[size];intmax(inta,int{returna;return}intgo(bool{inti,j,num,tmp,ans;{{} （1）)returnans;{ （2）}return}{ （3）{ （4）;（5）}return}return}int{inti;{}return0;}，2（有敵情發(fā)生，白天燃燒柴草，通過(guò)濃煙表達(dá)信息：夜晚燃燒，以火光傳遞軍情。在某兩座城市之間有n個(gè)烽火臺(tái)，每個(gè)烽火臺(tái)發(fā)出信號(hào)都有一定的代價(jià)。為了使準(zhǔn)確的傳遞，mn、m和每個(gè)烽火臺(tái)發(fā)出的信號(hào)的代價(jià)，請(qǐng)計(jì)算總共最少需要話費(fèi)多少代價(jià)，才能使敵軍來(lái)襲之時(shí)能在這兩座城市之間準(zhǔn)確的傳，425個(gè)烽火臺(tái)發(fā)出信號(hào)。#include<iostream>usingnamespacestd;constintsize=100;int//heap[i]表示用順序數(shù)組的堆heap中第i個(gè)元素的值//pos[i]表示opt[i]在堆heap中的位置，即//home[i]表示heap[i]在序列opt中的位置，即voidswap(inti,int//交換堆中的第ij個(gè)元素{inttmp;}voidadd(int//在堆中插入{inti; （1）（2）;while((i>1)&&{}}voidremove(int//在堆中刪除{inti,j;r--while((i>1)&&{}{if((i+i+1<=r)&&(heap[i+i+1]<heap[i+i]))（3）;{ }}}int{inti;{}{ （5）; }return0;}簡(jiǎn)單的進(jìn)制轉(zhuǎn)換，(A1.2)16=1016+1+216-1=161.125,因此答案選CABABAAAABA考查L(zhǎng)inux基礎(chǔ)知識(shí)，exe和com均是windows下的可執(zhí)行文件，dll是動(dòng)態(tài)庫(kù)D。10=（196）10；（196）10=（144）12144B?？藙诘隆は戕r(nóng)（ClaudeElwoodShannon，數(shù)學(xué)家、信息論的創(chuàng)始人；戈登·摩MooreInBabbage，十九世紀(jì)的英國(guó)數(shù)學(xué)家，發(fā)明了世界上第一臺(tái)機(jī)械計(jì)算機(jī)器——差分機(jī)；約翰·馮·諾依曼（Johnvon ann）提出“程序”的計(jì)算機(jī)工作原理，該理論的要點(diǎn)是：數(shù)字計(jì)算機(jī)的數(shù)制采用二進(jìn)制，計(jì)算機(jī)應(yīng)該按照程序順序執(zhí)行。人們把馮·諾依曼的這個(gè)理論稱為馮·諾依曼體系結(jié)構(gòu)。因此答案選擇D。2時(shí)彈出兩操作數(shù)和操作符運(yùn)算后再壓棧。因此前綴表達(dá)式“+3*2+512”運(yùn)算時(shí)是先依次存入+3*2+5125和“+1217，172又是連續(xù)2個(gè)操作數(shù)，取出“*3434+3=37C。來(lái)暫存指令、數(shù)據(jù)和位址。在處理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序計(jì)數(shù)器(PC)。在處理器的算術(shù)及邏輯部件中，包含的寄存器有累加器(ACC)。高速緩存是為了大幅提升系統(tǒng)的執(zhí)行效率，在CPU與主器之間，使用速度最快之SRAM來(lái)作為CPU的數(shù)據(jù)快取區(qū)，目的是為了讓數(shù)據(jù)的速度適應(yīng)CPU的處理速度，其基于的原理是內(nèi)存中“程序執(zhí)行與數(shù)據(jù)的局域性行為”，即一定程序執(zhí)行時(shí)間和空間內(nèi)，被的代碼集中于一部分。器按照用途可分為主器和輔助器，主器又稱內(nèi)器（簡(jiǎn)稱內(nèi)存B。的編號(hào)為[i/2],ii/2,它是雙親結(jié)點(diǎn)的左孩子，i為奇數(shù)時(shí)，其雙親結(jié)點(diǎn)的編號(hào)為(i-1)/2C。考查對(duì)信息學(xué)競(jìng)賽的了解程度。1984年鄧小平：“計(jì)算機(jī)的普及要從娃娃做起。”NOI二、選擇在棧底。因此答案選ACD。自然語(yǔ)言通常是指一種自然地隨文化演化的語(yǔ)言，如英語(yǔ)、漢語(yǔ)、法語(yǔ)等，與之相對(duì)應(yīng)的是如編程語(yǔ)言等為計(jì)算機(jī)而設(shè)的“人造”語(yǔ)言。計(jì)算機(jī)語(yǔ)言具有高級(jí)語(yǔ)言和低級(jí)語(yǔ)言之分。低級(jí)語(yǔ)言分機(jī)器語(yǔ)言（計(jì)算機(jī)語(yǔ)言具有高級(jí)語(yǔ)言和低級(jí)語(yǔ)言之分。低級(jí)語(yǔ)言分機(jī)器語(yǔ)言（二進(jìn)制語(yǔ)言）和匯編語(yǔ)言（符號(hào)語(yǔ)言，這兩種語(yǔ)言都是面向機(jī)器的語(yǔ)言，和具體機(jī)器的指令系統(tǒng)密切相關(guān)，難學(xué)難記，于是人們又發(fā)明了更加易用的所謂高級(jí)語(yǔ)言。在這種語(yǔ)言下，其語(yǔ)法和結(jié)構(gòu)更類(lèi)似普通英文，且由于遠(yuǎn)離對(duì)硬件的直接操作，使得一般人經(jīng)過(guò)學(xué)習(xí)之后都可以編程。如C/C++,Pascal等。編譯性語(yǔ)言寫(xiě)的程序須編譯成機(jī)器語(yǔ)言文件才可執(zhí)行，比如exe文件，以后要運(yùn)行的話就不用重新翻譯了，直接使用編譯的結(jié)果就行了（exe文件，因?yàn)榉g只做了一次，運(yùn)行時(shí)不需要翻譯，所以編譯型語(yǔ)言的程序一般執(zhí)行效率較高。解釋型語(yǔ)言編寫(xiě)的程序不需要編譯，只是在運(yùn)行程序的時(shí)候才翻譯，比如解釋性basic語(yǔ)言，專門(mén)有一個(gè)解釋器能夠直接執(zhí)行basic程序，每個(gè)語(yǔ)句都是執(zhí)行的時(shí)候才翻譯。這樣解釋性語(yǔ)言每執(zhí)行一次就要翻譯一次，效率比較低。但兼容性高。因此答案選AD。理解各種排序的基本原理即能選擇正確的答案，其中基數(shù)排序又叫“桶排序點(diǎn)是數(shù)據(jù)規(guī)模越大，輔助空間就越大。答案為ABD。為“1”A正確。例如8位補(bǔ)碼能夠表示數(shù)的范圍是-128~12710000000表示最小值-128, 最大值127，因此選項(xiàng)B不正確。+0的補(bǔ)碼就是其原碼，也就是說(shuō)是00000000而已（8位來(lái)說(shuō)，-0的補(bǔ)碼是其反碼加1，其反碼是11111111，當(dāng)然，其反碼加1后就是溢出一個(gè)進(jìn)位后，仍然是00000000，因此整數(shù)0只有唯一一個(gè)編碼。因此選項(xiàng)C正確。位，是由計(jì)算機(jī)來(lái)判斷的。計(jì)算機(jī)中常用的溢出判別稱為雙判別法。因此選項(xiàng)D不正二叉樹(shù)的遍歷，首先前序遍歷順序是根節(jié)點(diǎn)--左--右，而后序遍歷順序是左--右--根節(jié)點(diǎn)，A是根節(jié)點(diǎn)，又由后序遍歷知D必然是右的根節(jié)點(diǎn)，D前面的ABC中A是根節(jié)點(diǎn)剩下的BC兩個(gè)節(jié)點(diǎn)必然是左的，因此答案選B。HTML的格式是<ahref=””></a>BA到BBA立體幾何知識(shí)，設(shè)向量（x,y,z）垂直于該平面，則向量（x,y,z）垂直于該平n0，則兩向量垂直。根據(jù)題意，位于該平V3=（0，3，0）-（2，0，0）=（-2，3，0）根據(jù)向量的點(diǎn)積，列出方程組如下： --因此，所有為（32，1）倍數(shù)的向量均為該平面的垂直線。四個(gè)答案中：A（111）-（2，33）=（-1，-2，-2）B（11，1）-（32，1）=（-2，-1，0）C（03，0）-（-311）=（3，2，-1）D（200）-（5，21）=（-3，-2，-1）只有D符合條件，故選D?？疾殡p向鏈表知識(shí)，雙向鏈表參見(jiàn)下圖：模擬程序運(yùn)行即可，故答案為BCD p Windows7200910月由微軟發(fā)布的。因此答案為ABC634>25>1612。參考圖形如下：本題可用抽屜原理求解。設(shè)ai為各正整數(shù)值，則T的隊(duì)列順序?yàn)閍1a2ani項(xiàng)數(shù)之和，則b0=0b1a1b2a1a2b3a1a2a3…。如隊(duì)列T的數(shù)之和恰好為9，實(shí)際上即是找到某個(gè)bjbi，使得bjbi9。由題意可知bi取值范圍為1-32，現(xiàn)將這32個(gè)數(shù)構(gòu)造為集合{1,10},{2,11},,{8,17},{{19,28},…,{23,32},{24},{25},{26}，這17個(gè)集合中的任一個(gè)集合不能包含兩個(gè)或兩個(gè)以上的bi，否則它們的差為9。例如設(shè)n=17時(shí)，隊(duì)列T為

b2=2,…b8

b9

b11=20b17=26,它們中沒(méi)有任意兩個(gè)數(shù)是在同一集合內(nèi)的，所以不存在數(shù)之和恰好等于9故根據(jù)抽屜原理可得，當(dāng)n=18時(shí)，至少存在兩個(gè)bi在同一個(gè)集合，即它們的差為9。因此，答案為n=18。簡(jiǎn)單模擬題，程序從五個(gè)數(shù)中找到一個(gè)數(shù)，使得有m個(gè)數(shù)比該數(shù)字大。輸出結(jié)果6。簡(jiǎn)單算法題，考的是歸并排序，程序?qū)蓚€(gè)有序數(shù)組的數(shù)進(jìn)行歸并操作并輸出有序數(shù)列。輸出結(jié)果為12356791014?？疾檫f歸，可尋找到規(guī)律，即下面的式子： 因此輸出結(jié)果為4考查圖論知識(shí)里的哈密爾頓圖，即由指定的起點(diǎn)前往指定的終點(diǎn)，途中經(jīng)過(guò)所有其他169548327。答案如下：①num2（num3或num②pos[iLEFT（LEFT④hour[igo(RIGHT_TO_LEFT)（go(RIGHT_TO_LEFThour[i]）Cpascaltime[i]+go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT)+⑤pos[i]=分析：本題描述的實(shí)際是一個(gè)網(wǎng)上流行的Flash趣味小游戲，游戲中是一家5口人過(guò)河，每個(gè)人單獨(dú)過(guò)橋時(shí)間為1，3，6，8，12，我們最容易想到的方案是用最快的人（用1來(lái)指代該人）來(lái)充當(dāng)工具，但實(shí)際上這并不是最優(yōu)的，正確方案是：（1）131帶燈回來(lái)，時(shí)間為3+1=4秒；（2）812過(guò)河（最優(yōu)選擇，3帶燈回來(lái)，時(shí)間為12+3=15秒；（3）161帶燈回來(lái)，時(shí)間為6+1=7秒；（4）13過(guò)河，時(shí)間為3秒；共計(jì)花費(fèi)29秒。明白了思路，程序就好編寫(xiě)了。本程序采用的是遞歸方式窮舉所有可能以獲得最優(yōu)解，關(guān)鍵函數(shù)go()代碼注釋如下：intgo(boolstage)//stage用于控制這一步是從左岸到右岸還是從右岸到左岸{inti,j,num,tmp,ans;//num為人數(shù)，ans為花費(fèi)的總時(shí)間if(stage==right_to_left)//如果這一步是從右岸到左岸{{num++;//統(tǒng)計(jì)沒(méi)過(guò)河的人數(shù)ans=hour[i];//獲取最慢的人花費(fèi)的時(shí)間給}if(num<=2)//如果右岸只剩兩個(gè)人returnans