1999年至歷年信息學(xué)奧賽提高組初賽試題(編輯修改稿)

　

【文章內(nèi)容簡(jiǎn)介】 of boolean。 found : boolean。function successful : boolean。var i : integer。begin for i :=1 to n do if not map[r[i]][r[i mod n + 1]] then begin successful := false。 exit。 end。 successful :=true。end。procedure swap(var a, b : integer)。var t : integer。begin t := a。 a := b。 b := t。end。procedure perm(left, right : integer)。var i : integer。begin if found then exit。 if left right then begin if successful then begin for i := 1 to n do writeln(r[i], 39。 39。)。 found := true。 end。 exit。 end。 for i:= left to right do begin swap(r[left], r[i])。 perm(left + 1, right)。 swap(r[left], r[i])。 end。end。begin readln(n, m)。 fillchar(map, sizeof(map), false)。 for i := 1 to m do begin readln(x, y)。 map[x][y] := true。 map[y][x] := true。 end。 for i := 1 to n do r[i] := i。 found := false。 perm(1, n)。 if not found then writeln(39。No soloution39。)。end.輸入:9 121 22 33 44 55 66 11 72 73 84 85 96 9輸出：__________五、完善程序1.(過(guò)河問(wèn)題) 在一個(gè)月黑風(fēng)高的夜晚,有一群人在河的右岸,過(guò)橋時(shí)必須借照燈光來(lái)照明,不幸的是,獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過(guò),由于只有一盞燈,(2=N1000)和這N個(gè)人單獨(dú)過(guò)橋需要的時(shí)間,請(qǐng)計(jì)算總共最少需要多少時(shí)間,他們才能全部到達(dá)河左岸. 例如,有3個(gè)人甲、乙、丙,他們單獨(dú)過(guò)橋的時(shí)間分別為1 2 4,:甲 乙一起過(guò)橋到河的左岸,甲單獨(dú)回到河的右岸將燈帶回,然后甲,丙在一起過(guò)橋到河的左岸,總時(shí)間為2+1+4=7.constSIZE = 100。 INFINITY = 10000。 LEFT = true。 RIGHT = false。 LEFT_TO_RIGHT = true。 RIGHT_TO_LEFT = false。var n, i : integer。 time : array[1..Size] of integer。 pos :array[1..Size] of Boolean。function max(a, b :integer) : integer。beginif a b then max := a else max := b。end。function go(stage : boolean) : integer。var i, j, num, tmp, ans : integer。begin if (stage = RIGHT_TO_LEFT) then begin num := 0。 ans :=0。 for i := 1 to n do if pos[i] = Rignt then begin inc(num)。 if time[i] ans then ans := time[i]。end。if __________ thenbegin go := ans。 exit。end。ans := INFINITY。for i := 1 to n – 1 do if pos[i] = RIGHT then for j := i+1 to n do if pos[j] = RIGHT then begin pos[i] := LEFT。 pos[j] := LEFT。 tmp := max(time[i], time[j]) + _______。 if tmp ans then ans := tmp。 pos[i] := RIGHT。 pos[j] := RIGHT。 end。go := ans。endelse if (stage = LEFT_TO_RIGHT)then begin ans := INFINITY。 for i := 1 to n do if _______ then begin pos[i] := RIGHT。 tmp := ________。 if tmp ans then ans := tmp。 _________。 end。go := ans。 end else go := 0。end。begin readln(n)。 for i := 1 to n do begin read(time[i])。 pos[i] := RIGHT。 end。writeln(go(RIGHT_TO_LEFT))。end.第十五屆(2009)全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal語(yǔ)言 二小時(shí)完成 ）● ● 全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效 ●● 一． 單項(xiàng)選擇題 （共10題，共計(jì)15分。每題有且僅有一個(gè)正確答案。）關(guān)于圖靈機(jī)下面的說(shuō)法哪個(gè)是正確的：A) 圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。B) 由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。C) 圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。D) 圖靈機(jī)是英國(guó)人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。關(guān)于BIOS下面的說(shuō)法哪個(gè)是正確的：A) BIOS是計(jì)算機(jī)基本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱(chēng)。B) BIOS里包含了鍵盤(pán)、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C) BIOS一般由操作系統(tǒng)廠商來(lái)開(kāi)發(fā)完成。D) BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。已知大寫(xiě)字母A的ASCII編碼為65（十進(jìn)制），則大寫(xiě)字母J的 十六進(jìn)制 ASCII編碼為：A) 48 B) 49 C) 50 D) 以上都不是在字長(zhǎng)為16位的系統(tǒng)環(huán)境下，一個(gè)16位帶符號(hào)整數(shù)的二進(jìn)制補(bǔ)碼為1111111111101101。其對(duì)應(yīng)的十進(jìn)制整數(shù)應(yīng)該是：A) 19 B) 19 C) 18 D) 18一個(gè)包含n個(gè)分支結(jié)點(diǎn)（非葉結(jié)點(diǎn)）的非空滿k叉樹(shù)，k=1，它的葉結(jié)點(diǎn)數(shù)目為：A) nk + 1 B) nk1 C) (k+1)n1 D. (k1)n+1 6. 表達(dá)式a*(b+c)d的后綴表達(dá)式是：A) abcd*+ B) abc+*d C) abc*+d D) +*abcd最優(yōu)前綴編碼，也稱(chēng)Huffman編碼。這種編碼組合的特點(diǎn)是對(duì)于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。A)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001）快速排序平均情況和最壞情況下的算法時(shí)間復(fù)雜度分別為： A) 平均情況 O(nlog2n)，最壞情況O(n2)B) 平均情況 O(n)， 最壞情況O(n2)C) 平均情況 O(n)， 最壞情況O(nlog2n) D) 平均情況 O(log2n)， 最壞情況O(n2)左圖給出了一個(gè)加權(quán)無(wú)向圖，從頂點(diǎn)V0開(kāi)始用prim算法求最小生成樹(shù)。則依次加入最小生成樹(shù)的頂點(diǎn)集合的頂點(diǎn)序列為：A) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V5全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A) B) C) D) 二． 不定項(xiàng)選擇題 （共10題，共計(jì)15分。每題正確答案的個(gè)數(shù)不少于1。多選或少選均不得分）。關(guān)于CPU下面哪些說(shuō)法是正確的：A) CPU全稱(chēng)為中央處理器（或中央處理單元）。B) CPU能直接運(yùn)行機(jī)器語(yǔ)言。C) CPU最早是由Intel公司發(fā)明的。D) 同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。關(guān)于計(jì)算機(jī)內(nèi)存下面的說(shuō)法哪些是正確的：A) 隨機(jī)存儲(chǔ)器（RAM）的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。B) 一般的個(gè)人計(jì)算機(jī)在同一時(shí)刻只能存/取一個(gè)特定的內(nèi)存單元。C) 計(jì)算機(jī)內(nèi)存嚴(yán)格說(shuō)來(lái)包括主存（memory）、高速緩存（cache）和寄存器（register）三個(gè)部分。D) 1MB內(nèi)存通