自考數(shù)據(jù)結(jié)構(gòu)課后習題答案

本文格式為Word版，下載可任意編輯——自考數(shù)據(jù)結(jié)構(gòu)課后習題答案自考數(shù)據(jù)結(jié)構(gòu)課后習題答案

本章的重點是了解數(shù)據(jù)結(jié)構(gòu)的規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)的運算三方面的概念及相互關系，難點是算法繁雜度的分析方法。

需要達到層次的基本概念和術語有：

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關系。數(shù)據(jù)結(jié)構(gòu)的兩大類規(guī)律結(jié)構(gòu)和四種常用的存儲表示方法。

需要達到層次的內(nèi)容有算法、算法的時間繁雜度和空間繁雜度、最壞的和平均時間繁雜度等概念，算法描述和算法分析的方法、對一般的算法要能分析出時間繁雜度。對于基本概念，細心看書就能夠理解，這里簡單提一下：數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。如整數(shù)這個集合中，10這個數(shù)就可稱是一個數(shù)據(jù)元素.又譬如在一個數(shù)據(jù)庫(關系式數(shù)據(jù)庫)中，一個記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段就是一個數(shù)據(jù)項。

數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標準，但是它包括以下三方面內(nèi)容：規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。

譬如一個表(數(shù)據(jù)庫)，我們就稱它為一個數(shù)據(jù)結(jié)構(gòu)，它由好多記錄(數(shù)據(jù)元素)組成，每個元素又包括好多字段(數(shù)據(jù)項)組成。那么這張表的規(guī)律結(jié)構(gòu)是怎么樣的呢?我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(其實也就是元素、記錄、頂點，雖然在各種狀況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對于這個表中的任一個記錄(結(jié)點)，它只有一個直接前趨，只有一個直接后繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結(jié)點和一個終端結(jié)點，那我們知道了這些關系就能明白這個表的規(guī)律結(jié)構(gòu)了。

而存儲結(jié)構(gòu)則是指用計算機語言如何表示結(jié)點之間的這種關系。如上面的表，在計算機語言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的層次上探討存儲結(jié)構(gòu)。)

第三個概念就是對數(shù)據(jù)的運算，譬如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎么樣才能進行這樣的操作呢?這也就是數(shù)據(jù)的運算，它不僅僅是加減乘除這些算術運算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運算往往涉及算法問題。

弄清了以上三個問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個概念。

尋常我們就將數(shù)據(jù)的規(guī)律結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的規(guī)律結(jié)構(gòu)分兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)(這兩個很簡單理解)

數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。下一個是難點問題，就是算法的描述和分析，主要是算法繁雜度的分析方法及其運用。

首先了解一下幾個概念。一個是時間繁雜度，一個是漸近時間繁雜度。前者是某個算法的時間花費，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當問題規(guī)模趨向無窮大時，該算法時間繁雜度的數(shù)量級。

當我們評價一個算法的時間性能時，主要標準就是算法的漸近時間繁雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間繁雜度T(n)=O(f(n)簡稱為時間繁雜度，其中的f(n)一般是算法中頻度最大的語句頻度。

此外，算法中語句的頻度不僅與問題規(guī)模有關，還與輸入實例中各元素的取值相關。但是我們總是考慮在最壞的狀況下的時間繁雜度。以保證算法的運行時間不會比它更長。

常見的時間繁雜度，按數(shù)量級遞增排列依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數(shù)階O(2^n)。

時間繁雜度的分析計算請看書本上的例子，然后我們通過做練習加以領會和穩(wěn)定。[size=+3]數(shù)據(jù)結(jié)構(gòu)習題一

1.1簡述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。◆數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。

◆數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些狀況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成。

◆數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。

◆數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。

◆規(guī)律結(jié)構(gòu)：指各數(shù)據(jù)元素之間的規(guī)律關系。

◆存儲結(jié)構(gòu)：就是數(shù)據(jù)的規(guī)律結(jié)構(gòu)用計算機語言的實現(xiàn)。

◆線性結(jié)構(gòu)：數(shù)據(jù)規(guī)律結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。

◆非線性結(jié)構(gòu)：數(shù)據(jù)規(guī)律結(jié)構(gòu)中的另一大類，它的規(guī)律特征是一個結(jié)點可能有多個直接前趨和直接后繼。1.2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、表達其規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。

◆例如有一張學生成績表，記錄了一個班的學生各門課的成績。按學生的姓名為一行記成的表。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學號，成績等字段)就是一個結(jié)點，對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼(它的前面和后面均有且只有一個記錄)。這幾個關系就確定了這個表的規(guī)律結(jié)構(gòu)。

那么我們怎樣把這個表中的數(shù)據(jù)存儲到計算機里呢?用高級語言如何表示各結(jié)點之間的關系呢?是用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機存放各結(jié)點數(shù)據(jù)再用指針進行鏈接呢?這就是存儲結(jié)構(gòu)的問題，我們都是從高級語言的層次來探討這個問題的。(所以各位趕快學C語言吧)。

最終，我們有了這個表(數(shù)據(jù)結(jié)構(gòu))，確定要用它，那么就是要對這張表中的記錄進行查詢，修改，刪除等操作，對這個表可以進行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。1.3常用的存儲表示方法有哪幾種?常用的存儲表示方法有四種:

◆順序存儲方法：它是把規(guī)律上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的規(guī)律關系由存儲單元的鄰接關系來表達。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。

◆鏈接存儲方法：它不要求規(guī)律上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的規(guī)律關系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)。

◆索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。◆散列存儲方法：就是根據(jù)結(jié)點的關鍵字直接計算出該結(jié)點的存儲地址。

1.4設三個函數(shù)f,g,h分別為f(n)=100n^3+n^2+1000,g(n)=25n^3+5000n^2,h(n)=n^1.5+5000nlgn請判斷以下關系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n^1.5)(4)h(n)=O(nlgn)◆(1)成立。

這里我們復習一下漸近時間繁雜度的表示法T(n)=O(f(n))，這里的\是數(shù)學符號，它的嚴格定義是\若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和[size=+1]n[size=-3]0,使得當n≥[size=+1]n[size=-3]0時都滿足0≤T(n)≤C·f(n)。\用簡單理解的話說就是這兩個函數(shù)當整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。這么一來，就好計算了吧。第(1)題中兩個函數(shù)的最高次項都是n^3,因此當n→∞時，兩個函數(shù)的比值是一個常數(shù)，所以這個關系式是成立的?！簦?）成立?！簦?）成立?！簦?）不成立。

1.5設有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n^2和2^n,要使前者快于后者，n至少要多大?◆15

最簡單最笨的方法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個5，用15代入得前者為22500，后者為32768，已經(jīng)比前者大但相差不多，那我們再減個1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來就是n至少要是15.1.6設n為正整數(shù)，利用大\記號，將以下程序段的執(zhí)行時間表示為n的函數(shù)。(1)i=1;k=0while(i1while(x>=(y+1)*(y+1))y++;(5)x=91;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;

1.7算法的時間繁雜度僅與問題的規(guī)模相關嗎?

◆No,事實上，算法的時間繁雜度不僅與問題的規(guī)模相關，還與輸入實例中的元素取值等相關，但在最壞的狀況下，其時間繁雜度就是只與求解問題的規(guī)模相關的。我們在探討時間繁雜度時，一般就是以最壞狀況下的時間繁雜度為準的。

1.8按增長率由小至大的順序排列以下各函數(shù)：

2^100,(2/3)^n，(3/2)^n，n^n,,n!，2^n，lgn,n^lgn,n^(3/2)，√n

分析如下：2^100是常數(shù)階；(2/3)^n和(3/2)^n是指數(shù)階,其中前者是隨n的增大而減小的；n^n是指數(shù)方階；√n是方根階,n!就是n(n-1)(n-2)...就相當于n