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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、容請(qǐng)參考第七章視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(II)”與第七章課件。11. 閱讀下列算法，回答：Start of the algorithm(算法開(kāi)始)(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é)果為_(kāi)。(A) 24； (B) 26； (C) 55； (D) 45； (

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

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

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

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

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

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

46、n)；(B)O(1)；(C)O(n2)；(D)O(n!)；答案：B解釋：本題考查時(shí)間復(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)容請(qǐng)參考課堂視頻“高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性”和第七章課件；(4)算法的時(shí)間復(fù)雜性T(n)，可以通過(guò)計(jì)算算法基本語(yǔ)句的執(zhí)行次數(shù)來(lái)獲得。分析下列程序的時(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；該程序時(shí)間復(fù)雜性表達(dá)正確的是_。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對(duì)；答案：C解釋：本題考查時(shí)間復(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)容請(qǐng)參考課堂視頻“高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性”和第七章課件；(5)算法的時(shí)間復(fù)雜性T(n)，可以通過(guò)計(jì)算算法基本語(yǔ)句的執(zhí)行次數(shù)

49、來(lái)獲得。分析下列程序的時(shí)間復(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；該程序時(shí)間復(fù)雜性表達(dá)正確的是_。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對(duì)；答案：B解釋：本題考

50、查時(shí)間復(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)容請(qǐng)參考課堂視頻“高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性”和第七章課件；(6)閱讀下面的程序，其時(shí)間復(fù)雜度為_(kāi)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解釋：本題考查時(shí)間復(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)容請(qǐng)參考課堂視頻“高級(jí)問(wèn)題初探: 算法分析與計(jì)算復(fù)雜性”和第七章課件； (7)為什么要評(píng)估算法的復(fù)雜性下列說(shuō)法不正確的是_。(A)當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為多項(xiàng)式函數(shù)時(shí)，計(jì)算機(jī)是能夠完成計(jì)算的；(B)當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為非多項(xiàng)式函數(shù)時(shí)，如指數(shù)函數(shù)、階乘函數(shù)時(shí)，計(jì)算機(jī)是不能夠完成計(jì)算的；(C)當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為非多項(xiàng)式函數(shù)時(shí)，

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