數(shù)據(jù)結(jié)構(gòu)習題解析-面向?qū)ο蠓椒ê虲語言描述-殷人昆

1、1-1什么是數(shù)據(jù)？它與信息是什么關系？【解答】什么是信息？廣義地講，信息就是消息。宇宙三要素(物質(zhì)、能量、信息)之一。它是現(xiàn)實世界各種事物在人們頭腦中的反映。此外，人們通過科學儀器能夠認識到的也是信息。信息的特征為：可識別、可存儲、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因為信息的表現(xiàn)形式十分廣泛，許多信息在計算機中不方便存儲和處理，例如，一個大樓中4部電梯在軟件控制下調(diào)度和運行的狀態(tài)、一個商店中商品的在庫明細表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計算機中存儲、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中并被計

2、算機程序識別和處理的符號的集合。在計算機中，信息必須以數(shù)據(jù)的形式出現(xiàn)。1-2什么是數(shù)據(jù)結(jié)構(gòu)？有關數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個方面？【解答】數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間白關系。記為：數(shù)據(jù)結(jié)構(gòu)=D,R。其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關系的有限集合。有關數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三方面的內(nèi)容：數(shù)據(jù)成員以及它們相互之間的邏輯關系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱為數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)成員極其關系在計算機存儲器內(nèi)的存儲表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡稱為存儲結(jié)構(gòu)；施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲不是一碼事，是與計算機存儲無關的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以

3、看作是從具體問題中抽象出來的數(shù)據(jù)模型，是數(shù)據(jù)的應用視圖。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的實現(xiàn)(亦稱為映像)，它是依賴于計算機的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運算，每種數(shù)據(jù)結(jié)構(gòu)都有一個運算的集合。例如搜索、插入、刪除、更新、排序等。1-3數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、棧、隊列、優(yōu)先級隊列等；非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點是什么？【解答】線性結(jié)構(gòu)的特點是：在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于一個序列中，有且僅有一個開始成員和一個終端成員，并且所有數(shù)據(jù)成員都最多有一個直接前驅(qū)和一個直接后繼。例如，一維數(shù)組、線性表等

4、就是典型的線性結(jié)構(gòu)非線性結(jié)構(gòu)的特點是：一個數(shù)據(jù)成員可能有零個、一個或多個直接前驅(qū)和直接后繼。例如，樹、圖或網(wǎng)絡等都是典型的非線性結(jié)構(gòu)。1-4.什么是抽象數(shù)據(jù)類型？試用C+的類聲明定義“復數(shù)”的抽象數(shù)據(jù)類型。要求(1)在復數(shù)內(nèi)部用浮點數(shù)定義它的實部和虛部。(2)實現(xiàn)3個構(gòu)造函數(shù)：缺省的構(gòu)造函數(shù)沒有參數(shù)；第二個構(gòu)造函數(shù)將雙精度浮點數(shù)賦給復數(shù)的實部，虛部置為0;第三個構(gòu)造函數(shù)將兩個雙精度浮點數(shù)分別賦給復數(shù)的實部和虛部。(3)定義獲取和修改復數(shù)的實部和虛部，以及+、-、*、/等運算的成員函數(shù)。(4)定義重載的流函數(shù)來輸出一個復數(shù)。【解答】抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應用問題的數(shù)據(jù)模型。抽象

5、數(shù)據(jù)類型由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關的服務。/在頭文件complex.h中定義的復數(shù)類# ifndef_complex_h_# define_complex_h_# includeclasscomlexpublic:complex()Re=Im=0;complex(doubler)Re=r;Im=0;complex(doubler,doublei)Re=r;Im=i;doublegetReal()returnRe;doublegetImag()returnIm;voidsetReal(doubler)Re=r;voidsetImag(doublei)Im=i;complex&opera

6、tor不帶參數(shù)的構(gòu)造函數(shù)只置實部的構(gòu)造函數(shù)分別置實部、虛部的構(gòu)造函數(shù)取復數(shù)實部取復數(shù)虛部修改復數(shù)實部修改復數(shù)虛部=(complex&ob)Re=ob.Re;Im=ob.Im;復數(shù)賦值重載函數(shù)：復數(shù)四則運算complex&operator+(complex&ob);complex&operator(complex&ob);complex&operator*(complex&ob);complex&operator/(complex&ob);friendostream&operator(ostream&os,complex&c);友元函數(shù)：重載private:doubleRe,Im;復數(shù)的實部與虛

7、部;# endif復數(shù)類complex的相關服務的實現(xiàn)放在C+源文件complex.cpp中# include# include# include“complex.hcomplex&complex:operator+(complex&ob)重載函數(shù)：復數(shù)加法運算。complex*result=newcomplex(Re+ob.Re,Im+ob.Im);return*result;complex&complex:operator-(complex&ob)重載函數(shù)：復數(shù)減法運算complex*result=newcomplex(Re-ob.Re,Imob.Im);return*result;com

8、plex&complex:operator*(complex&ob)重載函數(shù)：復數(shù)乘法運算complex*result=newcomplex(Re*ob.ReIm*ob.Im,Im*ob.Re+Re*ob.Im);return*result;)complex&complex:operator/(complex&)重載函數(shù)：復數(shù)除法運算doubled=ob.Re*ob.Re+ob.Im*ob.Im;complex*result=newcomplex(Re*ob.Re+Im*ob.Im)/d,(Im*ob.Re-Re*ob.Im)/d);return*result;)friendostream&o

9、perator(ostream&os,complex&ob)友元函數(shù)：重載,將復數(shù)ob輸出到輸出流對象os中。returnosob.Re=0.0)?+-:abs(ob.Im);i)1-5用歸納法證明：(1)=2,n_1(1) W2(2) i2=n(n1)(2n1),n_1i16nn1(3) 、xi=x-1,x；1,n_01 ax-1【證明】略1-6什么是算法？算法的5個特性是什么？試根據(jù)這些特性解釋算法與程序的區(qū)別?！窘獯稹客ǔ＃x算法為“為解決某一特定任務而規(guī)定的一個指令序列。”一個算法應當具有以下特性：有輸入。一個算法必須有0個或多個輸入。它們是算法開始運算前給予算法的量。這些輸入取自于

10、特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。有輸出。一個算法應有一個或多個輸出，輸出的量是算法計算的結(jié)果。確定性。算法的每一步都應確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動作都應嚴格地、清晰地規(guī)定。有窮性。一個算法無論在什么情況下都應在執(zhí)行有窮步后結(jié)束。有效性。算法中每一條運算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運算就能完成。算法和程序不同，程序可以不滿足上述的特性（4）。例如，一個操作系統(tǒng)在用戶未使用前一直處于“等待”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運行，直到系統(tǒng)停工。(2)x

11、=0;y=0;for(inti=1;i=n;i+)for(intj=1;j=i;j+)for(intk=1;k=j;k+)x=x+y;)inti=1,j=1;while(i=n&j=n)i=i+1;j=j+i;)(4)inti=1;dofor(intj=1;j=n;j+)i=i+j;while(i3k32解出滿足上述不等式的2k值，即為語句i=i+1的程序步數(shù)。i=1時,jT.n(n1)2i=2時，n(n1),n(n1)=1.2n(n+1)22Ji=3時,n(n+1)+zj=1+3)n(n+1)、2J此外，算法是面向功能的，通常用面向過程的方式描述；程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣堋?-7設

12、n為正整數(shù)，分析下列各程序段中加下劃線的語句的程序步數(shù)。(1)for(inti=1;i=n;i+)for(intj=1;j=n;j+)cij=0.0;for(intk=1;k=n;k+)cij=cij+aik*bkj;般地,i=k時i=1kM2求出滿足此不等式的k值，即為語句i=i+j的程序步數(shù)。1-8試編寫一個函數(shù)計算n!*2n的值，結(jié)果存放于數(shù)組AarraySize的第n個數(shù)組元素中，0narraySize或者對于某一個k(0kmaxInt時，應按出錯處理?？捎腥缦氯N不同的出錯處理方(1)用cerr及exit(1)語句來終止執(zhí)行并報告錯誤；(2)用返回整數(shù)函數(shù)值0,1來實現(xiàn)算法，以區(qū)別是

13、正常返回還是錯誤返回；(3)在函數(shù)的參數(shù)表設置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。試討論這三種方法各自的優(yōu)缺點，并以你認為是最好的方式實現(xiàn)它?！窘獯稹?includeiostream.h#definearraySize100#defineMaxInt0x7fffffffintcalc(intT,intn)inti,value=1;if(n!=0)intedge=MaxInt/n/2;for(i=1;iedge)return0;)value*=n*2;)Tn=value;coutAn=Tnendl;return1;)voidmain()intAarraySize;inti;fo

14、r(i=0;iarraySize;i+)if(!calc(A,i)coutfailedati.endl;break;)1-9(1)在下面所給函數(shù)的適當?shù)胤讲迦胗嬎鉩ount的語句:voidd(ArrayElementx,intn)inti=1;doxi+=2;i+=2;while(i=n);i=1;while(i=(n/2)xi+=xi+1;i+;(2)將由(1)所得到的程序化簡。使得化簡后的程序與化簡前的程序具有相同的count值。(3)程序執(zhí)行結(jié)束時的count值是多少？(4)使用執(zhí)行頻度的方法計算這個程序的程序步數(shù)，畫出程序步數(shù)統(tǒng)計表。【解答】(1)在適當?shù)牡胤讲迦胗嬎鉩ount語句vo

15、idd(ArrayElementx,intn)inti=1;count+;doxi+=2;count+;i+=2;count+;count+;/針又：while語句while(i=n);i=1;count+;while(i=(n/2)count+;/針又：while語句xi+=xi+1;count+;i+;count+;count+;/針對最后一次while語句(2)將由(1)所得到的程序化簡?；喓蟮某绦蚺c原來的程序有相同的count值：voidd(ArrayElementx,intn)inti=1;docount+=3;i+=2;while(i=n);i=1;while(i=(n/2)co

16、unt+=3;i+;count+=3;)(3)程序執(zhí)行結(jié)束后的count值為3n+3。當n為偶數(shù)時，count=3*(n/2)+3*(n/2)+3=3*n+3當n為奇數(shù)時，count=3*(n+1)/2)+3*(nT)/2)+3=3*n+3(4)使用執(zhí)行頻度的方法計算程序的執(zhí)行步數(shù)，畫出程序步數(shù)統(tǒng)計表：行號程序語句一次執(zhí)行步數(shù)執(zhí)行頻度程序步數(shù)1voidd(ArrayElementx,intn)0102inti=1;1113do0Jn+1)/2j04xi+=2;1Jn+1)/2j_(n+1)/25i+=2;1Jn+1)/2j_(n+1)/26while(i=n);1Jn+1)/2j_(n+1)/

17、27i=1;1118while(im)m=b;if(cm)m=c;returnm;n個整數(shù))開始時假定data0最大與其他整數(shù)逐個比較/m記錄新的最大者)【方案2(此程序可修改循環(huán)終止變量擴大到intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;idatam)m=i;returndatam;)改為“”，可得求最小整數(shù)函數(shù)。(2)求3個整數(shù)中的最小整數(shù)的函數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】intmin(inta,intb,intc)intm=a;if(bm)m=b;if(cm)m=c;returnm;)【方案2(此程序可修改循環(huán)終止變量擴大到n個整數(shù))intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;i3;i+)if(dataidatam)m=i;returndatam;)求3個整數(shù)中具有中間值的整數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】intmid(inta,intb,intc)intml=a,m2;if(bml)m2=ml