NOIP2005提高組初賽試題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第十一屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組pascal 語言二小時(shí)完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案.）。6. 下列設(shè)備中沒有計(jì)算功能的是（ ）。A. 筆記本電腦 B. 掌上電腦 C. 智能手機(jī)D. 電子計(jì)算器 E. 液晶顯示器7. Intel的首顆64 位處理器是（ ）。A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium8. 常見的郵件傳輸服務(wù)器使用（ ）協(xié)議發(fā)送郵件。A. HTTP B. SMTP C. TCP D

2、. FTP E. POP39. 不能在Linux 上使用的網(wǎng)頁瀏覽器是（ ）。A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla10. 一位藝術(shù)史學(xué)家有20000 幅1024 * 768 的真彩色圖像，如果將這些圖像以位圖形式保存在CD 光盤上（一張CD 光盤的容量按600M計(jì)算），大約需要（）張CD光盤。A. 1 B. 10 C. 100 D. 1000 E. 10000二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。多選或少選均不得分）。11. 設(shè)A = true，B = false，C = false，D =

3、 true，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。A. (AB)(CD) B. (AB)C)D C. A(BC)D)D. (A(BC)D E. (AB)(CD)12. (3725)8 + (B)16的運(yùn)算結(jié)果是（ ）。A. (3736)8 B. (2016)10 C. ()2 D. (3006)10 E. (7E0)1613. 二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點(diǎn)，D 是G 的父結(jié)點(diǎn)，F(xiàn) 是I 的父結(jié)點(diǎn)，樹中所有結(jié)點(diǎn)的最大深度為3（根結(jié)點(diǎn)深度設(shè)為0），可知E的父結(jié)點(diǎn)可能是（ ）。A. A B. B C. C D. D E. F14. 設(shè)棧S的初始狀態(tài)

4、為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, gD. d, c, f, e, b, a, g E. g, e, f, d, c, b, a15. 下列外設(shè)接口中可以通過無線連接的方式連接設(shè)備的是（ ）。A. USB 2.0 高速版 B. 紅外 C. 藍(lán)牙 D. 串口 E. IEEE 802.11g 無線網(wǎng)卡16. 處理器A 每秒處理的指令數(shù)是處理器B 的2 倍。某一特定程序P 分別編譯為處理器A和處理器B 的指令，編

5、譯結(jié)果處理器A 的_指令數(shù)是處理器B 的4 倍。已知程序P 的算法時(shí)間復(fù)雜度為O(n2)，如果處理器A執(zhí)行程序P時(shí)能在一小時(shí)內(nèi)完成的輸入規(guī)模為n，則處理器B執(zhí)行程序P時(shí)能在一小時(shí)內(nèi)完成的輸入規(guī)模為（ ）。A. 4 * n B. 2 * n C. n D. n / 2 E. n / 417. 以下哪個(gè)（些）不是計(jì)算機(jī)的輸出設(shè)備（ ）。A. 鼠標(biāo) B. 顯示器 C. 鍵盤 D. 掃描儀 E. 繪圖儀18. 以下斷電之后將不能保存數(shù)據(jù)的有（ ）。A. 硬盤 B. 寄存器 C. 顯存 D. 內(nèi)存 E. 高速緩存19. 下列活動(dòng)中屬于信息學(xué)奧賽系列活動(dòng)的是（ ）。A. NOIP B. NOI C. IO

6、I D. 冬令營 E. 國家隊(duì)選拔賽20. 下列關(guān)于高級語言的說法正確的有（ ）。A. Ada 是歷史上的第一個(gè)高級語言B. Pascal和C都是編譯執(zhí)行的高級語言C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮恼Z言D. 編譯器將高級語言程序轉(zhuǎn)變?yōu)槟繕?biāo)代碼E. 高級語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上三問題求解（請?jiān)诳崭裉幪钌洗鸢福靠?分，共計(jì)10分）1. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換次。 52. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1

7、 根或2 根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當(dāng)N 分別為100，200，300，400，500 時(shí)，先取者有無必勝策略的標(biāo)記順序?yàn)椋ɑ卮饝?yīng)為一個(gè)由0 和/或1 組成的字符串）。 11011四閱讀程序（共4題，每題8分，共計(jì)32 分）1vara, b, c, p, q : integer;r : array0.2 of integer;beginread(a, b, c);p := a div b div c;q := b - c + a + p;r0 := a * p div q * q;r1 := r0 * (r0 - 30

8、0);if (3 * q - p mod 3 <= r0) and (r2 = r2) thenr1 := rr0 div p mod 2else r1 := q mod p;writeln(r0 - r1);end.輸入：100 7 3輸出：-74522 vara : array 1.50 of integer;n, i, sum : integer;procedure work(p, r: integer);vari, j, temp : integer;beginif p < r then begini := p - 1;for j := p to r - 1 doif aj

9、 >= ar then begininc(i);temp := ai; ai := aj; aj := temp;end;temp := ai + 1; ai + 1 := ar; ar := temp;work(p, i);work(i + 2, r);end;end;beginread(n);for i := 1 to n do read(ai);work(1, n);for i := 1 to n - 1 do sum := sum + abs(ai + 1 - ai);writeln(sum);end.輸入：10 23 435 12 345 3123 43 456 12 32 -

10、100輸出：3 32233 varstr : string;len, i, j : integer;nchr : array 0.25 of integer;mmin : char;beginmmin := 'z'readln(str);len := length(str);i := len;while i >= 2 do beginif stri - 1 < stri then break;dec(i);end;if i = 1 then beginwriteln('No result!');exit;end;for j := 1 to i - 2

11、 do write(strj);fillchar(nchr, sizeof(nchr), 0);for j := i to len do beginif (strj > stri - 1) and (strj < mmin) thenmmin := strj;inc(nchrord(strj) - ord('a');end;dec(nchrord(mmin) - ord('a');inc(nchrord(stri - 1) - ord('a');write(mmin);for i := 0 to 25 dofor j := 1 to

12、nchri dowrite(chr(i + ord('a');writeln;end.輸入：zzyzcccbbbaaa輸出：zzzaaabbbcccy4. varn : longint;function g(k : longint) : longint;beginif k <= 1 then g := kelse g := (2002 * g(k - 1) + 2003 * g(k - 2) mod 2005;end;beginread(n);writeln(g(n);end.輸入：2005輸出：五完善程序(前5空，每空2分，后6空，每空3分，共28分)1木材加工題目描述

13、:木材廠有一些原木，現(xiàn)在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有剩余），需要得到的小段的數(shù)目是給定的。當(dāng)然，我們希望得到的小段越長越好，你的任務(wù)是計(jì)算能夠得到的小段木頭的最大長度。木頭長度的單位是cm。原木的長度都是正整數(shù)，我們要求切割得到的小段木頭的長度也是正整數(shù)。輸入:第一行是兩個(gè)正整數(shù)N和K(1 N 10000，1 K 10000)，N是原木的數(shù)目，K是需要得到的小段的數(shù)目。接下來的N行，每行有一個(gè)1到10000之間的正整數(shù)，表示一根原木的長度。輸出:輸出能夠切割得到的小段的最大長度。如果連1cm長的小段都切不出來，輸出”0”。輸入樣例:3 7232124456輸出樣例:1

14、14程序：var n, k : integer; len : array 1.10000 of integer; i, left, right, mid : integer;function isok(t : integer) : boolean;var num, i : integer;begin num := 0; for i := 1 to n do begin if num >= k then break; num := ; end; if then isok := true else isok := false;end;begin readln(n, k); right :=

15、0; for i := 1 to n do begin readln(leni); if right < leni then right := leni; end; inc(right); ; while < right do begin mid := (left + right) div 2; if then right := mid else left := mid; end; writeln(left);end.2N叉樹題目描述:我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當(dāng)知道先根遍歷的結(jié)果和中根遍歷結(jié)果的時(shí)候，我們可以唯一的確定二叉樹；同樣的，如果知道了后根遍歷的結(jié)果

16、和中根遍歷結(jié)果，二叉樹也是唯一確定的。但是如果只知道先根遍歷和后根遍歷的結(jié)果，二叉樹就不是唯一的了。但是我們可以計(jì)算滿足條件的不同二叉樹一共有多少個(gè)。這不是一個(gè)很困難的問題，稍微復(fù)雜一點(diǎn)，我們把這個(gè)問題推廣到N叉樹。我們用小寫英文字母來表示N 叉樹的結(jié)點(diǎn)，不同的結(jié)點(diǎn)用不同的字母表示。比如，對于4叉樹，如果先根遍歷的結(jié)果是abdefgc，后根遍歷的結(jié)果是defgbca，那么我們可以得到6個(gè)不同的4叉樹（如下圖）。輸入:輸入數(shù)據(jù)包括3行。第一行是一個(gè)正整數(shù)N(2 N 20)，表示我們要考慮N叉樹。第二行和第三行分別是兩個(gè)字符串序列，分別表示先根遍歷和后根遍歷的結(jié)果。輸出:輸出不同的N叉樹的數(shù)目。題

17、目中給的數(shù)據(jù)保證得到的結(jié)果小于231。輸入樣例:4abdefgcdefgbca輸出樣例:6程序：var str1, str2 : string; N, len : integer; com : array0.100, 0.100 of longint;function getcom(x, y : integer) : longint;begin if (y = 0) or (x = y) then else if comxy <> 0 then getcom := comxy else begin comxy := getcom(x - 1, y)+ ; getcom := com

18、xy; end;end;function count(a, b, c : integer) : longint;var sum : longint; k, s, t, p : integer;begin sum := 1; k := 0; s := a + 1; t := c; if a = b then count := 1 else begin while s <= b do begin p := t; while str1s <> str2t do inc(t); sum := sum * count(s, s + t - p, p); s := ; ; inc(k); end; count := * getcom(N, k); end;end;begin readln(N); readln(str1); readln(str2); len := length(str1); writeln(count( );end.第十一屆全國青少年信息學(xué)奧林匹