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

1、第 7章 算法: 程序與計(jì)算系統(tǒng)之靈魂第7章算法程序與計(jì)算系統(tǒng)之靈 魂練習(xí)題答案解析1、算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則 規(guī)定了解決某一特定類(lèi)型問(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ō)法有不

2、正確的；答案：C解釋?zhuān)罕绢}考查對(duì)算法基本性質(zhì)的理解(C) 算法的輸出性：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。因此(C)選項(xiàng)錯(cuò)誤。其余選項(xiàng)，(A) (B) ( D )分 別是對(duì)算法的有窮性， 確定性和能行性的正確描 述。具體內(nèi)容參考第七章視頻之 “算法與算法類(lè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)算和

3、操作必須相當(dāng)基本，可以由機(jī)器自動(dòng)完(B) 違反了算法的有窮性：一個(gè)算法在執(zhí)行有 窮步規(guī)則之后必須結(jié)束。因此(B)選項(xiàng)錯(cuò)誤。 其余選項(xiàng)， ( A ) ( C ) ( D )分別是對(duì)算法的有窮 性，輸入輸出性和確定性的正確描述。具體內(nèi)容參考第七章視頻之 “算法與算法類(lè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è)算法不一定

4、獲得相同的 解。答案： B解釋?zhuān)罕绢}考查對(duì)算法基本性質(zhì)的理解(C) 算法是解決問(wèn)題的步驟，執(zhí)行的語(yǔ)言是步 驟書(shū)寫(xiě)的規(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)容參考第七章視頻之 “算法與算法類(lè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)解 決，“是

5、否會(huì)編程序”本質(zhì)上章是“能否想出求 解該問(wèn)題的算法”；(C) 一個(gè)算法不僅可以解決一個(gè)具體問(wèn)題，它 可以在變換輸入輸出的情況下， 求解一個(gè)問(wèn)題系 列；(D) 問(wèn)題求解都可以歸結(jié)到算法的構(gòu)造與設(shè) 計(jì)，系統(tǒng)和算法的關(guān)系是：算法是龍，而系統(tǒng)是睛，畫(huà)龍要點(diǎn)睛。(E) 上述說(shuō)法有不正確的;答案：D解釋?zhuān)?本題考查算法、程序與系統(tǒng)之間的關(guān)系(D) 選項(xiàng)，算法是計(jì)算系統(tǒng)的靈魂，因此系統(tǒng) 和算法的關(guān)系是：系統(tǒng)是龍，算法是睛，好的算 法能起到畫(huà)龍點(diǎn)睛的效果。(A)(B)(C)選項(xiàng) 描述正確。具體內(nèi)容參考第七章視頻之 “算法與算法類(lèi)問(wèn) 題的求解”以及第七章課件。2、哥尼斯堡七橋問(wèn)題，是一個(gè)經(jīng)典問(wèn)題，如下 圖(a)

6、所示，描述為“由河流隔開(kāi)的四塊陸地上建 造了七座橋， 尋找走遍這七座橋且只許走過(guò)每座 橋一次最后又回到原出發(fā)點(diǎn)的路徑” 。關(guān)于哥尼 斯堡七橋問(wèn)題， 著名數(shù)學(xué)家歐拉對(duì)該問(wèn)題做了一 個(gè)抽象：“頂點(diǎn)”為陸地，“邊”為連接兩塊陸地 的橋梁。這個(gè)抽象被稱(chēng)為“圖” ，并定義了頂點(diǎn) 的“度”為連接一個(gè)頂點(diǎn)的邊的數(shù)量。關(guān)于此問(wèn)題回答下列問(wèn)題。/本題考查問(wèn)題及其數(shù)學(xué)建模的作用（a）丫 （b）（1）哥尼斯堡七橋問(wèn)題的路徑能夠找到嗎？（A）一定能夠找到；（B） 定不能找到；（C）不確定能不能找到。答案：B解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用 選擇（B），根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖 形可以一筆畫(huà)，需要滿足：1）

7、圖形必須是連通 的; 2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù) 的點(diǎn)）個(gè)數(shù)是0或2 （該題中應(yīng)為0 個(gè)）。該問(wèn) 題中將四個(gè)島抽象成4個(gè)點(diǎn)，每條橋抽象成邊， 可知圖中奇點(diǎn)個(gè)數(shù)是4個(gè)，因此不可能找到。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法 策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料（2）對(duì)河流隔開(kāi)的 m 塊陸地上建造的 n 座橋梁， 能否找到走遍這 n 座橋且只許走過(guò)每座橋一次 最后又回到原出發(fā)點(diǎn)的路徑呢？ 。（A）定能夠找到；（B） 定不能找到；（C）不確定能不能找到。答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足：

8、1）圖形必須是連 通的； 2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn)）個(gè)數(shù)是 0 或 2（該題中因?yàn)槠瘘c(diǎn)和終點(diǎn) 是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè)）。該問(wèn)題中將 m 個(gè)島抽象成 m 個(gè)點(diǎn)，每條橋抽象成邊，但圖 中奇點(diǎn)個(gè)數(shù)未知，因此不能做判斷。具體內(nèi)容參考第七章視頻之 “算法與算法類(lèi)問(wèn) 題的求解，第七章課件或查閱歐拉回路相關(guān)資 料。(3) 對(duì)河流隔開(kāi)的 m 塊陸地上建造的 n 座橋梁， 若要找到走遍這 n 座橋且只許走過(guò)每座橋一次 最后又回到原出發(fā)點(diǎn)的路徑， 則需滿足以下條件(A) m 個(gè)頂點(diǎn) n 條邊的圖應(yīng)是連通的，即由一 個(gè)頂點(diǎn)出發(fā)可沿邊到達(dá)任何一個(gè)其他頂點(diǎn)；(B) 每個(gè)頂點(diǎn)的度應(yīng)為偶數(shù)；

9、(C) 既需要滿足(A)又需要滿足(B);(D) 上述條件還不夠，還需滿足更多條件。答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇(C)根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足： 1)圖形必須是連 通的； 2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn))個(gè)數(shù)是 0或 2(該題中因?yàn)槠瘘c(diǎn)和終點(diǎn) 是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè))。該問(wèn)題中將 m 個(gè)島抽象成 m 個(gè)點(diǎn)，每條橋抽象成邊，因此 應(yīng)該選擇 C。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法 策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。（4）下面所示的圖（c），能否找到走遍每一座橋， 且每座橋僅走過(guò)一次、最后又回

10、到原出發(fā)點(diǎn)的路 徑呢？卜9（c）（A） 一定能夠找到；（B） 定不能找到；（C）不確定能不能找到。答案：B解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（B）根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足：1）圖形必須是連 通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn)）個(gè)數(shù)是0或2 （該題中因?yàn)槠瘘c(diǎn)和終點(diǎn)是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè))。圖中奇點(diǎn)是C與G,個(gè)數(shù)為2,不符合要求，因此應(yīng)該選擇 B。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法 策略設(shè)計(jì) -算法思想”,第七章課件或查閱歐拉回 路相關(guān)資料。(5) 參見(jiàn)圖(c)，增加哪些邊，使得能夠找到走遍 每一座橋, 且每座橋僅走過(guò)一次、

11、 最后又回到原 出發(fā)點(diǎn)的路徑呢？(A) BG 邊； (B)AG 邊； (C)CG 邊； (D)AD 邊； (E)DE 邊。答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇(C)根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足： 1)圖形必須是連 通的； 2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn))個(gè)數(shù)是 0 或 2(該題中因?yàn)槠瘘c(diǎn)和終點(diǎn) 是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè))。圖中奇點(diǎn)是C與G,個(gè)數(shù)為2,不符合要求，因此在 CG間 增加一條邊， 將寄點(diǎn)數(shù)變成 0 可滿足要求， 因此 應(yīng)該選擇 C。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法策 略設(shè)計(jì)-算法思想”,第七章課件或查閱歐拉回路

12、 相關(guān)資料。(6-1)對(duì)河流隔開(kāi)的 m 塊陸地上建造的 n 座橋梁, 若要找到走遍這 n 座橋且只許走過(guò)每座橋一次 的路徑,則需滿足以下條件 。(A) m 個(gè)頂點(diǎn) n 條邊的圖應(yīng)是連通的,即由一 個(gè)頂點(diǎn)出發(fā)可沿邊到達(dá)任何一個(gè)其他頂點(diǎn)；(B) 每個(gè)頂點(diǎn)的度應(yīng)為偶數(shù)；(C) 既需要滿足(A)又需要滿足(B)；(D) 不滿足上述條件(A)(B)(C)的圖也能找出滿 足題目規(guī)定要求的路徑；答案：D解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇(D)，此題未要求回到原地，即起點(diǎn)和 終點(diǎn)可以不是一個(gè)， 那么可以有 2 個(gè)奇數(shù)點(diǎn)作為 起點(diǎn)和終點(diǎn)。 根據(jù)歐拉回路關(guān)系可知， 要是一個(gè) 圖形可以一筆畫(huà)，需要滿足： 1)

13、圖形必須是連 通的； 2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn))個(gè)數(shù)是 0或 2。不同時(shí)滿足( A)(B)， 可以有 2 個(gè)頂點(diǎn)的度為奇數(shù)， 也可以滿足題目要 求，因此應(yīng)該選擇 D。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法 策略設(shè)計(jì) -算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。(6-2)對(duì)河流隔開(kāi)的 m 塊陸地上建造的 n 座橋梁， 若要找到走遍這 n 座橋且只許走過(guò)每座橋一次 的路徑，則需滿足以下條件 。(A) m 個(gè)頂點(diǎn) n 條邊的圖應(yīng)是連通的，即由一 個(gè)頂點(diǎn)出發(fā)可沿邊到達(dá)任何一個(gè)其他頂點(diǎn)；(B) 每個(gè)頂點(diǎn)的度應(yīng)為偶數(shù)，或者，只有兩個(gè) 頂點(diǎn)的度為奇數(shù)而其他頂點(diǎn)的度均為偶數(shù)；(

14、C) 既需要滿足(A)又需要滿足(B);(D) 不滿足上述條件(A)(B)(C)的圖也能找出滿 足題目規(guī)定要求的路徑；答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）,此題未要求回到原地，即起點(diǎn)和 終點(diǎn)可以不是一個(gè)，那么可以有2個(gè)奇數(shù)點(diǎn)作為 起點(diǎn)和終點(diǎn)。根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足：1）圖形必須是連 通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn)）個(gè)數(shù)是0或2。因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法 策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。下面所示的圖（d）和圖（e）,問(wèn)能否找到走遍每 一座橋，且每座橋僅走過(guò)一次的路徑

15、呢？(A) 圖(d)和圖(e)都一定不能找到；(B) 圖(d)一定能夠找到；圖(e)一定不能找到;(C) 圖(d) 一定不能找到；圖(e)定能夠找到;(D) 圖(d)和圖(e)都 一定能夠找到；答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇(C)根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可以一筆畫(huà)，需要滿足：1)圖形必須是連 通的；2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn))個(gè)數(shù)是0或2。d圖有FGE三個(gè)奇點(diǎn), 一定不能找到，而e圖有FG兩個(gè)奇點(diǎn)，一定能 找到，因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法 策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。(8) 參見(jiàn)下圖(

16、f)，下列說(shuō)法正確的是.(A)對(duì)A、B、C、D、E、F、G中的任意兩個(gè) 頂點(diǎn)X和Y，都可以找到一條路徑，從X出發(fā)走 遍每一座橋，且每座橋僅走過(guò)一次，最后終止于(B) 對(duì)兩個(gè)頂點(diǎn)A和B，可以找到一條路徑， 從A出發(fā) 走遍每一座橋，且每座橋僅走過(guò)一次， 最后終止于B ；(C) 對(duì)兩個(gè)頂點(diǎn)D和G,可以找到一條路徑， 從D出發(fā) 走遍每一座橋，且每座橋僅走過(guò)一次， 最后終止于G ；(D) 對(duì)A、B、C、D、E、F、G中的任意兩個(gè) 頂點(diǎn)X和Y，都找不到一條路徑，從X出發(fā)走 遍每一座橋，且每座橋僅走過(guò)一次，最后終止于答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇(C)根據(jù)歐拉回路關(guān)系可知，要是一個(gè) 圖形可

17、以一筆畫(huà)，需要滿足： 1)圖形必須是連 通的； 2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇 數(shù)的點(diǎn))個(gè)數(shù)是0或2。該圖奇點(diǎn)為G和D，因 此可以找到一條歐拉回路， 并且只能以此兩點(diǎn)作 為起點(diǎn)和終點(diǎn)，因此應(yīng)該選擇 C。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法 策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。(9) 哥尼斯堡七橋問(wèn)題，給我們的啟示是 。(A) 一個(gè)具體問(wèn)題應(yīng)該進(jìn)行數(shù)學(xué)抽象，基于數(shù) 學(xué)抽象進(jìn)行問(wèn)題求解；(B) 個(gè)具體問(wèn)題的求解，進(jìn)行數(shù)學(xué)建模后， 通過(guò)模型中的性質(zhì)分析可以判斷該問(wèn)題是否有 解，如果有解，則可以進(jìn)行計(jì)算；而如果無(wú)解， 則無(wú)需進(jìn)行計(jì)算；(C) 一個(gè)具體問(wèn)題的求解方法，

18、進(jìn)行數(shù)學(xué)建模 后，可反映出一類(lèi)問(wèn)題的求解方法， 例如哥尼斯 堡七橋問(wèn)題的求解方法，建立“圖”后，可反映 任意 n 座橋的求解方法；(D) 上述全部；答案：D解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用 以上說(shuō)明都正確， 對(duì)一個(gè)具體問(wèn)題的求解， 可 先進(jìn)行數(shù)學(xué)建模，將具體問(wèn)題轉(zhuǎn)化成抽象問(wèn)題， 再進(jìn)行判斷是否有解， 若有解則計(jì)算， 若無(wú)解則 無(wú)需計(jì)算。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法 策略設(shè)計(jì) -算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。(10) 哥尼斯堡七橋問(wèn)題， 推而廣之就是 m 個(gè)頂點(diǎn) n 條邊的圖的“一筆畫(huà)”問(wèn)題，我們可以給出一 個(gè)算法來(lái)求解該問(wèn)題，即“對(duì)河流隔開(kāi)的 m 塊 陸地上

19、建造的 n 座橋梁，若要找到走遍這 n 座橋 且只許走過(guò)每座橋一次的路徑” 。 關(guān)于該算法的 基本思想，下列說(shuō)法正確的是 (A) 以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照?qǐng)D的“邊” 的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂 點(diǎn)，并標(biāo)記該邊為“已訪問(wèn)” ，依次循環(huán)，直到 所有的邊都被訪問(wèn)過(guò)為止， 便可找到給定問(wèn)題的 解；(B) 以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照?qǐng)D的未訪問(wèn) 過(guò)“邊”的指示，找到按該邊與該頂點(diǎn)相連的下 一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問(wèn)” ，依次循環(huán)， 直到所有的邊都被訪問(wèn)過(guò)為止， 便可找到給定問(wèn) 題的解；(C) 首先判斷該問(wèn)題是否有解，若無(wú)解，則直 接退出；若有解，則以任何一個(gè)頂點(diǎn)為起點(diǎn)，按 照?qǐng)D的未訪問(wèn)

20、過(guò)“邊”的指示，找到按該邊與該 頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪 問(wèn)”，依次循環(huán)， 直到所有的邊都被訪問(wèn)過(guò)為止， 便可找到給定問(wèn)題的解；(D) 首先判斷該問(wèn)題是否有解，若無(wú)解，則直 接退出；若有解， 則選擇一個(gè)奇數(shù)度的頂點(diǎn)為起 點(diǎn)，按照?qǐng)D的未訪問(wèn)過(guò)“邊”的指示，找到按該 邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問(wèn)”，依次循環(huán)，直到所有的邊都被訪問(wèn) 過(guò)為止，便可找到給定問(wèn)題的解；（E）上述都不正確答案：D解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（D）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖 形可以一筆畫(huà)，需要滿足： 1）圖形必須是連通 的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù) 的點(diǎn)）個(gè)

21、數(shù)是 0 或 2。因此，若有奇點(diǎn)，則起點(diǎn) 和終點(diǎn)必須是奇點(diǎn)，若無(wú)，則任意，因此（ A ）（ B）（ C） ，因此應(yīng)該選擇 D。具體內(nèi)容參考第七章視頻之 “數(shù)學(xué)建模與算法 策略設(shè)計(jì) -算法思想”，第七章課件或查閱歐拉回 路相關(guān)資料。3、背包問(wèn)題的定義是：給定一組物品，每種物 品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)， 我們?nèi)绾芜x擇， 才能使得物品的總價(jià)格最高。 問(wèn) 題的名稱(chēng)來(lái)源于如何選擇最合適的物品放置于 給定背包中。 背包問(wèn)題的一個(gè)例子： 應(yīng)該選擇哪些盒子，才能使價(jià)格盡可能地大，而保持重量小 于或等于15 kg?其示意圖如下：(1) 該背包問(wèn)題的可能解的數(shù)量是。(A) 5(B) 10(C) 3

22、2(D) 64答案：C解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知，只要可放入背包的狀態(tài)都算是可 能解，可以按背包容量由1到15遍歷可能性。 答案為(C)32個(gè)。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。(2) 假定求解該問(wèn)題的一種貪心策略是：優(yōu)先選擇 能裝下盒子中價(jià)格最高的，依據(jù)該算法策略所得到的解的總價(jià)值是 。(A) 16 (B) 15(C) 14(D) 13答案：B解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知使用貪心算法， 從價(jià)值最高的開(kāi)始 放入，第一個(gè)放入價(jià)值 $10的 4kg 物品，接下來(lái) 價(jià)值最大的是 $4，但再加上 12kg 已經(jīng)超過(guò)了背 包的限度，所以不可放入，接下來(lái)放入其余的 3 個(gè)

23、可滿足重量限制的物品，總價(jià)值是15，所以選擇( B)。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。(3) 假定求解該問(wèn)題的一種貪心策略是： 優(yōu)先選擇 能裝下盒子中單位重量?jī)r(jià)值最高的， 依據(jù)該算法 策略所得到的解的總價(jià)值是 。(A) 16(B) 15(C) 14(D) 13答案： B 解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用 由題意可知使用貪心算法， 從單位價(jià)值最高的 開(kāi)始放入，五個(gè)物品單位價(jià)值從大到小依次為： 2.5,2,1,1,1/3，依次放入并驗(yàn)證是否超出背包重量 限制：$10-4kg, $2-1kg,$1-1kg,$2-2kg ,之后放不 下$4-12kg的物品，到此總價(jià)值是15,所以選擇(B) 。具體內(nèi)

24、容查閱背包問(wèn)題相關(guān)資料。(4) 假定求解該問(wèn)題的一種貪心策略是：最大程 度地利用背包的容量(15kg)，依據(jù)該算法策略 所得到的解的總價(jià)值是 。(A) 8(B) 15(C) 14(D) 13答案： A解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知使用貪心算法， 需要讓剩余空間最 小 ， 那 么 可 以 得 到 的 組 合 是 ， 12kg+2kg+1kg=15kg ，重量得到最大利用，總價(jià) 值是 8，所以選擇（ A ）。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。（5）使用遍歷算法策略所得到的解的總價(jià)值是(A) 8 (B) 15 (C) 14 (D) 13答案：B解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用 用遍歷

25、算法策略，狀態(tài)轉(zhuǎn)移方程： fv=maxfv,fv-ci+wi ，即 fiv 表示前 i 件物品恰放入一個(gè)容量為 v 的背包可以獲得的 最大價(jià)值，第 i 件物品的重量是 ci ，價(jià)值是 wi 。 “將前 i 件物品放入容量為 v 的背包中 ”這個(gè)子問(wèn) 題，若只考慮第 i 件物品的策略（放或不放） ， 那么就可以轉(zhuǎn)化為一個(gè)只牽扯前 i-1 件物品的問(wèn) 題。如果不放第 i 件物品，那么問(wèn)題就轉(zhuǎn)化為 “前 i-1 件物品放入容量為 v 的背包中 ”，價(jià)值為 fi-1v ；如果放第 i 件物品，那么問(wèn)題就轉(zhuǎn)化為“前 i-1 件物品放 入剩下的容量為 v-ci 的背包 中 ”，此時(shí)能獲得的最大價(jià)值就是f

26、i-1v-ci再加上通過(guò)放入第 i 件物品獲得的價(jià)值 wi 。按 此方法，可得總價(jià)值是 15，所以選擇( B)。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。(6) 假定有 N 個(gè)物品，其價(jià)值分別為 V1, V2, ., 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ù)是 max xiVi ；i1(B) 問(wèn)題的目標(biāo)函數(shù)是 max x iWi ；i1(C) 問(wèn)題解所應(yīng)滿足的約束是xiWi Wmax ；i1

27、(D) 問(wèn)題解所應(yīng)滿足的約束是xiVi Wmax ；i1(E)前述(A)和(C);答案：E 解釋?zhuān)罕绢}考查問(wèn)題及其數(shù)學(xué)建模的作用 該問(wèn)題有兩個(gè)條件： 1）物品不能超過(guò)背包所能承受的重量，即（ C） 選項(xiàng)： x iWi Wmaxi12）背包內(nèi)物品價(jià)值最大，即（A）選項(xiàng)目標(biāo)函N max x iVi 數(shù)為 i1 i i（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è)城市逗留

28、一次，最后回到原出發(fā)城市， 問(wèn)如何事先確定好 一條最短的路線使其旅行的費(fèi)用最少” 。圍繞 TSP，回答下列問(wèn)題。關(guān)于TSP問(wèn)題的遍歷算法和貪心算法，下列 說(shuō)法正確的是。(A) 對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求 得的解是一樣的，所不同的是貪心算法更快一 些，而遍歷算法更慢一些；(B) 對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求 得的解是一樣的，所不同的是遍歷算法更快一 些，而貪心算法更慢一些；(C) 對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求 得的解是不一樣的，貪心算法是求近似解，執(zhí)行 更快一些，而遍歷算法是求精確解，執(zhí)行更慢一(D) 對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求 得的解是不一樣的，貪心

29、算法是求精確解，執(zhí)行 更快一些，而遍歷算法是求近似解，執(zhí)行更慢一 答案：C解釋?zhuān)罕绢}考查對(duì)貪心算法與遍歷算法的簡(jiǎn)單理解 貪心算法：一定要做當(dāng)前情況下的最好選擇， 否則將來(lái)可能會(huì)后悔，故名“貪心” 。如果以 A 城市為起點(diǎn)，選擇最近的下一點(diǎn)，為 B 城市。以 B城市為起點(diǎn)，選擇最近的下一個(gè)城市，可以選 擇C或D,以選擇D為例。以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)選擇，其

30、時(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)之靈魂”與第七章課件。關(guān)于TSP，下列說(shuō)法不正確的是。(A) TSP 問(wèn)題的一個(gè)可能解就是 n 個(gè)城市的一 個(gè)組合<tl,壇,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!)

31、 ，以致于計(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解釋?zhuān)罕绢}考查對(duì)TSP組合優(yōu)化問(wèn)題的理解 對(duì)所有組合進(jìn)行比較的思想， 即所謂的遍歷算 法策略，其組合數(shù)目為 n! 。2001 年解決了德國(guó) 15112個(gè)城市的TSP問(wèn)題，使用了美國(guó)Rice大 學(xué)和普林斯頓大學(xué)之間互連的、速度為 500MHz 的 Compaq EV6 Alpha 處理

32、器組成的 110 臺(tái)計(jì)算 機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為 22.6 年。由 此可見(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è)組合tl, t2,tn時(shí)，tk+1是與 tk相連接的城市中與tk距離最短的城市，即tk+1 是由 tk 確定的，與 tk 連接的若干

33、城市中的特性 最優(yōu)的城市；(C) 貪心算法確定的路徑，是由局部最優(yōu) (即 tk+1 在 tk 看來(lái)是最優(yōu)的 )組合起來(lái)的路徑， 該路徑 從全局角度也一定是最優(yōu)的；(D) 對(duì)一個(gè)具體的TSP問(wèn)題，每次執(zhí)行貪心算 法，所求得的最終解可能是不同的。答案：C解釋?zhuān)罕绢}考查對(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)的情 況，所以每次執(zhí)行貪心算法的最終解的結(jié)果可能 是不同的。故 (D) 正確。

34、詳細(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è)盤(pán)子在三個(gè)柱子上的移動(dòng)問(wèn)題 (梵天塔 問(wèn)題或者說(shuō)漢諾塔問(wèn)題 )；(C) n 座橋， 走過(guò)每座橋且僅走過(guò)一次的問(wèn)題(圖的遍歷問(wèn)題 )；(D) 上述(A)(B)(C)都可以答案：A解釋?zhuān)罕绢}考查對(duì)TSP問(wèn)題抽象的理解求解TSP問(wèn)題采用的是貪心算法。(A)選項(xiàng)所 描述的問(wèn)題其實(shí)就是TSP問(wèn)題。(B)選項(xiàng)所描述 的問(wèn)題是梵天塔問(wèn)

35、題，應(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,Vj V之間的距離記為：dvy，問(wèn) 題的解是尋找所有城市的一個(gè)訪問(wèn)順序 T= ti , t2,tn ,其中 ti V ,使得 min W dtiti+1，這里假定除 tn+1 = t1 夕卜，ti tj(i j 時(shí) )。（數(shù)學(xué)抽象II）電路元件記為：V=V1

36、,V2,Vn, 任意兩個(gè)元件Vi,Vj V之間的距離記為：dvjVj, 問(wèn)題的解是尋找所有元件之間的一個(gè)訪問(wèn)順序 T= ti , t2,tn ,其中 ti V ,使得 min習(xí)=1 dtiti+1，這里假定除 町+i = ti夕卜，ti tj（i j 時(shí) ）。（ 數(shù) 學(xué) 抽 象 III） 圖 的 結(jié) 點(diǎn) 記 為 ： V=Vi,V2,v n，任意兩個(gè)結(jié)點(diǎn)Vi,Vj V的邊的 權(quán)值記為：dvy，問(wèn)題的解是尋找所有結(jié)點(diǎn)之間 的一個(gè)訪問(wèn)順序T=ti ,t2,tn,其中ti V,使 得min EJ=1小匕治，這里假定除tn+i = ti外，ti tj（i j 時(shí) ）。（數(shù)學(xué)抽象 IV） 圖的結(jié)點(diǎn)記為：

37、N = i,2 ， ， n，任意兩個(gè)結(jié)點(diǎn)i, j的邊的權(quán)值記為：dij，問(wèn) 題的解是尋找所有結(jié)點(diǎn)之間的一個(gè)訪問(wèn)順序 t=ti,t2,tn, 其中 ti V , 使得 min min Ej=i dtiti+i，這里假定除 tn+i = ti 夕卜，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解釋?zhuān)罕绢}考查對(duì) TSP 問(wèn)題抽象的理解I 就是對(duì)最原始的 TSP 問(wèn)題的抽象描

38、述。 II 也是對(duì) TSP 問(wèn)題的描述，只是將城市換成了電 子元件o III和IV是對(duì)同一問(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ì)

39、算機(jī)可以存儲(chǔ)和處理的變量， 便于 算法和程序進(jìn)行處理；(C) 數(shù)據(jù)結(jié)構(gòu)是將具有一定語(yǔ)義關(guān)系的變量進(jìn) 行命名， 以便隱藏?cái)?shù)據(jù)結(jié)構(gòu)內(nèi)部的操作細(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解釋?zhuān)罕绢}考查對(duì)數(shù)據(jù)結(jié)構(gòu)的理解數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲(chǔ)結(jié)構(gòu)及其操 作的總稱(chēng)，它提供了問(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ō)法不

40、正確的是 ？(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ǔ)器中的相對(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解釋?zhuān)罕绢}考查對(duì)數(shù)據(jù)結(jié)構(gòu)的理解數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲(chǔ)結(jié)構(gòu)及其操 作的總稱(chēng)。(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)

41、 表示數(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)之靈魂”與第七章課件。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ù)組的不同的元素。如下圖所示：耐鬼址維5潮00000000 DOOOOOO-182DPI82D829&00000000 MODOOlO筒陽(yáng)100GO00000000 00900011r

42、 JLD2100閃00OOOOMKJO ODOOOIOO6060fanOCHXMXIOO (X)OQOl£l-aoD的mciaoDoa odmoho9090/0412Dt> JL 100000000 OOOOOHi100DM100QOOOOGOO 00001000沁&QDOOOOOOO MM100TTO0|5和OODOOOTO 0000101090&Q(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ǔ)單元的

43、地址；(C) 和存儲(chǔ)器一樣，一維數(shù)組是按線性方式組 織數(shù)據(jù)，一個(gè)數(shù)據(jù)元素需要一個(gè)或多個(gè)存儲(chǔ)單元 來(lái)存儲(chǔ)，一個(gè)下標(biāo)即相當(dāng)于一個(gè)存儲(chǔ)單元的地 址；(D) 和存儲(chǔ)器一樣，一維數(shù)組是按線性方式組 織數(shù)據(jù)，一個(gè)數(shù)據(jù)元素需要一個(gè)或多個(gè)存儲(chǔ)單元 來(lái)存儲(chǔ)，一個(gè)下標(biāo)即相當(dāng)于一個(gè)或多個(gè)存儲(chǔ)單元 的地址；答案：C解釋?zhuān)罕绢}考查對(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)觀察，

44、 右子圖 的二維數(shù)組是按左圖的形式存儲(chǔ)在存儲(chǔ)器中。 則 D42 元素所對(duì)應(yīng)的存儲(chǔ)單元的存儲(chǔ)地址為(A) 00000000 00000101；(B) 00000000 00001000；(C) 00000000 00001010；(D) 上述都不正確；答案：B解釋?zhuān)罕绢}考查對(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)觀察， 右子圖 的

45、二維數(shù)組是按左圖的形式存儲(chǔ)在存儲(chǔ)器中。 則Dij 元素，與對(duì)應(yīng)存儲(chǔ)單元的存儲(chǔ)地址的轉(zhuǎn)換 關(guān)系正確的為 。(A) Dij 元素的存儲(chǔ)地址 =數(shù)組的起始地址 +(i-1)* 每行的列數(shù) +j-1)* 單一元素占用存儲(chǔ)單元的數(shù)(B) Dij 元素的存儲(chǔ)地址 =數(shù)組的起始地址 +(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解釋?zhuān)罕绢}考查對(duì)存儲(chǔ)器和

46、二維數(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)參考第七章視頻 “算法， 程序與計(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ù)稱(chēng)為一個(gè)數(shù) 據(jù)元素。見(jiàn)下圖 I. 示意，采用三個(gè)數(shù)組來(lái)存儲(chǔ)樹(shù) 型數(shù)據(jù)，一個(gè)數(shù)組 TreeElement

47、存放數(shù)據(jù)元素 本身，一個(gè)數(shù)組 LeftPointer 存放該數(shù)據(jù)元素的 左側(cè)子元素的存放地址 （簡(jiǎn)稱(chēng)為左指針 ），另一個(gè) 數(shù)組 RightPointer 存放該數(shù)據(jù)元素的右側(cè)子元 素的存放地址 （簡(jiǎn)稱(chēng)為右指針 ）。參照?qǐng)D I. ，回答 下列問(wèn)題。存存儲(chǔ)內(nèi)客(如亞壬苗)沖釋TreeElem&ntoooooooo CWOCOOUloooomoo mooioo需1亍散魁丘表10000000000 00000010OOMOOOO (MOOOIO00000000 00000011Goooooeo iciooiioaOOOQQOQ WOQOLUaOOWDOW W0L1JJLD第心牛懿世元00000

48、000 0000-0101OOWOOOD 01000110第5,敬電孟塞“cooooooo wowuaMWDOOO 01111OTD笫*個(gè)數(shù)拯元素12D00000000 00000111HNWMOO 101DOODD弟7個(gè)塑竝兀親丄甜aooDOooo oooaiooo00000000 ODMIlOOlLeftPoinier00000000 00001010iXMMMW tOOXJtUU弟1介骰無(wú)皿察的生招軒00000000 000010110000(X)00 0)0001003ftz描*1OOlWOOOD (MiHIllOflIDDOMOdD OOODOllO第$亍數(shù)禹冠聿約東指計(jì)oooooO

49、dO woaiioiutAxxJua) tMoouaio第4亍散松朮崖的&指蚪OOOOQOOC 00001110ODOOOOOD (XJOOOQOO第石FKtlfi斤嚴(yán)懵左柑啊00000000 00001111OOOCMMt oooooooo鵡&帯訣IKS;廉的左指ftOOMODOO WC1DO00OOOMOi GMOOOOO第牛毀比凡末曲左漕斛OOODOOOO 00010001COOO0OOO OOOIDOLORight Pointer00000600 00C1D011jmwxwo utkjotwii朝丄傘塑愜”走內(nèi)尼ffiti00000000 00010100OOOOOOO

50、) 000)0 仙第z個(gè)敬熔兀案的右AHt0000000 W010101OOQOOOD OOODOS11籌耳亍誥魅兀求的右指劉00000&00 MOW LIOtKwaw tmmjn?第4亍敬無(wú)皿裹吋屯摺釗qqqOOQW W0101L1OQOWOOO Q0C000W笫5$敢駅尺垂叫右描刑O(píng)OOOOODC 041011000cewoaao axiotxw葩&個(gè)數(shù)惟朮素的右抬ti00000000 (MiOllOOlouiwauo MMMU&第7個(gè)數(shù)鋸無(wú)崑吋右描劭00000000 0001101000000000 D00110L1圖I.(1)關(guān)于“樹(shù)”這種數(shù)據(jù)結(jié)構(gòu)，下列說(shuō)法不正

51、確的。(A) “樹(shù)”既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù)， 還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系；(B) “樹(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ǔ)位置；(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解釋?zhuān)罕绢}考查對(duì)樹(shù)結(jié)構(gòu)的理解?！皹?shù)”既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù)， 還需 要存儲(chǔ)數(shù)據(jù)元素之間的

52、關(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ù)組組織樹(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ù)元素，不同的左指針和右指針 可以反映數(shù)據(jù)元素之間不同的關(guān)系；(D) 圖(a)說(shuō)明，一個(gè)數(shù)據(jù)元素最多