NOIP2005提高組初賽試題答案

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

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

3、 true，以下邏輯運算表達式值為真的有（ ）。A. (AB)(CD) B. (AB)C)D C. A(BC)D)D. (A(BC)D E. (AB)(CD)12. (3725)8 + (B)16的運算結果是（ ）。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的父結點，D 是G 的父結點，F(xiàn) 是I 的父結點，樹中所有結點的最大深度為3（根結點深度設為0），可知E的父結點可能是（ ）。A. A B. B C. C D. D E. F14. 設棧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. 下列外設接口中可以通過無線連接的方式連接設備的是（ ）。A. USB 2.0 高速版 B. 紅外 C. 藍牙 D. 串口 E. IEEE 802.11g 無線網卡16. 處理器A 每秒處理的指令數(shù)是處理器B 的2 倍。某一特定程序P 分別編譯為處理器A和處理器B 的指令，編

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

6、I D. 冬令營 E. 國家隊選拔賽20. 下列關于高級語言的說法正確的有（ ）。A. Ada 是歷史上的第一個高級語言B. Pascal和C都是編譯執(zhí)行的高級語言C. C+是歷史上的第一個支持面向對象的語言D. 編譯器將高級語言程序轉變?yōu)槟繕舜aE. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上三問題求解（請在空格處填上答案，每空5分，共計10分）1. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換次。 52. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1

7、 根或2 根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝策略記為0。當N 分別為100，200，300，400，500 時，先取者有無必勝策略的標記順序為（回答應為一個由0 和/或1 組成的字符串）。 11011四閱讀程序（共4題，每題8分，共計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ù)目是給定的。當然，我們希望得到的小段越長越好，你的任務是計算能夠得到的小段木頭的最大長度。木頭長度的單位是cm。原木的長度都是正整數(shù)，我們要求切割得到的小段木頭的長度也是正整數(shù)。輸入:第一行是兩個正整數(shù)N和K(1 N 10000，1 K 10000)，N是原木的數(shù)目，K是需要得到的小段的數(shù)目。接下來的N行，每行有一個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叉樹題目描述:我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當知道先根遍歷的結果和中根遍歷結果的時候，我們可以唯一的確定二叉樹；同樣的，如果知道了后根遍歷的結果

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

17、目中給的數(shù)據保證得到的結果小于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.第十一屆全國青少年信息學奧林匹