數(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ì)算機(jī)中不方便存儲和處理，例如，一個(gè)大樓中4部電梯在軟件控制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫明細(xì)表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲、處理、變換。因此，數(shù)據(jù)(data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)

2、算機(jī)程序識別和處理的符號的集合。在計(jì)算機(jī)中，信息必須以數(shù)據(jù)的形式出現(xiàn)。1-2什么是數(shù)據(jù)結(jié)構(gòu)？有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個(gè)方面？【解答】數(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ì)算機(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ì)算機(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ì)算機(jī)存儲器中的實(shí)現(xiàn)(亦稱為映像)，它是依賴于計(jì)算機(jī)的，是數(shù)據(jù)的物理視圖。數(shù)據(jù)的操作是定義于數(shù)據(jù)邏輯結(jié)構(gòu)上的一組運(yùn)算，每種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(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ù)成員都處于一個(gè)序列中，有且僅有一個(gè)開始成員和一個(gè)終端成員，并且所有數(shù)據(jù)成員都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。例如，一維數(shù)組、線性表等

4、就是典型的線性結(jié)構(gòu)非線性結(jié)構(gòu)的特點(diǎn)是：一個(gè)數(shù)據(jù)成員可能有零個(gè)、一個(gè)或多個(gè)直接前驅(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è)構(gòu)造函數(shù)：缺省的構(gòu)造函數(shù)沒有參數(shù)；第二個(gè)構(gòu)造函數(shù)將雙精度浮點(diǎn)數(shù)賦給復(fù)數(shù)的實(shí)部，虛部置為0;第三個(gè)構(gòu)造函數(shù)將兩個(gè)雙精度浮點(diǎn)數(shù)分別賦給復(fù)數(shù)的實(shí)部和虛部。(3)定義獲取和修改復(fù)數(shù)的實(shí)部和虛部，以及+、-、*、/等運(yùn)算的成員函數(shù)。(4)定義重載的流函數(shù)來輸出一個(gè)復(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_# 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ù)只置實(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&operator(ostream&os,complex&c);友元函數(shù)：重載private:doubleRe,Im;復(fù)數(shù)的實(shí)部與虛

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

8、plex&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/(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&o

9、perator(ostream&os,complex&ob)友元函數(shù)：重載,將復(fù)數(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個(gè)特性是什么？試根據(jù)這些特性解釋算法與程序的區(qū)別。【解答】通常，定義算法為“為解決某一特定任務(wù)而規(guī)定的一個(gè)指令序列?！币粋€(gè)算法應(yīng)當(dāng)具有以下特性：有輸入。一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開始運(yùn)算前給予算法的量。這些輸入取自于

10、特定的對象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。有輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。確定性。算法的每一步都應(yīng)確切地、無歧義地定義。對于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。有窮性。一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說，它們原則上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。算法和程序不同，程序可以不滿足上述的特性（4）。例如，一個(gè)操作系統(tǒng)在用戶未使用前一直處于“等待”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無休止地運(yùn)行，直到系統(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時(shí),jT.n(n1)2i=2時(shí)，n(n1),n(n1)=1.2n(n+1)22Ji=3時(shí),n(n+1)+zj=1+3)n(n+1)、2J此外，算法是面向功能的，通常用面向過程的方式描述；程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣堋?-7設(shè)

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時(shí)i=1kM2求出滿足此不等式的k值，即為語句i=i+j的程序步數(shù)。1-8試編寫一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組AarraySize的第n個(gè)數(shù)組元素中，0narraySize或者對于某一個(gè)k(0kmaxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理方(1)用cerr及exit(1)語句來終止執(zhí)行并報(bào)告錯(cuò)誤；(2)用返回整數(shù)函數(shù)值0,1來實(shí)現(xiàn)算法，以區(qū)別是

13、正常返回還是錯(cuò)誤返回；(3)在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(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ù)的適當(dāng)?shù)胤讲迦胗?jì)算count的語句: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é)束時(shí)的count值是多少？(4)使用執(zhí)行頻度的方法計(jì)算這個(gè)程序的程序步數(shù)，畫出程序步數(shù)統(tǒng)計(jì)表?！窘獯稹?1)在適當(dāng)?shù)牡胤讲迦胗?jì)算count語句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)所得到的程序化簡。化簡后的程序與原來的程序有相同的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。當(dāng)n為偶數(shù)時(shí)，count=3*(n/2)+3*(n/2)+3=3*n+3當(dāng)n為奇數(shù)時(shí)，count=3*(n+1)/2)+3*(nT)/2)+3=3*n+3(4)使用執(zhí)行頻度的方法計(jì)算程序的執(zhí)行步數(shù)，畫出程序步數(shù)統(tǒng)計(jì)表：行號程序語句一次執(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個(gè)整數(shù))開始時(shí)假定data0最大與其他整數(shù)逐個(gè)比較/m記錄新的最大者)【方案2(此程序可修改循環(huán)終止變量擴(kuò)大到intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;idatam)m=i;returndatam;)改為“”，可得求最小整數(shù)函數(shù)。(2)求3個(gè)整數(shù)中的最小整數(shù)的函數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】intmin(inta,intb,intc)intm=a;if(bm)m=b;if(cm)m=c;returnm;)【方案2(此程序可修改循環(huán)終止變量擴(kuò)大到n個(gè)整數(shù))intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;i3;i+)if(dataidatam)m=i;returndatam;)求3個(gè)整數(shù)中具有中間值的整數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】intmid(inta,intb,intc)intml=a,m2;if(bml)m2=ml