11高初試題及答案

1、第十七屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal語(yǔ)言 兩小時(shí)完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項(xiàng)選擇題（共20題，每題1.5分。共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。）1在二進(jìn)制下，1100011 +（ ）= 1110000。A1011B1101C1010 D11112字符“A”的ASCII碼為十六進(jìn)制41，則字符“Z”的ASCII碼為十六進(jìn)制的（ ）。A66 B5AC50 D視具體的計(jì)算機(jī)而定3右圖是一棵二叉樹，它的先序遍歷是（ ）。AABDEFC BDBEFACCDFEBCA DABCDEF4寄存器是（ ）的重要組成部分。A硬盤 B高

2、速緩存 C內(nèi)存D中央處理器（CPU）5廣度優(yōu)先搜索時(shí)，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。A鏈表 B隊(duì)列C棧D散列表6在使用高級(jí)語(yǔ)言編寫程序時(shí)，一般提到的“空間復(fù)雜度”中的“空間”是指（ ）。A程序運(yùn)行時(shí)理論上所占的內(nèi)存空間B程序運(yùn)行時(shí)理論上所占的數(shù)組空間C程序運(yùn)行時(shí)理論上所占的硬盤空間D程序源文件理論上所占的硬盤空間7應(yīng)用快速排序的分治思想，可以實(shí)現(xiàn)一個(gè)求第K大數(shù)的程序。假定不考慮極端的最壞情況，理論上可以實(shí)現(xiàn)的最低的算法時(shí)間復(fù)雜度為（ ）。 AO(n2)BO(n log n)CO(n)DO(1)8為解決Web應(yīng)用中的不兼容問題，保障信息的順利流通，（ ）制定了一系列標(biāo)準(zhǔn)，涉及HTML、XML、CS

3、S等，并建議開發(fā)者遵循。A微軟 B美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM） C聯(lián)臺(tái)國(guó)教科文組織D萬(wàn)維網(wǎng)聯(lián)盟（W3C）9體育課的鈴聲響了，同學(xué)們都陸續(xù)地奔向操場(chǎng)，按老師的要求從高到矮站成一排。每個(gè)同學(xué)按順序來到操場(chǎng)時(shí)，都從排尾走向排頭，找到第一個(gè)比自己高的同學(xué)，并站在他的后面。這種站隊(duì)的方法類似于（ ）算法。A快速排序B插入排序C冒泡排序D歸并排序101956年（ ）授予肖克利（William Shockley）、巴?。↗ohn Bardeen）和布拉頓（Walter Brattain)，以表彰他們對(duì)半導(dǎo)體的研究和晶體管效應(yīng)的發(fā)現(xiàn)。A諾貝爾物理學(xué)獎(jiǎng)B約翰馮諾依曼獎(jiǎng)C圖靈獎(jiǎng)D高德納獎(jiǎng)（Donald EKnuth

4、Prize）二、不定項(xiàng)選擇題（共10題，每題15分，共計(jì)15分。每題有一個(gè)或多個(gè)正確選項(xiàng)。多選或少選均不得分。）1如果根結(jié)點(diǎn)的深度記為1，則一棵恰有2011個(gè)葉子結(jié)點(diǎn)的二叉樹的深度可能是（ ）。A10B11C12 D20112在布爾邏輯中，邏輯“或”的性質(zhì)有（ ）。A交換律：P V Q = Q V P B結(jié)臺(tái)律：P V ( Q V R ) = ( P V Q ) V RC冪等律：P V P = P D有界律：P V 1 = 1 （1表示邏輯真）3一個(gè)正整數(shù)在十六進(jìn)制下有100位，則它在二進(jìn)制下可能有（ ）位。A399B400C401 D4044匯編語(yǔ)言（ ）。A是一種與具體硬件無關(guān)的程序設(shè)計(jì)語(yǔ)

5、言B在編寫復(fù)雜程序時(shí)，相對(duì)于高級(jí)語(yǔ)言而言代碼量較大，且不易調(diào)試C可以直接訪問寄存器、內(nèi)存單元、I/O端口D隨著高級(jí)語(yǔ)言的誕生，如今已完全被淘汰，不再使用5現(xiàn)有一段文言文，要通過二進(jìn)制哈夫曼編碼進(jìn)行壓縮。簡(jiǎn)單起見，假設(shè)這段文言文只由4個(gè)漢字“之”、“乎”、“者”、“也”組成，它們出現(xiàn)的次數(shù)分別為700、600、300、400。那么，“也”字的編碼長(zhǎng)度可能是（ ）。A1B2C3 D46生物特征識(shí)別，是利用人體本身的生物特征進(jìn)行身份認(rèn)證的一種技術(shù)。目前，指紋識(shí)別、虹膜識(shí)別、人臉識(shí)別等技術(shù)己廣泛應(yīng)用于政府、銀行、安全防衛(wèi)等領(lǐng)域。以下屬于生物特征識(shí)別技術(shù)及其應(yīng)用的是（ ）。A指靜脈驗(yàn)證B步態(tài)驗(yàn)證CATM

6、機(jī)密碼驗(yàn)證D聲音驗(yàn)證7對(duì)于序列“7、5、1、9、3、6、8、4”，在不改變順序的情況下，去掉（ ）會(huì)使逆序?qū)Φ膫€(gè)數(shù)減少3。A7B5C3 D68計(jì)算機(jī)中的數(shù)值信息分為整數(shù)和實(shí)數(shù)（浮點(diǎn)數(shù)）。實(shí)數(shù)之所以能表示很大或者很小的數(shù)，是由于使用了（ ）。A階碼B補(bǔ)碼C反碼D較長(zhǎng)的尾數(shù)9對(duì)右圖使用Dijkstra算法計(jì)算S點(diǎn)到其余各點(diǎn)的最短路徑長(zhǎng)度時(shí)，到B點(diǎn)的距離dB初始時(shí)賦為8，在算法的執(zhí)行過程中還會(huì)出現(xiàn)的值有（ ）。 A3B7C6 D510為計(jì)算機(jī)網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定的集合成為網(wǎng)絡(luò)協(xié)議。下列英文縮寫中，（ ）是網(wǎng)絡(luò)協(xié)議。AHTTPBTCP/IPCFTP DWWW三、問題求解（共2題，

7、每題5分，共計(jì)10分）1平面圖是可以畫在在平面上，且它的邊僅在頂點(diǎn)上才能相交的簡(jiǎn)單無向圖。4個(gè)頂點(diǎn)的平面圖至多有6條邊，如右圖所示。那么，5個(gè)頂點(diǎn)的平面圖至多有_條邊。2定義一種字符串操作，一次可以將其中一個(gè)元素移到任意位置。舉例說明，對(duì)于字符串”BcA”，可以將A移到B之前，變成字符串”ABC”。如果要將字符串”DACHEBGIF”變成”ABCDEFGHI”，最少需要_次操作。四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1ConstSIZE = 100;varn, i, sum, x : integer;a : array1.SIZE of integer;beginreadln(n)

8、;fillchar(a, sizeof(a), 0);for i:= 1 to n dobeginread(x);inc(ax);end;i := 0;sum := 0;while sum < (n div 2 + 1) dobegininc(i);sum :=sum + ai;end;writeln(i);end輸入：114 5 6 6 4 3 3 2 3 2 1輸出：2varn : integer;procedure f2(x, y : integer);forward;procedure f1(x, y : integer);beginif x < n thenf2(y, x

9、 + y);end;procedure f2(x, y : integer);beginwrite(x, );f1(y, x + y);end;beginreadln(n);f1(0, 1);end輸入：30輸出：_3constV = 100;varvisited : array1.v of boolean;e : array1.V, 1.V of integer;n, m, ans, i, j, a, b, c : integer; procedure dfs(x, len : integer);varI : integer;beginvisitedx := true;if len >

10、 ans thenans := len;for i := 1 to n doif (not visitedi) and (ex, i <> -1) thendfs(i, len + ex, i); visitedx := false;end;beginreadln(n, m);for i := 1 to n dofor j := 1 to n doeij := -1;for i := 1 to m dobeginreadln(a, b, c);eab := c;eba := c;end;for i := 1 to n dovisitedi := false;ans := 0;for

11、 i := 1 to n dodfs(i, 0);writeln(ans);end.輸入：4 61 2 102 3 203 4 304 1 401 3 502 4 60輸出：_4.constSIZE = 10000;LENGTH = 10;varsum : longint;n, m, i, j : integer;a : array1.SIZE, 1.LENGTH of integer;function h(u, v : integer) : integer;varans, i : integer;beginans := 0; for i := 1 to n doif aui <>

12、 avi theninc(ans); h := ans;end;beginreadln(n);filichar(a, sizeof(a), 0);m := 1;repeati := 1;while (i <= n) and (ami = 1) doinc(i);if i > n thenbreak;inc(m);ami :=1;for j := i + 1 to n doamj := am - 1j;until false;sum :=0;for i := 1 to m dofor j := 1 to m dosum := sum + h(i, j);writeln(sum);en

13、d.輸入：7輸出：_五、完善程序（第1題，每空2分，第2題，每空3分，共計(jì)28分）1. （大整數(shù)開方）輸入一個(gè)正整數(shù)n（1n<10100），試用二分法計(jì)算它的平方根的整數(shù)部分。constSIZE = 200;type hugeint = recordlen : integer;num : array1.SIZE of integer;end;/len表示大整數(shù)的位數(shù)；num1表示個(gè)位、num2表示十位，以此類推vars : string;i : integer;target, left, middle, right : hugeint;function times(a, b : huge

14、int) : hugeint:var i, j : integer; ans : hugeint;beginfilIchar(ans, sizeof(ans), 0);for i := 1 to a.1en dofor j := 1 to b.1en do_ := ans.numi + j 1 + a.numi * b.numj;for i := 1 to a.len + b.1en dobeginans.numi + 1 := ans.numi + 1 + ans.numi div 10;_;if ans.numa.1en + b.1en > 0then ans.len := a.1e

15、n + b.1enelse ans.len :=a.1en + b.1en 1;end;times := ans;end;function add(a, b : hugeint) : hugeint;vari : integer;ans : hugeint;beginfillchar(ans.num, sizeof(ans.num), 0);if a.1en > b.1enthen ans.len := a.1enelse ans.len := b.len;for i := 1 to ans.1en dobeginans.numi :=_;ans.numi + 1 := ans.numi

16、 + 1 + ans.numi div 10;ans.numi := ans.numi mod 10;end;if ans.numans.1en + 1 > 0then inc(ans.len);add:=ans;end;function average(a, b : hugeint) : hugeint;vari : integer;ans : hugeint;beginans := add(a, b);for i := ans.1en downto 2 dobeginans.numi - 1 := ans.numi - 1 + (_) * 10;ans.numi := ans.num

17、i div 2;end;ans.numi := ans.numi div 2;if ans.numans.len = 0 then dec(ans.len);average := ans;end;function plustwo(a : hugeint) : hugeint;vari : integer;ans : hugeint;beginans := a;ans.num1 := ans.num1 + 2;i := 1;while(i <= ans.len) and (ans.numi >= 10) do beginans.numi + 1 := ans.numi + 1 + a

18、ns.numi div 10;ans.numi := ans.numi mod 10;inc(i);end;if ans.numans.len + 1 > 0then_; plustwo := ans;end;function over(a, b : hugeint) : boolean;var i : integer;begin if(_)then beginover := false;exit; end; if a.1en > b.1en then beginover := true;exit;end;for i := a.len downto 1 dobeginif a.nu

19、mi < b.numi thenbeginover := false;exit;end;if a.numi > b.numi thenbeginover := true;exit;end;end;over := false;end;beginreadln(s);fillchar(target.num, sizeof(target.num), 0);target.1en := 1ength(s);for i := 1 to target.1en dotarget.numi := ord(starget.1en i + 1) - _;filichar(left.num, sizeof(

20、1eft.num), 0);left.1en := 1;left.numi := 1;right := target;repeatmiddle := average(1eft, right);if over(_)then right := middleelse 1eft := middle; until over(plustwo(1eft), right); for i := left.1en downto 1 dowrite(1eft.numi);writeln;end.2. （笛卡爾樹）對(duì)于一個(gè)給定的兩兩不等的正整數(shù)序列，笛卡爾樹是這樣的一棵二叉樹：首先，它是一個(gè)最小堆，即除了根結(jié)點(diǎn)外，每

21、個(gè)結(jié)點(diǎn)的權(quán)值都大于父節(jié)點(diǎn)的權(quán)值；其次，它的中序遍歷恰好就是給定的序列。例如，對(duì)于序列7、2、12、1、10、5、15、3，下圖就是一棵對(duì)應(yīng)的笛卡爾樹。現(xiàn)輸入序列的規(guī)模n（1n<100）和序列的n個(gè)元素，試求其對(duì)應(yīng)的笛號(hào)爾樹的深度d(根節(jié)點(diǎn)深度為1)，以及有多少個(gè)葉節(jié)點(diǎn)的深度為d。constSIZE = 100;INFINITY = 1000000; var n, maxDeep, num, i : integer; a : array1.SIZE of integer;procedure solve(1eft, right, deep : integer);var i, j, min : integer;begin if deep > maxDeep then beginmaxDeep := deep;num := 1;endelse if deep = maxDeep then_;min := INFINITY;for i := 1eft to right doif min > ai thenbeginmin := ai;_;end;if left < j then_;if j < right then_;end;beginreadln(n);for i := 1 to n dorea