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

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

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

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

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

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

7、66. 在下列HTML語句中，可以正確產生一個指向NOI官方網站的超鏈接的是（   ）。A<a url=”h t t p : / / w w w . n o i . c n”>歡迎訪問NOI網站</a>B<a href=”h t t p : / / w w w . n o i . c n”>歡迎訪問NOI網站</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”>歡迎訪問

8、NOI網站</a>7. 關于拓撲排序，下列說法正確的是(   )。A所有連通的有向圖都可以實現拓撲排序B對同一個圖而言，拓撲排序的結構是唯一的C拓撲排序中入度為0的結點總會排在入度大于0的結點的前面D拓撲排序結果序列中的第一個結點一定是入度大于0的點8. 一個平面的法線是指與該平面垂直的直線。過點(1,1,1)、（0,3,0）、(2,0,0)的平面的法線是（   ）。A過點（1，1，1）、（2，3，3）的直線B過點（1，1，1）、（3，2，1）的直線C過點（0，3，0）、（-3，1，1）的直線D過點（2，0，0）、（5，2，1）的直線9.雙向

9、鏈表中有兩個指針域llink和rlink，分別指向該結點的前驅及后繼。設p指向鏈表中的一個結點，他的左右結點均為非空。現要求刪除結點p，則下列語句序列中正確的是(    )。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年)發生的事件有（   ）。A惠普實驗室研究員Vinay De

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

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

13、-3-5-3-6，則解碼后的信息串是”_”。2.無向圖G有7個頂點，若不存在由奇數條邊構成的簡單回路，則它至多有_條邊。3.記T為一隊列，初始時為空，現有n個總和不超過32的正整數依次入列。如果無論這些數具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數之和恰好為9，那么n的最小值是_。四、閱讀程序寫結果專心-專注-專業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.(過河問題) 在一個月黑風高的夜晚,有一群人在河的右岸,想通過唯一的一根獨木橋走到河的左岸.在伸手不見

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

32、法是:甲   乙一起過橋到河的左岸,甲單獨回到河的右岸將燈帶回,然后甲,丙在一起過橋到河的左岸,總時間為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（烽火傳遞）烽火臺又稱烽燧，是重要的軍事防御設施，一般建在險要處或交通要道上。一旦有敵情發生，白天燃燒柴草，通過濃煙表達信息；夜晚燃燒干柴，以火光傳遞軍情。在某兩座城市之間有n個烽火臺，每個烽火臺發出信號都有一定的代價。為了使情報準確地傳遞，在連續m個烽火臺中至少要有一個發出信號。現輸入n、m和每個烽火臺發出信號的代價，請計算總共最少花費多少代價，才能使敵軍來襲之時，情報能在這兩座城市之間準確傳遞。 例如，有5個烽火臺，它們發出信號的代價依次為1、2、5、6、2，且m為3，則總共最少花費的代價為4，即由第

44、2個和第5個烽火臺發出信號。const SIZE= 100;varn. m, r， i ： integer;value, heap, pos, home, opt : arrayl.SIZEl of integer;/heap i表示用順序數組存儲的堆heap中第i個元素的值/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個和第j個元素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 :=