1999年至2010年歷年信息學(xué)奧賽提高組初賽試題

1、第十六屆(2021)全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 提高組 Pascal語(yǔ)言 二小時(shí)完成 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效 一、單項(xiàng)選擇題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.PPQ(PQ) B.QPQPQC.PQPQPQD.PQPQ(PQ)4.Linux下可執(zhí)行文件的默認(rèn)擴(kuò)展名是(  

2、0; )。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)的工作速度慢的多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問(wèn)的存儲(chǔ)單元通常都趨于一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的

3、執(zhí)行效率，在CPU中引入了(   )。A.存放器B.高速緩存 C.閃存D.外存9.完全二叉樹的順序存儲(chǔ)方案，是指將完全二叉樹的結(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. NOIPB.NOIC. IOID. APIO二、不定項(xiàng)選擇題1.元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第1

4、個(gè)出棧的是R3，那么第5個(gè)出棧的可能是(   )。A.R1         B.R2         C.R4         D.R52. Pascal語(yǔ)言，C語(yǔ)言和C+語(yǔ)言都屬于(   )。A.高級(jí)語(yǔ)言 B.自然語(yǔ)言 C.解釋性語(yǔ)言 D.編譯性語(yǔ)言3. 原地排序是指在排序過(guò)程中(除了存儲(chǔ)待排序元素以外的)輔助空間的

5、大小與數(shù)據(jù)規(guī)模無(wú)關(guān)的排序算法。以下屬于原地排序的有(   )。A.冒泡排序    B.插入排序     C.基數(shù)排序      D.選擇排序4. 在整數(shù)的補(bǔ)碼表示法中，以下說(shuō)法正確的選項(xiàng)是   。A只有負(fù)整數(shù)的編碼最高位為1B在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對(duì)值相同C整數(shù)0只有一個(gè)唯一的編碼D兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，假設(shè)在最高位產(chǎn)生進(jìn)位，那么表示運(yùn)算溢出5. 一顆二叉樹的前序遍歷序列是ABCDEFG，后序

6、遍歷序列是CBFEGDA，那么根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是   。A0      B. 2         C. 4         D. 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>

7、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 nameh t t p : / / w w w . n o i . c n>歡送訪問(wèn)NOI網(wǎng)站</a>7. 關(guān)于拓?fù)渑判?，以下說(shuō)法正確的選項(xiàng)是(   )。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é)果序列中

8、的第一個(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.雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向該結(jié)點(diǎn)的前驅(qū)及后繼。設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，他的左右結(jié)點(diǎn)均為非空?，F(xiàn)要求刪除結(jié)點(diǎn)p，那么以下語(yǔ)句序列中正確的選項(xiàng)是(    )。Ap->rlink->llink=p->rlink; 

9、;    p->llink->rlink=p->llink; 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->llin

10、k->rlink = p->rlink;     p->llink->rlink->link = p->llink; delete p;10. 今年(2021年)發(fā)生的事件有   。A惠普實(shí)驗(yàn)室研究員Vinay Deolalikar 自稱證明了PNPB英特爾公司收購(gòu)計(jì)算機(jī)平安軟件公司邁克菲(McAfee)C蘋果公司發(fā)布iPhone 4 D微軟公司發(fā)布Windows 7 操作系統(tǒng)三、問(wèn)題求解1LZW編碼是一種自適應(yīng)詞典編碼。在編碼的過(guò)程中，開(kāi)始時(shí)只有一部根底構(gòu)造元素的編碼詞典，如果在編碼的過(guò)程中遇到一

11、個(gè)新的詞條，那么該詞條及一個(gè)新的編碼會(huì)被追加到詞典中，并用于后繼信息的編碼。     舉例說(shuō)明，考慮一個(gè)待編碼的信息串：“xyx yy yy xyx。初始詞典只有3個(gè)條目，第一個(gè)為x,編碼為1；第二個(gè)為y，編碼為2；第三個(gè)為空格，編碼為3；于是串“xyx的編碼為1-2-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

12、-3-4。     我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接受方，接收方也只要根據(jù)根底詞典就可以完成對(duì)該序列的完全恢復(fù)。解碼過(guò)程是編碼過(guò)程的逆操作?，F(xiàn)在初始詞典的3個(gè)條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，那么解碼后的信息串是_。2.無(wú)向圖G有7個(gè)頂點(diǎn)，假設(shè)不存在由奇數(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的最小值是_

13、。四、閱讀程序?qū)懡Y(jié)果1.const    size = 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

14、 do    begin       cnt := 0;       for j := 1 to n do          if (datai < dataj) or (dataj = datai) and (j < i)          &#

15、160;  then inc(cnt);       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;   

16、a, b : array1.size of integer;begin    readln(na);    for i := 1 to na do        read(ai);    readln(nb);    for i := 1 to nb do        read(bi);    i := 1

17、;    j := 1;    while (i <= na) and (j <= nb) do    begin       if ai <= bj then       begin          write(ai,' ');   

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

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

20、          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  &

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

22、  r:=i;         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:

23、 array1. size of integer;   map : 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 &

24、#160;      successful := false;        exit;      end;   successful :=true;end;procedure swap(var a, b : integer);var    t : integer;begin    t := a;    a := b;

25、    b := t;end;procedure perm(left, right : integer);var    i : integer;begin    if found       then exit;    if left > right    then begin        if success

26、ful        then begin           for i := 1 to n do             writeln(ri, ' ');           found

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

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

29、= true;      mapyx := true;    end;    for i := 1 to n do      ri := i;    found := false;    perm(1, n);    if not found       then  

30、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)五指的黑夜里,過(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)

31、和這N個(gè)人單獨(dú)過(guò)橋需要的時(shí)間,請(qǐng)計(jì)算總共最少需要多少時(shí)間,他們才能全部到達(dá)河左岸.      例如,有3個(gè)人甲、乙、丙,他們單獨(dú)過(guò)橋的時(shí)間分別為1   2   4,那么總共最少需要的時(shí)間為7.具體方法是:甲   乙一起過(guò)橋到河的左岸,甲單獨(dú)回到河的右岸將燈帶回,然后甲,丙在一起過(guò)橋到河的左岸,總時(shí)間為2+1+4=7.constSIZE = 100;     INFINITY = 10000;     LEF

32、T = true;     RIGHT = false;     LEFT_TO_RIGHT = true;     RIGHT_TO_LEFT = false;var     n, i : integer;     time : array1.Size of integer;     pos :array1.Size of Boolean;function

33、 max(a, b :integer) : integer;beginif a > b then        max := a     else       max := b;end;function go(stage : boolean) : integer;var     i, j, num, tmp, ans : integer;begin   

34、0; if   (stage = RIGHT_TO_LEFT)     then begin        num := 0;        ans :=0;        for i := 1 to n do           

35、; if posi = Rignt then           begin              inc(num);              if timei > ans then    

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

37、    if posj = RIGHT then         begin            posi := LEFT;            posj := LEFT;        

38、;    tmp := max(timei, timej) + _;            if tmp < ans then              ans := tmp;            posi :=

39、 RIGHT;            posj := RIGHT;         end;go := ans;endelse if   (stage = LEFT_TO_RIGHT)then begin   ans := INFINITY;     for i := 1 to n do    &#

40、160;  if _ then         begin           posi := RIGHT;           tmp := _;           if tmp < ans then 

41、0;            ans := tmp;           _;         end;go := ans;   end   else go := 0;end;begin    readln(n);  &#

42、160; for i := 1 to n do    begin     read(timei);       posi := RIGHT;    end;writeln(go(RIGHT_TO_LEFT);end.第十五屆(2021)全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 提高組 Pascal語(yǔ)言 二小時(shí)完成 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無(wú)效 一 單項(xiàng)選擇題 共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答

43、案。1、關(guān)于圖靈機(jī)下面的說(shuō)法哪個(gè)是正確的：A) 圖靈機(jī)是世界上最早的電子計(jì)算機(jī)。B) 由于大量使用磁帶操作，圖靈機(jī)運(yùn)行速度很慢。C) 圖靈機(jī)只是一個(gè)理論上的計(jì)算模型。D) 圖靈機(jī)是英國(guó)人圖靈創(chuàng)造的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。2、關(guān)于BIOS下面的說(shuō)法哪個(gè)是正確的：A) BIOS是計(jì)算機(jī)根本輸入輸出系統(tǒng)軟件的簡(jiǎn)稱。B) BIOS里包含了鍵盤、鼠標(biāo)、聲卡、圖形界面顯器等常用輸入輸出設(shè)備的驅(qū)動(dòng)程序。C) BIOS一般由操作系統(tǒng)廠商來(lái)開(kāi)發(fā)完成。D) BIOS能提供各種文件拷貝、復(fù)制、刪除以及目錄維護(hù)等文件管理功能。3、大寫字母A的ASCII編碼為65十進(jìn)制，那么大寫字母J的 十六進(jìn)制 A

44、SCII編碼為：A) 48 B) 49 C) 50 D) 以上都不是4、在字長(zhǎng)為16位的系統(tǒng)環(huán)境下，一個(gè)16位帶符號(hào)整數(shù)的二進(jìn)制補(bǔ)碼為1111111111101101。其對(duì)應(yīng)的十進(jìn)制整數(shù)應(yīng)該是：A) 19 B) -19 C) 18 D) -185、一個(gè)包含n個(gè)分支結(jié)點(diǎn)非葉結(jié)點(diǎn)的非空滿k叉樹，k>=1，它的葉結(jié)點(diǎn)數(shù)目為：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 6. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是：A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd7、最優(yōu)前綴編碼，也稱Huffman編碼。這種編碼組合的特

45、點(diǎn)是對(duì)于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼。A)00，01，10，11 B)0，1，00，11 C)0，10，110，111 D)1，01，000，0018、快速排序平均情況和最壞情況下的算法時(shí)間復(fù)雜度分別為： A) 平均情況 O(nlog2n)，最壞情況O(n2)B) 平均情況 O(n)， 最壞情況O(n2)C) 平均情況 O(n)， 最壞情況O(nlog2n) D) 平均情況 O(log2n)， 最壞情況O(n2)9、左圖給出了一個(gè)加權(quán)無(wú)向圖，從頂點(diǎn)V0開(kāi)始用prim算法求最小生成樹。那么依次參加最小生成樹的頂點(diǎn)集合的頂點(diǎn)序列為：A)

46、 V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V510、全國(guó)信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競(jìng)賽的老師同學(xué)們提供相關(guān)的信息和資源，請(qǐng)問(wèn)全國(guó)信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：A) :/ noi /B) :/ /C) :/ noi /D) :/ xinxixue /二 不定項(xiàng)選擇題 共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)不少于1。多項(xiàng)選擇或少選均不得分。1、關(guān)于CPU下面哪些說(shuō)法是正確的：A) CPU全稱為中央處理器

47、或中央處理單元。B) CPU能直接運(yùn)行機(jī)器語(yǔ)言。C) CPU最早是由Intel公司創(chuàng)造的。D) 同樣主頻下，32位的CPU比16位的CPU運(yùn)行速度快一倍。2、關(guān)于計(jì)算機(jī)內(nèi)存下面的說(shuō)法哪些是正確的：A) 隨機(jī)存儲(chǔ)器RAM的意思是當(dāng)程序運(yùn)行時(shí)，每次具體分配給程序的內(nèi)存位置是隨機(jī)而不確定的。B) 一般的個(gè)人計(jì)算機(jī)在同一時(shí)刻只能存/取一個(gè)特定的內(nèi)存單元。C) 計(jì)算機(jī)內(nèi)存嚴(yán)格說(shuō)來(lái)包括主存memory、高速緩存cache和存放器register三個(gè)局部。D) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。3、關(guān)于操作系統(tǒng)下面說(shuō)法哪些是正確的：A. 多任務(wù)操作系統(tǒng)專用于多核心或多個(gè)CPU架構(gòu)的計(jì)算機(jī)系

48、統(tǒng)的管理。B. 在操作系統(tǒng)的管理下，一個(gè)完整的程序在運(yùn)行過(guò)程中可以被局部存放在內(nèi)存中。C. 分時(shí)系統(tǒng)讓多個(gè)用戶可以共享一臺(tái)主機(jī)的運(yùn)算能力，為保證每個(gè)用戶都得到及時(shí)的響應(yīng)通常會(huì)采用時(shí)間片輪轉(zhuǎn)調(diào)度的策略。D. 為了方便上層應(yīng)用程序的開(kāi)發(fā)，操作系統(tǒng)都是免費(fèi)開(kāi)源的。4、關(guān)于計(jì)算機(jī)網(wǎng)絡(luò)，下面的說(shuō)法哪些是正確的：A) 網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過(guò)去老的實(shí)現(xiàn)方案。B) 新一代互聯(lián)網(wǎng)使用的IPv6標(biāo)準(zhǔn)是IPv5標(biāo)準(zhǔn)的升級(jí)與補(bǔ)充。C) TCP/IP是互聯(lián)網(wǎng)的根底協(xié)議簇，包含有TCP和IP等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。D) 互聯(lián)網(wǎng)上每一臺(tái)入網(wǎng)主機(jī)通常都需要使用一個(gè)唯一的IP地址，否那么就必須注冊(cè)一

49、個(gè)固定的域名來(lái)標(biāo)明其地址。5、關(guān)于HTML下面哪些說(shuō)法是正確的：A) HTML全稱超文本標(biāo)記語(yǔ)言，實(shí)現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。B) HTML不單包含有網(wǎng)頁(yè)內(nèi)容信息的描述，同時(shí)也包含對(duì)網(wǎng)頁(yè)格式信息的定義。C) 網(wǎng)頁(yè)上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁(yè)間的聯(lián)系通過(guò)設(shè)置標(biāo)簽來(lái)實(shí)現(xiàn)。D) 點(diǎn)擊網(wǎng)頁(yè)上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符URL請(qǐng)求網(wǎng)絡(luò)資源或網(wǎng)絡(luò)效勞。6、假設(shè)3個(gè)頂點(diǎn)的無(wú)權(quán)圖G的鄰接矩陣用數(shù)組存儲(chǔ)為0，1，1，1，0，1，0，1，0，假定在具體存儲(chǔ)中頂點(diǎn)依次為: v1，v2，v3 關(guān)于該圖，下面的說(shuō)法哪些是正確的：A)該圖是有向圖。B)該圖是強(qiáng)連通

50、的。C)該圖所有頂點(diǎn)的入度之和減所有頂點(diǎn)的出度之和等于1。D)從v1開(kāi)始的深度優(yōu)先遍歷所經(jīng)過(guò)的頂點(diǎn)序列與廣度優(yōu)先的頂點(diǎn)序列是相同的。7、在帶尾指針鏈表指針clist指向尾結(jié)點(diǎn)的非空循環(huán)單鏈表中每個(gè)結(jié)點(diǎn)都以next字段的指針指向下一個(gè)節(jié)點(diǎn)。假定其中已經(jīng)有2個(gè)以上的結(jié)點(diǎn)。下面哪些說(shuō)法是正確的： A) 如果p指向一個(gè)待插入的新結(jié)點(diǎn)，在頭部插入一個(gè)元素的語(yǔ)句序列為：p.next:= clist.next; clist.next:= p; B) 如果p指向一個(gè)待插入的新結(jié)點(diǎn)，在尾部插入一個(gè)元素的語(yǔ)句序列為：p.next:= clist; clist.next:= p; C) 在頭部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列

51、為：p:= clist.next; clist.next:= clist.next.next; dispose(p); D) 在尾部刪除一個(gè)結(jié)點(diǎn)的語(yǔ)句序列為。p:= clist; clist:= clist .next; dispose(p);8、散列表的地址區(qū)間為0-10,散列函數(shù)為H(K)=K mod 11。采用開(kāi)地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲(chǔ)到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，那么元素59存放在散列表中的可能地址有：A) 5 B) 7 C) 9 D) 109、排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后

52、相對(duì)位置不發(fā)生改變，以下哪些排序算法是穩(wěn)定的：A) 插入排序 B) 基數(shù)排序 C) 歸并排序 D) 冒泡排序10、在參加NOI系列競(jìng)賽過(guò)程中，下面哪些行為是被嚴(yán)格禁止的：A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場(chǎng)。B) 在聯(lián)機(jī)測(cè)試中通過(guò)手工計(jì)算出可能的答案并在程序里直接輸出答案來(lái)獲取分?jǐn)?shù)。C) 通過(guò)互聯(lián)網(wǎng)搜索取得解題思路。D) 在提交的程序中啟動(dòng)多個(gè)進(jìn)程以提高程序的執(zhí)行效率。三問(wèn)題求解共2題，每空5分，共計(jì)10分1拓?fù)渑判蚴侵笇⒂邢驘o(wú)環(huán)圖G中的所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，假設(shè)<u，v> E(G)，那么u在線性序列中出現(xiàn)在v之前，這樣的線性序

53、列成為拓?fù)湫蛄?。如下的有向無(wú)環(huán)圖，對(duì)其頂點(diǎn)做拓?fù)渑判?，那么所有可能的拓?fù)湫蛄械膫€(gè)數(shù)為 。3215476892某個(gè)國(guó)家的錢幣面值有1, 7, 72, 73共計(jì)四種，如果要用現(xiàn)金付清10015元的貨物，假設(shè)買賣雙方各種錢幣的數(shù)量無(wú)限且允許找零，那么交易過(guò)程中至少需要流通 張錢幣。四閱讀程序?qū)懡Y(jié)果共4題，每題8分，共計(jì)32分1vara, b: integer;function work(a, b: integer): integer;beginif a mod b <> 0 thenwork := work(b, a mod b)elsework := b;end;beginread(a

54、, b);writeln(work(a, b);end.輸入：123 321輸出：_2vara, b: array0.3 of integer;i, j, tmp: integer;beginfor i := 0 to 3 doread(bi);for i := 0 to 3 dobeginai := 0;for j := 0 to i dobegininc(ai, bj);inc(bai mod 4, aj);end;end;tmp := 1;for i := 0 to 3 dobeginai := ai mod 10;bi := bi mod 10;tmp := tmp * (ai + b

55、i);end;writeln(tmp);end.輸入：2 3 5 7 輸出：_3consty = 2021;maxn = 50;varn, i, j, s: longint;c: array0.maxn, 0.maxn of longint;begins := 0;read(n);c0, 0 := 1;for i := 1 to n dobeginci, 0 := 1;for j := 1 to i - 1 doci, j := ci-1, j-1 + ci-1, j;ci, i := 1;end;for i := 0 to n dos := (s + cn, i) mod y;write(s

56、);end.輸入：17輸出： 4varn, m, i, j, k, p: integer;a, b: array0.100 of integer;beginread(n, m);a0 := n;i := 0;p := 0;k := 0;repeatfor j := 0 to i - 1 doif ai = aj thenbeginp := 1;k := j;break;end;if p <> 0 thenbreak;bi := ai div m;ai+1 := (ai mod m) * 10;inc(i);until ai = 0;write(b0, '.');fo

57、r j := 1 to k - 1 dowrite(bj);if p <> 0 thenwrite('(');for j := k to i - 1 dowrite(bj);if p <> 0 thenwrite(')');writeln;end.輸入：5 13輸出：_五完善程序 (前5空，每空2分，后6空，每空3分，共28分)1最大連續(xù)子段和給出一個(gè)數(shù)列元素個(gè)數(shù)不多于100，數(shù)列元素均為負(fù)整數(shù)、正整數(shù)、0。請(qǐng)找出數(shù)列中的一個(gè)連續(xù)子數(shù)列，使得這個(gè)子數(shù)列中包含的所有元素之和最大，在和最大的前提下還要求該子數(shù)列包含的元素個(gè)數(shù)最多，并輸出這個(gè)最

58、大和以及該連續(xù)子數(shù)列中元素的個(gè)數(shù)。例如數(shù)列為4，-5，3，2，4時(shí)，輸出9和3；數(shù)列為1 2 3 -5 0 7 8時(shí)，輸出16和7。vara: array1.100 of integer;n, i, ans, len, tmp, beg: integer;beginread(n);for i := 1 to n doread(ai);tmp := 0;ans := 0;len := 0;beg := ;for i := 1 to n dobeginif tmp + ai > ans thenbeginans := tmp + ai;len := i - beg;endelse if (

59、) and (i - beg > len) thenlen := i - beg;if tmp + ai thenbeginbeg := ;tmp := 0;endelse ; end;writeln(ans, ' ', len);end.2. (尋找等差數(shù)列) 有一些長(zhǎng)度相等的等差數(shù)列數(shù)列中每個(gè)數(shù)都為059的整數(shù)，設(shè)長(zhǎng)度均為L(zhǎng)，將等差數(shù)列中的所有數(shù)打亂順序放在一起?，F(xiàn)在給你這些打亂后的數(shù)，問(wèn)原先，L最大可能為多大？先讀入一個(gè)數(shù)n1<=n<=60，再讀入n個(gè)數(shù)，代表打亂后的數(shù)。輸出等差數(shù)列最大可能長(zhǎng)度L。varhash: array0.60 of intege

60、r;n, x, ans, maxnum, i: integer;function work(now: integer): boolean;varok: boolean;first, second, delta, i: integer;beginwhile ( ) and (hashnow=0) doinc(now);if now > maxnum thenbeginwork := true;exit;end;first := now;for second := first to maxnum doif hashsecond > 0 thenbegindelta := ;if fir

61、st + delta * > maxnum thenbreak;if delta = 0 thenok := ( )elsebeginok := true;for i := 0 to ans - 1 dook := and (hashfirst+delta*i>0);end;if ok thenbeginfor i := 0 to ans - 1 dodec(hashfirst+delta*i);if work(first) thenbeginwork := true;exit;end;for i := 0 to ans - 1 doinc(hashfirst+delta*i);e

62、nd;end;work := false;end;beginfillchar(hash, sizeof(hash), 0);read(n);maxnum := 0;for i := 1 to n dobeginread(x);inc(hashx);if x > maxnum thenmaxnum := x;end;for ans := n downto 1 doif (n mod ans = 0) and thenbeginwriteln(ans);break;end;end.第十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽2021年初賽試題 提高組 Pascal語(yǔ)言 二小時(shí)完成 全部試題答案均要求

63、寫在答卷紙上，寫在試卷紙上一律無(wú)效 一、單項(xiàng)選擇題共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確答案。1在以下各項(xiàng)中， 不是操作系統(tǒng)軟件。ASolaris    BLinux    CSybase   DWindows Vista   ESymbian2微型計(jì)算機(jī)中，控制器的根本功能是 。A控制機(jī)器的各個(gè)部件協(xié)調(diào)工作   B實(shí)現(xiàn)算數(shù)運(yùn)算與邏輯運(yùn)算  C存儲(chǔ)各種控制信息D獲取外部信息       E存放程序和數(shù)據(jù)3設(shè)字符串S=“

64、Olympic，S的非空字串的數(shù)目是 。A29 B28 C16 D17 E74完全二叉樹有2*N-1的結(jié)點(diǎn)，那么它的葉子結(jié)點(diǎn)數(shù)目是 。AN-1 B2*N CN D2N-1 EN/25將數(shù)組8，23，4，16，77，-5，53，100中元素從大到小按順序排序，每次可以交換任意兩個(gè)元素，最少要交換 次。A4 B5 C6 D7 E86設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧，出棧順序?yàn)閎，d，c，f，e，a那么棧容量至少應(yīng)該是 。A6 B5 C4 D3 E27與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是 A123.21 B131.22 C130.22 D130.21 E130.208遞歸過(guò)程和函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱為 的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C線性表 D鏈表 E棧9TCP/IP 是一組構(gòu)成互聯(lián)網(wǎng)根底的網(wǎng)絡(luò)協(xié)議，字面上包括兩組協(xié)議：傳輸控制協(xié)議TCP和網(wǎng)際互聯(lián)協(xié)議IP。TCP/IP協(xié)議把Internet網(wǎng)絡(luò)系統(tǒng)描述成具