NOIPPascal提高組模擬試題

1、NOIP （Pascal提高組）模擬試題（四）一、單項選擇題1.與16進制數(shù)A1.2等值的10進制數(shù)是（）A.101.2B.111.4C.161.125D.177.252. 一個字節(jié)（byte ）由（個二進制組成。A.8B.16C.32D.以上都有可能3.以下邏輯表達式的值恒為真的是(A.PV(n PA Q V (n PAn Q)C.PV QV( PAn Q V(n PA Q)。B.QV(n PA Q V( PAn QD.PVq QV( PAn QV (n PAn Q)4.L in ux下可執(zhí)行文件的默認擴展名是)。 A. exeB. comC. dllD.以上都不是5.如果在某個進制下等式7

2、*7=41成立，那么在該進制下等式A.100B.144C.164D. 19612*12=()也成立6.提岀“存儲程序”的計算機工作原理的是（ A.克勞德？香農(nóng)B.戈登？摩爾）。C.查爾斯？巴比奇D.馮?諾依曼7.前綴表達式“ + 3 * 2 + 512 ” 的值是（）。A. 23B. 25C. 37D. 658.主存儲器的存取速度比中央處理器理，CPU所訪問的存儲單元通常都趨于一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在 中引入了（）。A.寄存器 B.高速緩存C.閃存D.外存（CPU）的工作速度慢的多,從而使得后者的效率受到影響而根據(jù)局部性原CPU9. 完全二叉樹的順序存儲方案，

3、是指將完全二叉樹的結(jié)點從上到下、從左到右依次存放到一個順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點存放在數(shù)組的1號位置上，則第k號結(jié)點的父結(jié)點如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的（）號位置。 A. 2kB. 2k+1C. k/2 下取整 D. （k+1）/210. 以下競賽活動中歷史最悠久的是（）。A. NOIP B.NOI C. IOI D. APIO二、不定項選擇題1. 元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個岀棧的是R3，那么第5個岀棧的可能是（）。A.R1B.R2C.R4D.R52. Pascal語言，C語言和C+吾言都屬于（）。A.高級語言 B.自然語言 C.

4、解釋性語言 D.編譯性語言3. 原地排序是指在排序過程中（除了存儲待排序元素以外的）輔助空間的大小與數(shù)據(jù)規(guī)模無關(guān)的排序算法。以下屬于原地排序的有（）。A.冒泡排序B.插入排序C.基數(shù)排序D.選擇排序4.A.C.在整數(shù)的補碼表示法中，以下說法正確的是（ 只有負整數(shù)的編碼最高位為 整數(shù)0只有一個唯一的編碼）。B.在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對值相同D.兩個用補碼表示的數(shù)相加時，若在最高位產(chǎn)生進位，則表示運算溢岀5.(一顆二叉樹的前序遍歷序列是）。A. 0ABCDEFG后序遍歷序列是 CBFEGD，則根結(jié)點的左子樹的結(jié)點個數(shù)可能是C. 4D. 66.在下列HTML語句中，可以

5、正確產(chǎn)生一個指向NOI官方網(wǎng)站的超鏈接的是（A.<a url= ” h t t p : / / w w w . n o i . c n” 歡迎訪問NOI 網(wǎng)站 </a>B.<a href= ” h t t p : / / w w w . n o i . c n” 歡迎訪問NOI 網(wǎng)站 </a>C.<a>h t t p : / / w w w . n o i . c n</a>D.<a namW' h t t p : / / w w w . n o i . c n” 歡迎訪問NOI 網(wǎng)站 </a>7.關(guān)于拓撲排

6、序，下列說法正確的是（）。A.所有連通的有向圖都可以實現(xiàn)拓撲排序B. 2B. 對同一個圖而言，拓撲排序的結(jié)構(gòu)是唯一的C. 拓撲排序中入度為0的結(jié)點總會排在入度大于0的結(jié)點的前面D. 拓撲排序結(jié)果序列中的第一個結(jié)點一定是入度大于0的點8. 一個平面的法線是指與該平面垂直的直線。過點A. 過點（1, 1 , 1）、（ 2, 3, 3）的直線C.過點（0, 3, 0）、（ -3 , 1, 1）的直線（1,1,1）、（ 0,3,0 ）、（2,0,0）的平面的法線是（B. 過點（1,1 ,1）、（ 3,2,1）的直線D.過點（2,0,0）、（ 5,2,1）的直線p指向鏈表中的一個結(jié)點，他9. 雙向鏈表中

7、有兩個指針域llink和rlink，分別指向該結(jié)點的前驅(qū)及后繼。設(shè)的左右結(jié)點均為非空。現(xiàn)要求刪除結(jié)點p，則下列語句序列中正確的是（）A. p->rlink->llink=p->rlink;p->lli nk->rl in k=p->lli nk; delete p;B. p->llink->rlink=p->rlink;p->rl in k->lli nk = p->lli nk; delete p;C. p->rlink->llink = p->llink;p->rl in k->lli n

8、k ->rli nk = p->rl ink; delete p;D. p->llink->rlink = p->rlink;p->lli nk->rli nk->li nk = p->ll ink; delete p;10. 今年(2010年)發(fā)生的事件有()。A. 惠普實驗室研究員 V nay Deolalikar自稱證明了NPB. 英特爾公司收購計算機安全軟件公司邁克菲（McAfee）C. 蘋果公司發(fā)布iPhone 4手機D.微軟公司發(fā)布 Windows 7操作系統(tǒng)三、問題求解1. LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始

9、時只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼 的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個待編碼的信息串："xyx yy yy xyx "。初始詞典只有3個條目，第一個為x,編碼為1 ;第二個為y，編碼為2；第三個為空格，編碼為3；于是串"xyx"的編碼為1-2-1 （其中-為編碼分隔符），加上后面的一個空格就是1-2-1-3。但由于有了一個空格，我們就知道前面的“xyx ”是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個詞條添加到詞典里，編碼為4，然后按照新的詞典對后繼信息進行

10、編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作?，F(xiàn)在已知初始詞典的3個條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是" '。2. 無向圖G有7個頂點，若不存在由奇數(shù)條邊構(gòu)成的簡單回路，則它至多有條邊3. 記T為一隊列，初始時為空，現(xiàn)有n個總和不超過 32的正整數(shù)依次入列。如果無論這些數(shù)具體為何值，都能找到一種岀隊的方式，使得存在某個時刻隊列T

11、中的數(shù)之和恰好為 9,那么n的最小值是 。四、閱讀程序?qū)懡Y(jié)果1.con stsize = 10;vari, j, ent, n, m : in teger;data : array1.size of in teger;for i := 1 to n doread(datai);for i := 1 to n dobeginent := 0;for j := 1 to n doif (datai < dataj) or (dataj = datai) and (j < i)beginthen in c(c nt);if ent = mreadl n(n, m);the n write

12、l n(datai); en d;en d.輸入5 296 -8 0 16 87輸出：2.con stsize = 100;varna, nb, i, j, k : integer;a, b : array1.size of in teger;beginreadl n(n a);for i := 1 to na doread(ai);readl n(n b);for i := 1 to nb doread(bi);i := 1;j := 1;while (i <= na) and (j <= nb) do beginif ai <= bj the nbegin write(a

13、i,''); in c(i);end else begi n write(bj,''); in c(j);en d;en d;if i <= na the nfor k := i to na do write(ak,'');if j <= nb the nfor k := j to nb do write(bk,''); en d.輸入51 3 5 7 942 6 10 14輸出：3.con stnum = 5;varn: in teger;fun cti on r(n : in teger) : in teger;v

14、ari : in teger;beginif n <= num the nbeginr := n;exit;en d;for i :=1 to num doif r(n-i) < 0 thenbeginr:=i;exit;en d;r:=-1;en d;beginread ln(n);write In (r( n);en d.輸入16輸出：4.con stsize=100;varn,m,x,y,i :in teger;r: array1. size of in teger;map : array1.size, 1.size of boolean; found : boolea n;

15、fun cti on successful : boolea n;vari : in teger;beginfor i :=1 to n doif not mapriri mod n + 1 the n beg insuccessful := false;exit;en d;successful :=true;en d;procedure swap(var a, b : in teger);vart : in teger;begint := a;a := b;b := t;en d;procedure perm(left, right : in teger);vari : in teger;b

16、eginif foundthe n exit;if left > rightthe n begi nif successful the n beg infor i := 1 to n do writel n( ri,''); found := true;en d;exit;en d;for i:= left to right dobegin swap(rleft, ri); perm(left + 1, right); swap(rleft, ri);en d;en d;beginreadl n(n, m);fillchar(map, sizeof(map), false

17、); for i := 1 to m dobegin read ln(x, y); mapxy := true; mapyx := true;en d;for i := 1 to n dori := i;found := false;perm(1, n);if not foundthe nwritel n( 'Nosoloutio n');en d.輸入:9 121 22 33 44 55 66 11 72 73 84 85 96 9輸出：五、完善程序1.(過河問題)在一個月黑風(fēng)高的夜晚，有一群人在河的右 岸,想通過唯一的一根獨木橋走到河的左岸.在伸手不見五指的黑夜里，過橋時必

18、須借照燈光來照明，不幸的是，他們只 有一盞燈.另外,獨木橋上最多能承受兩個人同時經(jīng)過，否則將會坍塌.每個人單獨過獨木橋都需要一定的時間，不同的人要的時間可能不同.兩個人一起過獨木橋時，由于只有一 盞燈，所以需要的時間是較慢的那個人單獨過橋所花費的時 間.現(xiàn)在輸入N(2v=N<1000)和這N個人單獨過橋需要的時間 請計算總共最少需要多少時間，他們才能全部到達河左岸.例如，有3個人甲、乙、丙，他們單獨過橋的時 間分別為124,則總共最少需要的時間為 7.具體方法是：甲乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶回，然后甲，丙在一起過橋到河的左岸，總時間為 2+1+4=7.con stSI

19、ZE = 100;INFINITY = 10000;LEFT = true;RIGHT = false;LEFT_TO_RIGHT = true; RIGHT_TO_LEFT = false;varn, i : in teger;time : array1.Size of in teger;pos :array1.Size of Boolea n;function max(a, b :integer) : integer;beginif a > b the nmax := aelsemax := b;en d;fun cti on go(stage : boolea n) : in te

20、ger;vari, j, num, tmp, ans : integer;beginif (stage = RIGHT_TO_LEFT) the n beg innum := 0;ans :=0;for i := 1 to n doif posi = Rignt the nbegininc(nu m);、單項選擇題(共 10題，每題1.5分，共計15分)12345678910CA A DBD CBCB、不定項選擇題(共10題,每題1.5分，共計15分，多選或少選均不得分)12345678910ACDAD ABDAC BBDD BCDABC三、問題求解(共3題，每題5分，共計 15 分)1.yy

21、xy xx yyxy xyx xx xyx2. 123. 18if timei > ans the nans := timei;en d;ifthe nbegingo := ans;exit;en d;ans := INFINITY;for i := 1 to n- 1 doif posi = RIGHT the nfor j := i+1 to n doif posj = RIGHT the n beginposi := LEFT; posj := LEFT;tmp := max(timei, timej) +;if tmp < ans the n ans := tmp; posi := RIGHT; posj := RIGHT;en d;go := ans;endelse if(stage = LEFT_TO_RIGHT)the n begi nans := INFINITY;for i := 1 to n doift