提高組初賽試題及答案

1、第十一屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組pascal 語言二小時完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項選擇題（共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。1. 字符串“ababacbab”和字符串“abcba”的最長公共子串是（ ）。A. abcba B. cba C. abc D. ab E. bcba2. 設(shè)全集I = a, b, c, d, e, f, g, h，集合B A = a, b, c, d, e, f， C A = c, d, e，B A= a, d，那么集合C B A 為（ ）。A. c, e B. d, e

2、C. e D. c, d, e E. d, f3. 以下二進制數(shù)的值與十進制數(shù)23.456 的值最接近的是（ ）。A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.11114. 完全二叉樹的結(jié)點個數(shù)為4 * N + 3，則它的葉結(jié)點個數(shù)為（ ）。A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 25. 平面上有五個點A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以這五點作為完全圖G 的頂點，每兩點之間的直線

3、距離是圖G 中對應(yīng)邊的權(quán)值。圖G 的最小生成樹中的所有邊的權(quán)值綜合為（ ）。A. 8 B. 7+ 5 C. 9 D. 6+ 5 E. 4+2 2 + 56. 下列設(shè)備中沒有計算功能的是（ ）。A. 筆記本電腦B. 掌上電腦C. 智能手機D. 電子計算器E. 液晶顯示器7. Intel的首顆64 位處理器是（ ）。A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium8. 常見的郵件傳輸服務(wù)器使用（ ）協(xié)議發(fā)送郵件。A. HTTP B. SMTP C. TCP D. FTP E. POP39. 不能在Linux 上使用的網(wǎng)頁瀏覽器是（ ）。A. Internet

4、 Explore B. Netscape C. Opera D. Firefox E. Mozilla10. 一位藝術(shù)史學(xué)家有20000 幅1024 * 768 的真彩色圖像，如果將這些圖像以位圖形式保存在CD 光盤上（一張CD 光盤的容量按600M計算），大約需要（ ）張CD光盤。A. 1 B. 10 C. 100 D. 1000 E. 10000二、不定項選擇題（共10題，每題1.5分，共計15分。多選或少選均不得分）。11. 設(shè)A = true，B = false，C = false，D = true，以下邏輯運算表達式值為真的有（ ）。A. (A B )(C D ) B. (A B )

5、 C ) D C. A(B C ) D )D. (A(B C ) D E. (A B )(C D )12. (3725)8 + (B)16的運算結(jié)果是（ ）。A. (3736)8 B. (2016)10 2 D. (3006)10 E. (7E0)1613. 二叉樹T的寬度優(yōu)先遍歷序列為A B C D E F G H I，已知A是C的父結(jié)點，D 是G 的父結(jié)點，F(xiàn) 是I 的父結(jié)點，樹中所有結(jié)點的最大深度為3（根結(jié)點深度設(shè)為0），可知E的父結(jié)點可能是（ ）。A. A B. B C. C D. D E. F14. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e, f, g依次入棧，以下出棧序

6、列不可能出現(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. 藍牙D. 串口E. IEEE 802.11g 無線網(wǎng)卡16. 處理器A 每秒處理的指令數(shù)是處理器B 的2 倍。某一特定程序P 分別編譯為處理器A和處理器B 的指令，編譯結(jié)果處理器A 的指令數(shù)是處理器B 的4 倍。已知程序P 的算法時間復(fù)雜度為

7、O(n2)，如果處理器A執(zhí)行程序P時能在一小時內(nèi)完成的輸入規(guī)模為n，則處理器B執(zhí)行程序P時能在一小時內(nèi)完成的輸入規(guī)模為（ ）。A. 4 * n B. 2 * n C. n D. n / 2 E. n / 417. 以下哪個（些）不是計算機的輸出設(shè)備（ ）。A. 鼠標B. 顯示器C. 鍵盤D. 掃描儀E. 繪圖儀18. 以下斷電之后將不能保存數(shù)據(jù)的有（ ）。A. 硬盤B. 寄存器C. 顯存D. 內(nèi)存E. 高速緩存19. 下列活動中屬于信息學(xué)奧賽系列活動的是（ ）。A. NOIP B. NOI C. IOI D. 冬令營E. 國家隊選拔賽20. 下列關(guān)于高級語言的說法正確的有（ ）。A. Ada

8、是歷史上的第一個高級語言B. Pascal和C都是編譯執(zhí)行的高級語言C. C+是歷史上的第一個支持面向?qū)ο蟮恼Z言D. 編譯器將高級語言程序轉(zhuǎn)變?yōu)槟繕舜aE. 高級語言程序比匯編語言程序更容易從一種計算機移植到另一種計算機上三問題求解（請在空格處填上答案，每空5分，共計10分）1. 將數(shù)組32, 74, 25, 53, 28, 43, 86, 47中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換次。2. 取火柴游戲的規(guī)則如下：一堆火柴有N根，A、B兩人輪流取出。每人每次可以取1 根或2 根，最先沒有火柴可取的人為敗方，另一方為勝方。如果先取者有必勝策略則記為1，先取者沒有必勝

9、策略記為0。當N 分別為100，200，300，400，500 時，先取者有無必勝策略的標記順序為（回答應(yīng)為一個由0 和/或1 組成的字符串）。四閱讀程序（共4題，每題8分，共計32 分）1 vara, 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 - 300);if (3 * q - p mod 3 = r0) and (r2 = r2) thenr1 := rr

10、0 div p mod 2else r1 := q mod p;writeln(r0 - r1);end.輸入：100 7 3輸出：2 vara : array 1.50 of integer;n, i, sum : integer;procedure work(p, r: integer);vari, j, temp : integer;beginif p = ar then begininc(i);temp := ai; ai := aj; aj := temp;end;temp := ai + 1; ai + 1 := ar; ar := temp;work(p, i);work(i +

11、 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 -100輸出：3 varstr : string;len, i, j : integer;nchr : array 0.25 of integer;mmin : char;beginmmin := z;readln(str);len := lengt

12、h(str);i := len;while i = 2 do beginif stri - 1 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 nchri dowrite(chr(i + ord(a);writeln;end.輸入：zzyzcccbbbaaa輸出：4. varn : longi

13、nt;function g(k : longint) : longint;beginif k = k then break;num := ;end;if then isok := trueelse isok := false;end;beginreadln(n, k);right := 0;for i := 1 to n do beginreadln(leni);if right leni then right := leni;end;inc(right); ;while right do beginmid := (left + right) div 2;if then right := mi

14、delse left := mid;end;writeln(left);end.2N叉樹題目描述:我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當知道先根遍歷的結(jié)果和中根遍歷結(jié)果的時候，我們可以唯一的確定二叉樹；同樣的，如果知道了后根遍歷的結(jié)果和中根遍歷結(jié)果，二叉樹也是唯一確定的。但是如果只知道先根遍歷和后根遍歷的結(jié)果，二叉樹就不是唯一的了。但是我們可以計算滿足條件的不同二叉樹一共有多少個。這不是一個很困難的問題，稍微復(fù)雜一點，我們把這個問題推廣到N叉樹。我們用小寫英文字母來表示N 叉樹的結(jié)點，不同的結(jié)點用不同的字母表示。比如，對于4叉樹，如果先根遍歷的結(jié)果是abdefgc，后根遍歷的結(jié)果是

15、defgbca，那么我們可以得到6個不同的4叉樹（如下圖）。輸入:輸入數(shù)據(jù)包括3行。第一行是一個正整數(shù)N(2 N 20)，表示我們要考慮N叉樹。第二行和第三行分別是兩個字符串序列，分別表示先根遍歷和后根遍歷的結(jié)果。輸出:輸出不同的N叉樹的數(shù)目。題目中給的數(shù)據(jù)保證得到的結(jié)果小于231。輸入樣例:4abdefgcdefgbca輸出樣例:6程序：varstr1, str2 : string;N, len : integer;com : array0.100, 0.100 of longint;function getcom(x, y : integer) : longint;beginif (y =

16、 0) or (x = y) then else if comxy 0 then getcom := comxyelse begincomxy := getcom(x - 1, y)+ ;getcom := comxy;end;end;function count(a, b, c : integer) : longint;varsum : longint;k, s, t, p : integer;beginsum := 1; k := 0; s := a + 1; t := c;if a = b then count := 1else beginwhile s = b do beginp :=

17、 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;beginreadln(N); readln(str1); readln(str2);len := length(str1);writeln(count( );end.第十一屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組(P)參考答案一. 單項選擇題 （共10題，每題1.5分，共計15分。每題有且僅有一個正確答案.）。題號 1 2 4 5 6 7 8 9 10選擇 B A D E D E E B A C二不定項選擇題 （共10題，每題1.5分，共計15分。多選或少選均不得分）。題號 11 12 13 14 15 16 17 18 19 20選擇CDE BCE BC CE BCE B ACD BCDEABCDE BDE三問題求解（共2題，每題5分，共計10分）1. 答： 5 2. 答： 11011 四. 閱讀程序（共4題，每題8分，共計32分）（1）程序的運行結(jié)果是: -7452 (2) 程序的運行結(jié)果是: 3223 （3）程序的運行結(jié)果