算法程序與計算系統(tǒng)之靈魂練習(xí)習(xí)題答案解析

1、第7章 算法:程序與計算系統(tǒng)之靈魂1、算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特定類型問題的一個運算序列?；卮鹣铝袉栴}。(1)關(guān)于算法的特性，下列說法不正確的是_。(A)算法必須有明確的結(jié)束條件，即算法應(yīng)該能夠結(jié)束，此即算法的有窮性；(B)算法的步驟必須要確切地定義，不能有歧義性，此即算法的確定性； (C)算法可以有零個或多個輸入，也可以有零個或多個輸出，此即算法的輸入輸出性；(D)算法中有待執(zhí)行的運算和操作必須是相當(dāng)基本的，可以由機器自動完成，進一步，算法應(yīng)能在有限時間內(nèi)完成，此即算法的能行性；(E)上述說法有不正確的；答案：C解釋：本題考查對算法基本性質(zhì)的理解 （C）算法的輸出

2、性：算法有一個或多個的輸出/結(jié)果，即與輸入有某個特定關(guān)系的量。因此（C）選項錯誤。其余選項，（A）（B）（D）分別是對算法的有窮性，確定性和能行性的正確描述。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(2)關(guān)于算法的命題，下列說法不正確的是_。(A)算法規(guī)定了任務(wù)執(zhí)行/問題求解的一系列、有限的步驟。(B)算法所規(guī)定的計算/處理步驟是有限的，但算法實際執(zhí)行的計算/處理步驟可以是無限的。(C)算法可以沒有輸入，但必須有輸出。(D)算法的每一個步驟必須確切地定義，且其運算和操作必須相當(dāng)基本，可以由機器自動完成。答案：B解釋：本題考查對算法基本性質(zhì)的理解 （B）違反了算法的有窮

3、性：一個算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。因此（B）選項錯誤。其余選項，（A）（C）（D）分別是對算法的有窮性，輸入輸出性和確定性的正確描述。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(3)關(guān)于算法與程序、計算機語言之間的關(guān)系，下列說法不正確的是_。(A)算法是解決問題的步驟，某個問題可能有多個求解算法；(B)算法不能直接由計算機執(zhí)行，必須將其轉(zhuǎn)換為程序才能夠由計算機執(zhí)行；(C)算法只能由高級（計算機）語言實現(xiàn)，不能通過機器語言實現(xiàn)；(D)求解問題的多個算法不一定獲得相同的解。答案：C解釋：本題考查對算法基本性質(zhì)的理解 （C）算法是解決問題的步驟，執(zhí)行的語言是步驟書寫的

4、規(guī)范、語法規(guī)則、標(biāo)準(zhǔn)的集合是人和計算機都能理解的語言，不僅是高級語言。因此（C）選項錯誤。其余選項，（A）正確，解決問題的算法可以有多個。（B）選項，程序是算法的實現(xiàn)方式，正確。（D）選項，算法有優(yōu)劣，對于同一個問題，獲得的解可能不同。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(4)算法是計算系統(tǒng)的靈魂，為什么不正確的是_。(A)計算系統(tǒng)是執(zhí)行程序的系統(tǒng)，而程序是用計算機語言表達的算法；(B)一個問題的求解可以通過構(gòu)造算法來解決，“是否會編程序”本質(zhì)上章是“能否想出求解該問題的算法”； (C)一個算法不僅可以解決一個具體問題，它可以在變換輸入輸出的情況下，求解一個問題系

5、列；(D)問題求解都可以歸結(jié)到算法的構(gòu)造與設(shè)計，系統(tǒng)和算法的關(guān)系是：算法是龍，而系統(tǒng)是睛，畫龍要點睛。(E)上述說法有不正確的；答案：D解釋：本題考查算法、程序與系統(tǒng)之間的關(guān)系（D）選項，算法是計算系統(tǒng)的靈魂，因此系統(tǒng)和算法的關(guān)系是：系統(tǒng)是龍，算法是睛，好的算法能起到畫龍點睛的效果。（A）（B）（C）選項描述正確。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。2、哥尼斯堡七橋問題，是一個經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學(xué)家歐拉對該問題做了一個抽

6、象：“頂點”為陸地，“邊”為連接兩塊陸地的橋梁。這個抽象被稱為“圖”，并定義了頂點的“度”為連接一個頂點的邊的數(shù)量。關(guān)于此問題回答下列問題。., VN，重量分別為W1, W2, ., WN，背包所能承受的總重量為Wmax，為物品i定義一個決策變量xi，其中xi=1表示選擇該物品，xi=0表示不選擇該物品。下面哪個描述共同構(gòu)成了該問題的數(shù)學(xué)模型_。(A) 問題的目標(biāo)函數(shù)是；(B) 問題的目標(biāo)函數(shù)是；(C) 問題解所應(yīng)滿足的約束是；(D) 問題解所應(yīng)滿足的約束是；(E) 前述(A)和(C)；答案：E解釋：本題考查問題及其數(shù)學(xué)建模的作用該問題有兩個條件：1）物品不能超過背包所能承受的重量，即（C）選

7、項：2）背包內(nèi)物品價值最大，即（A）選項目標(biāo)函數(shù)為（B）和（D）選項明顯錯誤，將質(zhì)量和價值比較。所以選擇（E）。具體內(nèi)容查閱背包問題相關(guān)資料。4、TSP-旅行商問題，是一個經(jīng)典問題，如下圖所示，描述為“有n個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費用最少”。圍繞TSP，回答下列問題。(1)關(guān)于TSP問題的遍歷算法和貪心算法，下列說法正確的是_。(A)對TSP問題而言，遍歷算法和貪心算法求得的解是一樣的，所不同的是貪心算法更快一些，而遍歷算法更慢一些；(B)對TSP

8、問題而言，遍歷算法和貪心算法求得的解是一樣的，所不同的是遍歷算法更快一些，而貪心算法更慢一些；(C)對TSP問題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求近似解，執(zhí)行更快一些，而遍歷算法是求精確解，執(zhí)行更慢一些；(D)對TSP問題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求精確解，執(zhí)行更快一些，而遍歷算法是求近似解，執(zhí)行更慢一些；答案：C解釋：本題考查對貪心算法與遍歷算法的簡單理解貪心算法：一定要做當(dāng)前情況下的最好選擇，否則將來可能會后悔，故名“貪心”。如果以A城市為起點，選擇最近的下一點，為B城市。以B城市為起點，選擇最近的下一個城市，可以選擇C或D，以選擇D為例。

9、以D為起點，選擇最近的下一點，為C城市。最后回到A。整個過程的花費為：14。于是，該貪心算法的解為14。而通過遍歷可知，該問題的最優(yōu)解為A-B-C-D-A，花費為13?？梢?，貪心算法與遍歷算法的解不會總是完全相同。而貪心算法只會做當(dāng)前情況下最優(yōu)選擇，其時間復(fù)雜度為n3 級別。而遍歷則會將各種情況考慮在內(nèi)，其時間復(fù)雜度為（n-1）！級別當(dāng)城市的數(shù)量變多時，遍歷算法將會出現(xiàn)組合爆炸。故，相比之下，貪心算法的計算速度更快。所以(C)選項是正確的。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(2)關(guān)于TSP，下列說法不正確的是_。(A)TSP問題的一個可能解就是n個城市的一個組

10、合<t1, t2, , tn>，其中任何兩個ti，tj都對應(yīng)不同的城市。若要求得最優(yōu)解，則必須對所有的組合，即所有可能解進行比較。(B)TSP問題的難點是當(dāng)n值很大時，組合數(shù)目非常龐大(組合數(shù)目為n!)，以致于計算機不能在有限時間內(nèi)完成所有的組合；(C)TSP問題的難點是當(dāng)n值很大時，組合數(shù)目非常龐大(組合數(shù)目為n!)，雖如此，計算機仍然能夠在有限時間內(nèi)完成所有的組合； (D)上述思想-對所有組合進行比較的思想，即是所謂的遍歷算法策略，它僅僅對n值很小的TSP問題是能行的。答案：C解釋：本題考查對TSP組合優(yōu)化問題的理解對所有組合進行比較的思想，即所謂的遍歷算法策略，其組合數(shù)目為n

11、!。2001年解決了德國15112個城市的TSP問題，使用了美國Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz 的Compaq EV6 Alpha 處理器組成的110臺計算機，所有計算機花費的時間之和為年。由此可見，當(dāng)n巨大時，用遍歷算法解決TSP問題是不現(xiàn)實的。所以(C)選項錯誤。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(3)關(guān)于TSP的貪心算法的求解思想，下列說法不正確的是_。(A)無需對所有組合(所有可能解)進行比較，而僅需依照某種辦法確定其中的一個組合即可，該組合不一定是最優(yōu)解，但卻是一個較優(yōu)解或次優(yōu)解；(B)在確定一個組合<t1, t2,

12、, tn>時，tk+1是與tk相連接的城市中與tk距離最短的城市，即tk+1是由tk確定的，與tk連接的若干城市中的特性最優(yōu)的城市；(C)貪心算法確定的路徑，是由局部最優(yōu)(即tk+1在tk看來是最優(yōu)的)組合起來的路徑，該路徑從全局角度也一定是最優(yōu)的； (D)對一個具體的TSP問題，每次執(zhí)行貪心算法，所求得的最終解可能是不同的。答案：C解釋：本題考查對TSP貪心算法的理解（A）(B)選項都是對貪心算法的描述，貪心算法的核心就是：只考慮當(dāng)前情況下得最優(yōu)解。故（A）（B）正確。貪心算法得到的解釋可行解，但不一定是最優(yōu)解，故(C)錯誤。在執(zhí)行貪心算法的過程中，會遇到下一步有兩個最優(yōu)選項的情況，所

13、以每次執(zhí)行貪心算法的最終解的結(jié)果可能是不同的。故(D)正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(4)下列哪些問題可應(yīng)用求解TSP的算法，正確的是_。(A)電路板上需要鉆n個孔，選擇一條最短路徑使機器移動并完成所有孔的鉆孔工作的問題(機器在電路板上鉆孔的調(diào)度問題)；(B) n個盤子在三個柱子上的移動問題(梵天塔問題或者說漢諾塔問題)；(C) n座橋， 走過每座橋且僅走過一次的問題(圖的遍歷問題)； (D)上述(A)(B)(C)都可以。答案：A解釋：本題考查對TSP問題抽象的理解求解TSP問題采用的是貪心算法。(A)選項所描述的問題其實就是TSP問題。（B）選項所

14、描述的問題是梵天塔問題，應(yīng)該采用的是遞歸的思想。（C）選項所描述的圖的遍歷問題，主要有深度優(yōu)先搜索，和廣度優(yōu)先搜索兩種解決方法，不是貪心算法。綜上，（A）選項正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(5)關(guān)于下列四個數(shù)學(xué)抽象，說法正確的是_。(數(shù)學(xué)抽象I)城市記為：V=v1,v2,vn，任意兩個城市vi,vjV之間的距離記為：dvivj，問題的解是尋找所有城市的一個訪問順序T=t1,t2,tn，其中tiV，使得mini=1ndtiti+1，這里假定除tn+1=t1外，ti ¹ tj(i¹j時)。(數(shù)學(xué)抽象II)電路元件記為：V=v1,v2,

15、vn，任意兩個元件vi,vjV之間的距離記為：dvivj，問題的解是尋找所有元件之間的一個訪問順序T=t1,t2,tn，其中tiV，使得mini=1ndtiti+1，這里假定除tn+1=t1外，ti ¹ tj(i¹j時)。(數(shù)學(xué)抽象III)圖的結(jié)點記為：V=v1,v2,vn，任意兩個結(jié)點vi,vjV的邊的權(quán)值記為：dvivj，問題的解是尋找所有結(jié)點之間的一個訪問順序T=t1,t2,tn，其中tiV，使得mini=1ndtiti+1，這里假定除tn+1=t1外，ti ¹ tj(i¹j時)。 (數(shù)學(xué)抽象IV)圖的結(jié)點記為：N = 1,2，n，任意兩個結(jié)點i，

16、j的邊的權(quán)值記為：dij，問題的解是尋找所有結(jié)點之間的一個訪問順序t=t1,t2,tn，其中tiÎV，使得min mini=1ndtiti+1，這里假定除tn+1=t1外，ti ¹ tj(i¹j時)。(A)只有數(shù)學(xué)抽象I是TSP問題，數(shù)學(xué)抽象II和III不是；(B)數(shù)學(xué)抽象I和III可以被認為是TSP問題，數(shù)學(xué)抽象II和IV不是；(C)數(shù)學(xué)抽象I、II、III和IV都可以被認為是TSP問題；(D)上述說法都不正確。答案：C解釋：本題考查對TSP問題抽象的理解I就是對最原始的TSP問題的抽象描述。II也是對TSP問題的描述，只是將城市換成了電子元件。III和IV是對

17、同一問題的不同表述罷了，都是TSP問題，只是將城市換為了圖。四個數(shù)學(xué)抽象都可以被認為是TSP問題。故選項（C）正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。5、數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計的重要步驟，針對不同問題的算法設(shè)計應(yīng)該選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，不同的數(shù)據(jù)結(jié)構(gòu)會使得解決問題的算法的性能有所不同?；卮鹣铝袉栴}。(1)關(guān)于數(shù)據(jù)結(jié)構(gòu)，下列說法不正確的是_。(A)數(shù)據(jù)結(jié)構(gòu)是問題域數(shù)學(xué)模型中各種數(shù)據(jù)的存儲結(jié)構(gòu)；(B)數(shù)據(jù)結(jié)構(gòu)是將邏輯上有一定語義關(guān)系的數(shù)據(jù)，轉(zhuǎn)換成計算機可以存儲和處理的變量，便于算法和程序進行處理； (C)數(shù)據(jù)結(jié)構(gòu)是將具有一定語義關(guān)系的變量進行命名，以便隱藏數(shù)據(jù)結(jié)構(gòu)內(nèi)部的

18、操作細節(jié)，便于算法按邏輯語義通過操控該名字來操控該數(shù)據(jù)結(jié)構(gòu)； (D)數(shù)據(jù)結(jié)構(gòu)包含了數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其操作；(E)上述說法有不正確的。答案：E解釋：本題考查對數(shù)據(jù)結(jié)構(gòu)的理解數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其操作的總稱，它提供了問題求解/算法的數(shù)據(jù)操縱機制。(A) (B) (C)(D)的說法都沒有問題。所以（E）是不正確的。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(2)關(guān)于數(shù)據(jù)結(jié)構(gòu)，下列說法不正確的是_(A) 數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及運算3部分組成；(B) 存儲結(jié)構(gòu)定義了數(shù)據(jù)在存儲器中的存儲方式；(C) 向量使用順序存儲結(jié)構(gòu)，并借助元素在存儲器中的相

19、對位置來表示數(shù)據(jù)元素的邏輯關(guān)系；(D) 在樹結(jié)構(gòu)中，指針用于表達元素之間的邏輯關(guān)系父子關(guān)系，每個元素的指針指向其父節(jié)點，因此一個元素可以有一個或多個指針。答案：D解釋：本題考查對數(shù)據(jù)結(jié)構(gòu)的理解數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其操作的總稱。（A）正確。數(shù)據(jù)的存儲結(jié)構(gòu)也就是在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲器中的存儲方式。（B）正確。向量確實是使用順序存儲結(jié)構(gòu)，并且借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素的邏輯關(guān)系的，（C）正確。在樹結(jié)構(gòu)中，如果每個元素的指針都指向其父節(jié)點，那么每個元素只能有一個指針。因為每個元素只有一個父親。故（D）錯誤。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)

20、之靈魂”與第七章課件。6. 數(shù)據(jù)通常要存儲在存儲器中，存儲器是按地址訪問的存儲單元的集合，因此存儲器可被認為是按線性方式組織數(shù)據(jù)。數(shù)組是高級語言中經(jīng)常使用的一種數(shù)據(jù)結(jié)構(gòu)，其按照不同的下標(biāo)可訪問數(shù)組的不同的元素。如下圖所示：(1)關(guān)于數(shù)組和存儲器，下列說法不正確的是_。(A)和存儲器一樣，數(shù)組是按線性方式組織數(shù)據(jù)； (B)和存儲器一樣，一維數(shù)組是按線性方式組織數(shù)據(jù)，一個數(shù)據(jù)元素需要一個存儲單元來存儲，一個下標(biāo)即相當(dāng)于一個存儲單元的地址；(C)和存儲器一樣，一維數(shù)組是按線性方式組織數(shù)據(jù)，一個數(shù)據(jù)元素需要一個或多個存儲單元來存儲，一個下標(biāo)即相當(dāng)于一個存儲單元的地址； (D)和存儲器一樣，一維數(shù)組是按

21、線性方式組織數(shù)據(jù)，一個數(shù)據(jù)元素需要一個或多個存儲單元來存儲，一個下標(biāo)即相當(dāng)于一個或多個存儲單元的地址；答案：C解釋：本題考查對存儲器和數(shù)組的理解。數(shù)組是按照線性方式組織數(shù)據(jù)的。當(dāng)一個數(shù)據(jù)元素需要多個存儲單元存儲時，一個下標(biāo)代表的就是多個存儲單元的地址，所以(C)的說法不準(zhǔn)確。其余說法都對。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(2)請對照上圖的左子圖和右子圖來觀察，右子圖的二維數(shù)組是按左圖的形式存儲在存儲器中。則D42元素所對應(yīng)的存儲單元的存儲地址為_。(A)00000000 00000101； (B)00000000 00001000；(C)00000000 0

22、0001010； (D)上述都不正確；答案：B解釋：本題考查對存儲器和數(shù)組的理解。圖中，二維數(shù)組中，D42對應(yīng)的元素是80，而且是第二個80.在存儲器中，找到第二個80的位置，其所對應(yīng)的地址為：00000000 00001000；（B）正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(3)請參照上圖的左子圖和右子圖來觀察，右子圖的二維數(shù)組是按左圖的形式存儲在存儲器中。則Dij元素，與對應(yīng)存儲單元的存儲地址的轉(zhuǎn)換關(guān)系正確的為_。(A)Dij元素的存儲地址=數(shù)組的起始地址+(i-1)*每行的列數(shù)+j-1)*單一元素占用存儲單元的數(shù)目；(B)Dij元素的存儲地址=數(shù)組的起始

23、地址+(i-1)*每行的列數(shù)+j-1；此公式在任何情況下都正確；(C)Dij元素的存儲地址=數(shù)組的起始地址+(j-1)*每行的列數(shù)+i-1)*單一元素占用存儲單元的數(shù)目； (D)Dij元素的存儲地址=數(shù)組的起始地址+(j-1)*每行的列數(shù)+i-1；此公式在任何情況下都正確；答案：A解釋：本題考查對存儲器和二維數(shù)組的理解。記住數(shù)組的下標(biāo)是從0開始編號的。(i-1)*每行的列數(shù)+j-1)得到二維數(shù)組中，所求的元素的下標(biāo)偏移量。(i-1)*每行的列數(shù)+j-1) *單一元素占用存儲單元的數(shù)目得到地址的偏移量。再加上數(shù)組的起始地址，便可得到所求元素的地址。（A）正確。詳細內(nèi)容請參考第七章視頻“算法，程序

24、與計算系統(tǒng)之靈魂”與第七章課件。7.“樹”是一種典型的數(shù)據(jù)結(jié)構(gòu)，在很多算法中都應(yīng)用樹來組織相關(guān)的數(shù)據(jù)。樹是組織層次型數(shù)據(jù)的一種存儲結(jié)構(gòu)，它將每一個數(shù)據(jù)稱為一個數(shù)據(jù)元素。見下圖I.示意，采用三個數(shù)組來存儲樹型數(shù)據(jù)，一個數(shù)組TreeElement存放數(shù)據(jù)元素本身，一個數(shù)組LeftPointer存放該數(shù)據(jù)元素的左側(cè)子元素的存放地址(簡稱為左指針)，另一個數(shù)組RightPointer存放該數(shù)據(jù)元素的右側(cè)子元素的存放地址(簡稱為右指針)。參照圖I.，回答下列問題。圖I.(1)關(guān)于“樹”這種數(shù)據(jù)結(jié)構(gòu)，下列說法不正確的是_。(A)“樹”既需要存儲數(shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲數(shù)據(jù)元素之間的關(guān)系；(B)“樹”

25、可以采用兩個數(shù)組來組織樹型數(shù)據(jù)，其中一個數(shù)組用于存儲數(shù)據(jù)元素本身，另一個數(shù)組用于存儲與該數(shù)據(jù)元素發(fā)生某種關(guān)系的另一個數(shù)據(jù)元素的存儲位置； (C)“樹”可以采用三個數(shù)組來組織樹型數(shù)據(jù)，其中一個數(shù)組用于存儲數(shù)據(jù)元素本身，另外兩個數(shù)組用于存儲與該數(shù)據(jù)元素發(fā)生某種關(guān)系的另外兩個數(shù)據(jù)元素的存儲位置； (D)不僅可以采用(B)(C)的方式組織樹型數(shù)據(jù)，還有其他的方式；(E)上述說法有不正確的。答案：E解釋：本題考查對樹結(jié)構(gòu)的理解?！皹洹奔刃枰鎯?shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲數(shù)據(jù)元素之間的關(guān)系。（A）的說法沒有問題。用兩個數(shù)組組織樹形數(shù)據(jù)時，一個數(shù)組存放數(shù)據(jù)元素，另一個數(shù)組存儲對應(yīng)的父元素。用三個數(shù)組組織

26、樹形數(shù)據(jù)時，一個數(shù)組存放數(shù)據(jù)元素，剩下的兩個數(shù)據(jù)，一個存放對應(yīng)的左兒子，一個存放對應(yīng)的右兒子。組織樹形數(shù)據(jù)時，可以把每個元素當(dāng)做一個節(jié)點，通過指針來指向其兒子。故（B）（C）（D）正確。（E）不正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(2)參照上圖(I)，下列說法不正確的是_。(A)當(dāng)數(shù)據(jù)元素不發(fā)生變化，而只是數(shù)據(jù)元素之間的關(guān)系發(fā)生變化時，可以通過調(diào)整數(shù)據(jù)元素對應(yīng)的左指針數(shù)組或右指針數(shù)組中的值來完成；(B)當(dāng)數(shù)據(jù)元素不發(fā)生變化，而只是數(shù)據(jù)元素之間的關(guān)系發(fā)生變化時，既需要調(diào)整數(shù)據(jù)元素本身，又需要調(diào)整其對應(yīng)的左指針數(shù)組或右指針數(shù)組中的值來完成； (C)相同的數(shù)據(jù)元

27、素，不同的左指針和右指針可以反映數(shù)據(jù)元素之間不同的關(guān)系； (D)圖(a)說明，一個數(shù)據(jù)元素最多只能有兩個子元素，一個是左子元素，一個是右子元素；(E)上述說法有不正確的。答案：B解釋：本題考查對樹結(jié)構(gòu)的理解?！皹洹奔刃枰鎯?shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲數(shù)據(jù)元素之間的關(guān)系。當(dāng)數(shù)據(jù)元素不發(fā)生變化，而只是數(shù)據(jù)元素之間的關(guān)系發(fā)生變化時，數(shù)據(jù)本身是不需要調(diào)整的。(B)錯誤。其余說法均正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(3)上圖(I)表示的數(shù)據(jù)的邏輯關(guān)系，下列正確的是_。(A)圖II.(a)；(B)圖II.(b)； (C)圖II.(c)； (D)圖II.(d)；圖

28、II.答案：D解釋：本題考查對樹結(jié)構(gòu)的理解。第一個元素值為100。其左指針指向的存儲單元的內(nèi)容為地址：00000000 00000010。該地址存儲的數(shù)據(jù)為50。故第一個元素100的左兒子為50。一次類推，可以畫出（d）中的樹。故（D）正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(4)如想使圖(I)，改變?yōu)榇鎯ο聢DIII所示的邏輯關(guān)系，操作正確的是_。圖III.(A)將00000000 00001000號存儲單元的值修改00000000 01101110(即十進制的110)；(B)將00000000 00011010號存儲單元的值修改為00000000 00000

29、111； (C)將00000000 00010001號存儲單元的值修改為00000000 00000000(即Null)； (D)將00000000 00010011號存儲單元的值修改為00000000 00001000；(E)上述(A)(B)(C)(D)都需要正確完成；答案：E解釋：本題考查對樹結(jié)構(gòu)的理解。想要得到題目要求，則需要改變的是100的右兒子的值。首先，增加110這個元素。這是（A）的操作。很容易知道，110這個元素對應(yīng)的左指針指向00000000 00010001，將該單元的存儲內(nèi)容改為NULL，增加了110元素的左兒子為空。這是（C）的操作。然后將100元素的右指針指向110，

30、這是（D）的操作。最后，將110的右指針指向150。這是（C）的操作。至此，整個過程完成。所以，（E）正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(5)如想使圖(I)，改變?yōu)榇鎯ο聢DIV所示的邏輯關(guān)系，下列四步操作都是需要的，但有些操作的內(nèi)容卻是不正確的。不正確的是_。圖IV.(A)將00000000 00001000號存儲單元的值修改為00000000 01010101；(B)將00000000 00010010號存儲單元的值修改為00000000 00000010； (C)將00000000 00011010號存儲單元的值修改為00000000 0000000

31、0(即Null)； (D)將00000000 00001010號存儲單元的值修改為00000000 00001000；答案：B解釋：本題考查對樹結(jié)構(gòu)的理解。(A)的操作是在存儲表中增加85這個元素。（C）的操作是將85的右兒子設(shè)為NULL。（D）的操作是將100的左指針指向85元素的地址。（B）是對00000000 00010010地址進行操作。而改地址在整個過程中，通過其它選項來看，不會有涉及到（B）中的地址。故（B）不正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。8. 堆棧(stack)是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，其特殊支出在于只能允許在鏈結(jié)串行或陣列的一端

32、（稱為堆棧頂端指針，top）進行加入數(shù)據(jù)(push)或輸出數(shù)據(jù)(pop)的運算。其示意圖如下所示。(1)有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的說法，不正確的是_。(A) 堆棧按照先進先出（FIFO, First In First Out）的原理運作；(B) 堆棧按照后進先出（LIFO, Last In First Out）的原理運作；(C) 堆?？梢允褂庙樞虼鎯Y(jié)構(gòu)作為存儲結(jié)構(gòu)；(D) 堆棧可以使用鏈?zhǔn)酱鎯Y(jié)構(gòu)作為存儲結(jié)構(gòu)。答案：A解釋：本題考查對堆棧結(jié)構(gòu)的理解。在堆棧中，先進棧的元素被保存在堆棧下部。在彈出元素時，棧頂?shù)脑叵缺粡棾觥９识褩＿\行的原理是后進先出。（A）不正確，（B）正確。堆?？梢允鬼樞虼鎯Y(jié)構(gòu)和

33、鏈?zhǔn)浇Y(jié)構(gòu)來實現(xiàn)。（C）（D）正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(2) 有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的基本運算，說法不正確的是_。(A) 推入是將數(shù)據(jù)放入堆棧的頂端，堆棧頂端指針top加一；(B) 彈出是將堆棧頂端的數(shù)據(jù)取出，堆棧頂端指針top減一；(C) 如果堆棧頂端指針top為0，則堆棧為空；(D) 如果是固定長度的堆棧，當(dāng)堆棧頂端指針top與長度相等時，堆棧是滿的。(E) 上述說法有不正確的；答案：E解釋：本題考查對堆棧結(jié)構(gòu)的理解。堆棧只有一個出口，那便是棧頂。推入數(shù)據(jù)，是在堆棧的頂端推入，數(shù)據(jù)個數(shù)增加了一，棧頂指針加一，（A）正確。彈出數(shù)據(jù)，也是在堆棧的頂端彈

34、出，數(shù)據(jù)個數(shù)減一，棧頂指針減一，（B）正確。棧頂指針的值代表了堆棧中數(shù)據(jù)的個數(shù)。棧頂指針為0，堆棧為空。棧頂指針為堆棧的固定長度，則堆棧是滿的。（C）(D)均正確。故（E）的說法不正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。(3) 假定當(dāng)前堆棧頂端指針top=10，欲將棧底的元素取出，其他的元素仍然保持在棧中，則需要進行_ _次彈出操作，_ _次推入操作。(A) 1，1 (B) 2，1 (C) 10，9 (D) 10，0 (E) 11，8答案：C解釋：本題考查對堆棧結(jié)構(gòu)的理解。堆棧只有棧頂一個數(shù)據(jù)進出口。棧頂指針的值代表了堆棧中數(shù)據(jù)的個數(shù)。將棧底的元素彈出，則首先

35、必須要使堆棧變空，需要連續(xù)十次彈出操作。再將其他9個元素壓入堆棧，需要9次推入操作。故（C）選項正確。詳細內(nèi)容請參考第七章視頻“算法，程序與計算系統(tǒng)之靈魂”與第七章課件。9. 程序流程圖是表達算法控制結(jié)構(gòu)或者說算法步驟的重要方法?；卮鹣铝袉栴}：(1)觀察下圖I.，沒有錯誤的流程圖為_。圖I.(A)流程圖(a)無錯誤；(B)流程圖(b)無錯誤； (C)流程圖(c)無錯誤； (D)沒有無錯誤的流程圖；答案：D解釋：本題考查流程圖的知識點；圖(a)中，在進行“循環(huán)控制條件成立”這一判斷時，不應(yīng)該使用方向，而應(yīng)該用菱形判斷，所以流程圖(a)錯誤；圖(b)中，當(dāng)判斷循環(huán)控制條件成立為是后，修改部分的返回

36、箭頭不應(yīng)該指向初始化部分，而應(yīng)該返回判斷“循環(huán)控制條件成立”，所以流程圖(b)錯誤；圖(c)中，有兩處錯誤，一是在判斷“循環(huán)控制條件成立”時，沒有標(biāo)明兩個箭頭方向是“是”還是“否”，二是同圖(b)一樣，返回箭頭不應(yīng)該標(biāo)在初始化部分，所以流程圖(c)錯誤；綜上所述，三個圖當(dāng)中都有錯誤。詳細內(nèi)容請參考第七章視頻“算法設(shè)計-算法思想的精確表達(II)”與第七章課件。(2)觀察下圖II.，該流程圖中存在錯誤，下列說法最完整準(zhǔn)確的是_。圖II.(A)條件判斷框不應(yīng)為矩形，而應(yīng)為菱形或六角形；(B)條件判斷框中引出的箭頭應(yīng)標(biāo)記Yes(是)或No(否)，表明條件滿足或不滿足時的程序走向； (C)僅僅包含錯誤

37、(A)和(B)； (D)除錯誤(A)和(B)外，還包括其他錯誤；答案：D解釋：本題考查流程圖的知識點；條件判斷框“循環(huán)控制條件成立”應(yīng)該為菱形或六角形，不是矩形，所以A正確；同時條件判斷框中引出的箭頭要標(biāo)記是或否，表明程序的走向，所以B也正確；根據(jù)流程圖，在判斷控制條件是否成立時，當(dāng)條件為“是”時，返回部分不應(yīng)該是初始化部分，而應(yīng)該是“需循環(huán)執(zhí)行的規(guī)則或語句”，所以該圖中不止AB兩個錯誤，正確答案選D；詳細內(nèi)容請參考第七章視頻“算法設(shè)計-算法思想的精確表達(II)”與第七章課件。10. 閱讀下列算法，回答：Start of the algorithm(算法開始)(1)輸入N的值； (2)設(shè) i

38、 的值為1； (3)如果 i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(7)步執(zhí)行； (4)計算 sum + i，并將結(jié)果賦給sum； (5)計算 i+1，并將結(jié)果賦給i； (6)返回到第3步繼續(xù)執(zhí)行； (7)輸出sum的結(jié)果。 End of the algorithm(算法結(jié)束) 上述算法_。(A)能夠正確地計算sum=1+2+3+4+N； (B)不能正確地計算sum=1+2+3+4+N；答案：B解釋：本題考查步驟描述法 ；在上述步驟中，主要欠缺的是程序的初始化，雖然有將i的初始值設(shè)為1，但sum的初始值確忽略了，這樣，沒辦法正確計算sum=1+2+3.+N，應(yīng)該把sum初始值設(shè)為0；詳細內(nèi)

39、容請參考第七章視頻“算法設(shè)計-算法思想的精確表達(II)”與第七章課件。11. 閱讀下列算法，回答：Start of the algorithm(算法開始)(1) N=10； (2) i=2；sum=2； (3) 如果 i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(8)步執(zhí)行； (4) 如果i / 2 =0 則轉(zhuǎn)到第(6)步執(zhí)行；(5) sum = sum + i； (6) i = i+1； (7) 返回到第(3)步繼續(xù)執(zhí)行； (8) 輸出sum的結(jié)果。 End of the algorithm(算法結(jié)束) 算法執(zhí)行的結(jié)果為_。(A) 24； (B) 26； (C) 55； (D) 45； (

40、E) 46；答案：B解釋：本題考查步驟敘述法；由題意，可畫出如圖所示的流程圖：所以，當(dāng)i為奇數(shù)時，sum=sum+i；i=3，sum=5； i=5，sum=10；i=7，sum=17；i=9，sum=26；綜上所述，結(jié)果為26，選B；具體內(nèi)容請參考課堂視頻“算法設(shè)計-算法思想的精確表達(III)”和第七章課件；12. TSP算法流程圖如下圖I.示意，回答下列問題：圖I.(1)最內(nèi)層循環(huán)(L變量控制的循環(huán))的作用是_。(A)用于判斷某個城市是否是已訪問過的城市；(B)用于尋找距當(dāng)前城市距離最近的城市；(C)用于完整地產(chǎn)生一個路徑； (D)上述都不是； 答案：A解釋：本題考查學(xué)生是否能讀懂流程圖以

41、及TSP流程；圖中最內(nèi)層循環(huán)，L從1至I-1, 循環(huán)判斷第K個城市是否是已訪問過的城市，如是則不參加最小距離的比較；所以，正確答案選A；具體內(nèi)容請參考課堂視頻“算法設(shè)計-算法思想的精確表達(III)”和第七章課件；(2)中層循環(huán)(K變量控制的循環(huán))的作用是_。(A)用于判斷某個城市是否是已訪問過的城市；(B)用于尋找距當(dāng)前城市距離最近的城市；(C)用于完整地產(chǎn)生一個路徑； (D)上述都不是； 答案：B解釋：本題考查學(xué)生是否能讀懂流程圖以及TSP流程；圖中中層循環(huán)， K從第2個城市至第N個城市循環(huán), 判斷DK, SI-1是否是最小值，j記錄了最小距離的城市號K；所以，正確答案選B；具體內(nèi)容請參考

42、課堂視頻“算法設(shè)計-算法思想的精確表達(III)”和第七章課件；(3)外層循環(huán)(I變量控制的循環(huán))的作用是_。(A)用于判斷某個城市是否是已訪問過的城市；(B)用于尋找距當(dāng)前城市距離最近的城市；(C)用于完整地產(chǎn)生一個路徑； (D)上述都不是； 答案：C解釋：本題考查學(xué)生是否能讀懂流程圖以及TSP流程；圖中外層循環(huán)，I從2至N循環(huán)；I-1個城市已訪問過，正在找與第I-1個城市最近距離的城市；已訪問過的城市號存儲在S中；所以，正確答案選C；具體內(nèi)容請參考課堂視頻“算法設(shè)計-算法思想的精確表達(III)”和第七章課件；13.一般而言，算法設(shè)計完成后，需要進行算法的模擬與分析。關(guān)于算法的模擬與分析回

43、答下列問題：(1)通常從哪些方面，進行算法的模擬與分析_。(A)算法的正確性問題，即一個算法求得的解是滿足問題約束的正確的解嗎(B)算法的效果評價問題，即算法輸出的是最優(yōu)解還是可行解，其可行解與最優(yōu)解的偏差有多大(C)算法的時間效率問題(時間復(fù)雜性)，即算法執(zhí)行所需要的時間是多少(D)算法的空間效率問題(空間復(fù)雜性)，即算法執(zhí)性所需要的空間是多少(E)上述全部。 答案：E解釋：本題考查算法分析和算法復(fù)雜性；當(dāng)對一個算法進行模擬與分析時，有以下幾個方面要判斷：（1）問題求解的過程、方法算法是正確的嗎算法的輸出是問題的解嗎（2）算法的輸出是最優(yōu)解還是可行解如果是可行解，與最優(yōu)解的偏差多大（3）算法

44、獲得結(jié)果的時間有多長即分為時間復(fù)雜性和空間復(fù)雜性；所以，答案應(yīng)選E；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(2)算法的時間復(fù)雜性，可以表達為關(guān)于問題規(guī)模n的一個函數(shù)T(n)，T(n)可以用大O表示法來處理。問T(n)=O(f(n)是什么意思正確的是_。(A)T(n)是關(guān)于f(n)的一個函數(shù)；(B)T(n)是與f(n)同數(shù)量級的函數(shù)；(C)T(n)是將函數(shù)f(n)代入O(x)中所形成的新函數(shù)；(D)T(n)是依據(jù)f(n)計算出來的；答案：B解釋：本題考查時間復(fù)雜性，和大“O”記法；時間復(fù)雜性是指如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n

45、)，它是n的某一函數(shù)，T(n)稱為這一算法的“時間復(fù)雜性”?！按驩記法”：基本參數(shù) n表示問題實例的規(guī)模，把復(fù)雜性或運行時間表達為n的函數(shù)。“O”表示量級 (order)，允許使用“=”代替“”，如n2+n+1 =(n2)，所以正確答案選B；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(3)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復(fù)雜性。(10) K = 0；(20)I = 2；(30)While (I<=8)(40) K = K + I； (50)I = I + 2；該程序時間復(fù)雜性表達正確的是_。(A)O(

46、n)；(B)O(1)；(C)O(n2)；(D)O(n!)；答案：B解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：K = 0；1次I = 2； 1次While (I<=8) 8次 K = K + I； 8次I = I + 2； 8次T(n)=1+1+8 ×3= O(1)，所以答案選B；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(4)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復(fù)雜性。(10) sum=0；       

47、0;         (20) For(i=1; i<=n; i+)    (30)For(j=1; j<=n; j+)(40)For(k=1; k<=j; k+)(50)sum=sum+1；該程序時間復(fù)雜性表達正確的是_。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對；答案：C解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：(10) sum=0；       

48、;          1次(20) For(i=1; i<=n; i+)     n次(30)For(j=1; j<=n; j+) n2次(40)For(k=1; k<=j; k+) n3次(50)sum=sum+1； n3次T(n) = 2 n3 + n2 + n + 1 = O(n3)，所以正確答案選C；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(5)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)

49、來獲得。分析下列程序的時間復(fù)雜性。(10) sum=0；                 (20) For(i=1; i<=n; i+)    (30)For(j=1; j<=n; j+)(40)For(k=1; k<=5; k+)(50)sum=sum+1；該程序時間復(fù)雜性表達正確的是_。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對；答案：B解釋：本題考

50、查時間復(fù)雜性，和大“O”記法；具體分析如下：(10) sum=0；                 1次(20) For(i=1; i<=n; i+)     n次(30)For(j=1; j<=n; j+) n2次(40)For(k=1; k<=5; k+) 5 n2次(50)sum=sum+1； 5 n2次T(n)= 11n2 + n + 1 = O(n2)，所以正確答案選B

51、；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(6)閱讀下面的程序，其時間復(fù)雜度為_A. O(1) B. O(n) C. O(n2) D. O(n*log n)int index = 5;int condition=1;if (condition=1) then index+;else index-；for i = 1 to 100 for j = 1 to 200 index=index+2;答案：A解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：int index = 5; 1次int condition=1; 1次if (condition=1)

52、then 1次 index+; 1次else index-；for i = 1 to 100 100次 for j = 1 to 200 200×100次 index=index+2; 200×100次所以T(n)=O(1)，正確答案選A；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件； (7)為什么要評估算法的復(fù)雜性下列說法不正確的是_。(A)當(dāng)算法的時間復(fù)雜性量級為多項式函數(shù)時，計算機是能夠完成計算的；(B)當(dāng)算法的時間復(fù)雜性量級為非多項式函數(shù)時，如指數(shù)函數(shù)、階乘函數(shù)時，計算機是不能夠完成計算的；(C)當(dāng)算法的時間復(fù)雜性量級為非多項式函數(shù)時，

53、如指數(shù)函數(shù)、階乘函數(shù)時，對于大規(guī)模問題，計算機是不能夠完成計算的；(D)上述說法有不正確的；答案：B解釋：本題考查算法分析與計算復(fù)雜性；當(dāng)算法的時間復(fù)雜度的表示函數(shù)是一個多項式時，如O(n2)時，則計算機對于大規(guī)模問題是可以處理的。當(dāng)算法的時間復(fù)雜度是用指數(shù)函數(shù)表示時，如O(2n)，當(dāng)n很大（如10000）時計算機是無法處理的，在計算復(fù)雜性中將這一類問題被稱為難解性問題。所以對于B的表達，只有當(dāng)n很大時，屬于大規(guī)模問題時，計算機才不能完成，表達不精確，所以正確答案為B；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(*8)算法的時間復(fù)雜性T(n)，可以通過評估算法基本語句的執(zhí)行次數(shù)來獲得。分析下列算法的時間復(fù)雜性。Start of the algorithm(算法開始)(1) 輸入結(jié)點的數(shù)目n； (2) 當(dāng)前最短路徑Path設(shè)為空，當(dāng)前最短距離Dtemp設(shè)為最大值；注：一個路徑是n個結(jié)點的一個組合，任何一個結(jié)點在路經(jīng)中不能重復(fù)出現(xiàn) (3) 組合一條新路徑NewPath并計算該路徑的距離D； (4) 如果D<Dtemp 則Path = NewPa