noip2010初賽普及組c試題及答案

一、單項(xiàng)選擇題(共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確選項(xiàng)。)1.2E+03表示()。A.PV(-PAQ)V(-PAQ)B.QV(-PAQ)VPAC.PVQV(PA-Q)V(PAQPVQVPAPA5.如果樹根算第1層，那么一棵n層的二叉樹最多有()個(gè)結(jié)點(diǎn)。9.前綴表達(dá)式“+3*2+512”的值是()。11.一個(gè)字長為8位的整數(shù)的補(bǔ)碼是11111001,則它的原碼是()。13.一個(gè)自然數(shù)在十進(jìn)制下有n位，則它在二進(jìn)制下的位數(shù)與()最接近。14.在下列HTML語句中，可以正確產(chǎn)生一個(gè)指向NOI官方網(wǎng)站的超鏈接的是()。A.<aurl="">歡迎訪問NOI網(wǎng)站</a>B.<ahref="">歡迎訪問NOI網(wǎng)站<a>D.<aname="">歡迎訪問NOI網(wǎng)站<a>15.元素R1、R2、R3、R4、R5入棧的順序?yàn)镽1、R2、R3、R4、R5。如果第一個(gè)出棧的是R3,那么第五個(gè)出棧的不可能是()。16.雙向鏈表中有兩個(gè)指針域llink和rlink,分別指向該結(jié)點(diǎn)的前驅(qū)和后繼。設(shè)P指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空?，F(xiàn)要求刪除結(jié)點(diǎn)P,則下面語句序列中錯(cuò)誤的是()。P^.llink^rlinkllinkdisposerlinkllinkllinkdisposPArlinkllinkrlinkrlinkdispollinkrlinkllinkllinkdispose17.一棵二叉樹的前序遍歷序列是ABCDEFG,后序遍歷序列是CBFEGDA,則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是()。18.關(guān)于拓?fù)渑判?，下面說法正確的是()。A.所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判駼.對同一個(gè)圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的C.拓?fù)渑判蛑腥攵葹?的結(jié)點(diǎn)總會排在入度大于0的結(jié)點(diǎn)前面D.拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度為0的點(diǎn)19.完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點(diǎn)從上至下、從左至右依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號位置，則第K號結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在的話，應(yīng)當(dāng)存放在數(shù)組的()號位置。20.全國青少年信息學(xué)奧林匹克系列活動的主辦單位是()。A.教育部B.科技部C.共青團(tuán)中央D.中國計(jì)算機(jī)協(xié)會二.問題求解(共2題，每空5分，共計(jì)10分)如果在編碼的過程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會被追加到詞典中，并用于后繼x,編碼為1;第二個(gè)為y,編碼為2;第三個(gè)為空格，編碼為3;于是串“xyx”的編碼為1-2-1(其中-為編碼分隔符),加上后面的一個(gè)空格就是1-2-1-3。但由于有了一個(gè)空格，我們就知道前面的“xyx”是一個(gè)單詞，而由于該單詞沒有在詞典中，我們就可以自編碼為4,然后按照新的詞典對后繼信息進(jìn)行編碼，以此類推。于是，最后得到編碼：現(xiàn)在yyxyxxyyxyxyxxxxyx2.隊(duì)列快照是指某一時(shí)刻隊(duì)列中的元素組成的有序序列。例如，當(dāng)元素1、2、3入隊(duì)，元素1出隊(duì)后，此刻的隊(duì)列快照“23”。當(dāng)元素2、3也出隊(duì)后，隊(duì)列快照是“”,即為空?，F(xiàn)有3個(gè)正整數(shù)元素依次入隊(duì)、出隊(duì)。已知它們的和為8,則共有種可能的不同的隊(duì)列快照(不同隊(duì)列的相同快照因?yàn)槭Ｏ碌?個(gè)正整數(shù)的和不可能為1。三.閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分);cout<<x<<'’<<al<<''<<aendlcout<<al<<''<<x<<''<<aendlcout<<al<<''<<a2<<'’<endlcout<<al<<''<<a2<<'<<endlintrSum(intj)輸入：90120cout<<int(m1)<<intendl空格(1)輸入：7(2)輸入：16四.完善程序(第1題，每空2分，第2題，每空3分，共28分)1.(哥德巴赫猜想)哥德巴赫猜想是指，任一大于2的偶數(shù)都可寫成兩個(gè)質(zhì)數(shù)之和。迄今為止，這仍然是一個(gè)著名的世界難題，被譽(yù)為數(shù)學(xué)王冠上的明珠。試編寫程序，驗(yàn)證任一大于2且不超過nbooltmp;cin>>n;break;}}if(i+i==④1}若輸入n為2010,則輸出⑤時(shí)表示驗(yàn)證成功，即大于2且不超過2010的偶數(shù)都滿足哥德巴赫猜想。2.(過河問題)在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通過唯一的一根獨(dú)木橋走到河的左岸.在伸手不見五指的黑夜里，過橋時(shí)必須借照燈光來照明，不幸的是，他們只有一盞燈.另外，獨(dú)木橋上最多能承受兩個(gè)人同時(shí)經(jīng)過，否則將會坍塌.每個(gè)人單獨(dú)過獨(dú)木橋都需要一定的時(shí)間，不同的人要的時(shí)間可能不同.兩個(gè)人一起過獨(dú)木橋時(shí)，由于只有一盞燈，所以需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋所花費(fèi)的時(shí)間.現(xiàn)在輸入N(2<=N<1000)和這N個(gè)人單獨(dú)過橋需要的時(shí)間，請計(jì)算總共最少需要多少時(shí)間，他們才能全部到達(dá)河左岸.例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過橋的時(shí)間分別為1、2、4,則總共最少需要的時(shí)間為7.具體方法是：甲、乙一起過橋到河的左岸，甲單獨(dú)回到河的右岸將燈帶回，然后甲、丙在一起過橋到河的左岸，總時(shí)間為2+1+4=7.#include<iostream>#include<cstring>usingconstboolLEFT=true;constboolRIGHT=false;intn,hour[SIZE];boolpos[SIZE];intmax(inta,intb)returna;elsereturnb;if(pos[i]==RIGHT)if(pos[j]==RIGHT)tmp=max(hour[i],hour[if(tmp<ans)123456789DAADADBDCBDBBBBAADCD二、