《信息學(xué)競賽指導(dǎo)》參考答案

PAGEPAGE59《信息學(xué)競賽指導(dǎo)》參考答案信息技術(shù)基礎(chǔ)計算機(jī)與信息社會選擇題：1、B2、C3、D4、B5、B6、D7、C計算機(jī)系統(tǒng)組成原理一、選擇題：1、A2、A3、B4、C5、D6、C7、D8、B9、C10、A11、D12、B13、A14、D15、C16、B17、B18、D19、BDE20、AD21、B22、A23、ACDE24、C25、ACD二、思考題1、計算機(jī)系統(tǒng)由硬件和軟件兩大部分的組成。2、CAD是“計算機(jī)輔助設(shè)計”（Computer

Aided

Design）CAI是“計算機(jī)輔助教學(xué)”（ComputerAssistedInstructing）CAT是“計算機(jī)輔助翻譯”（ComputerAidedTranslation）CAM是“計算機(jī)輔助制造”（computerAidedManufacturing)CMOS是“互補金屬氧化物半導(dǎo)體（complementarymetal-oxicle-semiconductor）一種大規(guī)模應(yīng)用于集成電路芯片制造的原料是微機(jī)主板上的一塊可讀寫的RAM芯

片，用來保存當(dāng)前系統(tǒng)的硬件配置和用戶對某些參數(shù)的設(shè)定。第三節(jié)信息的表示一、選擇題：1、C2、C3、A4、C5、A6、C7、D8、C9、BD10、D11、A12、C13、B第四節(jié)網(wǎng)絡(luò)常識選擇題：1、C2、B3、C4、C5、D6、A7、D8、C9、D10、A11、C12、A13、B14、C15、B16、C第五節(jié)操作系統(tǒng)選擇題：1、E2、A3、軟件系統(tǒng)和硬件系統(tǒng)4、任務(wù)欄、開始、時鐘、系統(tǒng)已經(jīng)啟動了的程序5、B6、C7、D8、C9、B10、B11、CD第二章組合數(shù)學(xué)解析第一節(jié)加法原理與乘法原理思考與練習(xí)1、求1000！的末尾其有多少個零？1000\5+1000\25+1000\125+1000\625=249。2、在所有的七位數(shù)中，至少有連續(xù)四個1的數(shù)據(jù)其有多少個？分只有4個連續(xù)1、只有5個連續(xù)1、只有6個連續(xù)1、只有7個連續(xù)1函數(shù)進(jìn)行討論。3、求比1000小的正整數(shù)中含有數(shù)字1的數(shù)的個數(shù)。分僅含1個1、僅含2個1、僅含3個1等三種情況進(jìn)行討論。4、有n個不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組數(shù)據(jù)的最大數(shù)，問有多少種方案？設(shè)取的第一組數(shù)有a個，第二組有b個，而要求第一組數(shù)中最小數(shù)大于第二組中最大的，即只要取出一組m個數(shù)(設(shè)m=a+b)，從大到小取a個作為第一組,剩余的為第二組。此時方案數(shù)為C(n，m)。從m個數(shù)中取第一組數(shù)共有m-1種取法。

總的方案數(shù)為第二節(jié)排列與組合思考與練習(xí)1、在24名選手中進(jìn)行淘汰賽，最后產(chǎn)生一個冠軍，問一共要舉行多少場比賽？23場顯然。2、在一個凸n邊形中，沒有任意三條對角線在其內(nèi)部共點，求其全部對角線在其內(nèi)部的交點數(shù)。根據(jù)題意,每4個頂點可得到兩條對角線,1個對角線交點，從n個頂點任取4個的方案有。3、若一個凸十二邊形，無三條對角線在其內(nèi)部其點。這些對角線被它們的交點其分成多少條線段？根據(jù)圖論知識，每個對角線交點有4個度，每個頂點去掉與相鄰兩個頂點的連線還有9個度，可以得到（4*+12*9）/2條邊。4、求n個完全相同的骰子能擲出多少種不同的方案？相當(dāng)于把n個小球放入6個不同的盒子里，為可重組合，即共有種方案，即種方案。5、正整數(shù)n的一個k拆分就是把n表示為k個正整數(shù)的和。如果拆分不僅與各項的數(shù)值相關(guān)，也與各項的次序相關(guān)，這樣的拆分叫做有序拆分，否則叫做無序拆分。例如4=2+1+1=1+2+1=1+1+2是4的所有3個有序3拆分。試求正整數(shù)n的k拆分的個數(shù)。F（n，k）=F（n-k，k）+F（n-1，k-1）。6、在2n個球中有n個相同，求從這2n個球中選取n個球的方案數(shù)。相當(dāng)于從n個不同的小球中分別取出m個小球(0≤m≤n)，再從n個相同的小球中取出n-m個小球。共有方案：++…+=2n種。7、求從點（0，0）到點（n，n）的不穿過直線y=x的非降路徑數(shù)。為格路問題(弱領(lǐng)先條件)，即從(0，0)到(n，n)，只能從對角線上方走，可以碰到對角線，故方案數(shù)為-。8、排列的生成算法有序數(shù)法、字典排序法和鄰位互換掭算法等，用這些不同的方法寫出前5個自然數(shù)的全排列。略。第三節(jié)遞推關(guān)系思考與練習(xí)1、求n位十進(jìn)制中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個5的數(shù)的結(jié)構(gòu)入手，p1p1...pn-1是n-1位十進(jìn)制數(shù)，若含有偶數(shù)個5，則pn取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個，若p1p1...pn-1只有奇數(shù)個5，則取pn=5，使p1p1...pn-1pn成為出現(xiàn)偶數(shù)個5的十進(jìn)制數(shù)。令an位十進(jìn)制數(shù)中出現(xiàn)5的數(shù)的個數(shù)，bn位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個5的數(shù)的個數(shù)。故有：

an=9an-1+bn-1，bn=9bn-1+an-1，a1=8，b1=1。2、平面上有n條直線，任意兩條直線相交于不同的點，求這n條直線將平面分成的區(qū)域數(shù)f（n）。an=an-1+2（n-1），a1=2。3、平面上有n條直線，任意兩條直線相交于不同的點，求這n條直線的交點數(shù)f（n）。A(n)=a(n-1)+n-1，a1=0。4、N個不同的自然數(shù)順序進(jìn)棧，問有多少種不同的出棧方式？B(n)=。5、求n位二進(jìn)制數(shù)中最后三位數(shù)為010的數(shù)的個數(shù)。an+an-2=2n-3，n≥5，a3=1，a4=2。6．什么是常系數(shù)線性齊次方程和非齊次方程，其求解方法各是什么，請整理成一篇文章。略。第四節(jié)生成函數(shù)思考與練習(xí)1、求序列5，6，7，……，n+5，……的生成函數(shù)。G(X)=5+6x+7x2+8x3+……(n+5)xn+……=5(1+x+x2+x3+……)+（x+2x2+3x3+……）=5/（1-x）+x/（1-x）22、求用1角、2角和5角郵票貼出不同郵費的方案數(shù)。G(x)=（1+x+x2+x3+……）（1+x2+x4++x6……）（1+x5+x10++x15……），展開。3、若有1克砝碼2枚，2克砝碼1枚，3克砝碼2枚，4克砝碼2枚，各能稱出哪些重量？分別有多少種方案？（1+x+x2）(1+x2)(1+x3+x6)(1+x4+x8)，展開，項數(shù)即為可稱出的方案數(shù)，系數(shù)即為各重量的方案數(shù)。4、求不定方程x1+2x2=10的非負(fù)整數(shù)解的個數(shù)。相當(dāng)于將10個相同的球放入兩個不同的盒子。G（x）=（1+x+x2+x3+……x10）（1+x+x2+x3+……x5）展開后指數(shù)為10的項的系數(shù)。5、求S={2?a，3?b}的4可重排列數(shù)。G(x)=（1+x/1！+x2/2?。?+x/1！+x2/2！+x3/3?。?，展開后系數(shù)為4的項。6、求n位二進(jìn)制數(shù)中只有最后三位為010的不同三進(jìn)制數(shù)的數(shù)目。An=cos(n)-sin(n)+2n，n≥3。第五節(jié)組合問題設(shè)計思考與練習(xí)1、夫婦入座問題，n對夫婦出席宴會，圍圓桌而坐，要求同一對夫婦不能相鄰，問有多少種不同的入席方法？先女人定位，園排列n!/n=(n-1)!；再男人定位，即二重圓錯排問題；兩數(shù)相乘2、砝碼問題，1624年，法國數(shù)學(xué)家德.梅齊里亞克（Meziriac，1581-1638）提出了著名的砝碼問題。即一位商人有一個重40磅的砝碼，一不小心跌落在地上摔成四塊，稱得每一小塊砝碼的重都是整磅數(shù)，且用這四塊小砝碼可以稱出1到40磅之間任意重量的物品，問這四塊小砝碼的重量各為多少？1，3，9，27。3、骨牌連環(huán)陣，正方形的骨牌上刻有1到6個點，也有一種骨牌是空白的，即骨牌面上的點數(shù)有七種。對于這樣兩個點數(shù)相異的骨牌聯(lián)在一起形成一個長2寬1的長方形骨牌對，稱為多米諾骨牌對兒。如果把多米諾骨牌對兒擺成一圈，使得任意兩個相相鄰的骨牌對兒的兩個靠近的骨牌有相同的點數(shù)，則稱此圈為一個骨牌連環(huán)陣。如何才能構(gòu)造一個最大的骨牌連環(huán)陣。略。4、三對夫妻同時來到一個渡口，都欲渡過河去。但渡口只有一條最多能載兩人的小船，妻子在其丈夫不在場時也不能和另外的男子在一起，如何安排渡河方案才能使六人最快地渡到河的對岸去？略。5、某人給六人各寫了一封信，當(dāng)最后將這六封信分別放進(jìn)六個信封時，結(jié)果都放錯的可能有多少種？略。6、甲乙丙三人，甲能看到乙和丙，乙能看到丙，丙誰也看不到。有人在甲乙丙三人身后貼紙條，紙條是由三張白色的和兩張紅色的組成，他問甲身后貼的是什么顏色的紙條，甲不知。又問乙，乙也不知。最后又問丙，丙知道。丙為什么知道？丙身后貼的是什么顏色的紙條？略。第六節(jié)邏輯代數(shù)初步思考與練習(xí)1、證明反演律。列出真值表，逐項驗證即可。2、化簡A++D+C+BD。A++D+C+BD=A++C+D+C+BD=+C+D+C+BD=+C+D+BD3、化簡A+C+BC+D。A+C+BC+D=AC+A+BC+C+ABC+BC+D =C+BC+A+BC+D=C+A+D第三章程序設(shè)計第一節(jié)概述思考與練習(xí)：1、C語言的程序一般由哪些部分組成？C語言一般由若干個源文件組成，一個源文件由若干個函數(shù)組成，而主函數(shù)有且只有一個。2、在什么情況下程序要加上頭函數(shù)？當(dāng)函數(shù)中包含有庫函數(shù)時，應(yīng)該調(diào)用頭文件3、如何編譯、運行一個C程序？當(dāng)源程序?qū)懞煤?，?yīng)該對其進(jìn)行編譯操作(ALT+F9)，以便找出其中的語法錯誤；當(dāng)編譯通過后，應(yīng)該對其進(jìn)行連接操作(Compile→Linkexefile)，以便將其他庫函數(shù)“嵌入”到程序中，最后執(zhí)行該程序(CTRL+F9)。第二節(jié)數(shù)據(jù)類型思考與練習(xí)1、什么是常量？什么是變量？常量就是在程序執(zhí)行過程中固定不變的數(shù)據(jù)。變量就是在程序執(zhí)行過程中，可以根據(jù)程序的要求而隨時發(fā)生改變的數(shù)據(jù)存儲單元。2、整形變量和實型變量的取值范圍各是多少？整形變量可以再細(xì)分成多種類型，最大的取值范圍是-2147483648—2147483647，實型變量中單精度類型的取值范圍是3.4E-38—3.4E38，雙精度類型變量的取值范圍是1.7E-308—1.7E+3083、常見有哪些運算符？常見有算術(shù)運算符、關(guān)系運算符、邏輯運算符、位操作運算符、賦值運算符、條件運算符、逗號運算符、指針運算符、求字節(jié)運算符、分量運算符、下標(biāo)運算符等。4、C語言有哪些算術(shù)運算？常見的算術(shù)運算有反運算；自加、自減運算；正、負(fù)號運算5、輸入和輸出函數(shù)各有何特點？在C語言中，輸入和輸出函數(shù)較多，比較常用的輸入函數(shù)是scanf，它從鍵盤中接受數(shù)據(jù)，然后將其存放到變量中。常用的輸出函數(shù)是prinft，是向標(biāo)準(zhǔn)輸出設(shè)備：顯示器輸出內(nèi)存單元中的數(shù)據(jù)。第三節(jié)思考與練習(xí)3、寫出以下程序的執(zhí)行結(jié)果x=5x=5x=3x=7z=0x=3z=1第六節(jié)指針?biāo)伎寂c練習(xí)：1、輸入兩個字符串，將它們拼接起來，放在一個新的數(shù)組中。#include"stdio.h"main(){staticcharst1[20]="abcdefg",st2[]="hijklmn",*p1,*p2;p1=st1;p2=st2;while(*p1!='\0')p1++;while(*p2!='\0'){*p1=*p2;p1++;p2++;}printf("%s",st1);}2、輸入一個字符串，統(tǒng)計出其中數(shù)字的個數(shù)和e到k之間的字母的個數(shù)。#include"stdio.h"main(){staticcharst1[30]="abcde29fgsadf232332dx",*p1,*p2;inta=0,b=0;p1=st1;while(*p1!='\0'){if(*p1>='0'&&*p1<='9')a++;if(*p1>='e'&&*p1<='k')b++;p1++;}printf("a=%d,b=%d",a,b);}3、輸入一個字符串，將其中的每一個連續(xù)的數(shù)字序列看作一個整數(shù)，將這些整數(shù)檢索出來后依次放入一個longint型數(shù)組中。#include"stdio.h"main(){staticcharst1[30]="332ds435dfsf322dd",*p1;intstate=0,a,b=0;p1=st1;while(*p1!='\0'){if(*p1>='0'&&*p1<='9'){a=*p1-'0';b=b*10+a;state=1;}elseif(state==1){printf("%d\n",b);b=0;state=0;}//elseifp1++;}//whileif(state==1)printf("%d\n",b);}你只需要定義一個longint型數(shù)組,然后把輸出語句改為賦值語句就可.4、輸入8個整數(shù)，使用指針以折半插入法對其進(jìn)行排序（從小到大）。本題你可以參照書上第十一章來完成.5、輸入一個2*3的整數(shù)矩陣和一個3*2的整數(shù)矩陣，請使用指針數(shù)組實現(xiàn)這兩個矩陣的相乘。a11aa11a12a13a21a22a23b11b12×b21b22=b31b32a11*b11+a12*b21+a13*b31a11*b12+a12*b22+a13*b32a21*b11+a22*b21+a23*b31a21*b12+a22*b22+a23*b32本題主要是看你對指針的掌握情況,但如果用數(shù)組來做又簡單又能反應(yīng)數(shù)組的特點,用指針來做會比較繁雜,如果你有時間,可以按題目要求來完成。下面程序是其核心部份。For(i=1;i<=2;i++)For(j=1;j<=2;j++)For(k=1;k<=3;k++)c[i][j]=a[i][k]*b[k][j]+c[i][j];6、以字符串的形式一次輸入若干個變量標(biāo)志符存入一個字符數(shù)組中，各標(biāo)志符之間以空格隔開，輸出其中非法標(biāo)志符的個數(shù)。#include"stdio.h"main(){staticcharst1[30]="1eq_3F32_ds435'dfDSf322",*p1;intstate=0,a=0,x=1,i;p1=st1;while(*p1!='\0'){if((*p1>='a'&&*p1<='z')||(*p1>='A'&&*p1<='Z')||(*p1=='_')){while(*p1!=''&&*p1!='\0'){if((*p1>='a'&&*p1<='z')||(*p1>='0'&&*p1<='9')||(*p1>='A'&&*p1<='Z')||(*p1=='_'))state=1;elsex=0;p1++;}//while(*p1!='')if(state==1&&x==1)a=a+1;x=1;}elsewhile(*p1!=''&&*p1!='\0')p1++;p1++;}printf("%d",a);}第七節(jié)結(jié)構(gòu)體與共用體思考與練習(xí)：1、使用兩個結(jié)構(gòu)體變量，分別存入用戶輸入的兩個日期（包括年、月、日），然后計算兩日期之間相隔多少天。#include"stdio.h"main(){structrain{longinty,m,d;}a,b,c;longintad,bd;a.y=2006;a.m=2;a.d=6;b.y=2006;b.m=6;b.d=8;if(b.y*400+b.m*32+b.d<a.y*400+a.m*32+a.d){c=a;a=b;b=c;}switch(a.m){case1:ad=a.d;break;case2:ad=a.d+31;break;case3:ad=a.d+59;break;case4:ad=a.d+90;break;case5:ad=a.d+120;break;case6:ad=a.d+151;break;case7:ad=a.d+181;break;case8:ad=a.d+212;break;case9:ad=a.d+243;break;case10:ad=a.d+273;break;case11:ad=a.d+304;break;case12:ad=a.d+334;break;}if(((a.y%4==0)&&(a.y%100!=0))||(a.y%400==0)){if(a.m>2)ad=ad+1;}switch(b.m){case1:bd=b.d;break;case2:bd=b.d+31;break;case3:bd=b.d+59;break;case4:bd=b.d+90;break;case5:bd=b.d+120;break;case6:bd=b.d+151;break;case7:bd=b.d+181;break;case8:bd=b.d+212;break;case9:bd=b.d+243;break;case10:bd=b.d+273;break;case11:bd=b.d+304;break;case12:bd=b.d+334;break;}if(((b.y%4==0)&&(b.y%100!=0))||(b.y%400==0)){if(b.m>2)bd=bd+1;}bd=bd-ad;ad=0;while(a.y<b.y){if(((b.y%4==0)&&(b.y%100!=0))||(b.y%400==0))bd=bd+366;elsebd=bd+365;a.y=a.y+1;}printf("%ld",bd);}2、用戶輸入12個0~100之間的整數(shù)，統(tǒng)計出小于60、60~79、80~100三個范圍的整數(shù)各有多少個，將統(tǒng)計的結(jié)果存放在一個結(jié)構(gòu)體變量中，最后將此結(jié)構(gòu)體變量傳遞給一個函數(shù)，此函數(shù)負(fù)責(zé)打印出結(jié)果。3、用戶輸入兩個字符串，分別統(tǒng)計出字符串的長度、空格個數(shù)、字母的個數(shù)和數(shù)字的個數(shù)并放入兩個結(jié)構(gòu)體變量中，然后調(diào)用一個函數(shù)，比較這兩個結(jié)構(gòu)體變量，判斷4個統(tǒng)計項目中哪些相同哪些不同，輸出判斷的結(jié)果。#include"stdio.h"main(){staticstructrain{longintl,space,num,abc;}a1,a2;chara[30]="dsa234322d",b[30]="2343dsad2422";inti,m,n,e,k;a1.space=a1.num=a1.abc=0;a2=a1;a1.l=strlen(a);for(i=0;i<=a1.l;i++){if(a[i]>='0'&&a[i]<='9')a1.num=a1.num+1;if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z'))a1.abc=a1.abc+1;if(a[i]=='')a1.space=a1.space+1;}a2.l=strlen(b);for(i=0;i<=a2.l;i++){if(b[i]>='0'&&b[i]<='9')a2.num=a2.num+1;if((b[i]>='a'&&b[i]<='z')||(b[i]>='A'&&b[i]<='Z'))a2.abc=a2.abc+1;if(b[i]=='')a2.space=a2.space+1;}if(a1.l==a2.l)printf("thelengthissame\n");elseprintf("thenumberofthelengthisNO\n");if(a1.num==a2.num)printf("thenumberofthenumberissame\n");elseprintf("thenumberofthenumberisNO\n");if(a1.abc==a2.abc)printf("thenumberoftheletterissame\n");elseprintf("thenumberoftheletterisNO\n");if(a1.space==a2.space)printf("thenumberofthespaceissame\n");elseprintf("thenumberofthespaceisNO\n");}第八節(jié)文件思考與練習(xí)：1、將三個學(xué)生的數(shù)據(jù)（學(xué)號、姓名、年齡）從鍵盤輸入，存入到一個新建的文本文件中去。#include"stdio.h"#include"stdlib.h"main(){charname[20];longintID;intage;inti;FILE*fp;if((fp=fopen("test.txt","w"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}for(i=1;i<=3;i++){scanf("%ld%s%d",&ID,name,&age);fprintf(fp,"%ld%s%4d\n",ID,name,age);}fclose(fp);}2、有一文本文件，以‘\n’字符作為分行的標(biāo)志，請編定程序指出其中第幾行是最長的行，此行有多少個字符。#include"stdio.h"#include"stdlib.h"main(){intline=0,number=0,temp=0,x=0;charch;FILE*fp;if((fp=fopen("test.txt","r"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}ch=fgetc(fp);while(ch!=EOF){line=line+1;while(ch!='\n'&&ch!=EOF){temp=temp+1;ch=fgetc(fp);}if(temp>number){number=temp;x=line;}if(ch!=EOF)ch=fgetc(fp);temp=0;}printf("number=%dline=%d\n",number,x);fclose(fp);}3、10個實型數(shù)據(jù)以二進(jìn)制的形式存放在一個文件中，將它們逆序讀出，取三位小數(shù)后以字符形式存入一個新的文件中。例2.txt1001111例2.txt10011111101111111111111111例1.txt1111.0011111.0111111.1111111.1#include"stdio.h"#include"stdlib.h"main(){charaa[40],a;intline,i,number=0;FILE*fp_1,*fp_2;if((fp_1=fopen("1.txt","r"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}if((fp_2=fopen("2.txt","w"))==NULL){puts("\nThisfilecannotbeopened");exit(0);}fscanf(fp_1,"%s",aa);while(a!=EOF){line=strlen(aa);for(i=line-1;i>=0;i--){if(aa[i]!='.'){fputc(aa[i],fp_2);number=number+1;}if(number==3){fputc('',fp_2);number=0;}}fputc('\n',fp_2);number=0;a=fgetc(fp_1);fscanf(fp_1,"%s",aa);}fclose(fp_1);fclose(fp_2);}注:本其實是一道變化很多的題，比如把逆序讀出二進(jìn)制數(shù)每八位轉(zhuǎn)換成一個ASCII碼來存儲高位不足補零等。4、將用輸入的5個學(xué)生的學(xué)號和成績以結(jié)構(gòu)體的形式存入新建的文件，然后讀取該文件，將成績在80分段（大于等于80而小于90）的學(xué)生的學(xué)號和相應(yīng)的成績打印出來。本題其實是第1題與前一節(jié)第2題的綜合，是一道基本的語法練習(xí)題，請讀者自行完成。第四章數(shù)據(jù)結(jié)構(gòu)第一節(jié)線性表結(jié)構(gòu)1、[題目]一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是多少？[解答]第一個元素占地址100和101，依此類推第5個占地址108和109，所以答案為1082、[題目]已知一維數(shù)組a[4]的地址為1000，二維數(shù)組b[3,2]的地址為2000，數(shù)組只存儲的數(shù)據(jù)類型為integer,問數(shù)組a[15]和b[5,3](按行方式儲存,二維數(shù)組為5行5列)的地址各為多少?[解答]一個integer數(shù)據(jù)(-32768~32767)需要16位二進(jìn)制存儲，所以a[15]的地址為1022。3、[題目]采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度是多少？[解答]查找第一個元素的查找長度為1，第二個的長度為2…第n個的長度為n,所以總共長度為，平均長度為。4、[題目]設(shè)有一個棧，元素進(jìn)棧的次序為A,B,C,D,E。試問能否得到出棧序列：

1)C,E,A,B,D2)C,B,A,D,E3)D,C,A,B,E4)A,C,B,E,D5)A,B,C,D,E[解答]‘<’代表進(jìn)棧，‘>’代表出棧,下同1)不能

2)可以按<,<,<,>,>,>,<,<,>,>的順序

3)不能

4)可以按<,>,<,<,>,>,<,<,>,>的順序

5)可以按<，>，<，>，<，>，<，>，<，>的順序5、[題目]設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5和e6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧S的容量至少應(yīng)該是多少?[解答]根據(jù)棧先進(jìn)后出以及隊列先進(jìn)先出的特征，可知進(jìn)出棧的順序為<,<,>,<,<,>,>,<,<,>,>,>。某一時刻，棧中最多有3個元素，所以棧S的容量至少為36、[題目]設(shè)將整數(shù)1.2.3.4依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序加入其中，請回答下述問題：

(1)若入、出棧次序為Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),

Pop(),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop()表示出棧)？

(2)能否得到出棧序列1423和1432？并說明為什么不能得到或者如何得到。(3)請分析1,2,3,4的24種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。[解答](1)1,3,2,4

(2)按照<,>,<,<,<,>的順序可以得到1,4的輸出，此時棧中還有2,3。接著只能輸出3,2而不能輸出2,3。

(3)經(jīng)過觀察可以得到如下結(jié)論：1.一旦棧中輸出了元素n，那么1…n-1這些元素要么已經(jīng)出棧，要么還按從小到大的順序存在棧中；2.輸出元素n后，比n小的未輸出元素只能按從大到小的先后順序輸出。不難得出，可以輸出以下序列：(4,3,2,1)(3,4,2,1)(3,2,4,1)(2,4,3,1)(2,3,4,1)(2,1,4,3)(1,4,3,2)(1,3,4,2)(1,3,2,4)(1,2,4,3)(1,2,3,4)7、[題目]回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。[解答]根據(jù)提示不難完成。源程序：huiwen.pas,huiwen.exe輸入：huiwen.in輸出：huiwen.out輸入為一行待判斷字符，若有數(shù)字仍按字符形式判斷8、[題目]線性表用順序儲存，設(shè)計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后n個元素進(jìn)行整體互換。即將線性表(a1,a2,…am,b1,2b,…bn)改變?yōu)椋?b1,b2,…bn,a1,a2,…am)。[解答]以字符串形式進(jìn)行操作，直接交換。源程序：huhuan.pas,huhuan.exe輸入：huhuan.in輸出：huhuan.out輸入為一行待判斷字符，若有數(shù)字仍按字符形式判斷9、[題目]寫出下列中綴表達(dá)式的后綴形式：

(1)A*B*C(2)-A+B-C+D(3)A*B+C(4)(A+B)*D+E/(F+A*D)+C[解答](1)AB*C*

(2)A–B+C–D+

(3)AB*C+

(4)AB+D*EAD*F+/+第二節(jié)樹和二叉樹1、[題目]對于三個結(jié)點A、B、C，有多少種不同的樹？[解答]如圖，直線型的樹由于根結(jié)點中間結(jié)點和末結(jié)點的不同可以有3*2=6種不同的樹如圖，滿二叉樹型由于根結(jié)點不同可以有3種不同的樹(此處沒有考慮左右孩子結(jié)點的不同)。2、[題目]如果一棵樹有n1個度為1的結(jié)點，由n2個度為2的結(jié)點，…，nm個度為m的結(jié)點，則該樹共有多少個終端結(jié)點？[解答]經(jīng)過觀察，可得該樹共有3、[題目]如下圖所示，指出該樹的葉結(jié)點、分支結(jié)點，各個結(jié)點的層次和樹的高度，從結(jié)點A到結(jié)點H的路徑長度是多少，有多少條長度為2的路徑。[解答]結(jié)點ABCDEFGH葉結(jié)點NNNNYYYY分支YYYYNNNN層次12233334度22210000樹的高度4，從A到H的路徑長度是3，有8條長度為2的路徑4、[題目]對如下一棵二叉樹，其中序遍歷的序列是什么?[解答]樹的遍歷規(guī)則：先序中左右；中序左中右；后序左右中；答案：DGBACEF5、[題目]已知一棵二叉樹的前序遍歷結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試畫出這棵二叉樹。[解答]由樹的遍歷特征求得，答案如圖6、[題目]將下圖所示的樹轉(zhuǎn)化為二叉樹。將轉(zhuǎn)化得到的二叉樹，按前序、中序、后序進(jìn)行遍歷，寫出遍歷的結(jié)點序列。[解答]根據(jù)樹的轉(zhuǎn)換規(guī)則(P155)可得如圖

前序遍歷：GHKILEBCDFJA

中序遍歷：KHLIGEDJFCBA

后序遍歷：KLIHGEJFDCAB7、[題目]寫出一個將二叉樹左右孩子交換的算法程序。[解答]解法一用順序結(jié)構(gòu)(P153,以層順序)讀取和儲存二叉樹，‘0’代表空結(jié)點，交換后以順序結(jié)構(gòu)輸出。輸入輸出文件均為一行帶空格的大寫字母序列。

源程序：Programchangetree(input,output);varff:text;tree:array[1..100]ofchar;c:char;k,m,n:integer;Procedureinit;beginassign(ff,'changetree.in');reset(ff);fillchar(tree,sizeof(tree),'0');n:=0;k:=0;whilenot(eoln(ff))dobegininc(k);read(ff,tree[k],c);iftree[k]<>'0'theninc(n);end;close(ff);end;Procedurechange(i:integer);varj:integer;l:char;beginj:=i*2;fork:=ito(i*3div2-1)dobegindec(j);l:=tree[k];tree[k]:=tree[j];tree[j]:=l;end;ifi*2<=nthenchange(i*2);end;Proceduremain;beginchange(2);assign(ff,'changetree.out');rewrite(ff);m:=0;k:=1;repeatbeginwrite(ff,tree[k],'');iftree[k]<>'0'theninc(m);inc(k);enduntilm>=n;close(ff);end;begininit;main;end.解法二用指針形式儲存二叉樹后，利用循環(huán)使每個分支結(jié)點的左右指針交換。Typepoint=^node;

node=record

c：char

;left,right：point

;end

;Varhead:point;//head頭指針Procedurechange(p:point);

var

q,r:point;

begin

q:=p;r:=q^.left;

q^.left:=q^.right;q^.right:=r;if(r^.left<>nil)or(r^.right<>nil)

thenchange(r);

r:=q^.left;

if(r^.left<>nil)or(r^.right<>nil)

thenchange(r);

end;

…begin

…

change(head);

…

end.8、[題目]什么是哈夫曼樹？用給出的一組權(quán)值{4,2,3,5,7,8}，建立一棵哈夫曼樹。[解答]哈夫曼樹的定義：帶權(quán)路徑長度最短的樹哈夫曼樹的建立規(guī)則：

現(xiàn)將數(shù)組從小到大排序，再將它們依次填充到哈夫曼樹的葉結(jié)點上，而且越小的數(shù)深度約大。

源程序：Programbuild(input,output);varff:text;i,j,m,n:integer;tree:array[1..100,1..2]ofinteger;Procedureinit;beginassign(ff,'build.in');reset(ff);n:=0;whilenot(eoln(ff))dobegininc(n);read(ff,tree[n,1]);end;close(ff);fori:=1ton-1doforj:=i+1tondoiftree[i,1]>tree[j,1]thenbeginm:=tree[i,1];tree[i,1]:=tree[j,1];tree[j,1]:=m;end;end;Proceduremain;beginfori:=2tondobegintree[i-1,2]:=tree[i,1];inc(tree[i,1],tree[i-1,1]);end;assign(ff,'build.out');rewrite(ff);write(ff,tree[n,1],'');fori:=n-1downto1dowrite(ff,tree[i,2],'',tree[i,1],'');close(ff);end;begininit;main;end.第三節(jié)圖1、[題目]已知圖的鄰接矩陣表示，請畫出它所對應(yīng)的圖。[解答]2、[題目]對如下圖所示的有向圖，請寫出該圖的鄰接矩陣。[解答]

0代表沒有距離

1代表有通路

代表沒有通路3、[題目]寫出如下帶權(quán)無向圖的鄰接矩陣，并求出其最小生成樹。[解答]4、[題目]對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為多少；所有鄰接表中的結(jié)點總數(shù)是多少？[解答]由于每一個連接表結(jié)點數(shù)是其邊數(shù)的二倍減一，所以所有鄰接表中的結(jié)點總數(shù)是2e-n。5、[題目]畫出1個頂點2個頂點3個頂點4個頂點和5個頂點的無向完全圖。試證明在n個頂點的無向完全圖中，邊的條數(shù)為n(n-1)/2。[解答]n個頂點兩兩連接，任意選出兩個頂點形成一條不同的邊。所以邊的總數(shù)是6、[題目]對如下所示的圖中，分別寫出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法，從A點出發(fā)遍歷的結(jié)果序列。[解答]深度優(yōu)先：ABCDFEGH廣度優(yōu)先：ABEFHCDG7、[題目]設(shè)無向圖G如圖所示，試給出

(1)圖的鄰接矩陣

(2)該圖的鄰接表

(3)該圖的多重鄰接表

(4)從V0出發(fā)的“深度優(yōu)先”遍歷序列

(5)從V0出發(fā)的“廣度優(yōu)先”遍歷序列(1)[解答](2)(3)略

(4)V0V1V3V2V4V6V5

(5)V0V1V2V3V4V5V6第四節(jié)查找1、[題目]對線性表進(jìn)行二分查找時，要求線性表必須是：

A.以順序方式存儲

B.以鏈接方式存儲

C.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序

D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序[解答]答案：C2、[題目]有一個有序表為{1,3,9,12,32,41,45,62,75,82,88,95,100}，當(dāng)二分查找值為82的結(jié)點時，多少次比較后查找成功？[解答]根據(jù)二分查找的過程，比較的次序是：4582所以經(jīng)過2次比較3、[題目]設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11,表中已有4個結(jié)點。

addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空

如果用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是多少？[解答]哈希表如下，見P169開放定址法。答案：8123456789101112131415386184494、[題目]設(shè)哈希長度為10，哈希函數(shù)為H(K)=Kmod7,關(guān)鍵字集合為{15,10,12,20,25,35,31,15},請給出開放地址方法和拉鏈方法所構(gòu)造得到的哈希表結(jié)構(gòu)。[解答]地址0123456789開放法35153110251220拉連法3515(10,31)2512205、[題目]試設(shè)計遞歸二分(折半)查找算法。[解答]見P169，用開放地址法處理沖突。通過mod函數(shù)的運用，將longint型數(shù)據(jù)轉(zhuǎn)換成相應(yīng)的初始地址，再用一個過程來解決沖突。算法如下：Varn:longint;Hash:array[1..999]oflongint;Functionfind(i:longint):integer;

varj:string;

k,l,m:integer;beginstr(i,j);k:=length(j);l:=0;

whilek>0dobeginval(copy(j,1,3),m);inc(l,m);

k:=k-3;end;l:=lmod1000;find:=l;end;Proceduresearch(i,t:integer;j:longint);

varp:integer;beginifHash[i]=jthenwriteln(i)

elsebeginp:=(i+t)mod999;

search(p,t+1,j);end;end;beginreadln(n);search(find(n),1,n);end;遞歸二分（折半）查找算法。intBserach(elemtypea[],elemtypex,intlow,inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;if(x==a[mid])returnmid;if(x<a[mid])return(Bserach(a,x,low,mid-1));elsereturn(Bserach(a,x,mid+1,high));}第五節(jié)、排序1、什么是內(nèi)排序?什么是外排序?什么排序方法是穩(wěn)定的?什么排序方法是不穩(wěn)定的?在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲順序，稱為內(nèi)排序；

在排序過程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。

若對任意的數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵字進(jìn)行排序，若相同關(guān)鍵字元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)定的。

直接插入排序、冒泡排序、歸并排序是穩(wěn)定的排序方法；而簡單選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。2、希爾排序、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法,試舉例說明。簡單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。

比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩(wěn)定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。3、已知序列{17,18,60,40,7,35,73,65,85},請給出采用冒泡排序法對該序列作升序排序時的每一趟的結(jié)果。參照例4.18進(jìn)行排序4、已知序列{10,18,4,3,6,12,1,9,18,8},請給出采用希爾排序法對該序列作升序排序時的每一趟的結(jié)果(增量為5,2,1)。參照例4.17進(jìn)行排序5、已知序列{10,18,4,3,6,12,1,9,18,8},請給出采用歸并排序法對該序列作升序排序時的每一趟的結(jié)果。參照例4.22進(jìn)行排序6、設(shè)待排序的排序碼序列為{17,18,60,40,7,35,73,65,85},試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。

(1)直接插入排序(2)折半半插入排序(3)快速排序

(4)直接選擇排序(5)堆排序參照教材中示例7、判定下列序列是否為堆。如果不是，則請把它們調(diào)整為堆。（1）{100，86，48，73，35，39，42，57，66，21}（2）{12，70，33，65，24，56，48，92，86，33}略8、對于冒泡排序算法，什么樣的輸入數(shù)據(jù)使得算法的執(zhí)行時間最長？若初始文件是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值。9、試寫出折半排序的算法?；舅枷朐O(shè)在順序表中有一個對象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經(jīng)排好序的對象。在插入V[i]時,利用折半搜索法尋找V[i]的插入位置。折半插入排序的算法：typedefintSortData;voidBinInsSort(SortDataV[],intn){SortDatatemp;intLeft,Right;for(inti=1;i<n;i++){Left=0;Right=i-1;temp=V[i];while(Left<=Right){ intmid=(Left+Right)/2; if(temp<V[mid])Right=mid-1; elseLeft=mid+1;}for(intk=i-1;k>=Left;k--)V[k+1]=V[k];//記錄后移V[Left]=temp;//插入}}第五章常用算法第一節(jié)算法評估思考與練習(xí)P179：1、O(log2n)，O(nlog2n)2、O(nlog2n),O(n2)3、O(n2),O(n2),O(n2),O(nlog2n),O(nlog2n),O(nlog2n)第二節(jié)枚舉法思考與練習(xí)P182：1、算法分析：本題可以枚舉123到329之間的所有三位i，如果i、2*i、3*i這三個數(shù)中包含的9個數(shù)字剛好是1到9則輸出i、2*i、3*i。為了記錄1到9這9個數(shù)字在i、2*i、3*i中是否出現(xiàn)過，程序中用一個一維數(shù)組a。a[d]=1表示數(shù)字d在i、2*i、3*i這三個數(shù)中出現(xiàn)過，a[d]=0則表示未出現(xiàn)。2、提示：如果采取逐條路線枚舉的方法去試探，那么由于本題中的展室數(shù)目并不大，所以是可以行得通的。第三節(jié)遞推算法思考與練習(xí)P185：1、樓梯有N級臺階,上樓可以一步上一階,也可以一步上二階。試編程序計算共有多少種不同走法?算法分析：到第N級臺階時問題在第N-1級樓梯處上一級臺階或在第N-2級臺階樓梯處上兩級臺階，由此可得出遞推表達(dá)式a(n)=a(n-1)+a(n-2)。程序代碼：#include<stdio.h>main(){longf3,f2,f1;inti,n;printf("pleaseinputthesteps:");scanf("%d",&n);f1=1;f2=2;for(i=3;i<=n;i++){f3=f1+f2;f1=f2;f2=f3;}printf("%ld\n",f3);}2、宰相的麥子：相傳古印度宰相達(dá)依爾，是國際象棋的發(fā)明者。有一次，國王因為他的貢獻(xiàn)要獎勵他，問他想要什么。達(dá)依爾說：“只要在國際象棋棋盤上（共64格）擺上這么些麥子就行了：第一格一粒，第二格兩粒，……，后面一格的麥子總是前一格麥子數(shù)的兩倍，擺滿整個棋盤，我就感恩不盡了。”國王一想，這還不容易，剛想答應(yīng)，如果你這時在國王旁邊站著，你會不會勸國王別答應(yīng)，為什么？請輸出棋盤上擺放的麥子總數(shù)。假如一萬顆麥子有一斤重，請問共有多少噸麥子？算法分析：國際象棋棋盤每一格子上的麥子粒數(shù)都是上一格麥子粒數(shù)的兩倍，遞推式為a=2*a，總的麥子數(shù)為264-1粒，簡單算出其結(jié)果為20位的數(shù)值，可用高精度加法來遞推算出結(jié)果。3、階乘計算(用遞推)：寫一個程序，對給定的n（n≤100），計算并輸出n的階乘n！的全部有效數(shù)字。算法分析：用遞推法求解階乘函數(shù)的思路是：先求fac(1)，再求fac(2)，…,直到求出fac(n)，其程序代碼可參考第四節(jié)高精度計算中思考練習(xí)的第2題。4、一輛重型卡車欲穿過1000公里的沙漠，卡車耗油為1升/公里，卡車總載油能力為500公升，顯然卡車裝一次油是過不了沙漠的，因此司機(jī)必須設(shè)法在沿途建立幾個儲油點，使卡車順利穿越沙漠，試問司機(jī)如何建立這些儲油點？每一儲油點應(yīng)存多少油才能使卡車以消耗最少汽油代價通過沙漠？算法分析：可用倒推法解決該問題，最后一個貯油點應(yīng)離終點500公里，貯油量為500公升，這樣卡車可以順利到達(dá)終點，建立離終點的第二個貯油點時要為下一個貯油點往返運送500公升油，因此第二個貯油點應(yīng)貯存1000公升油，有500公升油消耗在送油的路途中，第二個貯油點離終點的距離為S=500+500/3，如此得出離終點第N個貯油點的遞推式S(N)=S(N-1)+500/(2N-1)，如此倒推下去一直到起點。#include<stdio.h>main(){intk;/*貯油點位置序號*/floatd,d1;/*d:累計終點至當(dāng)前貯油點的距離,d1:i=n至始點的距離*/floatoil[10],dis[10];inti;printf("NO.distance(k.m.)\toil(l.)\n");k=1;d=500;/*從i=1處開始向始點倒推*/dis[1]=500;oil[1]=500;do{k=k+1;d=d+500/(2*k-1);dis[k]=d;oil[k]=oil[k-1]+500;}while(!(d>=1000));dis[k]=1000;/*置始點至終點的距離值*/d1=1000-dis[k-1];/*求i=n處至始點的距離*/oil[k]=d1*(2*k+1)+oil[k-1];/*求始點藏油量*/for(i=0;iprintf("%d\t%f\t%f\t\n",i,1000-dis[k-i],oil[k-i]);}5、有一堆桃子和8只猴子，第1只猴子把桃子平均分成3堆后，還剩1個，它吃了剩下的一個，并拿走一堆。第2、3只猴子和第1只一樣。第4只猴子把桃子平均分成5堆后，還剩1個，它吃了剩下的一個，并拿走一堆。5、6、7、8和第4只一樣。問：至少還剩多少個桃子？原來至少有多少個桃子？算法分析：可采用枚舉嘗試與倒推的方法來解決該問題。從最后一只猴子起倒推能夠分成5堆且還剩一個的桃子數(shù)，每次以5個遞增枚舉滿足條件的桃子數(shù)直到第一只猴子能夠分成3堆還剩一個桃子為止。第四節(jié)高精度計算思考與練習(xí)P189：1、用高精度算法求菲波那契數(shù)列的前2000項。算法分析：該題采用遞推算法，因為要求到前2000項，具體計算時要用高精度加法實現(xiàn)。#include<stdio.h>main(){inta1[500],a2[500],a3[500];intjw,he,i,j,k;for(i=1;i<=500;i++){a1[i]=a2[i]=a3[i]=0;}a2[1]=1;jw=0;printf("%d\n",0);printf("%d\n",1);for(i=3;i<=2000;i++){for(j=1;j<=500;j++){he=a1[j]+a2[j]+jw;jw=he/10;a3[j]=he%10;}j=500;while(a3[j]==0)j--;for(k=j;k>=1;k--)printf("%d",a3[k]);printf("\n");for(j=1;j<=500;j++){a1[j]=a2[j];a2[j]=a3[j];}}}2、求1!+2!+3!+……+n!之和。(n≤500)算法分析：該題可以用高精度乘法來實現(xiàn)，也可以用高精度加法來實現(xiàn)，下面的程序代碼采用高精度加法來實現(xiàn)。#include<stdio.h>main(){ints[1200],a[1200],b[1200];intjw,he,i,j,k,n;scanf("%d",&n);for(i=1;i<=1200;i++){s[i]=a[i]=b[i]=0;}a[1]=1;for(i=1;i<=n;i++){for(j=1;j<=1200;j++)b[j]=0;for(j=1;j<=i;j++){jw=0;for(k=1;k<=1200;k++){he=a[k]+b[k]+jw;jw=he/10;b[k]=he%10;}}for(k=1;k<=1200;k++)a[k]=b[k];jw=0;for(k=1;k<=1200;k++){he=s[k]+b[k]+jw;jw=he/10;s[k]=he%10;}}j=1200;while(s[j]==0)j--;for(k=j;k>=1;k--)printf("%d",s[k]);printf("\n");}3、求數(shù)列1+1/2+1/3+…+1/n之和。(n≤500，和的值精確到小數(shù)點后500位)算法分析：本題采用高精度加法和兩個單精度數(shù)的除法(結(jié)果采用高精度存儲)來實現(xiàn)。#include<stdio.h>main(){inta[601],b[601];intn,i,j,g,s;scanf("%d",&n);for(i=0;i<=600;i++){a[i]=b[i]=0;}for(i=1;i<=n;i++){a[0]=1/i;g=1%i;for(j=1;j<=600;j++){s=g*10;g=s%i;a[j]=s/i;}s=g=0;for(j=600;j>=0;j--){s=a[j]+b[j]+g;g=s/10;b[j]=s%10;}}printf("%d.",b[0]);for(j=1;j<=500;j++){printf("%d",b[j]);}printf("\n");}4、試根據(jù)以下公式來設(shè)計程序求圓周率n，結(jié)果精確到小數(shù)點后指定的m位。算法分析：這道題目涉及到高精度加法，高精度乘法與兩個高精度數(shù)的除法運算，大家可以借助前面所列出的知識點來解決，代碼較長，略去。第五節(jié)模擬法思考與練習(xí)P190：1、機(jī)場檢票進(jìn)站口進(jìn)一個人的時間至少為12秒鐘，至多為30秒鐘，某個航班有n個乘客，試求這n個人進(jìn)站所需要的進(jìn)站時間，如要求排隊的n個乘客在30分鐘內(nèi)全部進(jìn)站，則一般需要安排多少個檢票口。(要求模擬m次，輸出m次各自所需時間和需要安排的檢票口數(shù))算法分析：用計算機(jī)可以模擬很多事件處理的過程。該題用隨機(jī)函數(shù)產(chǎn)生n個12-30之間的隨機(jī)數(shù)12+random(19)，累加起來即為所需要的進(jìn)站時間。再根據(jù)時間來安排檢票口的數(shù)量即可。2、玩撲克牌是人們最為喜愛的文娛活動之一。玩撲克牌有許多種不同的玩法，常見的有橋牌、升級等。請設(shè)計程序模擬升級時撲克牌的發(fā)牌過程，把含大小王在內(nèi)的54張牌隨機(jī)分發(fā)給4家，每家12張，底牌留6張。算法提示：可以簡單模擬產(chǎn)生1~54之間的隨機(jī)數(shù)，依次放到集合里面并用一個對應(yīng)的數(shù)組來存儲，如遇重復(fù)產(chǎn)生的數(shù)則跳過直到54個數(shù)全部產(chǎn)生為止，然后再根據(jù)要求分配這些數(shù)即可。第六節(jié)分治算法思考與練習(xí)P1941、算法描述：…e0<-1e-38函數(shù)f｛f<-exp(x*ln(2))+exp(x*ln(3))-exp(x*ln(4))}{a<-1b<-2repeatx<-(a+b)/2fa<-f(a)fx<-f(x)iffa*fx<0thenb<-x/*在A、X內(nèi)有解*/elsea<-xuntil(abs(b-a)<e0)｝…2、分析：我們可以先把比賽時間表看作一個2m*2A=A1BCD當(dāng)規(guī)模減半到只有兩個選手時，矩陣為：1221由于各種情況性質(zhì)一致，只是規(guī)模不同，參照這一矩陣，可知A1與A的關(guān)系：A1BBA1當(dāng)有4個選手參加比賽時，由于A、A1的關(guān)系可以得出下列矩陣：1221344334431221由于有這一規(guī)律，于是可以得到一種比賽順序。也就是將（2k*2k）矩陣分成了四塊，每塊是（2k－1*2k－1）的矩陣，它是對稱的（如A1與A1，B與B）。然后分別把A1、B分成四塊，一直劃分到（2*2）矩陣為止，這時就可定出每個元素的值，再按對稱關(guān)系構(gòu)成比賽表。問題就被簡化成了設(shè)計一個對稱矩陣。第七節(jié)回溯算法思考與練習(xí)P198：1、有n個0和n個1排成一個數(shù)列，要求從該數(shù)列的第一個位置到數(shù)列的任意一個位置時數(shù)字0的個數(shù)總是大于或等于數(shù)字1的個數(shù)，求所有可能的排列。算法分析：該題與書中排除買票問題類似，可以用數(shù)組a來存儲數(shù)列的排隊情況。先將a數(shù)組的各元素值賦為-1。從a[1]的值加1開始試探、搜索。試探時b[0]用于存儲0的個數(shù)，b[1]用于存儲1的個數(shù)。某個元素a[i]的值是否符合要求需滿足以下條件：①(a[i]=0)&&(b[0]<n)/*如果第i個元素值為0，而隊列中0的個數(shù)不到n個時表示可以放入*/②(a[i]=1)&&(b[1]<b[0])/*如果第i個元素值為1，而隊列中1的個數(shù)小于0的個數(shù)時表示可以放入*/如果滿足條件，則將條件判斷變量pd的值設(shè)為真。Pd值為真后將該元素加入，然后判斷i的值是否為總的人數(shù)，如等于則輸出這組排列，如否則將i值加1后繼續(xù)判斷下一個人的情況。如果不滿足條件，則a[i]的值加1后繼續(xù)試探，如果0,1兩個值均不符合要求，則回溯，返回上一個元素a[i-1]，將其值加1后繼續(xù)嘗試。樣例程序如下：#include<stdio.h>main(){inti,j,n,pd,a[100],b[2];scanf("%d",&n);n=n/2;i=1;for(i=1;i<=2*n;i++)a[i]=-1;/*先將a數(shù)組各元素的值全部置為-1，用-1來表示未放數(shù)的初始狀態(tài)*/i=1;b[0]=0;b[1]=0;/*將計零和計1個數(shù)的計數(shù)器b[0]、b[1]清零，i表示數(shù)組a的當(dāng)前元素位置*/do{do{ pd=0;/*能否放數(shù)的判斷變量*/ a[i]++;/*數(shù)組a的當(dāng)前元素值加1，開始試探*/ if(a[i]==0&&b[0]<n)/*元素值為零時能不能放的判定條件*/ {b[0]++;pd=1;} if(a[i]==1&&b[1]<b[0])/*元素值為1時能不能放的判定條件*/ {b[1]++;pd=1;} }while((pd!=1)&&(a[i]!=2));if(pd==1)/*pd值為1時表示能放*/ if(i==2*n)/*如果已經(jīng)放到最后一個數(shù)了，則輸出這一組排列*/ {for(j=1;j<=2*n;j++) printf("%2d",a[j]); printf("\n"); } elsei++;/*繼續(xù)放下一個位置*/else/*a[i]為2時表示已經(jīng)試探了0,1后均不成立，此時回溯*/{b[1]--;/*回溯時假設(shè)a[i]的值從1變?yōu)?時試探的1已經(jīng)被計數(shù)*/ a[i]=-1;/*將當(dāng)前元素還原為未放值時的初始狀態(tài)*/ i--;/*回到上一個位置*/ if(a[i]==0)/*上一個位置值為0時的處理*/ {b[0]--; if(b[1]==b[0])b[1]++; }}}while(i!=0);}注意回溯時上一位會進(jìn)行加1計算，因此不管上一位是0還是1，對應(yīng)的計數(shù)器都應(yīng)減少1，即有i--,b[a[i]]--。如果上一位的值為0，在加1時會有這樣一種情況，這個1在b[1]=b[0]時不會被計數(shù)而直接又加1后向前回溯，回溯時的dec(b[1])語句會導(dǎo)致b[1]被多減一次。為避免這種情況，在此處加一判斷，(a[i]=0)&&(b[1]=b[0])時b[1]++。2、用L型骨牌去覆蓋一個m×n個方格所組成的長方形，請問怎樣覆蓋才能使長方形上留下的方格數(shù)最少？算法分析：采用回溯搜索的方法來處理該問題?？偸谴嬖谝环N最優(yōu)的布局，使得每一塊骨牌至少有兩條邊與其他骨牌的邊或者棋盤的邊相鄰，處理時可先設(shè)初始狀態(tài)時的棋盤為空；再取棋盤的左上角，放第一張骨牌，使骨牌的一個頂點與棋盤的角的頂點重和。第一張骨牌有橫放和豎放兩種情況，因此得到兩個初始狀態(tài)的子結(jié)點；對于當(dāng)前的狀態(tài)，已經(jīng)放置的骨牌的圍成一個多邊形（其中可能有空隙），該多邊形的邊和棋盤的邊又將棋盤中的空地圍成一個多邊形，下面只要在這個多邊形內(nèi)部貼著邊放置一個骨牌就可以了。3、有一個由n×n個方格組成的迷宮，入口和出口分別在迷宮的左上角和右上角。用迷宮格子中的0表示此路可通，1表示此路不通。走迷宮時，從某點出發(fā)可沿8個方向前進(jìn)，請找出給出迷宮中從入口到出口的通路。算法分析：給出從某點出發(fā)沿4個方向前進(jìn)的提示，8個方向與之類似。在二維迷宮里面，從出發(fā)點開始，每個點按四鄰域算，按照右，上，左，下的順序搜索下一落腳點，有路則進(jìn)，無路即退，前點再從下一個方向搜索，即可構(gòu)成一有序模型。下表為10×10迷宮{1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1}從出發(fā)點開始