【正文】 it。 if then beginover := true。end。exit。if [i] [i] thenbeginover := true。end。over := false?！痓eginreadln(s)。 := 1ength(s)。filichar(, sizeof(), 0)。[i] := 1。repeatmiddle := average(1eft, right)。 until over(plustwo(1eft), right)。writeln。例如，對于序列113，下圖就是一棵對應(yīng)的笛卡爾樹。constSIZE = 100。 var n, maxDeep, num, i : integer。procedure solve(1eft, right, deep : integer)。begin if deep maxDeep then beginmaxDeep := deep。endelse if deep = maxDeep then___①___。for i := 1eft to right doif min a[i] thenbeginmin := a[i]。end。if j right then___④___。beginreadln(n)。maxDeep := 0。writeln(maxDeep, ‘ ’, num)。 ）個二進(jìn)制組成。 ）。 )。A. 100 B. 144 C. 164 D. 196“存儲程序”的計算機工作原理的是（ ）。A. 23 B. 25 C. 37 D. 65(CPU)的工作速度慢的多，從而使得后者的效率受到影響。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了( )。假定根結(jié)點存放在數(shù)組的1號位置上，則第k號結(jié)點的父結(jié)點如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的（ ）號位置。A. NOIP C. IOI D. APIO二、不定項選擇題、RRRR5入棧的順序為RRRRR5。 2. Pascal語言，C語言和C++語言都屬于( )。以下屬于原地排序的有( )。 4. 在整數(shù)的補碼表示法中，以下說法正確的是（ ）。 A．0 B. 2 C. 4 D. 66. 在下列HTML語句中，可以正確產(chǎn)生一個指向NOI官方網(wǎng)站的超鏈接的是（ ）。A．所有連通的有向圖都可以實現(xiàn)拓?fù)渑判駼．對同一個圖而言，拓?fù)渑判虻慕Y(jié)構(gòu)是唯一的C．拓?fù)渑判蛑腥攵葹?的結(jié)點總會排在入度大于0的結(jié)點的前面D．拓?fù)渑判蚪Y(jié)果序列中的第一個結(jié)點一定是入度大于0的點8. 一個平面的法線是指與該平面垂直的直線。A．過點（1，1，1）、（2，3，3）的直線 B．過點（1，1，1）、（3，2，1）的直線C．過點（0，3，0）、（3，1，1）的直線 D．過點（2，0，0）、（5，2，1）的直線，分別指向該結(jié)點的前驅(qū)及后繼?，F(xiàn)要求刪除結(jié)點p，則下列語句序列中正確的是(A．prlinkllink=prlink。 delete p。 prlinkllink = pllink。C．prlinkllink = pllink。 delete p。 pllinkrlinklink = pllink。10. 今年(2010年)發(fā)生的事件有（ ）。在編碼的過程中，開始時只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。初始詞典只有3個條目，第一個為x,編碼為1；第二個為y，編碼為2；第三個為空格，編碼為3；于是串“xyx”的編碼為121（其中為編碼分隔符），加上后面的一個空格就是1213。于是，最后得到編碼：1213223534。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對該序列的完全恢復(fù)?，F(xiàn)在已知初始詞典的3個條目如上述，接收端收到的編碼信息為22123113431213536，則解碼后的信息串是”____________”。，初始時為空，現(xiàn)有n個總和不超過32的正整數(shù)依次入列。四、閱讀程序?qū)懡Y(jié)果1.constvarbegin begin t := 0。 if (data[i] data[j]) or ((data[j] = data[i]) and (j i)) then inc(t)。 then writeln(data[i])。 end。 size = 100。 na, nb, i, j, k : integer。 a, b : array[1..size] of integer。 readln(na)。 for i := 1 to na do read(b[i])。 i := 1。 j := 1。 while (i = na) and (j = nb) do write(a[i],39。)。 inc(i)。 write(b[j], 39。)。 inc(j)。 write(a[k], 39。)。 if j = nb then for k := j to nb do 39。end.輸入51 3 5 7 94 2 6 10 14輸出：__________3.constvarfunction r(n : integer) : integer。 i : integer。 if n = num then exit。 end。 for i :=1 to num do if r(ni) 0 then begin r:=i。 end。 r:=1。beginend.輸入 16輸出：__________4.constvar n,m,x,y,i :integer。 map : array[1..size, 1..size] of boolean。function successful : boolean。begin for i :=1 to n do then begin successful :=true。procedure swap(var a, b : integer)。 t : integer。 t := a。 a := b。 b := t。procedure perm(left, right : integer)。 i : integer。 if found then exit。 if left right if successful 39。 found := true。 end。 exit。 end。 for i:= left to right do swap(r[left], r[i])。 perm(left + 1, right)。 swap(r[left], r[i])。 end。begin begin r[i] := i。 found := false。 perm(1, n)。 if not found then writeln(39。)。 例如,有3個人甲、乙、丙,他們單獨過橋的時間分別為1 2 4,:甲 乙一起過橋到河的左岸,甲單獨回到河的右岸將燈帶回,然后甲,丙在一起過橋到河的左岸,總時間為2+1+4=7.constSIZE = 100。 LEFT = true。 LEFT_TO_RIGHT = true。var n, i : integer。 pos :array[1..Size] of Boolean。beginif a b then max := a else max := b。function go(stage : boolean) : integer。begin if (stage = RIGHT_TO_LEFT) then begin inc(num)。 if time[i] ans thenend。 exit。ans := INFINITY。 if pos[i] = RIGHT then pos[i] := LEFT。 pos[j] := LEFT。 tmp := max(time[i], time[j]) + _______。 if tmp ans then end。endelse if (stage = LEFT_TO_RIGHT)then begin ans := INFINITY。 if _______ then tmp := ________。 _________。go := ans。end。 readln(n)。 for i := 1 to n do pos[i] := RIGHT。 end。end.第十五屆(2009)全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal語言 二小時完成 ）● ● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●● 一． 單項選擇題 （共10題，共計15分。）關(guān)于圖靈機下面的說法哪個是正確的：A) 圖靈機是世界上最早的電子計算機。C) 圖靈機只是一個理論上的計算模型。關(guān)于BIOS下面的說法哪個是正確的：A) BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。C) BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。已知大寫字母A的ASCII編碼為65（十進(jìn)制），則大寫字母J的 十六進(jìn)制 ASCII編碼為：A) 48 B) 49 C) 50 D) 以上都不是在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進(jìn)制補碼為1111111111101101。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。A)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001）快速排序平均情況和最壞情況下的算法時間復(fù)雜度分別為： A) 平均情況 O(nlog2n)，最壞情況O(n2)B) 平均情況 O(n)， 最壞情況O(n2)C) 平均情況 O(n)， 最壞情況O(nlog2n) D) 平均情況 O(log2n)， 最壞情況O(n2)左圖給出了一個加權(quán)無向圖，從頂點V0開始用prim算法求最小生成樹。每題正確答案的個數(shù)不少于1。關(guān)于CPU下面哪些說法是正確的：A) CPU全稱為中央處理器（或中央處理單元）。C) CPU最早是由Intel公司發(fā)明的。關(guān)于計算機內(nèi)存下面的說法哪些是正確的：A) 隨機存儲器（RAM）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。C) 計算機內(nèi)存嚴(yán)格說來包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。關(guān)于操作系統(tǒng)下面說法哪些是正確的：A. 多任務(wù)操作系統(tǒng)專用于多核心或多個CPU架構(gòu)的計算機系統(tǒng)的管理。C. 分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的：A) 網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。C) TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。關(guān)于HTML下面哪些說法是正確的：A) HTML全稱超文本標(biāo)記語言，實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。C) 網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實現(xiàn)。若3個頂點的無權(quán)圖G的鄰接矩陣用數(shù)組存儲為{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具體存儲中頂點依次為: v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的：A) 該圖是有向圖。C) 該圖所有頂點的入度之和減所有頂點的出度之和等于1。在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。下面哪些說法是正確的： A) 如果p指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為：p^.next:= clist^.next。 B) 如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為：p^.next:= clist。 C) 在頭部刪除一個結(jié)點的語句序列為：p:= clist^.next。 dispose(p)。p:= clist。 dispose(p)。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。B) 在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。D) 在提交的程序中啟動多個進(jìn)程以提高程序的執(zhí)行效率。如下的有向無環(huán)圖，對其頂點做拓?fù)渑判颍瑒t所有可能的拓?fù)湫蛄械膫€數(shù)