算法與數(shù)據(jù)結(jié)構(gòu)1

1、第一章緒論習題練習答案1.1 簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu) 、邏輯結(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ù)項組成。課后答案網(wǎng) 數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容 :數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。 存儲結(jié)構(gòu)：數(shù)據(jù)元素

2、及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu) . 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。 它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點， 并且所有結(jié)點都有且只有一個直接前趨1和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。1.2 試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。答：例如有一張學生體檢情況登記表，記錄了一個班的學生的身高、體重等各項體檢信息。這張登記表中， 每個學生的各項體

3、檢信息排在一行上。這個表就是一個數(shù)據(jù)結(jié)構(gòu)。每個記錄(有姓名，學號，身高和體重等字段 )就是一個結(jié)點， 對于整個表來說，只有一個開始結(jié)點 (它的前面無記錄 )和一個終端結(jié)點 (它的后面無記錄 )，其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼 (它的前面和后面均有且只有一個記錄)。這幾個關(guān)系就確定了這個表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。這個表中的數(shù)據(jù)如何存儲到計算機里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢 ? 即用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示 )還是隨機存放各結(jié)點2數(shù)據(jù)再用指針進行鏈接呢 ? 這就是存儲結(jié)構(gòu)的問題。課后答案網(wǎng)在這個表的某種存儲結(jié)構(gòu)基礎(chǔ)上，可實現(xiàn)對這張表中的記錄進行查詢，修改

4、，刪除等操作。對這個表可以進行哪些操作以及如何實現(xiàn)這些操作就是數(shù)據(jù)的運算問題了。1.3 常用的存儲表示方法有哪幾種?答：常用的存儲表示方法有四種: 順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位置相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)，通常借助程序語言的數(shù)組描述。 鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu),通常借助于程序語言的指針類型描述。 索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。組3成索引表的索引項由結(jié)點的關(guān)鍵

5、字和地址組成。若每個結(jié)點在索引表中都有一個索引項，則該索引表稱之為稠密索引（Dense Index）。若一組結(jié)點在索引表中只對應一個索引項，則該索引表稱為稀疏索引。 散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。1.4 設(shè)三個函數(shù) f,g,h分別為 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 ,h(n)=n1.5+5000nlgn請判斷下列關(guān)系是否成立：(1) f(n)=O(g(n)(2) g(n)=O(f(n)(3) h(n)=O(n1.5)(4) h(n)=O(nlgn)分析：數(shù)學符號 "O" 的嚴格的數(shù)學定義：若T（n）

6、和 f （n）是定義在正整數(shù)集合上的兩個函數(shù)，則T（n）=O（f（n）表示存在正的常數(shù) C 和n0，使得當 nn0 時都滿足 0T（n） C·f（n）。通俗地說，就是當 n時， f(n)的函數(shù)值增長速度與 T（n)的增長速度同階。一般，一課后答案網(wǎng)4個函數(shù)的增長速度與該函數(shù)的最高次階同階。即：O(f(n)=n3O(g(n)=n3O(h(n)=n1.5所以答案為：答：（ 1）成立。（ 2）成立。（ 3）成立。（ 4）不成立。1.5 設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者， n至少要多大 ?分析：要使前者快于后者，即前者的時間消耗低于后者，即：1

7、00n2<2n求解上式，可得答：n=151.6 設(shè)n為正整數(shù)，利用大 "O" 記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。5(1) i=1; k=0; while(i<n) k=k+10*i;i+;分析：i=1; /1k=0; /1while(i<n) /n課后答案網(wǎng) k=k+10*i; /n-1 i+; /n-1由以上列出的各語句的頻度，可得該程序段的時間消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示為 T(n)=O(n)(2) i=0; k=0;do k=k+10*i; i+;while(i<n);分析：i=0; /16k=0;

8、/1do /nk=k+10*i; /ni+; /nwhile(i<n);/n由以上列出的各語句的頻度，可得該程序段的時間消耗：T(n)=1+1+n+n+n+n=4n+2可表示為 T(n)=O(n)(3) i=1; j=0; while(i+j<=n)if (i>j) j+; else i+;課后答案網(wǎng)分析：通過分析以上程序段，可將i+j 看成一個控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)， i+j的值加 1。該程序段的主要時間消耗是while 循環(huán)，而 while 循環(huán)共做了n 次，所以該程序段的執(zhí)行時間為：7T(n)=O(n)(4)x=n; / n>1while (x>

9、;=(y+1)*(y+1)y+;分析：由x=n 且x 的值在程序中不變，又 while 的循環(huán)條件 (x>=(y+1)*(y+1)可知：當 (y+1)*(y+1)剛超過 n 的值時退出循環(huán)。由(y+1)*(y+1)<n 得： y<n0.5-1所以，該程序段的執(zhí)行時間為：向下取整 (n0.5-1)(5) x=91; y=100; while(y>0) if(x>100) x=x-10;y-;else x+;分析：x=91; /1y=100; /1while(y>0) /1101if(x>100) /1100 x=x-10; /1008y-; /100課后

10、答案網(wǎng)elsex+; /1000以上程序段右側(cè)列出了執(zhí)行次數(shù)。該程序段的執(zhí)行時間為：T(n)=O(1)1.7 算法的時間復雜度僅與問題的規(guī)模相關(guān)嗎?答：算法的時間復雜度不僅與問題的規(guī)模相關(guān)，還與輸入實例中的初始狀態(tài)有關(guān)。但在最壞的情況下，其時間復雜度就是只與求解問題的規(guī)模相關(guān)的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。1.8 按增長率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n ， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2)答：常見的時間復雜度按數(shù)量級遞增排列,依次為 :常數(shù)階 0(1)、對數(shù)階0(log2n)、線性

11、階 0(n)、線性對數(shù)階 0(nlog2n)、平方階 0(n2)、立方階 0(n3)、k 次方階 0(nk)、指數(shù)階 0(2n)。先將題中的函數(shù)分成如下幾類：9常數(shù)階： 2100對數(shù)階： lgnK 次方階： n0.5、n(3/2)指數(shù)階 (按指數(shù)由小到大排 )：nlgn、(3/2)n 、2n、n!、 nn注意：(2/3)n 由于底數(shù)小于 1，所以是一個遞減函數(shù)，其數(shù)量級應小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn1.9 有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大 "O"記號表示。例如，設(shè) T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n), 這兩個式子表示， 當n足夠大時 T1(n)優(yōu)于 T2(n)，因為前者的常數(shù)因子小于后者。請用此方法表示下列函數(shù)，并指出當 n 足夠大時， 哪