數(shù)據(jù)結構習題解答.pdf

《數(shù)據(jù)結構習題解答.pdf》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、習題一1、簡要回答術語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結構，數(shù)據(jù)類型。數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設計語言中已實現(xiàn)的數(shù)據(jù)結構。數(shù)據(jù)結構：指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結構、存儲結構和數(shù)據(jù)的運算。2、數(shù)據(jù)的邏輯結構？數(shù)據(jù)的物理結構？邏輯結構與物理結構的區(qū)別和聯(lián)系是？

2、元素之間的相互聯(lián)系（關系）稱為邏輯結構。四種基本類型是集合、線性結構、樹型結構、圖狀結構或網(wǎng)狀結構。數(shù)據(jù)結構在計算機中的表示（又稱為映像）稱為數(shù)據(jù)的物理結構，又稱為存儲結構。區(qū)別和聯(lián)系：數(shù)據(jù)的邏輯結構是數(shù)據(jù)間關系的描述，它只抽象地反映數(shù)據(jù)元素之間的邏輯關系，而不管其在計算機中的存儲方式，數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。需要注意以下幾點：邏輯結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關；與數(shù)據(jù)元素的相對位置無關；與所含數(shù)據(jù)元素的個數(shù)無關；與數(shù)據(jù)的存儲無關，他獨立于計算機。數(shù)據(jù)的存儲結構是數(shù)據(jù)邏輯結構在計算機存儲器里的，即數(shù)據(jù)的

3、存儲結構是數(shù)據(jù)及其邏輯結構在計算機中的表現(xiàn)，存儲結構除了存儲數(shù)據(jù)元素之外還必須能隱式或顯式的表示數(shù)據(jù)元素之間的邏輯關系，這樣，在邏輯上相鄰的數(shù)據(jù)元素在存儲結構中就未必相鄰。數(shù)據(jù)的存儲結構分為順序存儲結構和鏈式存儲結構。數(shù)據(jù)的邏輯結構和物理結構是密不可分的兩個方面，一個邏輯結構可表示成多種存儲結構，一個算法的設計取決于所選定的邏輯結構，而算法的實現(xiàn)依賴于所采用的存儲結構。3、數(shù)據(jù)結構的主要運算包括哪些？⑴建立(Create)一個數(shù)據(jù)結構；⑵消除(Destroy)一個數(shù)據(jù)結構；⑶從一個數(shù)據(jù)結構中刪除(Delete)一個數(shù)據(jù)元素

4、；⑷把一個數(shù)據(jù)元素插入(Insert)到一個數(shù)據(jù)結構中；⑸對一個數(shù)據(jù)結構進行訪問(Access)；⑹對一個數(shù)據(jù)結構(中的數(shù)據(jù)元素)進行修改(Modify)；⑺對一個數(shù)據(jù)結構進行排序(Sort)；⑻對一個數(shù)據(jù)結構進行查找(Search)。4、算法分析的目的是什么？算法分析的主要方面是什么？目的：分析算法的效率以求改進或對不同的算法進行比較算法分析的主要方面是：空間復雜性和時間復雜性。5、分析一下程序段的時間復雜度，請說明分析的理由或原因。（1）Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m+

5、+){p*=m;sum+=p;}Return(sum);}（2）Sum2(intn){intsum=0,m,t;For(m=1;m<=n;m++){p=1;For(t=1;t<=m;t++)p*=t;Sum+=p;}Return(sum);}(3)Fact(intn){if(n<=1)return1;Elsereturn(n*fact(n-1));}⑴基本操作的語句頻度為：2n，其時間復雜度為：O(n)。⑵基本操作的語句頻度為：1+2+3+?+n=n(n-1)/2，其時間復雜度為：O(n2)。⑶基本操作的語句頻度為：n，其

6、時間復雜度為：O(n)。習題二1、簡述下列術語：線性表，順序表，鏈表線性表：最常用且最簡單的一種數(shù)據(jù)結構。一個線性表是n個數(shù)據(jù)元素的有限序列。順序表：是指用一組連續(xù)的存儲單元一次存儲線性表中的數(shù)據(jù)元素。物理結構和邏輯結構都相鄰。鏈表：邏輯結構相鄰的數(shù)據(jù)元素物理結構不一定相鄰。采用指針的形式連接起來。2、何時選用順序表，何時選用鏈表作為線性表的存儲結構為宜？各自的主要有缺點是什么？在實際應用中，應根據(jù)具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構，通常有以下幾方面的考慮：（1）基于空間的考慮。當要求存儲的線性表長

7、度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結構為好。（2）基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜；反之，若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結構。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空間中，實現(xiàn)順序存取或(按下標)直接存取。它的存儲效率高，存取速度快。但它的空間大

8、小一經(jīng)定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序(沒有規(guī)定元素進棧順序)，平均需要移動一半(或近一半)元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不