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

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

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

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

4、；⑷把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中；⑸對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(Access)；⑹對一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(Modify)；⑺對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)；⑻對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)。4、算法分析的目的是什么？算法分析的主要方面是什么？目的：分析算法的效率以求改進(jìn)或?qū)Σ煌乃惴ㄟM(jìn)行比較算法分析的主要方面是：空間復(fù)雜性和時(shí)間復(fù)雜性。5、分析一下程序段的時(shí)間復(fù)雜度，請說明分析的理由或原因。（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，其時(shí)間復(fù)雜度為：O(n)。⑵基本操作的語句頻度為：1+2+3+?+n=n(n-1)/2，其時(shí)間復(fù)雜度為：O(n2)。⑶基本操作的語句頻度為：n，其

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

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

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