數(shù)據(jù)結(jié)構(gòu)習(xí)題解析第1章

1、第1章緒論本章主要討論貫穿和應(yīng)用于整個(gè)數(shù)據(jù)結(jié)構(gòu)課程始終的基本概念和性能分析方法。學(xué)習(xí)本章的內(nèi)容，將為后續(xù)章節(jié)的學(xué)習(xí)打下良好的基礎(chǔ)。本章復(fù)習(xí)的要點(diǎn)：1、基本知識(shí)點(diǎn)要求理解的概念包括：數(shù)據(jù)，數(shù)據(jù)對(duì)象，數(shù)據(jù)元素或數(shù)據(jù)成員，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型，數(shù)據(jù)抽象，抽象數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)的抽象層次，面向?qū)ο?，?duì)象與類的關(guān)系，類的繼承關(guān)系，對(duì)象間的消息通信等。需要對(duì)各個(gè)概念進(jìn)行區(qū)分與比較。例如，按照面向?qū)ο蠼＜夹g(shù)的要求，把建立對(duì)象類作為一個(gè)層次，把建立對(duì)象間的關(guān)系（即建立結(jié)構(gòu)）作為另外的層次。因此，在軟件開(kāi)發(fā)中做數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)時(shí)，不但要設(shè)計(jì)對(duì)象關(guān)，類的屬性，類的操作，還要建立類的實(shí)例之間的關(guān)系。從這個(gè)角度考慮，把數(shù)

2、據(jù)結(jié)構(gòu)定義為數(shù)據(jù)對(duì)象及對(duì)象中各數(shù)據(jù)成員之間關(guān)系的集合是合理的。又例如，類class或struct與C中的結(jié)構(gòu)類型struct的區(qū)別在于前者不但有對(duì)象的狀態(tài)描述（數(shù)據(jù)成員），還加入了操作（成員函數(shù)），描述對(duì)象的行為，這樣可以體現(xiàn)一個(gè)完整的實(shí)體概念，而后者不行。再例如，傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)概念從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和相關(guān)操作等3個(gè)方面進(jìn)行討論。它反映了數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的不同層次：邏輯結(jié)構(gòu)屬于問(wèn)題解決范疇，物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式。但在面向?qū)ο箝_(kāi)發(fā)模式中，本課程中涉及的數(shù)據(jù)結(jié)構(gòu)都屬于基本數(shù)據(jù)結(jié)構(gòu)，但有的屬于應(yīng)用級(jí)的數(shù)據(jù)結(jié)構(gòu)，如稀疏矩陣，字符串，棧與隊(duì)列，優(yōu)先級(jí)隊(duì)列，圖等；有的屬于實(shí)現(xiàn)級(jí)的

3、數(shù)據(jù)結(jié)構(gòu)，如數(shù)組，鏈表，堆，索引，散列表等。2、有關(guān)算法的概念和簡(jiǎn)單的算法性能分析方法算法的5個(gè)特性表明算法的實(shí)現(xiàn)屬于面向過(guò)程的開(kāi)發(fā)模式，即傳統(tǒng)的輸入-計(jì)算-輸出'模式。算法的應(yīng)用要求明確算法的時(shí)間和空間代價(jià)。因此，必須理解算法的定義和算法的5個(gè)特性，掌握簡(jiǎn)單的時(shí)間復(fù)雜度估計(jì)和空間復(fù)雜度估計(jì)方法（不討論程序復(fù)雜性）。3、描述語(yǔ)言要求數(shù)據(jù)結(jié)構(gòu)的描述既要體現(xiàn)算法的邏輯，又要體現(xiàn)面向?qū)ο蟮母拍?，需要一種能夠兼有面向?qū)ο蠛兔嫦蜻^(guò)程雙重特性的描述語(yǔ)言。傳統(tǒng)的Pascal語(yǔ)言和C語(yǔ)言只是面向過(guò)程的語(yǔ)言，不能適應(yīng)面向?qū)ο蟮拈_(kāi)發(fā)模式。因此，采用C+語(yǔ)言描述。要求學(xué)員基本掌握C+語(yǔ)言的基本才念和用C+語(yǔ)

4、言編寫(xiě)應(yīng)用程序的基本技術(shù)。例如，用類定義抽象數(shù)據(jù)類型的方式，定義模板類、抽象類的方法，函數(shù)與參數(shù)的定義，建立類（公有、私有）繼承的方法，例外與異常的處理等等，都需要掌握。二、難點(diǎn)與重點(diǎn)1、基本概念：理解什么是數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的抽象層次。2、面向?qū)ο蟾拍睿豪斫馐裁词菙?shù)據(jù)類型、抽象數(shù)據(jù)類型、數(shù)據(jù)抽象和信息隱蔽原則。了解什么是面向?qū)ο?。抽象?shù)據(jù)類型的封裝性Coad與Yourdon定義：面向?qū)ο?對(duì)象+類+繼承+通信。面向?qū)ο笙到y(tǒng)結(jié)構(gòu)的穩(wěn)定性面向?qū)ο蠓椒ㄖ埸c(diǎn)在于應(yīng)用問(wèn)題所涉及的對(duì)象3、算法與算法分析：理解算法的定義、算法的特性、算法的時(shí)間代價(jià)、算

5、法的空間代價(jià)。算法與程序的不同之處需要從算法的特性來(lái)解釋算法的正確性是最主要的要求算法的可讀性是必須考慮的程序的程序步數(shù)的計(jì)算與算法的事前估計(jì)程序的時(shí)間代價(jià)是指算法的漸進(jìn)時(shí)間復(fù)雜性度量三、教材中習(xí)題的解析1-1什么是數(shù)據(jù)？它與信息是什么關(guān)系？【解答】什么是信息？廣義地講，信息就是消息。宇宙三要素（物質(zhì)、能量、信息）之一。它是現(xiàn)實(shí)世界各種事物在人們頭腦中的反映。此外，人們通過(guò)科學(xué)儀器能夠認(rèn)識(shí)到的也是信息。信息的特征為：可識(shí)別、可存儲(chǔ)、可變換、可處理、可傳遞、可再生、可壓縮、可利用、可共享。什么是數(shù)據(jù)？因?yàn)樾畔⒌谋憩F(xiàn)形式十分廣泛，許多信息在計(jì)算機(jī)中不方便存儲(chǔ)和處理，例如，一個(gè)大樓中4部電梯在軟件控

6、制下調(diào)度和運(yùn)行的狀態(tài)、一個(gè)商店中商品的在庫(kù)明細(xì)表等，必須將它們轉(zhuǎn)換成數(shù)據(jù)才能很方便地在計(jì)算機(jī)中存儲(chǔ)、處理、變換。因此，數(shù)據(jù)（data）是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。在計(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ù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三方面的內(nèi)容：1數(shù)據(jù)成員以及它們相互之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)；數(shù)據(jù)成員極其

7、關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)，簡(jiǎn)稱為存儲(chǔ)結(jié)構(gòu)；3施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)不是一碼事，是與計(jì)算機(jī)存儲(chǔ)無(wú)關(guān)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題中抽象出來(lái)的數(shù)據(jù)模型，是數(shù)據(jù)的應(yīng)用視圖。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(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)先級(jí)隊(duì)列等；非線性結(jié)構(gòu)包括樹(shù)、圖

8、等、這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？【解答】線性結(jié)構(gòu)的特點(diǎn)是：在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于一個(gè)序列中，有且僅有一個(gè)開(kāi)始成員和一個(gè)終端成員，并且所有數(shù)據(jù)成員都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。例如，一維數(shù)組、線性表等就是典型的線性結(jié)構(gòu)非線性結(jié)構(gòu)的特點(diǎn)是：一個(gè)數(shù)據(jù)成員可能有零個(gè)、一個(gè)或多個(gè)直接前驅(qū)和直接后繼。例如，樹(shù)、圖或網(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ù)沒(méi)有參數(shù)；第二個(gè)構(gòu)造函數(shù)將雙精度浮點(diǎn)數(shù)賦給復(fù)數(shù)的實(shí)部，虛部置為0;第三個(gè)構(gòu)造函數(shù)將兩個(gè)雙精度浮點(diǎn)數(shù)分別

9、賦給復(fù)數(shù)的實(shí)部和虛部。(3)定義獲取和修改復(fù)數(shù)的實(shí)部和虛部，以及+、-、*、/等運(yùn)算的成員函數(shù)。(4)定義重載的流函數(shù)來(lái)輸出一個(gè)復(fù)數(shù)?！窘獯稹砍橄髷?shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型。抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)。/在頭文件complex.h中定義的復(fù)數(shù)類#ifndef_complex_h_#define_complex_h_#include<iostream.h>classcomlexpublic:不帶參數(shù)的構(gòu)造函數(shù)只置實(shí)部的構(gòu)造函數(shù)分別置實(shí)部、虛部的構(gòu)造函數(shù)取復(fù)數(shù)實(shí)部取復(fù)數(shù)虛部修改復(fù)數(shù)實(shí)部修改復(fù)數(shù)虛部complex()Re=Im=0;

10、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&operator=(complex&ob)Re=ob.Re;Im=ob.Im;復(fù)數(shù)賦值complex&operator+(complex&ob);重載函數(shù)：復(fù)數(shù)四則運(yùn)算complex&operator(complex&o

11、b);complex&operator*(complex&ob);complex&operator/(complex&ob);friendostream&operator<<(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&qu

12、ot;complex&complex:operator+(complex&ob)重載函數(shù)：復(fù)數(shù)加法運(yùn)算。complexresult;result.Re=Re+ob.Re;result.Im=Im+ob.Im;returnresult;)complex&complex:operator-(complex&ob)重載函數(shù)：復(fù)數(shù)減法運(yùn)算complexresult;result.Re=Reob.Re;result.Im=Imob.Im;returnresult;)complex&complex:operator*(complex&ob)重載函數(shù)：復(fù)數(shù)乘法

13、運(yùn)算complexresult;result.Re=Re*ob.ReIm*ob.Im;result.Im=Im*ob.Re+Re*ob.Im;returnresult;)complex&complex:operator/(complex&)重載函數(shù)：復(fù)數(shù)除法運(yùn)算doubled=ob.Re*ob.Re+ob.Im*ob.Im;complexresult;result.Re=(Re*ob.Re+Im*ob.Im)/d;result.Im=(Im*ob.ReRe*ob.Im)/d;returnresult;)friendostream&operator<<(ost

14、ream&os,complex&ob)友元函數(shù)：重載<<,將復(fù)數(shù)ob輸出到輸出流對(duì)象os中。returnos<<ob.Re<<(ob.Im>=0.0)?"+"-:"<<abs(ob.Im)<<"i")1-5用歸納法證明：(1)皿)，n_1im2<2_n(n1)(2n1)(2) ,'6，ni1-ixn1-1/c(3) -x,x：1,n_0 丑x-1【證明】略1-6什么是算法？算法的5個(gè)特性是什么？試根據(jù)這些特性解釋算法與程序的區(qū)別。【解答】通常，定義算

15、法為為解決某一特定任務(wù)而規(guī)定的一個(gè)指令序列。”一個(gè)算法應(yīng)當(dāng)具有以下特性： 有輸入。一個(gè)算法必須有0個(gè)或多個(gè)輸入。它們是算法開(kāi)始運(yùn)算前給予算法的量。這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語(yǔ)句由外部提供，也可以使用賦值語(yǔ)句在算法內(nèi)給定。 有輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。確定性。算法的每一步都應(yīng)確切地、無(wú)歧義地定義。對(duì)于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。有窮性。一個(gè)算法無(wú)論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。有效性。算法中每一條運(yùn)算都必須是足夠基本的。就是說(shuō)，它們?cè)瓌t上都能精確地執(zhí)行，甚至人們僅用筆和紙做有限次運(yùn)算就能完成。算法和程序不同，程序

16、可以不滿足上述的特性(4)。例如，一個(gè)操作系統(tǒng)在用戶未使用前一直處于等待”的循環(huán)中，直到出現(xiàn)新的用戶事件為止。這樣的系統(tǒng)可以無(wú)休止地運(yùn)行，直到系統(tǒng)停工。此外，算法是面向功能的，通常用面向過(guò)程的方式描述；程序可以用面向?qū)ο蠓绞酱罱ㄋ目蚣堋?-7設(shè)n為正整數(shù)，分析下列各程序段中加下劃線的語(yǔ)句的程序步數(shù)。(1) for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)cij=0.0;for(intk=1;k<=n;k+)cim=cij+aik*bkj;)inti=1,j=1;while(i<=n&&j<=n)1 =i+1;j=j+i

17、;(2)x=0;y=0;for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)for(intk=1;k<=j;k+)x=x+y;(4)inti=1;dofor(intj=1;j<=n;j+)i=i+j;while(i<100+n);【解答】(2)nnn:二1i1j=1k=1nij:二匚1iWjWk丑n,21丁.I一I二2i11n(n1)(2n1)1n(n1)_n(n1)(n2)26226時(shí),時(shí),時(shí),時(shí),=2,=3,=4,=5,j=j+i=1+2=2+1_,j=j+i=(2+1)+3=3+1+2,j=j+i=(3+1+2)+4=4+1+2+3,

18、j=j+i=(4+1+2+3)+5=5+1+2+3+4,)i=k時(shí)，i=k+1,j=j+i=(k+1)+(1+2+3+4+kj=k1%i三ni1kk1k23k3=_n解出滿足上述不等式的k值，即為語(yǔ)句i=i+1的程序步數(shù)。i=1時(shí)，i=1+£j=1+n(n+1)j42i=2時(shí)，i/+nl/jJ+nhn.+zK；<2JjJ2)212/i=3時(shí),i='；+2但a1+£j=1+3如5、I2/JI2)一般地，i=k時(shí)i=1+kn(n+1)c100+n,2求出滿足此不等式的k值，即為語(yǔ)句i=i+j的程序步數(shù)。1-8試編寫(xiě)一個(gè)函數(shù)計(jì)算n!*2n的值，結(jié)果存放于數(shù)組Aarr

19、aySize的第n個(gè)數(shù)組元素中，0<n<arraySize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxInt,則當(dāng)n>arraySize或者對(duì)于某一個(gè)k(0<k<n),使得k!*2k>maxInt時(shí)，應(yīng)按出錯(cuò)處理?？捎腥缦氯N不同的出錯(cuò)處理(1)用cerr<<及exit(1)語(yǔ)句來(lái)終止執(zhí)行并報(bào)告錯(cuò)誤；(2)用返回整數(shù)函數(shù)值0,1來(lái)實(shí)現(xiàn)算法，以區(qū)別是正常返回還是錯(cuò)誤返回；(3)在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來(lái)區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)，并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。【解答】#include"iostr

20、eam.h"#definearraySize100#defineMaxInt0x7fffffffintcalc(intT,intn)inti,edge=MaxInt/n/2;T0=1;if(n!=0)for(i=1;i<n;i+)Ti=Ti-1*i*2;if(Ti>edge)return0;)Tn=Tn-1*n*2;)cout<<"T"<<n<<"="<<Tn<<endl;return1;voidmain()intAarraySize;inti;for(i=0;i<a

21、rraySize;i+)if(!calc(A,i)cout<<"failedat"<<i<<"."<<endl;break;)1-9(1)在下面所給函數(shù)的適當(dāng)?shù)胤讲迦胗?jì)算count的語(yǔ)句：voidd(ArrayElementx,intn)inti=1;doxi+=2;i+=2;while(i<=n);i=1;while(i<=(n/2)xi+=xi+1;i+;count(2)將由(1)所得到的程序化簡(jiǎn)。使得化簡(jiǎn)后的程序與化簡(jiǎn)前的程序具有相同的值。(3)程序執(zhí)行結(jié)束時(shí)的count值是多少？(4)使

22、用執(zhí)行頻度的方法計(jì)算這個(gè)程序的程序步數(shù)，畫(huà)出程序步數(shù)統(tǒng)計(jì)表。【解答】(1)在適當(dāng)?shù)牡胤讲迦胗?jì)算count語(yǔ)句voidd(ArrayElementx,intn)inti=1;count+;doxi+=2;count+;i+=2;count+;count+;/針又：while語(yǔ)句while(i<=n);i=1;count+;while(i<=(n/2)count+;/針又：while語(yǔ)句xi+=xi+1;count+;i+;count+;)count+;/針對(duì)最后一次while語(yǔ)句)(2)將由所得到的程序化簡(jiǎn)。化簡(jiǎn)后的程序與原來(lái)的程序有相同的count值:voidd(ArrayElem

23、entx,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ù)時(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ù)，畫(huà)出程序步數(shù)統(tǒng)計(jì)表：行號(hào)程序語(yǔ)句一次執(zhí)行步數(shù)執(zhí)行頻度程序步數(shù)1voidd(ArrayElementx,intn)0102inti=1;1113do0n+1)/204xi+=2;

24、1n+1)/24n+1)/25i+=2;1n+1)/2S+1)/26while(i<=n);1n+1)/2n+1)/27i=1;1118while(i<=(n/2)13/2+1Jjn/2+1J9xi+=xi+1;1jn/2j6/210i+;1jn/2j6/2110jn/2j012010(n豐0)3n+3四、其他練習(xí)題1-10填空題（A）由某一數(shù)據(jù)對(duì)象和該對(duì)象中各個(gè)數(shù)據(jù)成員間的關(guān)系組成。依據(jù)所有數(shù)據(jù)成員之間關(guān)系的不同，（A）分為兩大類：（B）和（C）。在（B）中的各個(gè)數(shù)據(jù)成員依次排列在一個(gè)線性序列中；（C）的各個(gè)數(shù)據(jù)成員不再保持在一個(gè)線性序列中，每個(gè)數(shù)據(jù)成員可能與零個(gè)或多個(gè)其他數(shù)據(jù)成

25、員發(fā)生聯(lián)系。根據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的(D)和(E)。(D)是面向問(wèn)題的，(E)是面向計(jì)算機(jī)的?！窘獯稹緼:數(shù)據(jù)結(jié)構(gòu)B:線性結(jié)構(gòu)C:非線性結(jié)構(gòu)D:邏輯結(jié)構(gòu)E:存儲(chǔ)結(jié)構(gòu)1-11判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前打臚，否則打父。(1)數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(2)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對(duì)象與對(duì)象中數(shù)據(jù)元素之間關(guān)系的集合。(3)數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對(duì)象。(4)數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。(5)算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者是通用的?！窘獯稹?1)(2)(3)(4)(5)1-12判斷下列敘述的對(duì)錯(cuò)。如果正確，在題前打也否則打父。(1)所謂

26、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。(2)同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。(3)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。(4)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。(5)從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)?！窘獯稹?1) (2)(3)(4)(5)1-13填空題算法是一個(gè)有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。它應(yīng)當(dāng)具有輸入、輸出、(A)、有窮性和可執(zhí)行性等特性。算法效率的度量分為(B)和(C)。(B)主要通過(guò)在算法的某些部位插裝時(shí)間函數(shù)來(lái)測(cè)定算法完成某一規(guī)定功能所需的時(shí)

27、間。而(C)不實(shí)際運(yùn)行算法，它是分析算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的時(shí)間復(fù)雜性。程序所需的存儲(chǔ)空間包含兩個(gè)部分(D)和(E)。(D)空間的大小與輸入輸出數(shù)據(jù)的個(gè)數(shù)多少，數(shù)值大小無(wú)關(guān)；(E)空間主要包括其大小與問(wèn)題規(guī)模有關(guān)的成分變量所占空間，引用變量所占空間，以及遞歸棧所用的空間，還有在算法運(yùn)行過(guò)程中動(dòng)態(tài)分配和回收的空間?！窘獯稹緼:確定性B:事后測(cè)量C:事前估計(jì)D:固定部分E:可變部分1-14有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，試畫(huà)出它們分別對(duì)應(yīng)的圖形表示(當(dāng)出現(xiàn)多個(gè)關(guān)系時(shí)，對(duì)每個(gè)關(guān)系畫(huà)出相應(yīng)的結(jié)構(gòu)圖)，并指出它們分別屬于何種結(jié)構(gòu)。(2) A=(K,R),其中K=a1,a2,a3,a4,R=(3

28、) B=(K,R),其中K=a,b,c,d,e,f,g,h,R=r,r=<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>C=(K,R),其中K=a,b,c,d,e,f,g,h,R=r,r=<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>(4) D=(K,R),其中K=1,2,3,4,5,6,R=r,r=(1,2),(2,3),(2,4),(3,4),(3,5),

29、(3,6),(4,5),(4,6)【解答】1-15單選題(1) 一個(gè)數(shù)組元素ai與的表示等價(jià)。A：*(a+i)B:a+iC:*a+iD：&a+i(2)對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是不同則不是重載函數(shù)。A:參數(shù)類型B:參數(shù)個(gè)數(shù)C:函數(shù)類型(3)若需要利用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為參數(shù)A:指針B:引用C:值(4)下面程序段的時(shí)間復(fù)雜度為。for(inti=0;i<m;i+)for(intj=0;j<n;j+)a皿=i*j;A:O(m2)B：O(n2)C:O(m*n)D：O(m+n)(5)執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為。for(inti=1;i<=n;

30、i+)for(intj=1;j<=i;j+)S;A:n2B：n2/2C:n(n+1)D：n(n+1)/2(6)下面算法的時(shí)間復(fù)雜度為。intf(unsignedintn)if(n=0|n=1)return1;elsereturnn*f(n-1);)A：O(1)B：O(n)C：O(n2)D：O(n!)【解答】(1) A(2)C(3)B(4)C(5)D(6)B1-16填空題(1)數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、和四種。(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。(3)在線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)中，直接前驅(qū)和直接后繼結(jié)點(diǎn)之間分別存在著、和的聯(lián)系。(4) 一種抽象數(shù)據(jù)類型包括和兩個(gè)部分。(5)當(dāng)一個(gè)傳值型形式

31、參數(shù)所占的體積較大時(shí)，應(yīng)最好說(shuō)明為,以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。(6)當(dāng)需要用一個(gè)形式參數(shù)直接改變對(duì)應(yīng)實(shí)際參數(shù)的值時(shí)，則該形式參數(shù)應(yīng)說(shuō)明為(7)在函數(shù)中對(duì)引用型形式參數(shù)的修改就是對(duì)相應(yīng)的修改，而對(duì)型形式參數(shù)的修改只局限在該函數(shù)的內(nèi)部，不會(huì)反映到對(duì)應(yīng)的實(shí)際參數(shù)上。(8)當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí)，則應(yīng)在程序文件中包含頭文件，當(dāng)需要進(jìn)行文件I/O操作時(shí)，則應(yīng)在程序文件中包含頭文件。(9) 一個(gè)記錄r理論上占有的存儲(chǔ)空間的大小等于所有域,實(shí)際上占有的存儲(chǔ)空間的大小即記錄長(zhǎng)度為。(10) 一個(gè)數(shù)組a所占有的存儲(chǔ)空間的大小即數(shù)組長(zhǎng)度為,下標(biāo)為i的元素ai的存儲(chǔ)地址為,或者為。(11) 函數(shù)重

32、載要求、或有所不同。(12)對(duì)于雙目操作符，其重載函數(shù)(非成員函數(shù))帶有個(gè)參數(shù)，其中至少有一個(gè)為的類型。(13)若對(duì)象ra和rb中至少有一個(gè)是屬于用戶定義的類型，則執(zhí)行ra=rb時(shí)，需要調(diào)用重載函數(shù)，該函數(shù)的第一個(gè)參數(shù)應(yīng)與的類型相同，第二個(gè)參數(shù)應(yīng)與的類型相同。(14)從一維數(shù)組an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為,輸出一個(gè)二維數(shù)組bmn中所有元素值的時(shí)間復(fù)雜度為。(15)在下面程序段中，s=s+p語(yǔ)句的執(zhí)行次數(shù)為,p*=j語(yǔ)句的執(zhí)行次數(shù)為,該程序段的時(shí)間復(fù)雜度為。inti=0,s=0;while(+i<=n)intp=1;for(intj=1;j<=i;j+)p*=j;s=

33、s+p;)(16)一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n),其數(shù)量級(jí)表示為?！窘獯稹?1)集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)(次序無(wú)先后)(2)順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)(次序無(wú)先后)(3)1:1、1:N、M:N(或者1對(duì)1,1對(duì)N,M對(duì)N)(4)數(shù)據(jù)、操作(次序無(wú)先后)(5)引用型(6)引用型(7)實(shí)際參數(shù)的值、傳值型(8) iostream.h,fstream.h(9)長(zhǎng)度之和，sizeof(r)(10) sizeof(a)、a+i、(char*)a+i*sizeof(ai)(11)參數(shù)類型、參數(shù)個(gè)數(shù)、排列次序(次序無(wú)先后)(12)二、用戶定義(

34、13) intoperator=、ra、rb(14) O(n)、O(m*n)(15) n、n(n+1)/2、O(n2)(16) O(n)1-17試計(jì)算以下程序所有語(yǔ)句的總執(zhí)行次數(shù)。(1)非遞歸的求和程序floatsum(floata,intn)floats=0.0;for(inti=0;i<n;i+)s+=ai;returns;)(2)遞歸的求和程序floatrsum(floata,intn)if(n<=0)returna0;elsereturnrsum(a,n-1)+an-1;)【解答】2n+3(2)2n+11-18設(shè)有3個(gè)值大小不同的整數(shù)a、b和c,試編寫(xiě)一個(gè)C+函數(shù)，求(1)

35、其中值最大的整數(shù)；(2)其中值最小的整數(shù)；(3)其中位于中間值的整數(shù)?！窘獯稹?1)求3個(gè)整數(shù)中的最大整數(shù)的函數(shù)【方案1】intmax(inta,intb,intc)intm=a;if(b>m)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;i<3;i+)if(datai>datam)m=i;returndatam;)(2)求3個(gè)整數(shù)中的最小整數(shù)的函數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】intmin(inta,

36、intb,intc)intm=a;if(b<m)m=b;if(c<m)m=c;returnm;開(kāi)始時(shí)假定data0最大與其他整數(shù)逐個(gè)比較/m記錄新的最大者"改為“；可得求最小整數(shù)函數(shù)。）【方案2（此程序可修改循環(huán)終止變量擴(kuò)大到n個(gè)整數(shù)）intmax(inta,intb,intc)intdata3=a,b,c);intm=0;for(inti=1;i<3;i+)if(datai<datam)m=i;returndatam;)(3)求3個(gè)整數(shù)中具有中間值的整數(shù)可將上面求最大整數(shù)的函數(shù)稍做修改,【方案1】開(kāi)始時(shí)假定data0最小與其他整數(shù)逐個(gè)比較/m記錄新的最小者&

37、quot;改為“；可得求最小整數(shù)函數(shù)。intmin(inta,intb,intc)intm1=a,m2;if(b<m1)m2=m1;m1=b;elsem2=b;if(c<m1)m2=m1;m1=c;elseif(c<m2)m2=c;returnm2;【方案2(此程序可修改循環(huán)終止變量擴(kuò)大到intmid(inta,intb,intc)intdata3=a,b,c;intm1=0,m2=-1;for(inti=1;i<3;i+)n個(gè)整數(shù)尋求次小元素）/m1指示最小整數(shù)，m2指示次小整數(shù)與其他整數(shù)逐個(gè)比較if(datai<datam1)m2=ml;ml=i;原來(lái)最小變?yōu)?/p>

38、次小，ml指示新的最小elseif(m2=-1|datai<datam2)m2=i;/m2記錄新的次小者returndatam2;1-19用C+函數(shù)編寫(xiě)一個(gè)算法，比較兩個(gè)整數(shù)a和b的大小，對(duì)于a>b,a=b,a<b這三種不同情況應(yīng)分別返回”=和”字符。并求其時(shí)間復(fù)雜度。【解答】charCompare(inta,intb)if(a>b)return'>'elseif(a=b)return'='elsereturn'<'時(shí)間復(fù)雜度為O(1)1-20假定一維整型數(shù)組an中的每個(gè)元素值均在0,200區(qū)間內(nèi)，用C+函數(shù)編寫(xiě)一個(gè)算法，分別統(tǒng)計(jì)出落在0,20),20,50),50,80),80,130),1130,200等各區(qū)間內(nèi)的元素個(gè)數(shù)。intCount(inta,intn,intc)用數(shù)組c5保存統(tǒng)計(jì)結(jié)果intd5=20,50,80,130,201;inti,j;for(i=0;i<5;i+)ci=0;for(i=0;i<n;i+)if(ai<0|ai>200)return0;for(j=0;j<5;j+)if(ai<dj)break;cj+;return1;【解答】用來(lái)保存各統(tǒng)計(jì)區(qū)間的上限給數(shù)組c5中的每個(gè)元素賦初值0/