算法程序與計(jì)算系統(tǒng)之靈魂練習(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)題。/本題考查問(wèn)題及其數(shù)學(xué)建模的作用(a) (b)(1)哥尼斯堡七橋問(wèn)題的路徑能夠找到嗎？ _。(A)一定能夠找到； (B)一定不能找到； (C)不確定能不能找到。答案：B解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（B），根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；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è)，因此不可能找到。

7、具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(2)對(duì)河流隔開(kāi)的m塊陸地上建造的n座橋梁，能否找到走遍這n座橋且只許走過(guò)每座橋一次最后又回到原出發(fā)點(diǎn)的路徑呢？ _。 (A)一定能夠找到； (B)一定不能找到； (C)不確定能不能找到。答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：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ù)未知，因此不

8、能做判斷。具體內(nè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ù)； (C)既需要滿足(A)又需要滿足(B)；(D)上述條件還不夠，還需滿足更多條件。答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是

9、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ò)一次、最后又回到原出發(fā)點(diǎn)的路徑呢？(c)(A)一定能夠找到； (B)一定不能找到； (C)不確定能不能找到。答案：B解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（B）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是0或2（該題中因?yàn)槠瘘c(diǎn)和終點(diǎn)

10、是一個(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ò)一次、最后又回到原出發(fā)點(diǎn)的路徑呢？(A)BG邊； (B)AG邊； (C)CG邊； (D)AD邊； (E)DE邊。答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：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ù)

11、應(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ì)-算法思想”，第七章課件或查閱歐拉回路相關(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解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用

12、選擇（D），此題未要求回到原地，即起點(diǎn)和終點(diǎn)可以不是一個(gè)，那么可以有2個(gè)奇數(shù)點(diǎn)作為起點(diǎn)和終點(diǎn)。根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；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è)

13、其他頂點(diǎn)； (B)每個(gè)頂點(diǎn)的度應(yīng)為偶數(shù)，或者，只有兩個(gè)頂點(diǎn)的度為奇數(shù)而其他頂點(diǎn)的度均為偶數(shù)；(C)既需要滿足(A)又需要滿足(B)；(D)不滿足上述條件(A)(B)(C)的圖也能找出滿足題目規(guī)定要求的路徑；答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C），此題未要求回到原地，即起點(diǎn)和終點(diǎn)可以不是一個(gè)，那么可以有2個(gè)奇數(shù)點(diǎn)作為起點(diǎn)和終點(diǎn)。根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是0或2。因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(7)

14、下面所示的圖(d)和圖(e)，問(wèn)能否找到走遍每一座橋，且每座橋僅走過(guò)一次的路徑呢？ (d) (e)(A)圖(d)和圖(e)都一定不能找到；(B)圖(d)一定能夠找到；圖(e)一定不能找到；(C)圖(d)一定不能找到；圖(e)一定能夠找到；(D)圖(d)和圖(e)都一定能夠找到；答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：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é)建模與算法策略

15、設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(8)參見(jiàn)下圖(f)，下列說(shuō)法正確的是_。(f)(A)對(duì)A、B、C、D、E、F、G中的任意兩個(gè)頂點(diǎn)X和Y，都可以找到一條路徑，從X出發(fā) 走遍每一座橋，且每座橋僅走過(guò)一次，最后終止于Y；(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ò)一次，最后終止于Y；答案：C解釋：本題考查問(wèn)題及

16、其數(shù)學(xué)建模的作用選擇（C）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：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

17、)一個(gè)具體問(wèn)題的求解方法，進(jìn)行數(shù)學(xué)建模后，可反映出一類問(wèn)題的求解方法，例如哥尼斯堡七橋問(wèn)題的求解方法，建立“圖”后，可反映任意n座橋的求解方法；(D)上述全部；答案：D解釋：本題考查問(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條邊的圖的“一筆畫”問(wèn)題，我們可以給出一個(gè)算法來(lái)求解該問(wèn)題，即“對(duì)河流隔開(kāi)的m塊陸地上建造的n座橋梁，若要找到走遍這n

18、座橋且只許走過(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)過(guò)“邊”的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問(wèn)”，依

19、次循環(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解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（D）根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是0或2。因此，若有奇點(diǎn)，則起點(diǎn)和終點(diǎn)必須是奇點(diǎn)，若無(wú)，則任意，因此（A）（B）（C），因此應(yīng)該選擇D

20、。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。3、背包問(wèn)題的定義是：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。背包問(wèn)題的一個(gè)例子：應(yīng)該選擇哪些盒子，才能使價(jià)格盡可能地大，而保持重量小于或等于15 kg？其示意圖如下：(1)該背包問(wèn)題的可能解的數(shù)量是_。(A) 5 (B) 10 (C) 32 (D) 64答案：C解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知，只要可放入背包的狀態(tài)都算是可能解，可以按背包容量由1到15遍歷可能性。答案

21、為（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解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知使用貪心算法，從價(jià)值最高的開(kāi)始放入，第一個(gè)放入價(jià)值$10的4kg物品，接下來(lái)價(jià)值最大的是$4，但再加上12kg已經(jīng)超過(guò)了背包的限度，所以不可放入，接下來(lái)放入其余的3個(gè)可滿足重量限制的物品，總價(jià)值是15，所以選擇（B）。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。(3)假定求解該問(wèn)題的一種貪心策略是：優(yōu)先選擇能裝下盒子中單位重量?jī)r(jià)值最高的，依據(jù)該算法策

22、略所得到的解的總價(jià)值是_。(A) 16 (B) 15 (C) 14 (D) 13答案：B解釋：本題考查問(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)容查閱背包問(wèn)題相關(guān)資料。(4) 假定求解該問(wèn)題的一種貪心策略是：最大程度地利用背包的容量（15kg），依據(jù)該算法策略所得到的解的總價(jià)值是_。(A) 8 (B) 15 (C) 14 (D) 13答案：

23、A解釋：本題考查問(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解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用用遍歷算法策略，狀態(tài)轉(zhuǎn)移方程：fv=maxfv,fv-ci+wi，即fiv表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值，第i件物品的重量是ci，價(jià)值是wi?！皩⑶癷件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略

24、（放或不放），那么就可以轉(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 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=

25、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）選項(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ò)每一

26、個(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問(wèn)題而言，遍歷算法和貪心算法求得的解是一樣的，所不同的是遍歷算法更快一些，而貪心算法更慢一些；(C)對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求近似解，執(zhí)行更快一些，而遍歷算法是求精確解，執(zhí)行更慢一些；(D)對(duì)TSP問(wèn)題而言，遍歷算法和貪心算法求得的解是不一樣的

27、，貪心算法是求精確解，執(zhí)行更快一些，而遍歷算法是求近似解，執(zhí)行更慢一些；答案：C解釋：本題考查對(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)選擇，其時(shí)間復(fù)雜度為n3 級(jí)別。而遍歷則會(huì)

28、將各種情況考慮在內(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è)組合<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)

29、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!。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í)間之和為22.6年。由此可見(jiàn)，當(dāng)n巨大時(shí)，用遍歷算法解決TSP問(wèn)題是不現(xiàn)實(shí)的。所以

30、(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, , 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è)具體的T

31、SP問(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)的情況，所以每次執(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ī)器在電路板

32、上鉆孔的調(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)所描述的問(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ō)法正確的是_。(

33、數(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,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=

34、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，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和

35、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ì)同一問(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)

36、會(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)部的操作細(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) (

37、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ǔ)器中的相對(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)也就是在

38、反映數(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)之靈魂”與第七章課件。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)和

39、存儲(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ù)組是按線性方式組織數(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)確。

40、其余說(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 00001010； (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)參考第七章視頻“算法，程

41、序與計(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ù)組的起始地址+(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；此公式在任何情況下都正確；答

42、案：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)參考第七章視頻“算法，程序與計(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ù)組Left

43、Pointer存放該數(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ù)”可以采用兩個(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ù)元

44、素的存儲(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ù)組組織樹(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)參

45、照上圖(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ù)元素最多只能有兩個(gè)子元素，一個(gè)是左子元素，一個(gè)是右子元素；(E)上述說(shuō)法有不正確的。答案：B解釋：本題考查對(duì)樹(shù)結(jié)構(gòu)的理解?！皹?shù)”既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。當(dāng)

46、數(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)；圖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)參考第七章視頻“算法，程

47、序與計(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 00000111； (C)將00000000 00010001號(hào)存儲(chǔ)單元的值修改為00000000 00000000(即Null)； (D)將00000000 00010011號(hào)存儲(chǔ)單元的值修改為00000000 00001000；(E)上述(A)(B)(C)(D)都需要正確完成；答案

48、：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，這是（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)容卻是

49、不正確的。不正確的是_。圖IV.(A)將00000000 00001000號(hào)存儲(chǔ)單元的值修改為00000000 01010101；(B)將00000000 00010010號(hào)存儲(chǔ)單元的值修改為00000000 00000010； (C)將00000000 00011010號(hào)存儲(chǔ)單元的值修改為00000000 00000000(即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的左指針指向8

50、5元素的地址。（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é)串行或陣列的一端（稱為堆棧頂端指針，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

51、 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)和鏈?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減一；

52、(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ù)，也是在堆棧的頂端彈出，數(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)前堆棧頂

53、端指針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ù)。將棧底的元素彈出，則首先必須要使堆棧變空，需要連續(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ò)誤的流

54、程圖為_(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)控制條件成立為是后，修改部分的返回箭頭不應(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ò)誤(A)和(B)； (D)除錯(cuò)誤(A)和(B)外，還包括其他錯(cuò)誤；答案：D解釋：本題考查