信息學(xué)奧賽初賽試題(第十六屆)(共8頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第十六屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal語(yǔ)言 二小時(shí)完成 ） 全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效 一 單項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案。）1.與16進(jìn)制數(shù) A1.2等值的10進(jìn)制數(shù)是 （ ）A.101.2B.111.4C.161.125D.177.252.一個(gè)字節(jié)（byte）由（    ）個(gè)二進(jìn)制組成。A.8B.16C.32D.以上都有可能3.以下邏輯表達(dá)式的值恒為真的是（    ）。A.P（PQ）(PQ) B.Q（PQ）

2、（PQ）C.PQ（PQ）（PQ）D.PQ（PQ）(PQ)4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名是(    )。A. exeB. comC. dllD.以上都不是5.如果在某個(gè)進(jìn)制下等式7*7=41成立，那么在該進(jìn)制下等式12*12=（ ）也成立。A. 100B. 144C. 164D. 1966.提出“存儲(chǔ)程序”的計(jì)算機(jī)工作原理的是（ ）。A. 克勞德香農(nóng)B.戈登摩爾C.查爾斯巴比奇D.馮諾依曼7.前綴表達(dá)式“+ 3 * 2 + 5   12 ” 的值是（ ）。A. 23B. 25 C. 37D. 658.主存儲(chǔ)器的存取速度比中央處理器(CPU

3、)的工作速度慢的多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問(wèn)的存儲(chǔ)單元通常都趨于一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了(   )。A.寄存器B.高速緩存 C.閃存D.外存9.完全二叉樹(shù)的順序存儲(chǔ)方案，是指將完全二叉樹(shù)的結(jié)點(diǎn)從上到下、從左到右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號(hào)位置上，則第k號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組中的（   ）號(hào)位置。A. 2kB. 2k+1 C. k/2下取整D. (k+1)/210.以下競(jìng)賽活動(dòng)中歷史最悠久的是（   ）。A

4、. NOIPB.NOIC. IOID. APIO二 不定項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)不少于1。多選或少選均不得分）。1.元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1個(gè)出棧的是R3，那么第5個(gè)出棧的可能是(   )。A.R1         B.R2         C.R4      

5、;   D.R52. Pascal語(yǔ)言，C語(yǔ)言和C+語(yǔ)言都屬于(   )。A.高級(jí)語(yǔ)言 B.自然語(yǔ)言 C.解釋性語(yǔ)言 D.編譯性語(yǔ)言3. 原地排序是指在排序過(guò)程中(除了存儲(chǔ)待排序元素以外的)輔助空間的大小與數(shù)據(jù)規(guī)模無(wú)關(guān)的排序算法。以下屬于原地排序的有(   )。A.冒泡排序    B.插入排序     C.基數(shù)排序      D.選擇排序4. 在整數(shù)的補(bǔ)碼表示法中，以下說(shuō)法正確的是（  

6、 ）。A只有負(fù)整數(shù)的編碼最高位為1B在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對(duì)值相同C整數(shù)0只有一個(gè)唯一的編碼D兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，若在最高位產(chǎn)生進(jìn)位，則表示運(yùn)算溢出5. 一顆二叉樹(shù)的前序遍歷序列是ABCDEFG，后序遍歷序列是CBFEGDA，則根結(jié)點(diǎn)的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可能是（   ）。A0      B. 2         C. 4         D.

7、66. 在下列HTML語(yǔ)句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的是（   ）。A<a url=”h t t p : / / w w w . n o i . c n”>歡迎訪問(wèn)NOI網(wǎng)站</a>B<a href=”h t t p : / / w w w . n o i . c n”>歡迎訪問(wèn)NOI網(wǎng)站</a>C<a>h t t p : / / w w w . n o i . c n</a>D<a name”h t t p : / / w w w . n o i . c n”>歡迎訪問(wèn)

8、NOI網(wǎng)站</a>7. 關(guān)于拓?fù)渑判颍铝姓f(shuō)法正確的是(   )。A所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判駼對(duì)同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)構(gòu)是唯一的C拓?fù)渑判蛑腥攵葹?的結(jié)點(diǎn)總會(huì)排在入度大于0的結(jié)點(diǎn)的前面D拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度大于0的點(diǎn)8. 一個(gè)平面的法線是指與該平面垂直的直線。過(guò)點(diǎn)(1,1,1)、（0,3,0）、(2,0,0)的平面的法線是（   ）。A過(guò)點(diǎn)（1，1，1）、（2，3，3）的直線B過(guò)點(diǎn)（1，1，1）、（3，2，1）的直線C過(guò)點(diǎn)（0，3，0）、（-3，1，1）的直線D過(guò)點(diǎn)（2，0，0）、（5，2，1）的直線9.雙向

9、鏈表中有兩個(gè)指針域llink和rlink，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，他的左右結(jié)點(diǎn)均為非空?，F(xiàn)要求刪除結(jié)點(diǎn)p，則下列語(yǔ)句序列中正確的是(    )。Ap->rlink->llink=p->rlink;     p->llink->rlink=p->llink; delete p;Bp->llink->rlink=p->rlink;     p->rlink->llink = p->llin

10、k; delete p;Cp->rlink->llink = p->llink;     p->rlink->llink ->rlink = p->rlink; delete p;Dp->llink->rlink = p->rlink;     p->llink->rlink->link = p->llink; delete p;10. 今年(2010年)發(fā)生的事件有（   ）。A惠普實(shí)驗(yàn)室研究員Vinay De

11、olalikar 自稱證明了PNPB英特爾公司收購(gòu)計(jì)算機(jī)安全軟件公司邁克菲(McAfee)C蘋(píng)果公司發(fā)布iPhone 4手機(jī)D微軟公司發(fā)布Windows 7 操作系統(tǒng)三、問(wèn)題求解1LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過(guò)程中，開(kāi)始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過(guò)程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。     舉例說(shuō)明，考慮一個(gè)待編碼的信息串：“xyx yy yy xyx”。初始詞典只有3個(gè)條目，第一個(gè)為x,編碼為1；第二個(gè)為y，編碼為2；第三個(gè)為空格，編碼為3；于是串“xyx”的編碼為1-2

12、-1（其中-為編碼分隔符），加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx”是一個(gè)單詞，而由于該單詞沒(méi)有在詞典中，我們就可以自適應(yīng)的把這個(gè)詞條添加到詞典里，編碼為4，然后按照新的詞典對(duì)后繼信息進(jìn)行編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。     我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)基礎(chǔ)詞典就可以完成對(duì)該序列的完全恢復(fù)。解碼過(guò)程是編碼過(guò)程的逆操作。現(xiàn)在已知初始詞典的3個(gè)條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1

13、-3-5-3-6，則解碼后的信息串是”_”。2.無(wú)向圖G有7個(gè)頂點(diǎn)，若不存在由奇數(shù)條邊構(gòu)成的簡(jiǎn)單回路，則它至多有_條邊。3.記T為一隊(duì)列，初始時(shí)為空，現(xiàn)有n個(gè)總和不超過(guò)32的正整數(shù)依次入列。如果無(wú)論這些數(shù)具體為何值，都能找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列T中的數(shù)之和恰好為9，那么n的最小值是_。四、閱讀程序?qū)懡Y(jié)果專心-專注-專業(yè)1.const    size = 10;var    i, j, cnt, n, m : integer;    data : array1.size of integer

14、;begin    readln(n, m);    for i := 1 to n do       read(datai);    for i := 1 to n do    begin       cnt := 0;       for j := 1 to n do  &#

15、160;       if (datai < dataj) or (dataj = datai) and (j < i)             then inc(cnt);       if cnt = m          then writeln(da

16、tai);    end;end.輸入5 296 -8 0 16 87輸出：_2.const    size = 100;var    na, nb, i, j, k : integer;    a, b : array1.size of integer;begin    readln(na);    for i := 1 to na do      

17、60; read(ai);    readln(nb);    for i := 1 to nb do        read(bi);    i := 1;    j := 1;    while (i <= na) and (j <= nb) do    begin     

18、0; if ai <= bj then       begin          write(ai,' ');          inc(i);       end       else begin 

19、0;        write(bj, ' ');          inc(j);       end;    end;    if i <= na then       for k := i to na do  &

20、#160;       write(ak, ' ');    if j <= nb then       for k := j to nb do          write(bk, ' ');end.輸入51 3 5 7 94 2 6 10 14輸出：_3.const    num = 5

21、;var    n: integer;function r(n : integer) : integer;var    i : integer;begin    if n <= num then    begin       r := n;       exit;    end;    for

22、 i :=1 to num do       if r(n-i) < 0 then       begin         r:=i;         exit;       end;    r:=-1;end;begin&

23、#160;   readln(n);    writeln(r(n);end.輸入 16輸出：_4.const    size=100;var   n,m,x,y,i :integer;   r: array1. size of integer;   map : array1.size, 1.size of boolean;   found : boolean;function successful : boolean;var 

24、;  i : integer;begin   for i :=1 to n do      if not mapriri mod n + 1      then begin        successful := false;        exit;      end;

25、60;  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 &#

26、160;     then exit;    if left > right    then begin        if successful        then begin           for i := 1 to n do &

27、#160;           writeln(ri, ' ');           found := true;        end;        exit;    end;  

28、0; for i:= left to right do    begin      swap(rleft, ri);      perm(left + 1, right);      swap(rleft, ri);    end;end;begin    readln(n, m);    fillchar(map, sizeo

29、f(map), false);    for i := 1 to m do    begin      readln(x, y);      mapxy := true;      mapyx := true;    end;    for i := 1 to n do     

30、 ri := i;    found := false;    perm(1, n);    if not found       then   writeln('No soloution');end.輸入:9 121 22 33 44 55 66 11 72 73 84 85 96 9輸出：_五、完善程序1.(過(guò)河問(wèn)題) 在一個(gè)月黑風(fēng)高的夜晚,有一群人在河的右岸,想通過(guò)唯一的一根獨(dú)木橋走到河的左岸.在伸手不見(jiàn)

31、五指的黑夜里,過(guò)橋時(shí)必須借照燈光來(lái)照明,不幸的是,他們只有一盞燈.另外,獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過(guò),否則將會(huì)坍塌.每個(gè)人單獨(dú)過(guò)獨(dú)木橋都需要一定的時(shí)間,不同的人要的時(shí)間可能不同.兩個(gè)人一起過(guò)獨(dú)木橋時(shí),由于只有一盞燈,所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過(guò)橋所花費(fèi)的時(shí)間.現(xiàn)在輸入N(2<=N<1000)和這N個(gè)人單獨(dú)過(guò)橋需要的時(shí)間,請(qǐng)計(jì)算總共最少需要多少時(shí)間,他們才能全部到達(dá)河左岸.      例如,有3個(gè)人甲、乙、丙,他們單獨(dú)過(guò)橋的時(shí)間分別為1   2   4,則總共最少需要的時(shí)間為7.具體方

32、法是:甲   乙一起過(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

33、     n, i : integer;     time : array1.Size of integer;     pos :array1.Size of Boolean;function max(a, b :integer) : integer;beginif a > b then        max := a     else   

34、    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;  

35、0;     ans :=0;        for i := 1 to n do            if posi = Rignt then           begin         &#

36、160;    inc(num);              if timei > ans then                ans := timei;end;if _ thenbegin   go := ans;   exit;end;

37、ans := INFINITY;for i := 1 to n 1 do    if posi = RIGHT then      for j := i+1 to n do         if posj = RIGHT then         begin        

38、60;   posi := LEFT;            posj := LEFT;            tmp := max(timei, timej) + _;            if tmp < ans then &#

39、160;            ans := tmp;            posi := RIGHT;            posj := RIGHT;         end;go

40、:= ans;endelse if   (stage = LEFT_TO_RIGHT)then begin   ans := INFINITY;     for i := 1 to n do       if _ then         begin           posi := RIGHT;

41、           tmp := _;           if tmp < ans then              ans := tmp;           _;&

42、#160;        end;go := ans;   end   else go := 0;end;begin    readln(n);    for i := 1 to n do    begin     read(timei);       posi := RIGHT; 

43、60;  end;writeln(go(RIGHT_TO_LEFT);end.2（烽火傳遞）烽火臺(tái)又稱烽燧，是重要的軍事防御設(shè)施，一般建在險(xiǎn)要處或交通要道上。一旦有敵情發(fā)生，白天燃燒柴草，通過(guò)濃煙表達(dá)信息；夜晚燃燒干柴，以火光傳遞軍情。在某兩座城市之間有n個(gè)烽火臺(tái)，每個(gè)烽火臺(tái)發(fā)出信號(hào)都有一定的代價(jià)。為了使情報(bào)準(zhǔn)確地傳遞，在連續(xù)m個(gè)烽火臺(tái)中至少要有一個(gè)發(fā)出信號(hào)?，F(xiàn)輸入n、m和每個(gè)烽火臺(tái)發(fā)出信號(hào)的代價(jià)，請(qǐng)計(jì)算總共最少花費(fèi)多少代價(jià)，才能使敵軍來(lái)襲之時(shí)，情報(bào)能在這兩座城市之間準(zhǔn)確傳遞。 例如，有5個(gè)烽火臺(tái)，它們發(fā)出信號(hào)的代價(jià)依次為1、2、5、6、2，且m為3，則總共最少花費(fèi)的代價(jià)為4，即由第

44、2個(gè)和第5個(gè)烽火臺(tái)發(fā)出信號(hào)。const SIZE= 100;varn. m, r， i ： integer;value, heap, pos, home, opt : arrayl.SIZEl of integer;/heap i表示用順序數(shù)組存儲(chǔ)的堆heap中第i個(gè)元素的值/pos i表示opt i在堆heap中的位置，即heap lpos i =opt i/home i表示heap i在序列opt中的位置，即opt home i =heap iprocedure swap (i, j : integer)j交換堆中的第i個(gè)和第j個(gè)元素var tmp ： integer;begin pos home i ：=j； pos homej ：=i； tmp ：=heap i； heap i ：=heap j； heap j ：=tmp; tmp ：=home i;home i ：=homej; home j :=