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

PAGEPAGE59《信息學(xué)競(jìng)賽指導(dǎo)》參考答案信息技術(shù)基礎(chǔ)計(jì)算機(jī)與信息社會(huì)選擇題：1、B2、C3、D4、B5、B6、D7、C計(jì)算機(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ì)算機(jī)系統(tǒng)由硬件和軟件兩大部分的組成。2、CAD是“計(jì)算機(jī)輔助設(shè)計(jì)”（Computer

Aided

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

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

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

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

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

(1)若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),

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

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

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

(3)經(jīng)過(guò)觀(guān)察可以得到如下結(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”不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。[解答]根據(jù)提示不難完成。源程序：huiwen.pas,huiwen.exe輸入：huiwen.in輸出：huiwen.out輸入為一行待判斷字符，若有數(shù)字仍按字符形式判斷8、[題目]線(xiàn)性表用順序儲(chǔ)存，設(shè)計(jì)一個(gè)算法，用盡可能少的輔助存儲(chǔ)空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行整體互換。即將線(xià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、[題目]寫(xiě)出下列中綴表達(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é)樹(shù)和二叉樹(shù)1、[題目]對(duì)于三個(gè)結(jié)點(diǎn)A、B、C，有多少種不同的樹(shù)？[解答]如圖，直線(xiàn)型的樹(shù)由于根結(jié)點(diǎn)中間結(jié)點(diǎn)和末結(jié)點(diǎn)的不同可以有3*2=6種不同的樹(shù)如圖，滿(mǎn)二叉樹(shù)型由于根結(jié)點(diǎn)不同可以有3種不同的樹(shù)(此處沒(méi)有考慮左右孩子結(jié)點(diǎn)的不同)。2、[題目]如果一棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn)，由n2個(gè)度為2的結(jié)點(diǎn)，…，nm個(gè)度為m的結(jié)點(diǎn)，則該樹(shù)共有多少個(gè)終端結(jié)點(diǎn)？[解答]經(jīng)過(guò)觀(guān)察，可得該樹(shù)共有3、[題目]如下圖所示，指出該樹(shù)的葉結(jié)點(diǎn)、分支結(jié)點(diǎn)，各個(gè)結(jié)點(diǎn)的層次和樹(shù)的高度，從結(jié)點(diǎn)A到結(jié)點(diǎn)H的路徑長(zhǎng)度是多少，有多少條長(zhǎng)度為2的路徑。[解答]結(jié)點(diǎn)ABCDEFGH葉結(jié)點(diǎn)NNNNYYYY分支YYYYNNNN層次12233334度22210000樹(shù)的高度4，從A到H的路徑長(zhǎng)度是3，有8條長(zhǎng)度為2的路徑4、[題目]對(duì)如下一棵二叉樹(shù)，其中序遍歷的序列是什么?[解答]樹(shù)的遍歷規(guī)則：先序中左右；中序左中右；后序左右中；答案：DGBACEF5、[題目]已知一棵二叉樹(shù)的前序遍歷結(jié)果是ABECDFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試畫(huà)出這棵二叉樹(shù)。[解答]由樹(shù)的遍歷特征求得，答案如圖6、[題目]將下圖所示的樹(shù)轉(zhuǎn)化為二叉樹(shù)。將轉(zhuǎn)化得到的二叉樹(shù)，按前序、中序、后序進(jìn)行遍歷，寫(xiě)出遍歷的結(jié)點(diǎn)序列。[解答]根據(jù)樹(shù)的轉(zhuǎn)換規(guī)則(P155)可得如圖

前序遍歷：GHKILEBCDFJA

中序遍歷：KHLIGEDJFCBA

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

源程序：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.解法二用指針形式儲(chǔ)存二叉樹(shù)后，利用循環(huán)使每個(gè)分支結(jié)點(diǎn)的左右指針交換。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、[題目]什么是哈夫曼樹(shù)？用給出的一組權(quán)值{4,2,3,5,7,8}，建立一棵哈夫曼樹(shù)。[解答]哈夫曼樹(shù)的定義：帶權(quán)路徑長(zhǎng)度最短的樹(shù)哈夫曼樹(shù)的建立規(guī)則：

現(xiàn)將數(shù)組從小到大排序，再將它們依次填充到哈夫曼樹(shù)的葉結(jié)點(diǎn)上，而且越小的數(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、[題目]已知圖的鄰接矩陣表示，請(qǐng)畫(huà)出它所對(duì)應(yīng)的圖。[解答]2、[題目]對(duì)如下圖所示的有向圖，請(qǐng)寫(xiě)出該圖的鄰接矩陣。[解答]

0代表沒(méi)有距離

1代表有通路

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

(1)圖的鄰接矩陣

(2)該圖的鄰接表

(3)該圖的多重鄰接表

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

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

(4)V0V1V3V2V4V6V5

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

A.以順序方式存儲(chǔ)

B.以鏈接方式存儲(chǔ)

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

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

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

如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是多少？[解答]哈希表如下，見(jiàn)P169開(kāi)放定址法。答案：8123456789101112131415386184494、[題目]設(shè)哈希長(zhǎng)度為10，哈希函數(shù)為H(K)=Kmod7,關(guān)鍵字集合為{15,10,12,20,25,35,31,15},請(qǐng)給出開(kāi)放地址方法和拉鏈方法所構(gòu)造得到的哈希表結(jié)構(gòu)。[解答]地址0123456789開(kāi)放法35153110251220拉連法3515(10,31)2512205、[題目]試設(shè)計(jì)遞歸二分(折半)查找算法。[解答]見(jiàn)P169，用開(kāi)放地址法處理沖突。通過(guò)mod函數(shù)的運(yùn)用，將longint型數(shù)據(jù)轉(zhuǎn)換成相應(yīng)的初始地址，再用一個(gè)過(guò)程來(lái)解決沖突。算法如下：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)定的?在排序過(guò)程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱(chēng)為內(nèi)排序；

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

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

直接插入排序、冒泡排序、歸并排序是穩(wěn)定的排序方法；而簡(jiǎn)單選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。2、希爾排序、簡(jiǎn)單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法,試舉例說(shuō)明。簡(jiǎn)單地說(shuō)就是所有相等的數(shù)經(jīng)過(guò)某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，我們就說(shuō)這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。

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

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

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