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

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

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

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

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

5、數(shù)據(jù)類型由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)。/在頭文件complex.h中定義的復(fù)數(shù)類# ifndef_complex_h_# define_complex_h_# include<iostream.h>classcomlexpublic: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)

6、Im=i;complex&operator不帶參數(shù)的構(gòu)造函數(shù)只置實(shí)部的構(gòu)造函數(shù)分別置實(shí)部、虛部的構(gòu)造函數(shù)取復(fù)數(shù)實(shí)部取復(fù)數(shù)虛部修改復(fù)數(shù)實(shí)部修改復(fù)數(shù)虛部=(complex&ob)Re=ob.Re;Im=ob.Im;復(fù)數(shù)賦值重載函數(shù)：復(fù)數(shù)四則運(yùn)算complex&operator+(complex&ob);complex&operator(complex&ob);complex&operator*(complex&ob);complex&operator/(complex&ob);friendostream&ope

7、rator<<(ostream&os,complex&c);友元函數(shù)：重載<<private:doubleRe,Im;復(fù)數(shù)的實(shí)部與虛部;# endif復(fù)數(shù)類complex的相關(guān)服務(wù)的實(shí)現(xiàn)放在C+源文件complex.cpp中# include<iostream.h># include<math.h># include“complex.h"complex&complex:operator+(complex&ob)重載函數(shù)：復(fù)數(shù)加法運(yùn)算。complex*result=newcomplex(Re+ob.Re,I

8、m+ob.Im);return*result;complex&complex:operator-(complex&ob)重載函數(shù)：復(fù)數(shù)減法運(yùn)算complex*result=newcomplex(Re-ob.Re,Imob.Im);return*result;complex&complex:operator*(complex&ob)重載函數(shù)：復(fù)數(shù)乘法運(yùn)算complex*result=newcomplex(Re*ob.ReIm*ob.Im,Im*ob.Re+Re*ob.Im);return*result;)complex&complex:operator/(

9、complex&)重載函數(shù)：復(fù)數(shù)除法運(yùn)算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&operator<<(ostream&os,complex&ob)友元函數(shù)：重載<<,將復(fù)數(shù)ob輸出到輸出流對象os中。returnos<<ob.Re<<(ob.Im>=0.0)?"+"-:&

10、quot;<<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ū)別?！窘獯稹客ǔ?，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個指令序列?！币粋€算法應(yīng)當(dāng)具有以下特性：有輸入。一個算法必須有0個或多個輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。有輸出。一個算法應(yīng)有

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

12、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(i<100+n);【解答】(2)nnn二二二1=n3i1j3k注nijnin=221=、'j;i=1j=1k=1i1j=1i133i212J2y1n(n1)(2n1)1n(n1)n(n1)(n2)2622一6=1時，i=2,j=j+i=1+2=2+1_,=2時，i=3,j=j+i=(2+1)+3=3+1+2.=3時，i=4,

13、j=j+i=(3+1+2)+4=4+1+2+3,=4時，i=5,j=j+i=(4+1+2+3)+5=5+1+2+3+4時,i=k+1,j=j+i=(k+1)+(1+2+3+4+kk1好;k>3k32解出滿足上述不等式的2k值，即為語句i=i+1的程序步數(shù)。i=1時,jT.n(n1)2i=2時，n(n1),n(n1)=1.2'n(n+1)22Ji=3時,n(n+1)+zj=1+3)'n(n+1)、2J此外，算法是面向功能的，通常用面向過程的方式描述；程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣堋?-7設(shè)n為正整數(shù)，分析下列各程序段中加下劃線的語句的程序步數(shù)。(1)for(inti=1

14、;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ù)組元素中，0<n<arraySize。若設(shè)計算機(jī)中允許的整數(shù)的最大值為maxInt,則當(dāng)n>arraySize或者對于某一個k(0<k<n),使得k!*2k>maxInt時，應(yīng)按出錯處理?？捎腥缦氯N不同的出錯處理方(1)用cerr<

15、<及exit(1)語句來終止執(zhí)行并報告錯誤；(2)用返回整數(shù)函數(shù)值0,1來實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯誤返回；(3)在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。【解答】#include"iostream.h"#definearraySize100#defineMaxInt0x7fffffffintcalc(intT,intn)inti,value=1;if(n!=0)intedge=MaxInt/n/2;for(i=1;i<n;i+)value*=i*2;if(value

16、>edge)return0;)value*=n*2;)Tn=value;cout<<"A"<<n<<"="<<Tn<<endl;return1;)voidmain()intAarraySize;inti;for(i=0;i<arraySize;i+)if(!calc(A,i)cout<<"failedat"<<i<<"."<<endl;break;)1-9(1)在下面所給函數(shù)的適當(dāng)?shù)胤讲迦胗嬎鉩o

17、unt的語句: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)在適當(dāng)?shù)牡胤讲迦胗嬎鉩ount語句voidd(ArrayElementx,intn)inti=1;count+;doxi+=2;count+;i+=2;count+;count+;/針又：

18、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)count+=3;i+;count+=3;)(3)程序執(zhí)行結(jié)束后的count值為3n+3。當(dāng)n為偶數(shù)時，count=3*(

19、n/2)+3*(n/2)+3=3*n+3當(dāng)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)/27i=1;1118while(i<=(n/2)1j/2+1-jn/2+1-9xi+=xi+1;11/2

20、?/210i+;11/2?/2110?/2012010(n豐0)3n+3b和c,試求1-10設(shè)有3個值大小不同的整數(shù)a、(1)其中值最大的整數(shù)；(2)其中值最小的整數(shù)；(3)其中位于中間值的整數(shù)?！窘獯稹?1)求3個整數(shù)中的最大整數(shù)的函數(shù)【方案1】intmax(inta,intb,intc)intm=a;if(b>m)m=b;if(c>m)m=c;returnm;n個整數(shù))開始時假定data0最大與其他整數(shù)逐個比較/m記錄新的最大者)【方案2(此程序可修改循環(huán)終止變量擴(kuò)大到intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;i<3;i+)if(datai>datam)m=i;returndatam;)>"改為“<”，可得求最小整數(shù)函數(shù)。