1、第十三屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（提高組Pal語言二小時(shí)完成）●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案.）。1.在以下各項(xiàng)中。（）不是CPU的組成部分。A.控制器B.運(yùn)算器C.寄存器D.主板E.算術(shù)邏輯單元(ALU)2.在關(guān)系數(shù)據(jù)庫(kù)中存放在數(shù)據(jù)庫(kù)中的數(shù)據(jù)的邏輯結(jié)構(gòu)以()為主。A.二叉樹B.多叉樹C.哈希表D.B樹E.二維表3.在下

2、列各項(xiàng)中，只有（）不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。A.ByteB.KBC.MBD.UBE.TB4II碼的含義是（）。A.二—十進(jìn)制轉(zhuǎn)換碼B.美國(guó)信息交換標(biāo)準(zhǔn)代碼C.數(shù)字的二進(jìn)制數(shù)碼D.計(jì)算機(jī)可處理字符的唯一編碼E.常用字符的二進(jìn)制編碼5在Pal語言中，表達(dá)式(232x5)的值是（）A.18B.1C.23D.32E.246在Pal語言中，判斷整數(shù)a等于0或b等于0或c等于0的正確的條件表達(dá)式是（）A.not((a0)(c0)(b0))C.n

3、ot((a=0)(b=0))(c=0)D.(a=0)(b=0)(c=0)E.not((a=0)(b=0)(c=0))7.地面上有標(biāo)號(hào)為A、B、C的3根細(xì)柱在A柱上放有10個(gè)直徑相同中間有孔的圓盤從上到下次依次編號(hào)為123……，將A柱上的部分盤子經(jīng)過B柱移入C柱也可以在B柱上暫存。如果B柱上的操作記錄為：“進(jìn)，進(jìn)，出，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，出，進(jìn)，出，出”。那么在C柱上從下到上的盤子的編號(hào)為（）。A.243657B.241257C.24

4、3176D.243675E.2143758.與十進(jìn)制數(shù)17.5625相對(duì)應(yīng)的8進(jìn)制數(shù)是（）。A.21.5625B.21.44C.21.73D.21.731E.前4個(gè)答案都不對(duì)9.歐拉圖G是指可以構(gòu)成一個(gè)閉回路的圖，且圖G的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆畫成）。在以下各個(gè)描述中不一定是歐拉圖的是：（）。A.圖G中沒有度為奇數(shù)的頂點(diǎn)B.與用高級(jí)語言編寫的數(shù)據(jù)處理系統(tǒng)相比，用關(guān)系數(shù)據(jù)庫(kù)編寫的系統(tǒng)更容易消除冗余數(shù)據(jù)C.為了提高查詢效

5、率，在數(shù)據(jù)庫(kù)中可以適當(dāng)保留一些冗余數(shù)據(jù)，但更新時(shí)要做相容性檢驗(yàn)D.做相容性檢驗(yàn)會(huì)降低效率，可以不理睬數(shù)據(jù)庫(kù)中的冗余數(shù)據(jù)16.在下列各軟件中，屬于NOIP競(jìng)賽（復(fù)賽）推薦使用的語言環(huán)境有（）。A.gccB.gC.TurboCD.freepal17.以下斷電之后將仍能保存數(shù)據(jù)的有（）。A.硬盤B.ROMC.顯存D.RAM18.在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（）。A.高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高B.隨著Pal

6、、C等高級(jí)語言的出現(xiàn)，機(jī)器語言和匯編語言已經(jīng)退出了歷史舞臺(tái)C.高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上D.C是一種面向過程的高級(jí)計(jì)算機(jī)語言19.在下列關(guān)于算法復(fù)雜性的說法中，正確的有（）。A.算法的時(shí)間復(fù)雜度，是指它在某臺(tái)計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間B.算法的時(shí)間復(fù)雜度，是指對(duì)于該算法的一種或幾種主要的運(yùn)算，運(yùn)算的次數(shù)與問題的規(guī)模之間的函數(shù)關(guān)系C.一個(gè)問題如果是NPC類的，就意味著在解決該問題時(shí)，不存在一個(gè)具有多

7、項(xiàng)式時(shí)間復(fù)雜度的算法.但這一點(diǎn)還沒有得到理論上證實(shí)，也沒有被否定D.一個(gè)問題如果是NP類的，與C有相同的結(jié)論由收集20.近20年來，許多計(jì)算機(jī)專家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問題的強(qiáng)有力的工具.在下列關(guān)于遞歸的說法中，正確的是（）。A.在1977年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級(jí)語言“FTRAN77“禁止在程序使用遞歸，原因之一是該方法可能會(huì)占用更多的內(nèi)存空間.B.和非遞歸算法相比，解決同一個(gè)問題，遞歸算法一般運(yùn)行得更快一些C.對(duì)于較

8、復(fù)雜的問題，用遞歸方式編程往往比非遞歸方式更容易一些D.對(duì)于已定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)sin(x)，應(yīng)用程序中的語句“y=sin(sin(x))”就是一種遞歸調(diào)用三問題求解（共2題，每題5分，共計(jì)10分）1給定n個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為1，2，…，n。將這n個(gè)球放入r個(gè)相同的盒子里，不允許有空盒，其不同放置方法的總數(shù)記為S(nr)。例如，S(42)=7，這7種不同的放置方法依次為(1)(234)(2)(134)(3)(124)(4)(123