1、第十六屆全國青少年信息學奧林匹克聯賽初賽試題試題及答案NOIP2010（Pascal提高組）一、單項選擇題1.與16進制數 A1.2等值的10進制數是 （ ）2.一個字節（byte）由（    ）個二進制組成。A.8          B.16           C.32         

2、;  D.以上都有可能3.以下邏輯表達式的值恒為真的是（    ）。A.P（PQ）(PQ) B.Q（PQ）（PQ）C.PQ（PQ）（PQ）D.PQ（PQ）(PQ)4.Linux下可執行文件的默認擴展名是(    )。A. exe           B. com         C.     dll 

3、;        D.     以上都不是5.如果在某個進制下等式7*7=41成立，那么在該進制下等式12*12=（ ）也成立。A. 100         B.     144         C.     164   

4、;      D.     1966.提出“存儲程序”的計算機工作原理的是（ ）。A. 克勞德香農         B.     戈登摩爾         C.     查爾斯巴比奇       &#

5、160; D.     馮諾依曼7.前綴表達式“+ 3 * 2 + 5   12 ” 的值是（ ）。A.     23         B.     25         C.     37      

6、;   D.     658.主存儲器的存取速度比中央處理器(CPU)的工作速度慢的多，從而使得后者的效率受到影響。而根據局部性原理，CPU所訪問的存儲單元通常都趨于一個較小的連續區域中。于是，為了提高系統整體的執行效率，在CPU中引入了(   )。A.     寄存器         B.     高速緩存    &

7、#160;    C.     閃存         D.     外存9.完全二叉樹的順序存儲方案，是指將完全二叉樹的結點從上到下、從左到右依次存放到一個順序結構的數組中。假定根結點存放在數組的1號位置上，則第k號結點的父結點如果存在的話，應當存放在數組中的（   ）號位置。A.     2k    

8、60;    B.     2k+1         C. k/2下取整             D.     (k+1)/210.     以下競賽活動中歷史最悠久的是（   ）。A. NOIP   

9、;      B.     NOI         C.     IOI         D.     APIO二、不定項選擇題1.元素R1、R2、R3、R4、R5入棧的順序為R1、R2、R3、R4、R5。如果第1個出棧的是R3，那么第5個出棧的可能是( &#

10、160; )。A.     R1         B.     R2         C.R4         D.R52. Pascal語言，C語言和C+語言都屬于(   )。A.     高級語言 

11、0;       B.     自然語言         C.     解釋性語言         D.     編譯性語言3. 原地排序是指在排序過程中(除了存儲待排序元素以外的)輔助空間的大小與數據規模無關的排序算法。以下屬于原地排序的有( &#

12、160; )。A.     冒泡排序         B.     插入排序         C.     基數排序         D.     選擇排序4. 在整數的補碼表示法中，以下說法正確的是

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

14、160; C.     4         D.     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&g

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

16、的法線是（   ）。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.雙向鏈表中有兩個指針域llink和rlink，分別指向該結點的前驅及后繼。設p指向鏈表中的一個結點，他的左右結點均為非空。現要求刪除結點p，則下列語句序列中正確的是(    )。Ap->rlink->llink=p->rlink;     p->llink->rlink=p->l

17、link; delete p;Bp->llink->rlink=p->rlink;     p->rlink->llink = p->llink; delete p;Cp->rlink->llink = p->llink;     p->rlink->llink ->rlink = p->rlink; delete p;Dp->llink->rlink = p->rlink;    

18、; p->llink->rlink->link = p->llink; delete p;10. 今年(2010年)發生的事件有（   ）。A惠普實驗室研究員Vinay Deolalikar 自稱證明了PNPB英特爾公司收購計算機安全軟件公司邁克菲(McAfee)C蘋果公司發布iPhone 4手機D微軟公司發布Windows 7 操作系統三、問題求解1LZW編碼是一種自適應詞典編碼。在編碼的過程中，開始時只有一部基礎構造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。 

19、60;   舉例說明，考慮一個待編碼的信息串：“xyx yy yy xyx”。初始詞典只有3個條目，第一個為x,編碼為1；第二個為y，編碼為2；第三個為空格，編碼為3；于是串“xyx”的編碼為1-2-1（其中-為編碼分隔符），加上后面的一個空格就是1-2-1-3。但由于有了一個空格，我們就知道前面的“xyx”是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應的把這個詞條添加到詞典里，編碼為4，然后按照新的詞典對后繼信息進行編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。     我們可以看到，信息被壓縮

20、了。壓縮好的信息傳遞到接受方，接收方也只要根據基礎詞典就可以完成對該序列的完全恢復。解碼過程是編碼過程的逆操作。現在已知初始詞典的3個條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是”_”。2.無向圖G有7個頂點，若不存在由奇數條邊構成的簡單回路，則它至多有_條邊。3.記T為一隊列，初始時為空，現有n個總和不超過32的正整數依次入列。如果無論這些數具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數之和恰好為9，那么n的最小值是_。四、閱讀程序寫結果1.const    size

21、= 10;var    i, j, cnt, n, m : integer;    data : array1.size of integer;begin    readln(n, m);    for i := 1 to n do       read(datai);    for i := 1 to n do    begin  &#

22、160;    cnt := 0;       for j := 1 to n do          if (datai < dataj) or (dataj = datai) and (j < i)             then inc(cnt);  

23、0;    if cnt = m          then writeln(datai);    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 

24、   readln(na);    for i := 1 to na do        read(ai);    readln(nb);    for i := 1 to nb do        read(bi);    i := 1;    j := 1;  &#

25、160; while (i <= na) and (j <= nb) do    begin       if ai <= bj then       begin          write(ai,' ');          inc

26、(i);       end       else begin          write(bj, ' ');          inc(j);       end;    end; 

27、;   if i <= na then       for k := i to na do          write(ak, ' ');    if j <= nb then       for k := j to nb do       

28、;   write(bk, ' ');end.輸入51 3 5 7 94 2 6 10 14輸出：_3.const    num = 5;var    n: integer;function r(n : integer) : integer;var    i : integer;begin    if n <= num then    begin     

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

30、;    exit;       end;    r:=-1;end;begin    readln(n);    writeln(r(n);end.輸入 16輸出：_4.const    size=100;var   n,m,x,y,i :integer;   r: array1. size of integer;   map

31、 : array1.size, 1.size of boolean;   found : boolean;function successful : boolean;var   i : integer;begin   for i :=1 to n do      if not mapriri mod n + 1      then begin        succe

32、ssful := false;        exit;      end;   successful :=true;end;procedure swap(var a, b : integer);var    t : integer;begin    t := a;    a := b;    b := t;end;procedure p

33、erm(left, right : integer);var    i : integer;begin    if found       then exit;    if left > right    then begin        if successful      &#

34、160; then begin           for i := 1 to n do             writeln(ri, ' ');           found := true;     

35、60;  end;        exit;    end;    for i:= left to right do    begin      swap(rleft, ri);      perm(left + 1, right);      swap(rleft, ri);&

36、#160;   end;end;begin    readln(n, m);    fillchar(map, sizeof(map), false);    for i := 1 to m do    begin      readln(x, y);      mapxy := true;      map

37、yx := true;    end;    for i := 1 to n do      ri := i;    found := false;    perm(1, n);    if not found       then   writeln('No soloution');end.輸入:9

38、121 22 33 44 55 66 11 72 73 84 85 96 9輸出：_五、完善程序1.(過河問題) 在一個月黑風高的夜晚,有一群人在河的右岸,想通過唯一的一根獨木橋走到河的左岸.在伸手不見五指的黑夜里,過橋時必須借照燈光來照明,不幸的是,他們只有一盞燈.另外,獨木橋上最多能承受兩個人同時經過,否則將會坍塌.每個人單獨過獨木橋都需要一定的時間,不同的人要的時間可能不同.兩個人一起過獨木橋時,由于只有一盞燈,所以需要的時間是較慢的那個人單獨過橋所花費的時間.現在輸入N(2<=N<1000)和這N個人單獨過橋需要的時間,請計算總共最少需要多少時間,他們才能全部到達河左岸.&

39、#160;     例如,有3個人甲、乙、丙,他們單獨過橋的時間分別為1   2   4,則總共最少需要的時間為7.具體方法是:甲   乙一起過橋到河的左岸,甲單獨回到河的右岸將燈帶回,然后甲,丙在一起過橋到河的左岸,總時間為2+1+4=7.constSIZE = 100;     INFINITY = 10000;     LEFT = true;     RIGHT = f

40、alse;     LEFT_TO_RIGHT = true;     RIGHT_TO_LEFT = false;var     n, i : integer;     time : array1.Size of integer;     pos :array1.Size of Boolean;function max(a, b :integer) : integer;beginif a >

41、; b then        max := a     else       max := b;end;function go(stage : boolean) : integer;var     i, j, num, tmp, ans : integer;begin     if   (stage = RIGHT_TO_LEFT)&#

42、160;    then begin        num := 0;        ans :=0;        for i := 1 to n do            if posi = Rignt then   

43、60;       begin              inc(num);              if timei > ans then           

44、     ans := timei;end;if _ thenbegin   go := ans;   exit;end;ans := INFINITY;for i := 1 to n 1 do    if posi = RIGHT then      for j := i+1 to n do         if posj = RIGHT then

45、0;        begin            posi := LEFT;            posj := LEFT;            tmp := max(timei, timej

46、) + _;            if tmp < ans then              ans := tmp;            posi := RIGHT;            posj := RIGHT;         end;go := ans;endelse if   (stage = LEFT_TO_RIGHT)then begin   ans := INFINITY; &#