算法數(shù)數(shù)據(jù)結(jié)構(gòu)-第3版-緒論課后答案

算法與數(shù)據(jù)結(jié)構(gòu)C語言描述（第三版）第1章緒論1、解釋以下概念：邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，操作，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的表示，數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，抽象數(shù)據(jù)類型，算法，算法的時間代價，算法的空間代價，大O表示法，貪心法，回溯法，分治法。答：邏輯結(jié)構(gòu)（數(shù)學(xué)模型）：=1\*GB3①指數(shù)據(jù)元素之間地邏輯關(guān)系。=2\*GB3②具體解釋：指數(shù)學(xué)模型（集合，表，樹，和圖）之間的關(guān)系。=3\*GB3③描述方式：B=<K,R>,K是節(jié)點的有窮集合，R是K上的一個關(guān)系。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的映射（或表示）。(3)操作（行為）：指抽象數(shù)據(jù)類型關(guān)心的的各種行為在不同的存儲結(jié)構(gòu)上的具體算法（或程序）。(4)數(shù)據(jù)結(jié)構(gòu)：=1\*GB3①傳統(tǒng)觀念：數(shù)據(jù)結(jié)構(gòu)是計算機中表示（存儲）的、具有一定邏輯關(guān)系和行為特征的一組數(shù)據(jù)。②根據(jù)面向?qū)ο蟮挠^點：數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型的物理實現(xiàn)。(5)數(shù)據(jù)結(jié)構(gòu)的表示：(6)數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)：(7)抽象數(shù)據(jù)類型：(8)算法：是由有窮規(guī)則構(gòu)成（為解決某一類問題）的運算序列。-算法可以有若干輸入（初始值或條件）。-算法通常又有若干個輸出（計算結(jié)果）。-算法應(yīng)該具有有窮性。一個算法必須在執(zhí)行了有窮步之后結(jié)束。-算法應(yīng)該具有確定性。算法的每一步，必須有確切的定義。-算法應(yīng)該有可行性。算法中國的每個動作，原則上都是能夠有機器或人準(zhǔn)確完成的。(9)算法的時間代價：(10)算法的空間代價：(11)大O表示法：-更關(guān)注算法復(fù)雜性的量級。-若存在正常數(shù)c和n0，當(dāng)問題的規(guī)模n>=c*f(n),則說改算法的時間（或空間）代價為O（f(n)）(12)貪心法： 當(dāng)追求的目標(biāo)是一個問題的最優(yōu)解是，設(shè)法把整個問題的求解工作分成若干步來完成。在其中的每一個階段都選擇都選擇從局部來看是最優(yōu)的方案，以期望通過各個階段的局部最有選擇達到整體的最優(yōu)。例如：著色問題：先用一種顏色盡可能多的節(jié)點上色，然后用另一種顏色在為著色節(jié)點中盡可能多的節(jié)點上色，如此反復(fù)直到所有節(jié)點都著色為止；(13)回溯法有一些問題，需要通過徹底搜索所有的情況尋找一個滿足某些預(yù)定條件的最優(yōu)解。由于徹底搜索的運算量非常大，所以采用一步一步向前試探，當(dāng)有多重選擇是可以任意選擇一種，只要目前可行就繼續(xù)向前，一旦發(fā)現(xiàn)失敗或問題就后退，回到上一步重新選擇，借助于回溯技巧和中間增加判斷，這樣常?？梢源蟠蟮販p少搜索的時間。-常見的迷宮問題以及八皇后問題都可以用回溯方法來解決。(14)分治法把一個規(guī)模較大的問題分成兩個或多個較小的與原問題相似的子問題。首先對子問題進行求解，然后設(shè)法把子問題進行求解，即對問題分而治之。如果一個問題的規(guī)模仍然比較大，不能很容易的求解，就可以對這個子問題重復(fù)地應(yīng)用分治策略。-二分法檢索就是用分治法策略的典型例子。2、理解以下關(guān)系：答：算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系： =1\*GB3①算法+數(shù)據(jù)結(jié)構(gòu)=程序 =2\*GB3②程序就是在數(shù)據(jù)的某些特定的結(jié)構(gòu)和表示的基礎(chǔ)上對于算法的描述。 =3\*GB3③算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計中相輔相成、不可分割的兩個方面。數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)類型的關(guān)系：算法和數(shù)據(jù)結(jié)構(gòu)問題的求解關(guān)系：3.為整數(shù)定義一個抽象數(shù)據(jù)類型。它包含整數(shù)的常見運算，每一個運算對應(yīng)一個函數(shù)，由它的輸入/輸出定義。4.什么叫數(shù)據(jù)結(jié)構(gòu)？試舉一個簡單的例子說明。答：=1\*GB3①傳統(tǒng)的概念：數(shù)據(jù)結(jié)構(gòu)是計算機中表示（存儲）的、具有一定邏輯關(guān)系和行為特征的一組數(shù)據(jù)。=2\*GB3②根據(jù)面向?qū)ο蟮挠^點：數(shù)據(jù)結(jié)構(gòu)是抽象的數(shù)據(jù)類型的物理實現(xiàn)。5.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成哪幾類？答：（1）給定B=<K,R>,若<K1,K2>∈R,則稱K1為K2的前驅(qū)，K2為K1的后繼。沒有前驅(qū)的結(jié)點為開始結(jié)點，沒有后繼結(jié)點為終端結(jié)點。（2）根據(jù)R的特點可以將數(shù)據(jù)結(jié)構(gòu)分為以下三類：=1\*GB3①線性結(jié)構(gòu)：K中每個結(jié)點最多只有一個前驅(qū)和一個后繼；=2\*GB3②樹形結(jié)構(gòu)：K中每個結(jié)點做多有一個前驅(qū)，單可以有多個后繼；=3\*GB3③復(fù)雜結(jié)構(gòu)：K中節(jié)點的前驅(qū)、后繼結(jié)點的個數(shù)都不做限制；=4\*GB3④集合結(jié)構(gòu)：當(dāng)R為空集時，K中結(jié)點間沒有約束關(guān)系；7.將下列復(fù)雜度由小到大重新排序：A、2n B、n!C、n5 D、10000 E、n*log?n【答】DECAB8.將下列復(fù)雜度由小到大重新排序：A．n*log2(n)?? B．n?+?n2?+?n3 C．24 D．n0.5【答】24<n0.5<n*log2(n)<n?+?n2?+?n3 CDAB9.用大O表示法描述下列復(fù)雜度：A．5n5/2+n2/5??B．6*log2(n)+9n?C．3n4+n*log2(n)??????D．5n2+n3/2【答】A:O(n5/2) B:O(n) C:O(n4) D:O(n2)10.按照增長率從低到高的順序排列以下表達式：4n2,log3n,3n,20n,2000,z,n2/3。又n！應(yīng)排在第幾位?【答】按照增長率從低到高依次為：2000,log3n,log2n,n2/3,20n,4n2,3nn!:增長率比她們中的每一個要打，應(yīng)該排在最后一位。算法分析題1.計算下列程序片段的時間代價：inti=1;while(i<=n){printf("i=%d\n",i);i=i+1;}【答】循環(huán)控制變量i從1增加到n，循環(huán)體執(zhí)行n次，第一句i的初始化執(zhí)行次數(shù)為1，第二句執(zhí)行n次，循環(huán)體中第一句printf執(zhí)行n次，第二句i從1循環(huán)的n，共執(zhí)行n次。所以該程序的總時間代價為：T(n)=1+n+(n+n)=1+3n=O(n)2.計算下列程序片段的時間代價： inti=1; while(i<=n){ intj=1; while(j<=n){ intk=1; while(k<=n){ printf("i=%d,j=%d,k=%d\n",i,j,k); k=k+1; } j=j+1; } i=i+1; }【答】循環(huán)變量i從1增加到n，最外層循環(huán)體執(zhí)行n次；循環(huán)變量j從1增加到n，中間層循環(huán)