noip2010提高組初賽試題解析

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

b2=2,…b8

b9

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