NOIP(Pascal提高組)重點(diǎn)試題(四)

1、NOIP（Pascal提高組）重點(diǎn)試題（四）1單項(xiàng)選擇題1.與 16 進(jìn)制數(shù) A1.2 等值的 10 進(jìn)制數(shù)是A.101.2B.111.4C.161.125D.177.252. 一個(gè)字節(jié)byte由個(gè)二進(jìn)制組成。A.8B.16C.32D.以上都有可能3.以下邏輯表達(dá)式的值恒為真的是A.P V h PA QV （PAn Q）C.PVQV PAn Q:V PA QB.QV h PA QQ V PAQD.PVq QVPAn Q4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名是)。 A. exeB. comC. dllD.以上都不是12*12=也成立5 .假如在某個(gè)進(jìn)制下等式7*7=41成立，那么在該進(jìn)制下等式A

2、. 100B. 144C. 164D. 1966 .提出“存儲(chǔ)程序”的計(jì)算機(jī)工作原理的是A.克勞德？香農(nóng) B.戈登？摩爾C.查爾斯？巴比奇D.馮?諾依曼7.前綴表達(dá)式“ + 3 * 2 + 5的值是。A. 23B. 25C. 37D. 658.主存儲(chǔ)器的存取速度比中央處理器（CPU）的工作速度慢的多,從而使得后者的效率受到妨礙。而依照局部性原CPU理，CPU所訪(fǎng)問(wèn)的存儲(chǔ)單元通常都趨于一個(gè)較小的連續(xù)區(qū)域中。因此，為了提高系統(tǒng)整體的執(zhí)行效率，在 中引入了（）。A.寄存器B.高速緩存C.閃存 D.外存9 .完全二叉樹(shù)的順序存儲(chǔ)方案，是指將完全二叉樹(shù)的結(jié)點(diǎn)從上到下、從左到右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組

3、中。假定根結(jié)點(diǎn)存放在數(shù)組的1號(hào)位置上，那么第k號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)假如存在的話(huà)，應(yīng)當(dāng)存放在數(shù)組中的號(hào)位置。A. 2kB. 2k+1 C. k/2 下取整 D. （k+1）/210 .以下競(jìng)賽活動(dòng)中歷史最悠久的是。A. NOIP B.NOI C. IOI D. APIO【二】不定項(xiàng)選擇題1 .元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。假如第1個(gè)出棧的是 R3,那么第5個(gè)出棧的可能是（）。A.R1B.R2C.R4D.R52 . Pascal語(yǔ)言，C語(yǔ)言和C+吾言者B屬于（）。A.高級(jí)語(yǔ)言 B.自然語(yǔ)言 C.解釋性語(yǔ)言 D.編譯性語(yǔ)言3 .原地排序是指在排序過(guò)程中（除了存儲(chǔ)

4、待排序元素以外的）輔助空間的大小與數(shù)據(jù)規(guī)模無(wú)關(guān)的排序算法。以下屬于原地排序的有（）。A.冒泡排序B.插入排序C.基數(shù)排序D.選擇排序4 .在整數(shù)的補(bǔ)碼表示法中，以下說(shuō)法正確的選項(xiàng)是。A、只有負(fù)整數(shù)的編碼最高位為1B、在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對(duì)值相同C、整數(shù)0只有一個(gè)唯一的編碼D、兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，假設(shè)在最高位產(chǎn)生進(jìn)位，那么表示運(yùn)算溢出5 . 一顆二叉樹(shù)的前序遍歷序列是ABCDEFG后序遍歷序列是 CBFEGD A那么根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可能是B. 2C. 4D. 6NOI官方網(wǎng)站的超鏈接的是” 歡迎訪(fǎng)問(wèn)NOI網(wǎng)站/a” 歡迎訪(fǎng)問(wèn)NOI網(wǎng)站/a"

5、 歡迎訪(fǎng)問(wèn)NOI網(wǎng)站/a6 .在以下HTML語(yǔ)句中，能夠正確產(chǎn)生一個(gè)指向A <a url= " h t t p : / / w w w . n o i . c nB、<a href= " h t t p : / / w w w . n o i . c nC、<a>h t t p : / / w w w . n o i . c n</a>D> <a name" h t t p : / / w w w . n o i . c n7 .關(guān)于拓?fù)渑判?，以下說(shuō)法正確的選項(xiàng)是（A、所有連通的有向圖都能夠?qū)崿F(xiàn)拓?fù)渑判駼、對(duì)同一個(gè)圖

6、而言，拓?fù)渑判虻慕Y(jié)構(gòu)是唯一的C、拓?fù)渑判蛑腥攵葹?0的結(jié)點(diǎn)總會(huì)排在入度大于 0的結(jié)點(diǎn)的前面D拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度大于0的點(diǎn)8. 一個(gè)平面的法線(xiàn)是指與該平面垂直的直線(xiàn)。過(guò)點(diǎn)A、過(guò)點(diǎn)1, 1 , 1、 2, 3, 3的直線(xiàn)C、過(guò)點(diǎn)0, 3, 0、-3,1,1的直線(xiàn)(1,1,(1) 、 0,3,0、(2,0,0)的平面的法線(xiàn)是B、過(guò)點(diǎn)1,1 ,1、 3,2,1的直線(xiàn)D過(guò)點(diǎn)2,0,0、 5,2,1的直線(xiàn)p指向鏈表中的一個(gè)結(jié)點(diǎn)，他()。9 .雙向鏈表中有兩個(gè)指針域llink 和rlink ,分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)的左右結(jié)點(diǎn)均為非空?，F(xiàn)要求刪除結(jié)點(diǎn)p,那么以下語(yǔ)句序列中正確的選

7、項(xiàng)是A、p->rlink->llink=p->rlink;p->llink->rlink=p->llink; delete p;B、p->llink->rlink=p->rlink;p->rlink->llink = p->llink; delete p;C、p->rlink->llink = p->llink;p->rlink->llink ->rlink = p->rlink; delete p;D> p->llink->rlink = p->rlink

8、;p->llink->rlink->link = p->llink; delete p;10 .今年(2017年)發(fā)生的事件有。A、惠普實(shí)驗(yàn)室研究員Vinay Deolalikar自稱(chēng)證明了 P*NPB、英特爾公司收購(gòu)計(jì)算機(jī)安全軟件公司邁克菲(McAfee)【三】問(wèn)題求解1、LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過(guò)程中，開(kāi)始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，假如在編碼 的過(guò)程中遇到一個(gè)新的詞條，那么該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。舉例說(shuō)明，考慮一個(gè)待編碼的信息串：“ xyxyyyyxyx ”。初始詞典只有 3個(gè)條目，第一個(gè)為 x,編碼為 1

9、;第二個(gè)為y,編碼為2;第三個(gè)為空格，編碼為 3;因此串“ xyx”的編碼為1-2-1 其中-為編碼分隔符， 加上后面的一個(gè)空格確實(shí)是1-2-1-3 o但由于有了一個(gè)空格，我們就明白前面的“xyx”是一個(gè)單詞，而由于該單詞沒(méi)有在詞典中，我們就能夠自適應(yīng)的把那個(gè)詞條添加到詞典里，編碼為4,然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類(lèi)推。因此，最后得到編碼：1-2-1-3-2-2-3-5-3-4。我們能夠看到，信息被壓縮了。壓縮好的信息傳遞到同意方，接收方也只要依照基礎(chǔ)詞典就能夠完成 對(duì)該序列的完全恢復(fù)。解碼過(guò)程是編碼過(guò)程的逆操作?，F(xiàn)在初始詞典的3個(gè)條目如上述，接收端收到的編碼信息為 2-2-1-2

10、-3-1-1-3-4-3-1-2-1-3-5-3-6,那么解碼后的信息串是“ "。2 .無(wú)向圖G有7個(gè)頂點(diǎn)，假設(shè)不存在由奇數(shù)條邊構(gòu)成的簡(jiǎn)單回路，那么它至多有 條邊3 .記T為一隊(duì)列，初始時(shí)為空，現(xiàn)有 n個(gè)總和不超過(guò) 32的正整數(shù)依次入列。假如不管這些數(shù)具體為何值，都能 找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列T中的數(shù)之和恰好為9,那么n的最小值是 o【四】閱讀程序?qū)懡Y(jié)果1. const size=10;vari,j,cnt,n,m:integer;data:array1.sizeofinteger; begin readln(n,m);fori:=1tondoread(datai);

11、fori:=1tondobegincnt:=0;forj:=1tondoif(datai<dataj)or(dataj=datai)and(j<i) theninc(cnt);ifcnt=mthenwriteln(datai);end;end.輸入5296-801687輸出：2.constsize=100;varna,nb,i,j,k:integer;a,b:array1.sizeofinteger;beginreadln(na);fori:=1tonadoread(ai);readln(nb);fori:=1tonbdoread(bi);i:=1;j:=1;while(i<

12、=na)and(j<=nb)dobeginifai<=bjthenbeginwrite(ai,'');inc(i);endelsebeginwrite(bj,'');inc(j);end;end;ifi<=nathenfork:=itonadowrite(ak,");ifj<=nbthen fork:=jtonbdo write(bk,");end.輸入5135794261014輸出：3.constnum=5;varn:integer;functionr(n:integer):integer;vari:integer;

13、beginifn<=numthenbeginr:=n;exit;end;fori:=1tonumdoifr(n-i)<0thenbeginr:=i;exit;end;r:=-1;end;beginreadln(n);writeln(r(n);end.輸入16輸出：4.constsize=100;varn,m,x,y,i:integer;r:array1.sizeofinteger;map:array1.size,1.sizeofboolean;found:boolean;functionsuccessful:boolean;vari:integer;beginfori:=1tond

14、oifnotmapririmodn+1 thenbeginsuccessful:=false;exit;end;successful:=true;end;procedureswap(vara,b:integer);vart:integer;begint:=a;a:=b;b:=t;end;procedureperm(left,right:integer);vari:integer;beginiffoundthenexit;ifleft>rightthenbeginifsuccessfulthenbeginfori:=1tondowriteln(ri,");found:=true;

15、end;exit;end;fori:=lefttorightdobeginswap(rleft,ri);perm(left+1,right);swap(rleft,ri);end;end;beginreadln(n,m);fillchar(map,sizeof(map),false);fori:=1tomdobegin readln(x,y); mapxy:=true; mapyx:=true;end;fori:=1tondori：=i； found:=false; perm(1,n); ifnotfound then writeln('Nosoloution');end. 輸

16、入： 912 12 23 34 45 56 61 17 27 38 48 59 69 輸出：【五】完善程序1.(過(guò)河問(wèn)題)在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過(guò)唯一的一根獨(dú)木橋走到河的左岸.在伸手不見(jiàn)五指的黑夜里,過(guò)橋時(shí)必須借照燈光來(lái)照明，不幸的是，他們只有一盞燈.另外，獨(dú)木橋上最多能承受兩個(gè)人同時(shí)通過(guò)，否那么將會(huì)坍塌.每個(gè)人單獨(dú)過(guò)獨(dú)木橋都需要一定的時(shí)間，不同的人要的時(shí)間可能不同.兩個(gè)人一起過(guò)獨(dú)木橋時(shí)，由于只有一盞燈，因此需要的時(shí)間是較慢的那個(gè)人單獨(dú)過(guò)橋所花費(fèi)的時(shí)間.現(xiàn)在輸入N(2<=N<1000)和這N個(gè)人單獨(dú)過(guò)橋需要的時(shí)間，請(qǐng)計(jì)算總共最少需要多少時(shí)間，他們才能全部到達(dá)

17、河左岸.例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過(guò)橋的時(shí)間分別為124,那么總共最少需要的時(shí)間為7.具體方法是：甲乙一起過(guò)橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶回，然后甲，丙在一起過(guò)橋到河的左岸，總時(shí)間為2+1+4=7.constSIZE=100;INFINITY=10000;LEFT=true;RIGHT=false;LEFT_TO_RIGHT=true; RIGHT_TO_LEFT=false; varn,i:integer;time:array1.Sizeofinteger;pos:array1.SizeofBoolean; functionmax(a,b:integer):integer;b

18、eginifa>bthenmax:=aelsemax:=b;end;functiongo(stage:boolean):integer;vari,j,num,tmp,ans:integer;beginif (stage=RIGHT_TO_LEFT)thenbeginnum:=0;ans:=0;fori:=1tondoifposi=Rigntthen begininc(num);iftimei>ansthen ans:=timei;end;if thenbegingo:=ans;exit;end;ans:=INFINITY;fori:=1ton - 1doifposi=RIGHTth

19、enforj:=i+1tondoifposj=RIGHTthen beginposi:=LEFT;posj:=LEFT;tmp:=max(timei,timej)+ iftmp<ansthenans:=tmp;posi:=RIGHT; posj:=RIGHT;end;go:=ans;endelseif (stage=LEFT_TO_RIGHT)thenbeginans:=INFINITY;fori:=1tondoif thenbeginposikRIGHT;tmp:=iftmp<ansthenans:=tmp;end;go:=ans;endelsego:=0;end;beginreadln(n);fori:=1tondobeginread(timei);posi:=RIGHT;end;wri