信息學(xué)初賽模擬試題(一二)及答案

信息學(xué)初賽模擬試題（一）（普及組PASCAL語(yǔ)言二小時(shí)完成滿分100分）一、選擇一個(gè)正確答案代碼（人兄/。/口），填入每題的括號(hào)內(nèi)（每題1.5分，多選無(wú)分，共30分）1、MAN英文縮寫的含義是（）A.局域網(wǎng) B.城域網(wǎng)C.廣域網(wǎng)D.增值網(wǎng)2、小張用十六進(jìn)制，八進(jìn)制和十進(jìn)制寫了如下一個(gè)等式： 64－13=33TOC\o"1-5"\h\z式中三個(gè)數(shù)是各不相同進(jìn)位制的數(shù)，試問(wèn)64，13，33，分別為 。A．八進(jìn)制，十進(jìn)制，十六進(jìn)制 B．十進(jìn)制，十六進(jìn)制，八進(jìn)制C八進(jìn)制，十六進(jìn)制，十進(jìn)制 D.十進(jìn)制，八進(jìn)制，十六進(jìn)制3、表達(dá)式（4MOD（－3））與（－4MOD3）的值為： 。A．－1，－1B．1，－1 C．－1，1 D．1，14、試指出：下列if語(yǔ)句中，當(dāng)x=80時(shí)，運(yùn)行的結(jié)果為。beginy:=0;readln（x）;ifx<0theny:=5elseifx<10thenbeginy:=10;ifx<100theny:=100;endelsey:=200;write（'y=',y）;end.A．y=9 B．y=200 C．y=10 D．y=1005、設(shè)棧S的初始狀態(tài)為空，現(xiàn)有5個(gè)元素組成的序列{1,2,3,4,5},對(duì)該序列在S棧上依次進(jìn)行如下操作（從序列中的1開(kāi)始，出棧后不再進(jìn)棧）：進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，出棧，進(jìn)棧，試問(wèn)出棧的元素序列是。A．{5,4,3,2,1}B．{2,1}C．{2,3} D．{3,4}6、ASCII碼是（ ）。A.國(guó)標(biāo)碼B.二進(jìn)制編碼C.十進(jìn)制編碼D.美國(guó)標(biāo)準(zhǔn)信息交換碼7、一臺(tái)計(jì)算機(jī)的字長(zhǎng)是4個(gè)字節(jié),這意味著（）。A.能處理的數(shù)值最大為4位十進(jìn)制數(shù)9999B.能處理的字符串最多由4個(gè)英文字母組成C.在CPU中能夠同時(shí)處理32位二進(jìn)制數(shù)據(jù)D.在CPU中運(yùn)算的最大結(jié)果為2的32次方8、假設(shè)一臺(tái)計(jì)算機(jī)的地址總線為 16,那么中央處理器CPU能訪問(wèn)的最大存儲(chǔ)器容量為（）TOC\o"1-5"\h\zA.2*16KBB.16KBC.216BD.16*1024*8B9、計(jì)算機(jī)最終處理的信息形式是（ ）A-ASCII碼B.BCD碼C.二進(jìn)制 D.十六進(jìn)制10、與十六進(jìn)制數(shù)6F等值的八進(jìn)制數(shù)是（）A.166B.139c.157D.18311、以下屬非法用戶自定義標(biāo)識(shí)符的是 （）。A.dateB.dirC.listD.type12、設(shè)X和Y是同一種枚舉類型變量，則下列語(yǔ)句中合法的是 （）。A．X:=ORD(Y)B．X:=Y C．READ(X,Y) D．WRITE(T,Y)13、計(jì)算機(jī)能夠直接識(shí)別和處理的程序是 程序A.匯編語(yǔ)言 B.源程序C.機(jī)器語(yǔ)言D.高級(jí)語(yǔ)言14、設(shè)有說(shuō)明VARA：ARRAY['A'．．'E'，1．．4，BOOLEAN]OFREA1；則A['A',3]是( )。A.一個(gè)實(shí)型的數(shù)組元素B.一個(gè)數(shù)組，該數(shù)組具有兩個(gè)實(shí)型數(shù)組元素C.一個(gè)數(shù)組，該數(shù)組具有4*2個(gè)實(shí)型數(shù)組元素D.一個(gè)數(shù)組，該數(shù)組具有5*4*2個(gè)實(shí)型數(shù)組元素15、下列屬于線性時(shí)間的排序算法是： ()A.快速排序B.桶排序C.冒泡排序16、一棵包含n個(gè)節(jié)點(diǎn)的樹(shù)有幾條邊：nB.n-1C.不一定17、在Pascal語(yǔ)言中，表達(dá)式35div3mod4的值是。A.0 b.2 C.3 D.618、在數(shù)據(jù)結(jié)構(gòu)中，"樹(shù)"結(jié)構(gòu)下層結(jié)點(diǎn)出現(xiàn)三個(gè)以上的結(jié)點(diǎn)，這種結(jié)構(gòu)稱為 A.三層樹(shù)B.三叉樹(shù)C.多層樹(shù)D.多叉樹(shù)19、在Pascal語(yǔ)言中，下列程序段所計(jì)算的公式是。程序段：S：=0；T：=1；ForI：=1to10doBeginT：=T*I；S：=S+T；end;A.S=1+2+3+4+ +10S=1*2*3*4*……*10C.D.20、以下說(shuō)法正確的是(A-CPU與內(nèi)存不交換信息S=1!+2!+3!C.D.20、以下說(shuō)法正確的是(A-CPU與內(nèi)存不交換信息S=1+2*3+3*4+4*5+……+10*11)。B. CPU與內(nèi)存直接交換信息C.C.CPU與內(nèi)存間接不交換信息D- CPU與內(nèi)存部分交換信息二、閱讀下列程序，寫出程序運(yùn)行結(jié)果(第1二、閱讀下列程序，寫出程序運(yùn)行結(jié)果(第1題5分，第2，3，4題各6分，共23分)programexp1;constn=5;varI,j,k:integer;r:array[0..10]ofinteger;beginforI:=1tondoread(r[I]);forI:=2tondobegink:=r[I];j:=I-1;while(k>r[j])and(j>0)dobeginr[j+1]:=r[j];j:=j-1;end;r[j+1]:=k;end;forI:=1tondowrite(r[I],'');writelnend.鍵盤輸入:84935屏幕輸出：programexp2;vara,b,f:integer;functiongd(m,n:integer):integer;beginifn=0thengd:=melsegd:=gd(n,mmodn);end;beginreadln(a,b);write(‘(‘,a,',',b,')=');f:=gd(a,b);writeln⑴end,鍵盤輸入：17216屏幕輸出：Programexp3(input,output);VARI,J,S：INTEGER;B：ARRAY[0,,5]OFINTEGER;BEGINS：=1;FORI：=1TO5DOB[I]：=I;J：=1;WHILEJ>0DOBEGINJ：=5;WHILE(J>0)AND(B[J]=10+J-5)DOJ：=J-1;IFJ>0THENBEGINS：=S+1;B[J]：=B[J]+1;FORi：=J+1TO5DOB[i]：=B[J]+i-JEND;END;WRITELN('S=',S);END,programexp4(input,output);varm,n,g：integer;functiongcd(m,n：integer)：integer;beginifn=0thengcd：=melsegcd：=gcd(n,mmodn)end;beginread(m,n);g：=gcd(m,n);writeln('m=',m,'n=',n,'gcd=',g)end,輸入：489輸出：三、問(wèn)題解答(第1題每空4分，第2題8分)1、數(shù)據(jù)結(jié)構(gòu)中，下面是一個(gè)樹(shù)結(jié)構(gòu)圖，這個(gè)樹(shù)的 "先序遍歷"結(jié)果是 ，中序遍歷結(jié)果是：2、給出一個(gè)后綴算術(shù)表達(dá)式為248+3*4107-*/@寫出對(duì)應(yīng)的中綴算術(shù)表達(dá)式： 四、完善程序(第一題每空3分，第二題每空2分，第三題每空4分，共32分)1、連續(xù)整數(shù)平臺(tái)問(wèn)題已知一個(gè)含有多個(gè)整數(shù)的數(shù)組，其中相同的元素集中在一起形成一個(gè)平臺(tái)。以下程序用于對(duì)輸入的數(shù)組求出其中最大平臺(tái)長(zhǎng)度。例如，中元素個(gè)數(shù)為20，它們依次為22223333311111111144則它的最大平臺(tái)長(zhǎng)度為9。constmaxlength=100;vara:array[1..maxlength]ofinteger;i,maxi,n,s,t:integer;beginwrite('n=');readln(n);fori:=1tondoread(a[i]);readln;maxi:=0;t:=[1]s:=1;fori:=2tondoifa[i]=tthen[2]elsebeginifs>maxithenmaxi:=s;t:=a[i];end;writeln('maxi=',maxi);end.2、 1000！尾0問(wèn)題以下程序用于統(tǒng)計(jì)1000!末尾有多少個(gè)0。其中1000!=123…1000。實(shí)際上我們只要統(tǒng)計(jì)1000!有多少個(gè)因子10。由于10=52,因而只需統(tǒng)計(jì)有多少個(gè)因子5和2。顯然在1?1000的所有數(shù)中，5的因子個(gè)數(shù)比2的因子個(gè)數(shù)少。因此，只要統(tǒng)計(jì)1?1000的所有數(shù)中共有多少個(gè)因子5就行了。vari,j,n:integer;beginn:=0;fori:=1to200dobeginj:=i*5;while[5]=0dobeginn:=n+1;j:=[6]end;end;writeln(n:4);end.3、[問(wèn)題描述]找數(shù)問(wèn)題：以下程序用在n個(gè)不同元素中找出第憶個(gè)最小元素。程序中用分治策略來(lái)設(shè)計(jì)算法。把這n個(gè)元素放在一個(gè)數(shù)組中，然后取出第k個(gè)元素為標(biāo)準(zhǔn)m,把n個(gè)元素重新排列:小于標(biāo)準(zhǔn)m的元素放在數(shù)組前面，大于該標(biāo)準(zhǔn)的放在數(shù)組的后面。把該元素 m放在兩者之間。設(shè)小于標(biāo)準(zhǔn)的元素個(gè)數(shù)為j-1,如果j=k,則A(k)即為所求元素。如果j>k,則第k個(gè)元素必在區(qū)間[1,j],因此取A[1],…，A[j]為新的元素集合然后重復(fù)上述的"部分排序”的過(guò)程。如果j<k,則第k個(gè)元素必在區(qū)間[j+1,n],因此取A[j],…，A[n]為新的元素集合，重復(fù)過(guò)程。直至j=k為止。[程序清單]varj,k,n:integer;a:array[1..100]ofinteger;proceduresearch(b,e:integer);varI,m,t:integer;beginifb=ethenbeginj:=b;exitend;I:=b;j:=e;m:=[7];RepeatWhilea[I]<mdoinc(i);Whilem<a[j]do[8];IfI<jthenBegint:=a[I];a[I]:=a[j];a[j]:=tend;UntilI>=j;IfI=kthenexit;If[9]thensearch(b,j)elsesearch(j+1,e)End;procedure[10]varI:integer;beginforI:=1tondowrite(a[I], '');writeln;writeln(‘a(chǎn)[‘,k,']=',a[k]);end;beginwrite(‘n=');readln(n);write(‘a(chǎn)[1..',n,']=');fork:=1tondoread(a[k]);readln;write(‘k=');readln(k);search([11]);pr(n);readlnend.信息學(xué)競(jìng)賽初賽模擬試題（一）參考答案、單項(xiàng)選擇題（每題1分，共30分）12345678910DCBBDDCCCC11121314151617181920DBCBBBCDDB二、閱讀下列程序，寫出程序運(yùn)行結(jié)果（第1題5分，第2，3，4題各6分，共23分）1、 985431、(172，16)=43、 S=2524、 m=48n=9gcd=3三、問(wèn)題解答(第1題每空4分，第2題8分)1、ABCDE BADCE2、(24+8)*3/4*(10-7)四、完善程序(第一題每空3分，第二題每空2分，第三題每空4分，共32分)(1)a[1](2)s:=s+1(3)s:=1(4)ifs>maxithenmaxi:=s;(5)jmod5 (6)jdiv5(7)a[k](8)de(j)(9)j>k(10)pr(n:integer);(11)Ln信息學(xué)初賽模擬試題(二)一、選擇題：（選出每題正確的答案代碼，填在括號(hào)里， 1—10題為單選題，每小題只有一個(gè)正確答案，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-DOS C．Linux D．Windows2000E．Unix3、計(jì)算機(jī)病毒的傳染是以計(jì)算機(jī)運(yùn)行和（ ）為基礎(chǔ)的，沒(méi)有這兩個(gè)條件，病毒是不會(huì)傳染的。A.編輯文稿 B.讀寫磁盤 C編程序D.掃描圖畫E.打印ISP,它的中文ISP,它的中文意思是（）A.因特網(wǎng)連接 B.因特網(wǎng)使用C.因特網(wǎng)設(shè)計(jì) D.因特網(wǎng)服務(wù)提供者 E.信息傳輸Internet給我們提供了資源共享、瀏覽、檢索信息和遠(yuǎn)程登錄等多種服務(wù)，下面幾個(gè)選項(xiàng)中用于遠(yuǎn)程登錄的是（）。A．WWWB．TCP/IPC．TelnetD．E-mailE．FTPIE是目前流行的瀏覽器軟件，它的工作基礎(chǔ)是解釋執(zhí)行用（ ）語(yǔ)言書寫的文件。A．VCB．HTML C．BASIC D．HTTP E．VB7、給出3種排序：插入排序、冒泡排序、選擇排序。這 3種排序的時(shí)間代價(jià)分別是（ ）。222A．O（n）、O（n2）、O（logn） B．O（logn）、O（n）、O（n2）C．O（n2）、O（n）、O（logn）2222D．O（n2）、O（n）、O（n）E．O（n2）、O（n2）、O（n2）8、一棵完全二叉樹(shù)的結(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.數(shù)組C.線性表D.隊(duì)列E.鏈表11、多媒體技術(shù)中的“多媒體”的含義主要是指如（ ）等多種表達(dá)信息的形式。A.磁盤B.音箱C顯示器D.聲音E.圖像12、下面有關(guān)計(jì)算機(jī)知識(shí)說(shuō)明，正確的是（ ）。A.在WINDOWS98操作系統(tǒng)下，刪除磁盤中的文件時(shí)都先存放在回收站中B-FOXMAIL是用于收發(fā)電子郵件的工具C.文件夾組織是一個(gè)有層次的樹(shù)狀結(jié)構(gòu)，其中最頂層的是桌面D.存儲(chǔ)器具有記憶能力，其中的信息任何時(shí)候都不會(huì)丟失TOC\o"1-5"\h\zE.為了提高軟件的測(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.21543 D.12534 E.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è)棧的入棧順序2,3,…，n,排列），則在輸出序列中可能出其輸出序列為Pi，P2,P3,…，Pn（它是輸入序列的一現(xiàn)的情況是（A． 個(gè)）。Pj<Pk<Pi,其中i<j<kPk<Pj<Pi,其中i<j<kPj<Pi<Pk,其中i<j<kPi<Pk<「『其中舊"以E.上都不可能出現(xiàn)如下的結(jié)構(gòu)特點(diǎn)：（）A.均勻性B.單一性C.簡(jiǎn)單性19、下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是（A.數(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ì)歹D是無(wú)序性在一端進(jìn).插序性在另一端進(jìn)行刪除的線性表D.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表E.圖是一種非線性數(shù)據(jù)結(jié)構(gòu)20、任意一棵樹(shù)均可惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)中,頂點(diǎn)N在原樹(shù)里對(duì)應(yīng)頂點(diǎn)的（）。A.最左子頂點(diǎn)/最鄰近的右兄弟B.最右子頂點(diǎn)/最右的兄弟。.最鄰近的右兄弟D.最鄰近的左兄弟F.最鄰近的右兄弟N的左右子女分別是/最左的兄弟/最鄰近的右兄弟/最右的兄弟問(wèn)題解答：（共2題,每題5分,共10分）光明中學(xué)開(kāi)設(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表示），其對(duì)應(yīng)權(quán)值分別為2,3,1,7,8,4。請(qǐng)以A,B,C,

D,E,F為葉子頂點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并求出它的最小帶權(quán)路徑長(zhǎng)度 WPL的值。信息學(xué)命題（二）參考答案選擇題：（選出每題正確的答案代碼,填在括號(hào)里, 1—10題為單選題,每小題只有一個(gè)正確答案,11—20題為不定項(xiàng)選擇題,每小題有一個(gè)或一個(gè)以上的正確答案,共 20題,每題1.5,共30分）題號(hào)12345678910答案BABDCBECBD題號(hào)11121314151617181920答案DEBCEDCEABCEACEBCDAEACDEA、問(wèn)題解答一（共2題，每題5分，共10分）第1題:7第2題：61信息學(xué)初賽模擬試題（二）三、選擇題：（選出每題正確的答案代碼,填在括號(hào)里, 1—10題為單選題,每小題只有一個(gè)正確答案,11—20題為不定項(xiàng)選擇題,每小題有一個(gè)或一個(gè)以上的正確答案,共 20題,每題1.5,共30分）

1、二進(jìn)制數(shù)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-DOS C．Linux D．Windows2000E．Unix3、計(jì)算機(jī)病毒的傳染是以計(jì)算機(jī)運(yùn)行和（ ）為基礎(chǔ)的，沒(méi)有這兩個(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.信息傳輸Internet給我們提供了資源共享、瀏覽、檢索信息和遠(yuǎn)程登錄等多種服務(wù)，下面幾個(gè)選項(xiàng)中用于遠(yuǎn)程登錄的是（）。A．WWWB．TCP/IPC．TelnetD．E-mailE．FTPIE是目前流行的瀏覽器軟件，它的工作基礎(chǔ)是解釋執(zhí)行用（ ）語(yǔ)言書寫的文件。A．VCB．HTML C．BASIC D．HTTP E．VB7、給出3種排序：插入排序、冒泡排序、選擇排序。這 3種排序的時(shí)間代價(jià)分別是（ ）。222A．O（n）、O（n2）、O（logn） B．O（logn）、O（n）、O（n2）C．O（n2）、O（n）、O（logn）2222D．O（n2）、O（n）、O（n）E．O（n2）、O（n2）、O（n2）8、一棵完全二叉樹(shù)的結(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.數(shù)組C.線性表D.隊(duì)列E.鏈表11、多媒體技術(shù)中的“多媒體”的含義主要是指如（ ）等多種表達(dá)信息的形式。A.磁盤B.音箱C.顯示器D.聲音E.圖像12、下面有關(guān)計(jì)算機(jī)知識(shí)說(shuō)明，正確的是（ ）。C.在WINDOWS98操作系統(tǒng)下，刪除磁盤中的文件時(shí)都先存放在回收站中FOXMAIL是用于收發(fā)電子郵件的工具C.文件夾組織是一個(gè)有層次的樹(shù)狀結(jié)構(gòu)，其中最頂層的是桌面D.存儲(chǔ)器具有記憶能力，其中的信息任何時(shí)候都不會(huì)丟失為了提高軟件的測(cè)試效率，應(yīng)該選擇發(fā)現(xiàn)錯(cuò)誤的可能性大的測(cè)試數(shù)據(jù)TOC\o"1-5"\h\z13、對(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.12534 E.1234515、評(píng)價(jià)一個(gè)算法的好壞有多種指標(biāo)，下列是算法評(píng)價(jià)指標(biāo)的是（ ）。B.正確性 B.運(yùn)行時(shí)間 C.占用空間 D.迭代次數(shù) E.簡(jiǎn)單性16、下面描述用多維數(shù)組表示的數(shù)據(jù)結(jié)構(gòu)的語(yǔ)句中，正確的是（ ）。G.多維數(shù)組存放的都是同一種類型的數(shù)據(jù)H．多維數(shù)組各維的下標(biāo)范圍必須一樣I．多維數(shù)組在內(nèi)存中的地址是連續(xù)的J．多維數(shù)組中的下標(biāo)不能是表達(dá)式K．多維數(shù)組是隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)17、若已知一個(gè)棧的入棧順序1,2,3,…，5其輸出序列為P1, P2, P3,…，Pn (它是輸入序列的一個(gè)排列)，貝IJ在輸出序列中可能出現(xiàn)的情況是()。A-Pj<Pk<Pi,其中i<j<kPk<Pj<Pi,其中i<j<kC「].q[^^其中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.數(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、任意一棵樹(shù)均可惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二叉樹(shù)。由樹(shù)轉(zhuǎn)換成的二叉樹(shù)中，頂點(diǎn) N的左右子女分別是N在原樹(shù)里對(duì)應(yīng)頂點(diǎn)的()。最左子頂點(diǎn)/最鄰近的右兄弟D.最右子頂點(diǎn)/最右的兄弟。.最鄰近的右兄弟/最左的兄弟口.最鄰近的左兄弟/最鄰近的右兄弟L.最鄰近的右兄弟/最右的兄弟問(wèn)題解答：(共2題,每題5分,共10分)光明中學(xué)開(kāi)設(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表示)，其對(duì)應(yīng)權(quán)值分別為2,3,1,7,8,4。請(qǐng)以A,B,C,D,E,F為葉子頂點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并求出它的最小帶權(quán)路徑長(zhǎng)度 WPL的值。寫出程序的運(yùn)行結(jié)果(共4題,每題8分,共32分)第1題：programtest1；varn：integer；functioncount(n：integer)：integer；beginifn=1thencount：=0elseifnmod2=0thencount=count(ndiv2)+1elsecount：=count(n*3+1)+1；end；beginreadln(n)；writeln(count(n))；end.輸入：99輸出：第2題：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.輸出：第3題：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分)第1題(7分)【問(wèn)題描述】設(shè)有n種物品，每種物品有一個(gè)重量及一個(gè)價(jià)值。但每種物品的數(shù)量是無(wú)限的，同時(shí)有一個(gè)背包，最大載重量為XK,今從n種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于而價(jià)值的和為最大。 XK，【程序清單】Programpackage;constmaxxk=400;maxn=20;typetlist=array[1…maxn]ofbyte;tmake=array[0…maxn,0…maxxk]ofinteger;varn,xk:integer;w,u:tlist;f:tmake;procedureinit;vari:byte;beginfillchar(w,sizeof(w),0);fillchar(u,sizeof(u),0);readln(n,xk);fori:=1tondo①;end;proceduremake;vari,j:byte;beginfori:=1tondobeginforj:=1tow[i]-1dof[i,j]:=f[i-1,j];forj:=w[i]toxkdoiff[i-1,j]>f[i,j-w[i]]+u[i]then ② ;elseend;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,‘,',‘xk=',xk);writeln(‘maxworth=', ⑦);fori:=1tondowriteln(‘no.',i‘,weight:',w[i]:2,‘worth:',u[i]:2, ‘get',get[i]:2);end;begininit;make;print;end.第2題(7分)【問(wèn)題描述】給定一個(gè)01串，請(qǐng)你找出長(zhǎng)度介于a,b之間，重復(fù)出現(xiàn)次數(shù)最多的01串。輸入：a,b(0<a<=b<=i2)由0，1組合的數(shù)列，由‘.'結(jié)尾。輸出：要求的串。提示：本程序中將01序列轉(zhuǎn)換為2進(jìn)制數(shù)存取?！境绦蚯鍐巍縫rogramshuchuan;vari,j,s,k,a,b,max: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])mod