全國青少信息學奧林匹克聯(lián)賽初賽練習卷(十)new答案

1、全國青少年信息學奧林匹克聯(lián)賽初賽練習卷（十二）答案（普及組 PASCAL 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 、單項選擇題（ 20 題，每題 1.5 分，共計 30 分。每題有且僅有一個正確答案）1. 在網絡上，若某 臺電腦的設備及數(shù)據可由其他電腦共享，這臺電腦稱為（ ）。D. 個人計算機）地址， 該地址共含（）個字節(jié)，）。為了避免使用數(shù)字，人們經常使A. 主機 B. 服務器 C. 副機2. 連接到 Intern et 上的每臺計算機都必須有一個（ 前面若干字節(jié)表示（ ），后面若干字節(jié)表示（ 用字母代替，這些名字稱為（ ）。A. IP 、四、網絡地址、計

2、算機地址、網名B. 網絡、四、 IP 地址、網內計算機地址、域名C. 網絡、不超過十、網頁、網址、網名D. IP 、四、網絡地址、網內計算機地址、域名3. 產生 100 至 300 之間的隨機整數(shù)（包含 100 、300 ）的表達式是（）。A. Random（100）+200B. Random（200）+100C. Random（201）+100D. Random（300）4. OSI 七層協(xié)議中，最底層的協(xié)議是（ ）。A. 會話層 B. 數(shù)據鏈路層 C. 物理層 D. 網絡層5. 設x為值大于零的實型變量，在PascaI中，計算x8的表達式為（）。A. In（ 8*（exp（x）B. exp

3、（8*（l nx）C. xA8D. sqr（sqr（sqr（x）*x6. 十進制數(shù) -103 的補碼是（ ）。A. 10011001 B. 11100111 C. 10110011D. 000110017. 為了區(qū)分漢字與 ASCII碼，計算機中漢字編碼的最高位為（）。A. 0B. 1C. 2D. 48. 在微型計算機系統(tǒng)中，I/O接口位于（ ）之間。A. CPU 和內存儲器B. 外部設備與內存儲器C. 總線與輸入輸出設備D. 主機和輸入輸出設備9. 在微型計算機中，常用（ ）碼實現(xiàn)十進制數(shù)與二進制數(shù)之間的自動轉換。A. BCD 碼B. ASCII 碼C. 海明碼D. 機內碼10. 下列關于排

4、序算法的說法中，正確的是()。A. 快速排序就是最快的排序B. 歸并排序是穩(wěn)定的排序C. 選擇排序比插入排序好11. 含 5 個結點的不同的二叉樹有(A. 22 B. 30 C. 40D. 無論如何，排序的時間復雜度不小于 (NlogN)種。D. 4212. JPG 是一種()的靜態(tài)圖像文件存儲格式。A. 有損壓縮 B. 無損壓縮 C. 不可壓縮 D. 以上都正確13. 插入排序是一種簡單實用的排序算法， 在對數(shù)據進行排序時， 我們可能用二分查找， 對 要插入的元素快速找到在已經排好的元素序列中的位置。 下面的描述中正確的是 ( )。B. 二分查找的時間復雜度為A. 二分查找的時間復雜度為 O

5、(lgN) ，因此排序的時間復雜度為 O(N*lgN)O(N) ，因此排序的時間復雜度為 O(N*lgN)C. 二分查找的時間復雜度為O(lgN) ，排序的時間復雜度不變，為O(N*N)D. 二分查找的時間復雜度為O(N) ，排序的時間復雜度不變，為O(N*N)二分查找的時間復雜度為 O(lgN) ，排序的時間復雜度為 O(N 2)，故答案為 C。14. 某班有 30 個同學報名參加 100、 400、 800 米三個運動項目的比賽。已知有6 人獲 100米參賽資格， 8人獲 400米參賽資格， 15 人獲 800米參賽資格， 且其中有 3人獲全部三 項參賽資格，則至少有( )人沒有獲任何項目

6、參賽資格。A. 5 B. 7 C. 9D. 10設至少有 x 人沒有獲任何項目的參賽資格。 剩下的 30-3-x 個人必須參加 100、400、800 米，其中有 6-3 人獲 100 米的參賽資格， 8-3 人獲 400 米的參賽資格， 15-3 人獲 800 米的參 賽資格，即 30-3-x=3+5+12 。顯然， x=7 。答案： B。15. 如下的敘述中，哪一個是關于數(shù)據類型的正確描述？( )A. 是一組值的集合B. 不包含子結構的信息C. 一條信息或是其值屬于某個類型的一條記錄D. 指一組值的集合以及定義在該集合上的一組操作16. 通信時， 模擬信號也可以用數(shù)字信道來傳輸， 實現(xiàn)模擬

7、信號與數(shù)字信號之間轉換功能的 是( )。A. D/AB. A/DC. Modem D. Codec通常， 模擬信號要轉換成數(shù)字信號才能在數(shù)字傳輸系統(tǒng)上進行傳輸， 模擬信號轉換成數(shù) 字信號要使用脈碼調制技術，即PCM ，經過對模擬信號采樣、量化、編碼三個步驟，使之變換成數(shù)字信號。在接收方，收到數(shù)字信號后，再將它還原為原來的模擬信號。這種在發(fā)送方將模擬信號變換為數(shù)字信號的裝置稱為編碼器(Coder)，在接收方將數(shù)字信號變換為模擬信號的裝置稱為解碼器(Decoder)。通常進行的雙向通信使用既能編碼又能解碼的裝置，稱為編碼解碼器(Codec)。17.在TCP/IP協(xié)議中，TCP和IP分別提供什么服務

8、？(18.A.傳輸層、C.傳輸層、邏輯代數(shù)式A. AB網絡層會話層B.鏈路層、網絡層D.物理層、鏈路層f=AB+ABC+AB(C+D)，貝U f的簡化式子為(B. A+BC. ABCD. ABCD19.設有一個十階的對稱矩陣, 其存儲地址為米用壓縮的存儲方式，1, 每個元素占1個地址空間，則以行序為主存儲，a11為第一個元素, a85的的地址為()。20.A. 13B. 33C. 18D. 50當用一個帶符號的字節(jié)來表示整數(shù)(可正可負)時，最小的二進制數(shù)是(A.10000000B. 11111111C. 01111111D. 00000000二、問題求解(三小題，每題4分，共12分)1. 某校

9、有學號分別為1, 2, 3,，n的n位學生要去音樂廳聽音樂，音樂老師手里有座 位號分別為1, 2, 3,，n的票要分給學生，希望每個學生的座位號與自己的學號都 不相同，請問老師有多少種不同的方案來分配這些票？例如，當n=2時，只有一種方案，n=3時，有2種方案?，F(xiàn)對任意的n>1,記F(n)為不同的方案數(shù)，請寫出 F(n)的遞歸關系式。答：本題是“錯排”問題。禾U用容斥原理，可知錯排的方案數(shù)為：f(n )=n!(1-1/1!+1/2!-1/3!+(-1)A n1/n!)其對應的遞歸/遞推公式為：f(n) = (n-1) * (f(n-1) + f(n-2)f(1)=0f(2)=12. 以正

10、2n+1 (n>0)邊形的頂點為頂點的三角形的集合記為Mn。求：Mn中有多少個銳角三角形？當N=10時，Mn中有多少個兩兩不全等的三角形。答：(1)設銳角三角形的某個頂點為 V。連接V與O (O為圓心)，將剩下的2n個點分作兩半。 左邊的點從上到下依次是A1、A2、An,右邊的點從上到下依次是B1、B2、Bn。B1B n-1記A=A1, A2,An , B=B1, B2,Bn。以V為頂點的銳角三角形的另外兩個頂 點不能同屬于 A，若不然，設為 Ai , Aj (l<j)，則/ AjAiV為鈍角。同理，不能同屬于 B。于是，可以設這個三角形VAiBj。/ AiBjV和/ BjAiV必

11、然都是銳角，因此，只要 / AiVBj為銳角即可。如果i=1,稍加分析可以發(fā)現(xiàn)，j的取值范圍是n;如果i=2 , j的取值范圍是n-1, n;如果l=n , j的取值范圍是1 , 2, 3，,n。因此，(i, j)總共有1+2+3+n= n(n+1)/2種不同的取法。V是任意的，有2n+1種取法。每個銳角三角形被重復算了3次，故而此問題的答案就是：n(n+1)/2*(2n+1) / 3 = n(n+1)(2n+1)/6。(2) Mn中有a個等邊三角形、b個等腰三角形、c個不等邊三角形，那么，a+b+c就 是我們要求的答案。 從2n+1個點中任取3個點有C(2n+1,3)種取法。考察這C(2n+

12、1,3)種取 法：a) 分析等邊三角形。 在2n+1個點中，任意確定一個點 V，那么就能唯一確定一個以V為頂點的等邊三角形；按照這樣計算，位于一個固定位置的等邊三角形會計算3次。所以，在C(2n+1,3)種取法中，同一個等邊三角形會被計算(2n+1)/3次。b) 分析等腰非等邊三角形。 在2n +1個點中，任意確定一個點 V，那么，就能唯一確 定一個以V為頂點的等腰非等邊三角形。所以，在 C(2n+1, 3)種取法中，同一個等邊三角形 會被計算(2n+1)次。c) 同理，一個不等邊三角形會被計算2(2 n+1)次。總的來說，就是(2n+1)/3*a+(2n+1)*b+2(2n+1)*c=C(2

13、n+1,3)(* )然后分分兩種情況討論。1、 (2n+1)是3的倍數(shù)。此時，a=1, b=n-1，通過(*)式解出 c=(n2-2n+1)/3，所以2a+b+c=( n +n+1)/3 ;222、(2 n+1)不是 3 的倍數(shù)。此時，a=0, b=n,通過(* )式解出 c=( n -2n )/3,故 a+b+c=( n +n)/3; 綜合起來，就是(n?+n+1)/3(表示高斯函數(shù))。具體到此題，n=10就是(10*10+10+1)/3=37。答案：37。3. 將n個不同顏色的球 放入k個無標號的盒子中(n>=k,且盒子不允許為空)的方案數(shù)為 S(n, k)。例如，當 n=4, k=

14、3 時，S (n, k)=6。當 n=6, k=3 時，S(n, k) = 90。答：將n個不同顏色的球放到 k個無標號的盒子中的方案數(shù)可以分為以下兩種情況來 討論：(1) 第n個球單獨成堆，此時有S(n-1, k-1)種方案；(2) 第n個球不單獨成堆，而是和其他若干個球合成一堆。此時，我們先將前(n-1)個球分成k堆，然后將第n個球插入某一堆中。對于每一種將前(n-1)個球分成k堆的方案，我們都有k種插法，所以此時有k*S(n-1, k)種方案。綜上所述，S(n, k)的遞推式為：(注意此處采用了遞推方法)S(1, 1) = 1S( n, k) = 0 (n < k)S(n, k)

15、= S(n-1, k-1) + k * S(n-1, k) (n >=k)利用遞推式，我們可以比較方便地計算出結果。N、7、1231100211031314176511525613190三、閱讀程序（共 4題，每題7分，共計28分） 1.program ex12_3_1; varm, n: byte;procedure fen (I, j: byte; s: stri ng);var begink: byte; s1: stri ng;beginif j = 1 the n write In elsefor k := 1 to Ibeginstr(k, s1);fen( I-k, j-e

16、n d;en d;(m, =' , s, i);+ 1 do1, S+S1+ ' +');readl n(m, n); fen(m, n,en d.輸入：6 3輸出：6 = 1 + 1 + 46 = 1 + 2 + 36 = 1 + 3 + 26 = 1 + 4 + 16 = 2 + 1 + 36 = 3 + 2 + 16 = 4 + 1 + 1 【分析】fen(m-k, n-1) 是從fen(m, n)是一個遞歸過程，其功能是將m拆成n個數(shù)相加的形式,m 中拆分出 k 。2.program ex12_3_2;vara: array2.6 of integer;i, j

17、, m: integer;begin for i := 2 to 6 doai := i + 1;repeatm := 2;for i := 3 to 6 doif am > ai then m := i;am := am + m;m := 1;for i := 2 to 5 dofor j := i+1 to 6 do if ai < aj then m:=0;until m <> 0;write(a2:6);end.輸出： 613.program ex12_3_3;const n = 200;varsi, pr: set of 2.n;x, j, m: intege

18、r;beginwriteln( Please input m:); readln(m);si := 2.m; pr := ;x := 2;repeatwhile not(x in si) dox := succ(x);pr := pr + x;j := x;while j <= m dobeginsi := si - j;j ：= j + x;en d;un til si =;j ：= 0;for x := 2 to m doif x in pr the nbeginwrite(x:5);in c(j);if j mod 10 = 0 the n write In;en d;writel

19、nen d.輸入：m=30輸出：23571113171923294. (此題有問題，不完整) program ex12_3_4;varlink: array1.13 of in teger;coun t, I, pre, n ext: in teger;beginfor I := 1 to 13 do lin ki := I + 1;link13: = 1;pre := 13; n ext := 1; count := 0; repeat un til cou nt = 13;writeln( Last pice:' , next);for I := 1 to 13 do write(

20、li nki:4); en d.四、完善程序(19個空，共30分)1. OIM地形題目描述：二維離散世界有一種地形叫OIM ( 01 Mountain)，這種山的坡度只能上升(7')或下降(''),而且兩邊的山腳都與地平線等高，山上所有地方都不低于地平線。例如：AA/ V是一座OIM ; 而/ 不是V這個世界的地理學家們?yōu)榱朔奖阌涗洠oOIM所有可能的形狀用正整數(shù)編號，而且每個正整數(shù)恰好對應一種山形。他們規(guī)定，若兩座山的寬度不同，則較寬的編號較大；若寬度相同，則比較從左邊開始第1個坡度不同的地方，坡度上升的編號較大。以下3座OIM的編號由小到大遞增：A AA A/ V

21、/ VV / V 。顯然A的編號為1,但是地理學家在整理記錄時發(fā)覺，查找編號與山形的對應關系不是很方便。他們希望能快速地從編號得到山的形狀。你自告奮勇答應他們寫一個程序，輸入編號，能馬上輸出山形?！据斎搿恳粋€編號（編號大小不超過600,000,000）【輸出】輸入編號所對應的山形，一座山所占行數(shù)恰為它的高度，即山頂上不能有多余空行?！据斎霕永?5問題：從手工角度來看，本問題的本質是什么？【輸出樣例】A A 已知和求解的各是什么？該如何下手來分析？ / V 【源程序】program program2;const L: in teger = 19;sz: in teger = 50;up: ch

22、ar =/ 'dn: char =''var i, n th, x, y, h, e, f: in teger;m: array0.1,0.38, 0.19 of integer; m數(shù)組的作用是什么？pic: array0.49, 0.49 of char; pic數(shù)組的作用是什么？ procedure in it;var k, s, a, b, c: in teger;beginfor a := 0 to 1 dofor b := 0 to 2 * L dofor c := 0 to L doma,b,c := 0;m0,0,0 := 1;for k := 0 to

23、 2 * L-1 do beginfor s := 1 to L do begi nm0,k+1,s := m0,k,s+1 + m1,k,s+1;m1,k+1,s:= m0,k,s-1 + m1,k,s-1;en d;m0,k+1,0 := m0,k,1 + m1,k,1;end;end; of procedure in it procedure draw(k, s, n th: in teger);beginif (k=0) then exit;if (nth - m1,k,s) >= 0) then beginnth := nth - m1,k,s;if (y > h) th

24、e n_ h := y; picy,x := up; y := y + 1; x := x + 1; y 是行，x 是列draw( _ k - 1, s + 1, nth);endelse begi n-1, nth);y := y 1; picy, x := dn; x := x + 1; draw(k-1, sen d;en d;begi n main program in it;read(nth); 讀入編號for e := 0 to sz- 1 dofor f := 0 to sz-1 do pice, f:=;x :=();x是源點/左下角的橫坐標y :=();y是源點/左卜角的縱坐

25、標h :=(:一 n);h是山的高度i 一 wwhile (nth-m0,2*i,0) >= 0) do beginnth := nth - m0,2*i,0; i := i + 1;end;-1 do begi n-1 dodraw( 2 * i, 0, nth_);for i := h dow nto x for e := 0 to x write(pici, e);writel n( en d;en d.2. 表的操作【問題描述】設有一個表，記為L= (ai, 32,，an),其中：L :表名；ai,32,an為表中的元素；當&為09數(shù)字時，表示元素；a為大寫字母時，表示是

26、另一個表，但不能循環(huán)定義。 例如，下列表的定義是合法的(約定 L是第一個表的表名)：L = (1, 3, K, 8, 0, 4)K = (3, P, 4, H, 7)P = (2, 3)H = (4, 0, 5, 3)【程序要求】當全部表給出之后，求出表中所有元素的最大元素，以及表中全部元素的和?！舅惴皵?shù)據結構簡要說明】表用記錄類型定義，該記錄包含以下兩個域：長度(LENGTH );表體(是元素為字符類型的數(shù)組ELEMENT );隊列用數(shù)組BASE表示，隊列指針用整型變量FRONT與REAR表示。設計一個字符入隊的過程in queue, 一個出隊的函數(shù) outqueue。表中最大元素及元素求

27、和均采用遞歸計算?！境绦蚯鍐巍縞onst maxle n = 100;type list = recordlen gth : in teger;eleme nt: array1.maxle n of char;varmax : in teger;tab no: char;q : arrayprocedure inqueue(q, c); 過程需要二個參數(shù)，q為記錄類型，c字符類型q.rear := ;q.baseq.rear := c;en d;function outqueue(q); q 為記錄類型q.fro nt :=;outqueue := q.baseq.fro nten d;fun

28、ction maxnu mber(c: char): char;var m: char;beginmax := chr(O);for i := 1 to tcen gth dobeginch := tc.eleme nti;if _ then m := maxnumber(ch)else m := ch;if max < m the n max := men d;_-en d;function total (c: char): in teger;var k, i , m : in teger;begink := 0;for i:= 1 to tc.le ngth dobeginch :=

29、 tc.elelme nti;if _ the nm := total (ch);else m := ord (ch) -ord ( 'O'); k := k + men d;total := k;en d;begi n ma in programmax := 36;for tab no :='a' to 'z' do ttab no .le ngth := 0;q.front := 0; q.rear := 0;inq ueue(q, 'L');while (q.fro nt <>q .rear ) dobegint

30、ab no := outqueue(q);write(tab no, =;read In ( s );i := 1;while si <> ' ( ' do i := i+ 1;while si <> ' ) ' dobeginif (si>='a') and (si<='z')thenbeginsi:=chr(ord(si)+ord('a')-ord('a');if (si>='a') and (si<='z') th

31、enbegininc(ttabno.length);ttabno.elementttabno.length := si; inqueue(q, si);end;endelseif (si>='0') andn (si<='9') thenbegininc(ttabno.length);ttabno.elementttabno.length := siend;inc(i)end;edn;write('the max number in table L is:', maxnumber('L');write('tot

32、al is:', total('L')end.3. 最小修路費用【問題描述 】現(xiàn)在政府計劃在某個區(qū)域內的城市間架設高速公路， 以使任意兩個城市間能夠直接或間 接到達?，F(xiàn)在問怎樣修路，才能使得費用最小?！据斎胛募?】第一行一個整數(shù) n( n <= 100)，表示城市的數(shù)目；第二行至第 n+1 行每行兩個數(shù) xi、yi(0 <= xi, yi <= 100 )，表示第 i 個城市的坐標(單 位：千米)?！据敵?】最小費用(每千米一個單位價格) ?！境绦蚯鍐?】program ex12_4_3;const maxn=100;typetcity = recordx, y: realend;varc : array1.maxn of tcity;d : arr