NOIP2010第十六屆初賽試題及答案資料1

NOIP2010第十六屆初賽試題及答案（普及組Pascal）NOIP2010第十六屆初賽試題及答案（普及組Pascal）PDF格式第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（普及組語言兩小時完成）??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一.單項選擇題（共20題，每題1.分5，共計30分。每題有且僅有一個正確答案。）+表示（）。一個字節(jié)（）由（）個二進制位組成。.以上都有可能.以下邏輯表達式的值恒為真的是（）V「AVA「V「VAV「AVA「V「VA「V「A「VVArVrA下可執(zhí)行文件的默認擴展名為（）。以是都不是如果樹根算是第層，那么一棵層的二叉樹最多有（）結(jié)點。6以提出“存儲程序”的計算機工作原理的是（）?？藙诘?香農(nóng)戈登?摩爾查爾斯?巴比奇馮?諾依曼設(shè)X、分別代表三進制下的一位數(shù)字，若等式+=在三進制下成立，那么同樣在三進制下，等式X=（）也成立。前綴表達式“+X+1的值是（）。主存儲器的存取速度比中央處理器（）的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，所訪問的存儲單元通常都趨于聚集在一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在中引入了

（）。.寄存器高.速緩存.閃存（）。.寄存器高.速緩存.閃存外.存一.個字長為8位的整數(shù)的補碼是11111則0它0的1原,碼是（）?；诒容^的排序時間復(fù)雜度的下限是（），其中表示待排序的元素個數(shù)。一個自然數(shù)在十進制下有位，則它在二進制下的位數(shù)與（）最接近。在下列語句中，可以正確產(chǎn)生一個指向官方網(wǎng)站的超鏈接的是（）。"”>歡迎訪問NOI網(wǎng)站</a>"”>歡迎訪問NOI網(wǎng)站</a>C.<hattp>://</a>"”>歡迎訪問NOI網(wǎng)站</a>15.元素、、、、入棧的順序為、23、。如果第個出棧的是那么第個出棧的不可能是（）。雙向鏈表中有兩個指針域的，分別指向該結(jié)點的前驅(qū)及后繼。設(shè)指向鏈表中的一個結(jié)點，它的左右結(jié)點均非空?，F(xiàn)要求刪除結(jié)點則下面語句序列中錯誤的是（）。一棵二叉樹的前序遍歷序列是，后序遍歷序列是，則根結(jié)點的左子樹的結(jié)點個數(shù)可能是（）。18關(guān).于拓撲排序，下面說法正確的是（）。所有連通的有向圖都可以實現(xiàn)拓撲排序。對同一個圖而言，拓撲排序的結(jié)果是唯一的。拓撲排序中入度為的結(jié)點總會排在入度大于的結(jié)點的前面。拓撲排序結(jié)果序列中的第一個結(jié)點一定是入度為的點。19完拓全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點從上至下、從左至右依次存放到一個順序結(jié)構(gòu)的數(shù)組中，假定根結(jié)點存放在數(shù)組的1號位置，則第號結(jié)點的父結(jié)點如果存在的話，應(yīng)當(dāng)存放在數(shù)組的（）號位置。

/取2/取2整下1取整20全.國青少年信息學(xué)奧林匹克系列活動的主辦單位是（）。教育部科技部共青團中央中國計算機學(xué)會二.問題求解（共2題，每空5分，共10分）編碼是一種自適應(yīng)詞典編碼。在編碼的過程中，開始時只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個新的詞條，則該詞條及一個新的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個待編碼的信息串："”y初始詞典只有個條目，第一個為，編碼為第二個為，編碼為：第三個為空格，編碼為3于是串“"的編碼為（其中為編碼分隔符），加上后面的一個空格就是-但由于有了一個空格，我們就知道前面的“”是一個單詞，而由于該單詞沒有在詞典中，我們就可以自適應(yīng)的把這個詞條添加到詞典里，編碼為4然,后按照新的詞典對后繼信息進行編碼，以此類推。于是，最后得到編碼：1-2-1-3-2-。2-3-5-3-4現(xiàn)在已知初始詞典的個條目如上述，則信息串“”的編碼是:2教隊列快照是指在某一時刻隊列中的元素組成的有序序列。例如，當(dāng)元素1、2、3入隊，元素1出隊后，此刻的隊列快照是“2”3。當(dāng)元素2、3也出隊后，隊列快照是“”，即為空。現(xiàn)有3個正整數(shù)元素依次入隊、出隊。已知它們的和為則共有種可能的不同的隊列快照（不同的隊列的相同快照只計一次）。例如，“”、“”、“”都是可能的隊列快照；而“”不是可能的隊列快照，因為剩下的2個正整數(shù)的和不可能是1。三教閱讀程序?qū)懡Y(jié)果（共4題，每題8分，其中第4題（、）、（2）各4分，共計32分）4，4，4輸入輸出：輸入:90輸出輸入輸出提示:字符空格’0‘A‘a(chǎn)碼輸入:7輸出分輸入輸出（分）四.完善程序（前4空，每空2.分5，后6空，每空3分，共28分）1（.哥德巴赫猜想）哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫成兩個質(zhì)數(shù)之和，迄今為止，這仍然是一個著名的世界難題，被譽為數(shù)學(xué)王冠上的明珠。試編寫程序，驗證任一大于且不超過的偶數(shù)都能寫成兩個質(zhì)數(shù)之和。若輸入為，則輸出⑤時表示驗證成功，即大于且不超過的偶數(shù)都滿足哥德巴赫猜想。2（.過河問題）在一個月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過唯一的一根獨木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時必須借助燈光來照明，不幸的是，他們只有一盞燈。另外，獨木橋上最多承受兩個人同時經(jīng)過，否則將會坍塌。每個人單獨過橋都需要一定的時間，不同的人需要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，所以需要的時間是較慢的那個人單獨過橋時所花的時間?，F(xiàn)輸入和這個人單獨過橋時需要的時間，請計算總共最少需要多少時間，他們才能全部到達河的左岸。例如，有3個人甲、乙、丙，他們單獨過橋的時間分別為1、2、4，則總共最少需要的時間為7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨回到河的右岸將燈帶回，然后甲、丙再一起過橋到河的左岸，總時間為=4time:array[1..size]ofinteger;pos:array[1..size]ofboolean;functionmax(a,b:integer):integer;beginifa>bthenmax:=aelsemax:=b;end;functiongo(stage:boolean):integer;varI,j,num,tmp,ans:integer;beginif(stage=right_to_lefft)thenbeginnum:=0;ans:=0;fori:=1tondoifpos[i]=rightthenbegininc(num);iftime[i]>ansthenans:=time[i];NOIP2010普及組(Pascal語言)參考答案與評分標(biāo)準一,單項選擇題(共20題,每題1.5分,共計30分)12345678910DAADADBDCB11121314151617181920DBBBBAADCD二,問題求解(共2題,每題5分,共計10分)1.2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6(或22123113431213536)2.49三,閱讀程序?qū)懡Y(jié)果(共4題,每題8分,其中第4題(1),(2)各4分,共計32分)1.22077912.991011113.1201124.(1)1(2)4四,完善程序(前4空,每空2.5分,后6空,每空3分,共計28分)(說明:以下各程序填空可能還有一些等價的寫法,各省可請本省專家審定和上機驗證,不一定上報科學(xué)委員會審查)1.①tmp:=truep[j]p[r]:=iP[j]+P[k](或P[k]+P[j])10042.①num<=2(或num<3或num=2)go(LEFT_TO