信息學(xué)初賽復(fù)習(xí)資料-綜合練習(xí)

信息學(xué)初賽復(fù)習(xí)資料(綜合練習(xí))初賽考的知識(shí)點(diǎn)就是計(jì)算機(jī)基本常識(shí)、基本操作和程序設(shè)計(jì)基礎(chǔ)知識(shí)。其中選擇題考查的是知識(shí)，而問題解決類型的題目更加重視能力的考查。一般說(shuō)來(lái)，選擇題只要多用心積累就可以了。問題解決題目的模式比較固定，大家應(yīng)當(dāng)做做以前的題目。寫運(yùn)行結(jié)果和程序填空也需要多做題目，并且培養(yǎng)良好的程序閱讀和分析能力，就像語(yǔ)文的閱讀理解一樣。近幾年來(lái)，初賽的考查范圍有了很大的變化，越來(lái)越緊跟潮流了。這就需要大家有比較廣泛的知識(shí)，包括計(jì)算機(jī)硬件、軟件、網(wǎng)絡(luò)、簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)(例如棧、隊(duì)列、樹和圖等)和簡(jiǎn)單的算法(例如排序、查找和搜索等)，程序設(shè)計(jì)語(yǔ)言以及一些基本的數(shù)學(xué)知識(shí)和技巧(例如排列組合)。但最主要的，還是取決于你對(duì)程序設(shè)計(jì)語(yǔ)言的熟悉程度，再加上認(rèn)真仔細(xì)的心態(tài)。綜合練習(xí)下面四個(gè)不同進(jìn)制的數(shù)中，最小的一個(gè)是。(A)(11011001)2(B)(75)10(C)(37)8(D)(A7)16如果52-19=33是成立的，則52、19、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)制把下列二進(jìn)制數(shù)分別化成八進(jìn)制數(shù)、十六進(jìn)制數(shù)和十進(jìn)制數(shù)。(1)1110B(2)-101010B(3)10.0101B(4)101101.11B把下列十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)(按0舍1入取6位二進(jìn)制小數(shù))。(1)75(2)1024(3)0.2(4)18.692用8位二進(jìn)制定點(diǎn)整數(shù)或定點(diǎn)小數(shù)寫出下列真值的原碼、補(bǔ)碼形式，然后用2位十六進(jìn)制數(shù)表不。(1)11001B(2)-10010B(3)100000B(4)-100000B(5)0.1B(6)-0.1B(7)0.100111B(8)-0.100111B(9)-15/128D已知x的補(bǔ)碼，寫出補(bǔ)碼的十六進(jìn)制表示，再求出x的原碼。(1)[x]補(bǔ)=01010011B(2)[x]補(bǔ)=10001001B[x]補(bǔ)=11111111B(4)[x]補(bǔ)=11000000B已知[x]原=10011011是定點(diǎn)純小數(shù)，寫出x的浮點(diǎn)數(shù)規(guī)格化形式。設(shè)其階碼是4位補(bǔ)碼，尾數(shù)是8位原碼。.數(shù)組A[30..100,20..100]以行優(yōu)先的方式存儲(chǔ)，每個(gè)元素占8個(gè)字節(jié)，且已知A[40,30]的地址為2000,則A[60,90]的地址為：如果以列優(yōu)先存儲(chǔ)，則為:考查了數(shù)據(jù)結(jié)構(gòu)中數(shù)組存儲(chǔ)方式。AAAAAAAAAAAA.設(shè)棧S的初始狀態(tài)為空，現(xiàn)有6個(gè)元素組成的序列｛1,3,5,7,9,11),對(duì)該序列在S棧上依次進(jìn)行如下操作(從序列中的1開始，出棧后不在進(jìn)棧)：進(jìn)棧，出棧，進(jìn)棧，進(jìn)棧，進(jìn)棧，進(jìn)棧，出棧，進(jìn)棧，問出棧的元素序列是：,棧頂指針的值為棧頂元素為:考查了數(shù)據(jù)結(jié)構(gòu)中的棧。AAAAAMA.把中綴表達(dá)式寫成后綴及前綴表達(dá)式⑴(P+Q)*(A-B)/((C+D)/(E-F))-G后:前:A-C*D+B/E*(D/A)后:前:.根據(jù)后綴表達(dá)式，寫出前綴及中綴表達(dá)式ABC/DE+GH-/*+前:中：這兩題實(shí)際上考查了數(shù)據(jù)結(jié)構(gòu)中的表達(dá)式樹AAAAAMAAAAAAAAA.用一個(gè)字節(jié)來(lái)表示整數(shù)，最高位用作符號(hào)位(1為正,0為負(fù))，其他位表示數(shù)值，(1)這樣的表示法稱為原碼表示法，表示數(shù)的范圍為：(2)原碼表示法，將出現(xiàn)有兩種表示(3)實(shí)際上計(jì)算機(jī)中是用補(bǔ)碼表示數(shù)，其表示范圍為：考查了數(shù)的原碼，補(bǔ)碼表示。.已知N*N個(gè)數(shù)據(jù)成方陣排列：A11A12A13...A1nA21A22A23...A2n...An1An2An3...Ann已知Aij=Aji,(1)將A11,A21,A22,A31,A32,A33...存儲(chǔ)到一維數(shù)組A(1),A(2),A(3)...A(K)給出i,j寫出求K的表達(dá)式：(2)將A11,A12,...A1n,A22,A23,...A2n,A33...Ann存儲(chǔ)到一維數(shù)組A(1),A(2),A(3)...A(K),給出i,j寫出求K的表達(dá)式：.已知一個(gè)數(shù)列U1,U2,U3...Un...,往往可以找到一個(gè)最小的K值和K個(gè)數(shù)a1,a2,..,ak,使得數(shù)列從某項(xiàng)開始都滿足：U(n+k)=a1*U(n+k-1)+a2*U(n+k-2)+...+akUn(式A)例如數(shù)列1,1,2,3,5...可以發(fā)現(xiàn)：當(dāng)K=2,a1=1,a2=1時(shí)，從第3項(xiàng)起(N>=1)滿足：U(n+2)=U(n+1)+Un試對(duì)數(shù)列1人3,2A3,3A3,...,NA3,...,求K和a1,a2,...ak,使得式A成立.實(shí)質(zhì)是考數(shù)學(xué)。.給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA,畫出此二叉樹.給出二叉樹的前序遍歷與后序遍歷，能確定一棵二叉樹嗎，舉例說(shuō)明..下面是一個(gè)利用完全二叉樹特性，用順序表來(lái)存儲(chǔ)的一個(gè)二叉樹，結(jié)點(diǎn)數(shù)據(jù)為字符型(結(jié)點(diǎn)層次從小到大，同一層從左到右順序存儲(chǔ)，#表示空結(jié)點(diǎn)，@表示存儲(chǔ)數(shù)據(jù)結(jié)束)結(jié)點(diǎn)123456789101112131415數(shù)據(jù)ABC##DE#####GF@畫出對(duì)應(yīng)的二叉樹：考查了數(shù)據(jù)結(jié)構(gòu)中的二叉樹AAAAAMA10.用鄰接矩陣表示有向圖(圖略)考查了數(shù)據(jù)結(jié)構(gòu)中的圖的表示AAAAAMA11根據(jù)Nocomachns定理，任何一個(gè)正整數(shù)n的立方一定可以表示成n個(gè)連續(xù)的奇數(shù)的和。例如：13=123=3+533=7+9+1143=13+15+17+19在這里，若將每一個(gè)式中的最小奇數(shù)稱為X,那么當(dāng)給出n之后，請(qǐng)寫出X與n之間的關(guān)系表達(dá)式：其實(shí)是考代數(shù)12某班有50名學(xué)生，每位學(xué)生發(fā)一張調(diào)查卡，上寫a,b,c三本書的書名，將讀過的書打“*”，結(jié)果統(tǒng)計(jì)數(shù)字如下：只讀a者8人；只讀b者4人；只讀c者3人；全部讀過的有2人；讀過a,b兩本書的有4人；讀過a,c兩本書的有2人；讀過b,c兩本書的有3人。(1)讀過a的人數(shù)是()。(2)一本書也沒讀過的人數(shù)是()。一個(gè)商場(chǎng)有m種顏色的小球，每種小球足夠多，在這m種小球中挑選n個(gè)小球的選法有多少種？如m=2,n=3時(shí)有4種選法分別是：兩種小球的個(gè)數(shù)分別為03,12,21,30.問：當(dāng)m=4n=4時(shí)選法數(shù)=。35如果一棵m度樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，.有nm個(gè)度為m的結(jié)點(diǎn)，則該樹中葉結(jié)點(diǎn)的的個(gè)數(shù)=.n2+2n3+-+(m-1)nm+1programt1;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輸出：25.programt2;varhi,lo:integer;procedurepl(m,n:integer;varhi,lo:integer);varI:integer;beginI:=n;hi:=0;lo:=0;RepeatI:=I-1;lo:=lo+m;Iflo>=10000thenbeginLo:=lo-10000;Hi:=hi+1;End;UntilI=0;Write(hi:4,',',lo:4);End;BeginP1(200,343,hi,lo);End.輸出：6.8600.programt3;Vard1,d2,X,Min:real;beginMin:=10000;X:=3;whileX<15dobegind1:=sqrt(9+(X-3)*(X-3));d2:=sqrt(4+(15-X)*(15-X));if(d1+d2)<MinthenMin:=d1+d2;X:=x+0.001;end;writeln(Min:10:2);end.輸出：13.00.programt4;vari,k,n:integer;x,w:array[1..500]ofinteger;beginreadln(n);fori:=1tondobeginx[i]:=0;w[i]:=1;end;fori:=2totrunc(sqrt(n))+1doifx[i]=0thenbegink:=i*i;whileK<=ndobeginx[k]:=i;k:=k+i;end;end;fori:=ndownto1doifx[i]<>0thenbeginw[x[i]]:=w[x[i]]+w[i];w[idivx[i]]:=w[idivx[i]]+w[i];w[i]:=0;end;writeln(w[2],w[3]:5,w[5]:5);end.輸入:20輸出：1884降序組合.給定兩個(gè)自然數(shù)n,r(n>r),輸出從數(shù)1到n中按降序順序取r個(gè)自然數(shù)的所有組合.例如，n=5,r=3時(shí)，有如下組合：543542541532531521432431421321程序如下：programtk1;varn,r,i,j:integer;a:array[1..20]ofinteger;beginwrite('n,r=');repeatreadln(n,r);untiln>r;i:=1;a[1]:=n;writeln('result:');repeatifi<>rthenifa[i]>r-ithenbegin(1);i:=i+1;endelsebegin—(2)—;a[I]:=a[I]-1endelsebeginforj:=1tordowrite(a[j]:3);writeln;ifa[r]=1thenbegini:=i-1;a[i]:=a[i]-1;endelse___(3)___end;untila[1]=r-1;end.1.a[i+1]:=a[i]-1i:=i-1;a[i]:=a[i]-1或a[r]:=a[r]-1;2.現(xiàn)在政府計(jì)劃在某個(gè)區(qū)域內(nèi)的的城市間架設(shè)高速公路，以使任意兩個(gè)城市間能夠直接或間接到達(dá)，怎樣修路，費(fèi)用最小。輸入文件：第一行一個(gè)整數(shù)n(n<=100)表示城市數(shù)目。第二行至第n+1行每行兩個(gè)數(shù)xi,yi(0<=xi,yi<=100)表示第i個(gè)城市的坐標(biāo)(單位：千米)；輸出最小費(fèi)用(每千米一個(gè)單位價(jià)格)。程序如下：programt6;constmaxn=100;typetcity=recordx,y:realend;varc:array[1..maxn]oftcity;d:array[1..maxn,1..maxn]ofreal;p:array[1..maxn]ofinteger;n,i,j,k:integer;a,min:real;beginreadln(n);fori:=1tondoreadln(c[i].x,c[i].y);fori:=1tondoforj:=1tondod[i,j]:=sqrt(sqr(c[i].x-c[j].x)+s