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

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