數(shù)據(jù)結(jié)構(gòu)陳明習題答案

1、數(shù)據(jù)結(jié)構(gòu)_陳明_習題答案第1頁共41頁習題一答案習題一答案1填空題（1）數(shù)據(jù)元素的有限集合，k上關系的有限集合（2）順序存儲（連續(xù)），鏈式存儲（不連續(xù)）（3）有窮性，確定性，可行性，輸入，輸出（4）時間復雜度，空間復雜度3簡述下列術語（1）數(shù)據(jù)——是信息的載體，它是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中被計算機程序識別、加工處理的信息的集合。（2）數(shù)據(jù)元素——是數(shù)據(jù)的基本單位，是對一個客觀實體的數(shù)據(jù)描述。一個數(shù)據(jù)元素可以由一個或

2、若干個數(shù)據(jù)項組成。數(shù)據(jù)元素也被稱為結(jié)點或記錄。（3）數(shù)據(jù)對象——具有相同性質(zhì)的數(shù)據(jù)元素的集合就是一個數(shù)據(jù)對象，它是數(shù)據(jù)的一個子集。（4）數(shù)據(jù)結(jié)構(gòu)——數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間的相互關系（即數(shù)據(jù)的組織形式）及在這些數(shù)據(jù)上定義的數(shù)據(jù)運算方法的集合。（5）存儲結(jié)構(gòu)——數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)部的表示或?qū)崿F(xiàn)，又稱為數(shù)據(jù)的物理結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和關系的表示。（6）數(shù)據(jù)類型——是具有相同性質(zhì)的計算機數(shù)據(jù)的集合及定義在這個數(shù)據(jù)集合上

3、的一組操作的總稱。5常用的存儲表示方法有哪幾種？（1）順序存儲方法——該方法是將邏輯上相鄰的結(jié)點存儲在物理位置上也相鄰的存儲單元里，結(jié)點之間的邏輯關系由存儲單元的鄰接關系來表示（也就是說，只存儲結(jié)點的值，不存儲結(jié)點之間的關系），這種存儲表示稱為順序存儲結(jié)構(gòu)。（2）鏈式存儲方法——鏈式存儲方法不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的關系由附加的指針來表示，指針指向結(jié)點的鄰接結(jié)點，這樣將所有結(jié)點串聯(lián)在一起，稱為鏈式存儲結(jié)構(gòu)。（3）

4、索引存儲方法——索引存儲是在存儲結(jié)點信息的同時，再建立一個附加的索引表，然后利用索引表中索引項的值來確定結(jié)點的實際存儲單元地址。（4）散列存儲方法——散列存儲的基本思想是根據(jù)結(jié)點的關鍵字直接計算出結(jié)點的存儲地址。7舉例說明一下數(shù)據(jù)結(jié)構(gòu)和算法的關系。通過公式：程序=數(shù)據(jù)結(jié)構(gòu)算法我們可以比較直觀地看出二者的關系，即數(shù)據(jù)結(jié)構(gòu)（包個完整的程序括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)）的設計和算法的編寫是程序設計的兩個關鍵步驟，一就是由一套合理的數(shù)據(jù)結(jié)構(gòu)和建立在該結(jié)

5、構(gòu)上的算法構(gòu)成的。具體的說：在進行程序設計之前我們首先要為待處理的數(shù)據(jù)設計一個合理的邏輯結(jié)構(gòu)，進而為之設計一種適合的存儲結(jié)構(gòu)，因為光有邏輯結(jié)構(gòu)是不夠的，只有存儲結(jié)構(gòu)才是與計算機語言直接相關的！有了這一套前期準備，我們才能在這個基礎上設計算法，用一種計算機語言去處理這些數(shù)據(jù)，最終達到程序設計的目的。當然，隨著邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的不同，我們設計的算法也會有所差別，這在以后的學習中會體會到。下面通過一個簡單的例子說明這種關系。假設我們要設計一

6、個兩個n階方陣相乘的程序：已知兩個n階方陣A和B，我們要計算它們的乘積，得到一個新的n階方陣C。那么在設計這個程序之前首先想到得就是設計一種邏輯結(jié)構(gòu)表示方陣，這里我們用二維數(shù)組表示它們，因為二維數(shù)組最能直觀地表示這種結(jié)構(gòu)；有了邏輯結(jié)構(gòu)了自然還要為之設計一種存儲結(jié)構(gòu)，這里我們選擇順序存儲方法，因為C語言對這種存儲結(jié)構(gòu)給予了很好的支持，例如定義一個n階實型的二維數(shù)組A只要用floatA[n][n]這條語句就可以了，C語言在內(nèi)存種為之分配了一

7、個nn長度的順序存儲空間（注意：C語言默認二維數(shù)組是按行優(yōu)先存儲的），是不是很方便？有了這些準備，我們就可以設計算法進行計算了，其算法算法如下：voidmatrixmult(floatA[n][n]floatB[n][n]floatC[n][n])intijkfloatxf(i=0i10000）哪個程序?qū)\行時間有保證？Ab.N值較小（N1000）時，哪一個程序?qū)\行時間有更好的保證？Bc.在N=1，000的平均情況下，哪個程序運行更好

8、？Ad.在所有可能的輸入中，程序B總比程序A運行的快嗎？當然不是。當N很大是程序B就沒有程序A效果好6.對于這些你用手工來計算的典型算法，確定其運行時間。a.兩個N位整數(shù)相加O（1）b.兩個N位整數(shù)相乘O（n2）c.兩個N位整數(shù)相除0(n2)7.對于N個項來說，以下計算XN的算法運行時間是多少？doublepower（doublex，intn）doubleresult=1.0f（inti=0ini）result=xreturnresul

9、t8.對于求最大子序列之和問題的平方算法而言，精確的確定語句最內(nèi)部循環(huán)被執(zhí)行多少次？參考答案：（1N）N29.一個算法在輸入規(guī)模為100時，花費0.5ms的時間，在下列情況下，輸入規(guī)模為500時，它將花費多少時間？（低次項不考慮）（單位全是MS）a.線性算法（500100）0.5=2.5b.O(NlogN)(500log500)(100LOG100)0.5=2.5LOG5=5.0c.平方算法500500(100100)0.5=12.5d