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

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

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

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

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

5、構(gòu)上的算法構(gòu)成的。具體的說(shuō)：在進(jìn)行程序設(shè)計(jì)之前我們首先要為待處理的數(shù)據(jù)設(shè)計(jì)一個(gè)合理的邏輯結(jié)構(gòu)，進(jìn)而為之設(shè)計(jì)一種適合的存儲(chǔ)結(jié)構(gòu)，因?yàn)楣庥羞壿嫿Y(jié)構(gòu)是不夠的，只有存儲(chǔ)結(jié)構(gòu)才是與計(jì)算機(jī)語(yǔ)言直接相關(guān)的！有了這一套前期準(zhǔn)備，我們才能在這個(gè)基礎(chǔ)上設(shè)計(jì)算法，用一種計(jì)算機(jī)語(yǔ)言去處理這些數(shù)據(jù)，最終達(dá)到程序設(shè)計(jì)的目的。當(dāng)然，隨著邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的不同，我們?cè)O(shè)計(jì)的算法也會(huì)有所差別，這在以后的學(xué)習(xí)中會(huì)體會(huì)到。下面通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明這種關(guān)系。假設(shè)我們要設(shè)計(jì)一

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

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

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

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