NOIP2015提高組Pascal試題及參考答案

1、第二十一屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組Pascal語(yǔ)言試題競(jìng)賽時(shí)間：2015年10月11日14:3016:30選手注意：試題紙共有9頁(yè)，答題紙共有2頁(yè)，滿分100分。請(qǐng)?jiān)诖痤}紙上作答，寫在試題紙上的一律無(wú)效。不得使用任何電子設(shè)備（如計(jì)算器、手機(jī)、電子詞典等）或查閱任何書籍資料。一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分；每題有且僅有一個(gè)正確選項(xiàng)）1. 在計(jì)算機(jī)內(nèi)部用來(lái)傳送、存貯、加工處理的數(shù)據(jù)或指令都是以（ ）形式進(jìn)行的。A. 二進(jìn)制碼 B. 八進(jìn)制碼 C. 十進(jìn)制碼 D. 智能拼音碼2. 下列說(shuō)法正確的是（ ）。A. CPU的主要任務(wù)是執(zhí)行數(shù)據(jù)運(yùn)算和程序控制B. 存儲(chǔ)器

2、具有記憶能力，其中信息任何時(shí)候都不會(huì)丟失C. 兩個(gè)顯示器屏幕尺寸相同，則它們的分辨率必定相同D. 個(gè)人用戶只能使用Wifi的方式連接到Internet3. 與二進(jìn)制小數(shù)0.1相等的十六進(jìn)制數(shù)是（ ）。A. 0.8 B. 0.4 C. 0.2 D. 0.14. 下面有四個(gè)數(shù)據(jù)組，每個(gè)組各有三個(gè)數(shù)據(jù)，其中第一個(gè)數(shù)據(jù)為八進(jìn)制數(shù)，第二個(gè)數(shù)據(jù)為十進(jìn)制數(shù)，第三個(gè)數(shù)據(jù)為十六進(jìn)制數(shù)。這四個(gè)數(shù)據(jù)組中三個(gè)數(shù)據(jù)相同的是（ ）。A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F25. 線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元地址（ ）。A. 必須連

3、續(xù) B. 部分地址必須連續(xù)C. 一定不連續(xù) D. 連續(xù)不連續(xù)均可6. 今有一空棧S，對(duì)下列待進(jìn)棧的數(shù)據(jù)元素序列a,b,c,d,e,f依次進(jìn)行進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，進(jìn)棧，出棧的操作，則此操作完成后，棧S的棧頂元素為（ ）。A. f B. c C. a D. b7. 前序遍歷序列與后序遍歷序列相同的二叉樹為（ ）。A. 非葉子結(jié)點(diǎn)只有左子樹的二叉樹 B. 只有根結(jié)點(diǎn)的二叉樹C. 根結(jié)點(diǎn)無(wú)右子樹的二叉樹 D. 非葉子結(jié)點(diǎn)只有右子樹的二叉樹8. 如果根的高度為1，具有61個(gè)結(jié)點(diǎn)的完全二叉樹的高度為（ ）。A. 5 B. 6 C. 7 D. 89. 6個(gè)頂點(diǎn)的連通圖的最小生成樹，其邊數(shù)為（ ）。A.

4、6 B. 5 C. 7 D. 410. 設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T(n) = T(n - 1) + n（n為正整數(shù)）及T(0) = 1，則該算法的時(shí)間復(fù)雜度為（ ）。A. O(log n) B. O(nlogn) C. O(n) D. O(n2)11. 具有n個(gè)頂點(diǎn)，e條邊的圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運(yùn)算的時(shí)間復(fù)雜度均為（ ）。A. (n2) B. (e2) C. (ne) D. (n+e)12. 在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼（Huffman）算法是一種采用了（ ）思想的算法。A. 貪心 B. 分冶 C. 遞推 D. 回溯13. 雙向鏈表中有兩個(gè)指針域，l

5、link和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ）。A. p.llink := q; q.rlink := p;p.llink.rlink := q; q.llink := p.llink;B. q.llink := p.llink; p.llink.rlink := q;q.rlink := p; p.llink := q.rlink;C. q.rlink := p; p.rlink := q;p.llink.rlink := q; q.rlink := p;D. p.llink.rlink := q; q.rli

6、nk := p;q.llink := p.llink; p.llink := q;14. 對(duì)圖G中各個(gè)結(jié)點(diǎn)分別指定一種顏色，使相鄰結(jié)點(diǎn)顏色不同，則稱為圖G的一個(gè)正常著色。正常著色圖G所必需的最少顏色數(shù)，稱為G的色數(shù)。那么下圖的色數(shù)是（ ）。 A. 3 B. 4 C. 5 D. 615. 在NOI系列賽事中參賽選手必須使用由承辦單位統(tǒng)一提供的設(shè)備。下列物品中不允許選手自帶的是（ ）。A. 鼠標(biāo) B. 筆 C. 身份證 D. 準(zhǔn)考證二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，多選或少選均不得分）1. 以下屬于操作系統(tǒng)的有（ ）。A. Windows XP B.

7、UNIX C. Linux D. Mac OS2. 下列屬于視頻文件格式的有（ ）。A. AVI B. MPEG C. WMV D. JPEG3. 下列選項(xiàng)不是正確的IP地址的有（ ）。A. 202.300.12.4 B. 192.168.0.3 C. 100:128:35:91 D. 111-127-35-214. 下列有關(guān)樹的敘述中，敘述正確的有（ ）。A. 在含有n個(gè)結(jié)點(diǎn)的樹中，邊數(shù)只能是(n-1)條B. 在哈夫曼樹中，葉結(jié)點(diǎn)的個(gè)數(shù)比非葉結(jié)點(diǎn)個(gè)數(shù)多1C. 完全二叉樹一定是滿二叉樹D. 在二叉樹的前序序列中，若結(jié)點(diǎn)u在結(jié)點(diǎn)v之前，則u一定是v的祖先5. 以下圖中一定可以進(jìn)行黑白染色的有（

8、）。（黑白染色：為各個(gè)結(jié)點(diǎn)分別指定黑白兩種顏色之一，使相鄰結(jié)點(diǎn)顏色不同。）A. 二分圖 B. 完全圖 C. 樹 D. 連通圖三、問(wèn)題求解（共2題，每題5分，共計(jì)10分；每題全部答對(duì)得5分，沒有部分分）1. 在1和2015之間（包括1和2015在內(nèi)）不能被4、5、6三個(gè)數(shù)任意一個(gè)數(shù)整除的數(shù)有_個(gè)。2. 結(jié)點(diǎn)數(shù)為5的不同形態(tài)的二叉樹一共有_種。（結(jié)點(diǎn)數(shù)為2的二叉樹一共有2種：一種是根結(jié)點(diǎn)和左兒子，另一種是根結(jié)點(diǎn)和右兒子。）四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1. typepoint = recordx: longint;y: longint;end;EX = recorda: lon

9、gint;b: longint;c: point;end;vare: EX;begine.a := 1;e.b := 2;e.c.x := e.a + e.b;e.c.y := e.a * e.b;writeln(e.c.x, ',', e.c.y);end.輸出：_2. typep_char = char;varc1, c2: char;p1, p2: p_char;procedure fun(a, b: p_char);begina := b;inc(a);end;beginc1 := 'A'c2 := 'a'p1 := c1;p2 := c

10、2;fun(p1,p2);writeln(c1, c2);end.輸出：_3. varlen, maxlen: longint;s, ss: string;beginmaxlen := 0;while true dobeginreadln(ss);len := length(ss);if ss1 = '#' then break;if len > maxlen thenbegins := ss;maxlen := len;end;end;writeln(s);end.輸入：IamacitizenofChina#輸出：_4. varn: longint;function f

11、un(n, fromPos, toPos: longint): longint;vart, tot: longint;beginif n = 0 then exit(0);for t := 1 to 3 doif (t <> fromPos) and (t <> toPos) then break;tot := 0;inc(tot, fun(n - 1, fromPos, t);inc(tot);inc(tot, fun(n - 1, t, toPos);exit(tot);end;beginread(n);writeln(fun(n, 1, 3);end.輸入：5輸出

12、：_五、完善程序（共2題，每題14分，共計(jì)28分）1. （雙子序列最大和）給定一個(gè)長(zhǎng)度為n（3 n 1000）的整數(shù)序列，要求從中選出兩個(gè)連續(xù)子序列，使得這兩個(gè)連續(xù)子序列的序列和之和最大，最終只需輸出這個(gè)最大和。一個(gè)連續(xù)子序列的序列和為該連續(xù)子序列中所有數(shù)之和。要求：每個(gè)連續(xù)子序列長(zhǎng)度至少為1，且兩個(gè)連續(xù)子序列之間至少間隔1個(gè)數(shù)。（第五空4分，其余2.5分）Const MAXN = 1000;varn, i, ans, sum: longint;x: array 1.MAXN of longint;lmax: array 1.MAXN of longint;/ lmaxi為僅含xi及xi左側(cè)整

13、數(shù)的連續(xù)子序列的序列和中，最大的序列和 rmax: array 1.MAXN of longint;/ rmaxi為僅含xi及xi右側(cè)整數(shù)的連續(xù)子序列的序列和中，最大的序列和beginread(n);for i := 1 to n do read(xi);lmax1 := x1;for i := 2 to n doif lmaxi - 1 <= 0 then lmaxi := xielse lmaxi := lmaxi - 1 + xi;for i := 2 to n doif lmaxi < lmaxi - 1 then lmaxi := lmaxi - 1; (1) ;for

14、i := n - 1 downto 1 doif rmaxi + 1 <= 0 then (2) else (3) ;for i := n - 1 downto 1 doif rmaxi < rmaxi + 1 then (4) ;ans := x1 + x3;for i := 2 to n - 1 dobeginsum:= (5) ;if sum > ans then ans := sum;end;writeln(ans);end.2. （最短路徑問(wèn)題）無(wú)向連通圖G有n個(gè)結(jié)點(diǎn)，依次編號(hào)為1,2,3,.,n。用鄰接矩陣的形式給出每條邊的邊長(zhǎng)，要求輸出以結(jié)點(diǎn)1為起點(diǎn)出發(fā)，到各結(jié)

15、點(diǎn)的最短路徑長(zhǎng)度。 使用Dijkstra算法解決該問(wèn)題：利用dist數(shù)組記錄當(dāng)前各結(jié)點(diǎn)與起點(diǎn)的已找到的最短路徑長(zhǎng)度；每次從未擴(kuò)展的結(jié)點(diǎn)中選取dist值最小的結(jié)點(diǎn)v進(jìn)行擴(kuò)展，更新與v相鄰的結(jié)點(diǎn)的dist值；不斷進(jìn)行上述操作直至所有結(jié)點(diǎn)均被擴(kuò)展，此時(shí)dist數(shù)據(jù)中記錄的值即為各結(jié)點(diǎn)與起點(diǎn)的最短路徑長(zhǎng)度。（第五空2分，其余3分）Const MAXV = 100;varn, i, j, v: longint;w: array 1.MAXV, 1.MAXV of longint;/ 鄰接矩陣，記錄邊長(zhǎng)/ 其中wi, j為連接結(jié)點(diǎn)i和結(jié)點(diǎn)j的無(wú)向邊長(zhǎng)度，若無(wú)邊則為-1dist: array 1.MAXV

16、of longint;used: array 1.MAXV of longint;/ 記錄結(jié)點(diǎn)是否已擴(kuò)展（0：未擴(kuò)展；1：已擴(kuò)展）beginread(n);for i := 1 to n dofor j := 1 to n do read(wi, j);dist1 := 0;for i := 2 to n do disti := -1;for i := 1 to n do usedi := 0;while true dobegin (1) ; for i := 1 to n doif (usedi <> 1) and (disti <> -1) and (v=-1) o

17、r ( (2) ) then (3) ;if v = -1 then break; (4) ;for i := 1 to n doif (wv, i <> -1) and (disti = -1) or ( (5) ) then disti := distv + wv, i;end;for i := 1 to n do writeln(disti);end.第二十一屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組參考答案一、單項(xiàng)選擇題（共15題，每題1.5分，共計(jì)22.5分）12345678AAADDBBB9101112131415BDDADAA二、不定項(xiàng)選擇題（共5題，每題1.5分，共計(jì)

18、7.5分；每題有一個(gè)或多個(gè)正確選項(xiàng)，沒有部分分）12345ABCDABCACDABAC三、問(wèn)題求解（共2題，每題5分，共計(jì)10分；每題全部答對(duì)得5分，沒有部分分）1、10752、42四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1、3，22、Ab3、citizen4、31五、完善程序（共計(jì)28分，以下程序填空可能還有一些等價(jià)的寫法，由各省賽區(qū)組織本省專家審定及上機(jī)驗(yàn)證，可以不上報(bào)CCF NOI科學(xué)委員會(huì)復(fù)核）Pascal語(yǔ)言C+語(yǔ)言C語(yǔ)言分值1（1）Rmaxn:=xnRmaxn-1=xn-12.5（2）Rmaxi:=xiRmaxi=xi2.5（3）Rmaxi:=rmaxi+1+xiRmaxi=rmaxi+1+xi2.5（4）Ramxi:=rmaxi+1Rmaxi=rmaxi+12.5（5）Lmaxi-1+rmaxi+142（