NOIP普及組初賽模擬試題四

-.z.信息學(xué)競(jìng)賽普及組初賽模擬試題(四)一、選擇題：（選出每題正確的答案代碼，填在括號(hào)里，1—10題為單選題，每小題只有一個(gè)正確答案，11—20題為不定項(xiàng)選擇題，每小題有一個(gè)或一個(gè)以上的正確答案，共20題，每題1.5，共30分）1、二進(jìn)制數(shù)01100100轉(zhuǎn)換成十六進(jìn)制數(shù)是（）。A．32B．64C．128D．100E．2562、操作系統(tǒng)是一類重要的系統(tǒng)軟件，下面幾個(gè)軟件中，不屬于系統(tǒng)軟件的是（）。A．JavaB．MS-DOSC．Linu*D．Windows2000E．Uni*此題出得不是很好，事實(shí)上，JAVA是一門程序設(shè)計(jì)語(yǔ)言，它應(yīng)是系統(tǒng)軟件，其他均是操作系統(tǒng)。見《計(jì)算機(jī)軟件》（整理者注）3、計(jì)算機(jī)病毒的傳染是以計(jì)算機(jī)運(yùn)行和（）為基礎(chǔ)的，沒有這兩個(gè)條件，病毒是不會(huì)傳染的。A．編輯文稿B．讀寫磁盤C．編程序D．掃描圖畫E．打印4、因特網(wǎng)不屬于任何個(gè)人，也不屬于任何組織。其中在網(wǎng)絡(luò)知識(shí)這一塊中有一個(gè)英文簡(jiǎn)寫ISP，它的中文意思是（）。A．因特網(wǎng)連接B．因特網(wǎng)使用C．因特網(wǎng)設(shè)計(jì)D．因特網(wǎng)服務(wù)提供者E．信息傳輸5、Internet給我們提供了資源共享、瀏覽、檢索信息和遠(yuǎn)程登錄等多種服務(wù)，下面幾個(gè)選項(xiàng)中用于遠(yuǎn)程登錄的是（）。A．WWWB．TCP/IPC．TelnetD．E-mailE．FTP6、IE是目前流行的瀏覽器軟件，它的工作基礎(chǔ)是解釋執(zhí)行用（）語(yǔ)言書寫的文件。A．VCB．HTMLC．BASICD．HTTPE．VB7、給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時(shí)間代價(jià)分別是（）。A．O(n)、O(n2)、O(log2n)B．O(log2n)、O(n)、O(n2)C．O(n2)、O(n)、O(log2n)D．O(n2)、O(n)、O(n)E．O(n2)、O(n2)、O(n2)8、一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為18，其葉結(jié)點(diǎn)數(shù)為（）。A．7個(gè)B．8個(gè)C．9個(gè)D．10個(gè)E．11個(gè)9、在流程圖的符號(hào)中，菱形框一般作為（）。A．起始框B．判斷框C．輸入輸出框D．處理工作框E．結(jié)速框10、在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主要將要輸出打印的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。A．堆棧B．?dāng)?shù)組C．線性表D．隊(duì)列E．鏈表11、多媒體技術(shù)中的"多媒體”的含義主要是指如（）等多種表達(dá)信息的形式。A．磁盤B．音箱C．顯示器D．聲音E．圖像12、下面有關(guān)計(jì)算機(jī)知識(shí)說明，正確的是（）。A．在WINDOWS98操作系統(tǒng)下，刪除磁盤中的文件時(shí)都先存放在回收站中B．FO*MAIL是用于收發(fā)電子郵件的工具C．文件夾組織是一個(gè)有層次的樹狀結(jié)構(gòu)，其中最頂層的是桌面D．存儲(chǔ)器具有記憶能力，其中的信息任何時(shí)候都不會(huì)丟失E．為了提高軟件的測(cè)試效率，應(yīng)該選擇發(fā)現(xiàn)錯(cuò)誤的可能性大的測(cè)試數(shù)據(jù)13、對(duì)按關(guān)鍵字排序好的線性表進(jìn)行二分查找，該線性表適合的存儲(chǔ)結(jié)構(gòu)為（）。A．鏈接存儲(chǔ)B．索引存儲(chǔ)C．散列存儲(chǔ)D．順序存儲(chǔ)E．循環(huán)存取14、一個(gè)棧的輸入順序?yàn)?、2、3、4、5，下列序列中可能是棧的輸出序列的是（）。A．54312B．24135C．21543D．12534E．1234515、評(píng)價(jià)一個(gè)算法的好壞有多種指標(biāo)，下列是算法評(píng)價(jià)指標(biāo)的是（）。A．正確性B．運(yùn)行時(shí)間C．占用空間D．迭代次數(shù)E．簡(jiǎn)單性16、下面描述用多維數(shù)組表示的數(shù)據(jù)結(jié)構(gòu)的語(yǔ)句中，正確的是（）。A．多維數(shù)組存放的都是同一種類型的數(shù)據(jù)B．多維數(shù)組各維的下標(biāo)范圍必須一樣C．多維數(shù)組在內(nèi)存中的地址是連續(xù)的D．多維數(shù)組中的下標(biāo)不能是表達(dá)式E．多維數(shù)組是隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)17、若已知一個(gè)棧的入棧順序1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn（它是輸入序列的一個(gè)排列），則在輸出序列中可能出現(xiàn)的情況是（）。A．Pj<Pk<Pi，其中i<j<kB．Pk<Pj<Pi，其中i<j<kC．Pj<Pi<Pk，其中i<j<kD．Pi<Pk<Pj，其中i<j<kE．以上都不可能出現(xiàn)18、線性表具有如下的結(jié)構(gòu)特點(diǎn)：（）A．均勻性B．單一性C．簡(jiǎn)單性D．無(wú)序性E．有序性19、下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是（）。A．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合B．線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C．隊(duì)列是限定僅在一端進(jìn)行插入，在另一端進(jìn)行刪除的線性表D．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表E．圖是一種非線性數(shù)據(jù)結(jié)構(gòu)20、任意一棵樹均可惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹中，頂點(diǎn)N的左右子女分別是N在原樹里對(duì)應(yīng)頂點(diǎn)的（）。A．最左子頂點(diǎn)/最鄰近的右兄弟B．最右子頂點(diǎn)/最右的兄弟C．最鄰近的右兄弟/最左的兄弟D．最鄰近的左兄弟/最鄰近的右兄弟F．最鄰近的右兄弟/最右的兄弟二、問題解答：（共2題，每題5分，共10分）1、光明中學(xué)開設(shè)數(shù)學(xué)、英語(yǔ)和信息學(xué)三個(gè)興趣學(xué)習(xí)小組，其中數(shù)學(xué)小組30人，英語(yǔ)小組15人，信息學(xué)小組18人，參加三個(gè)小組總?cè)藬?shù)為50人，其中有3人同時(shí)參加3個(gè)小組，則同時(shí)只參加兩個(gè)小組的同學(xué)有多少人？2、給出一組頂點(diǎn)（頂點(diǎn)值用A，B，C，D，E，F(xiàn)表示），七對(duì)應(yīng)權(quán)值分別為2，3，1，7，8，4。請(qǐng)以A，B，C，D，E，F(xiàn)為葉子頂點(diǎn)構(gòu)造一棵哈夫曼樹，并求出它的最小帶權(quán)路徑長(zhǎng)度WPL的值。三、寫出程序的運(yùn)行結(jié)果（共4題，每題8分，共32分）programtest1；varn：integer；functioncount(n：integer)：integer；beginifn=1thencount：=0elseifnmod2=0thencount：=count(ndiv2)+1elsecount：=count(n*3+1)+1；end；begin

readln(n)；writeln(count(n))；end.輸入：99輸出：programtest2(input,output);vari,j,k,s:integer;begins:=0fori:=3downto1dobeginforj:=1to3dobegink:=0;repeatk:=k+1;s:=s+k;untilk=j;end;s:=s-(k+1);end;write(‘s=’,s);end.輸出：programtest3;vara,b,n:longint;beginreadln(n);a:=0;b:=0;repeata:=a+1;b:=b+a;untilb>=n;writeln(a);end.輸入：415377輸出：programtest4;varm,n,i,p,k：integer;r:array[1…200]ofinteger;b:Boolean;beginm:=6;n:=2;forI:=1tom-1dor[i]:=i+1;r[m]:=1;i:=0;p:=1;b:=true;whilebdobegini:=i+1;k:=p;p:=r[p];ifk=pthenbeginwriteln(p);b:=falseendelseifi=n+1thenbeginwrite(p,‘

’);i:=0;p:=r[p];r[k]:=p;endendend.輸出：四、完善程序（共2題，每題14分，共28分）【問題描述】設(shè)有n種物品，每種物品有一個(gè)重量及一個(gè)價(jià)值。但每種物品的數(shù)量是無(wú)限的，同時(shí)有一個(gè)背包，最大載重量為*K，今從n種物品中選取若干件（同一種物品可以多次選?。?，使其重量的和小于等于*K，而價(jià)值的和為最大?！境绦蚯鍐巍縋rogrampackage;constma**k=400;ma*n=20;typetlist=array[1…ma*n]ofbyte;tmake=array[0…ma*n,0…ma**k]ofinteger;varn,*k:integer;w,u:tlist;f:tmake;procedureinit;vari:byte;beginfillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,*k);fori:=1tondo

①;end;proceduremake;vari,j:byte;beginfori:=1tondobeginforj:=1tow[i]-1dof[i,j]:=f[i-1,j];forj:=w[i]to*kdoiff[i-1,j]>f[i,j-w[i]]+u[i]then

②;else

③

;end;end;procedureprint;varget:tlist;i,j:byte;beginfillchar(get,sizeof(get),0);i:=

④

;j:=

⑤

;whilei>0doiff[i,j]=f[i-1,j]thendec(i)elsebegindec(j,w[i]);⑥

;end;writeln(‘n=’,n,

‘,’,

‘*k=’,*k);writeln(‘ma*worth=’,

⑦

);fori:=1tondowriteln(‘no.’,i‘,weight:’,w[i]:2,

‘worth:’,u[i]:2,

‘get’,get[i]:2);end;begininit;make;print;end.二、【問題描述】給定一個(gè)01串，請(qǐng)你找出長(zhǎng)度介于a,b之間，重復(fù)出現(xiàn)次數(shù)最多的01串。輸入：a,b(0<a<=b<=12)由0，1組合的數(shù)列，由‘.’結(jié)尾。輸出：要求的串。提示：本程序中將01序列轉(zhuǎn)換為2進(jìn)制數(shù)存取?！境绦蚯鍐巍縫rogramshuchuan;vari,j,s,k,a,b,ma*:integer;m:array[1…8192]ofinteger;two,v:array[1…20]ofinteger;c:char;beginfori:=1to13do

①;readln(a,b);read(c);s:=1;k:=1;whilec<>‘.’dobegins:=sshl1+ord(c)-48;if

②

thens:=((s-two[b+1])modtwo[b])+two[b];inc(m[s]);ifk<bthenfori:=atok-1do

③

;inc(k);read(c);end;fori:=two[b]totwo[b+1]doifm[i]>0thenforj:=a