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

1、第7章算法：程序與計(jì)算系統(tǒng)之靈魂1、算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特定類型問題的一個(gè)運(yùn)算序列?；卮鹣铝袉栴}。(i)關(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)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(2)關(guān)于算法的命題，下列說(shuō)法不正確的是。(A)算法規(guī)定了任務(wù)執(zhí)行/問題求解的一系列、有限的步驟。(B)算法所規(guī)定的計(jì)算/處理步驟是有限的，但算法實(shí)際執(zhí)行的計(jì)算/處理步驟可以是無(wú)限的。(C)算法可以沒有輸入，但必須有輸出。(D)算法的每一個(gè)步驟必須確切地定義，且其運(yùn)算和操作必須相當(dāng)基本，可以由機(jī)器自動(dòng)完成。答案：B解釋：本題考查對(duì)算法基本性質(zhì)的理解(B)違反了算法的有窮性：一個(gè)算法

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

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

5、都可以歸結(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)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。2、哥尼斯堡七橋問題，是一個(gè)經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點(diǎn)的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學(xué)家歐拉對(duì)該問題做了一個(gè)抽象：“頂點(diǎn)”為陸地

6、，“邊”為連接兩塊陸地的橋梁。這個(gè)抽象被稱為“圖”，并定義了頂點(diǎn)的“度”為連接一個(gè)頂點(diǎn)的邊的數(shù)量。關(guān)于此問題回答下列問題。本題考查問題及其數(shù)學(xué)建模的作用(a)(b)哥尼斯堡七橋問題的路徑能夠找到嗎?(A)一定能夠找到；(B)一定不能找到；(C)不確定能不能找到。答案：B解釋：本題考查問題及其數(shù)學(xué)建模的作用選擇（B）,根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是0或2（該題中應(yīng)為0個(gè)）。該問題中將四個(gè)島抽象成4個(gè)點(diǎn)，每條橋抽象成邊，可知圖中奇點(diǎn)個(gè)數(shù)是4個(gè)，因此不可能找到。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法

7、策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。（2）對(duì)河流隔開的m塊陸地上建造的n座橋梁，能否找到走遍這n座橋且只許走過每座橋一次最后又回到原出發(fā)點(diǎn)的路徑呢？。（A）一定能夠找到；（B）一定不能找到；（C）不確定能不能找到。答案：C解釋：本題考查問題及其數(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è)）。該問題中將m個(gè)島抽象成m個(gè)點(diǎn)，每條橋抽象成邊，但圖中奇點(diǎn)個(gè)數(shù)未知，因此不能做判斷。具體內(nèi)容參考第七章視頻之“算法與算法類問

8、題的求解，第七章課件或查閱歐拉回路相關(guān)資料。（3）對(duì)河流隔開的m塊陸地上建造的n座橋梁，若要找到走遍這n座橋且只許走過每座橋一次最后又回到原出發(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解釋：本題考查問題及其數(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è)

9、）。該問題中將m個(gè)島抽象成m個(gè)點(diǎn)，每條橋抽象成邊，因此應(yīng)該選擇Co具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(4)下面所示的圖(c),能否找到走遍每一座橋，且每座橋僅走過一次、最后又回到原出發(fā)點(diǎn)的路徑呢？(A)一定能夠找到；(B)一定不能找到;(C)不確定能不能找到。答案：B解釋：本題考查問題及其數(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)是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為0個(gè))。圖中奇點(diǎn)是C與G,個(gè)數(shù)為2,不符合

10、要求，因此應(yīng)該選擇Bo具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(5)參見圖(c),增加哪些邊，使得能夠找到走遍每一座橋，且每座橋僅走過一次、最后又回到原出發(fā)點(diǎn)的路徑呢？(A)BG邊；(B)AG邊；(C)CG邊；(D)AD邊；(E)DE邊。答案：C解釋：本題考查問題及其數(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è))。圖中奇點(diǎn)是C與G,個(gè)數(shù)為2,不符合要求，因此在CG間增加一條邊

11、，將寄點(diǎn)數(shù)變成0可滿足要求，因此應(yīng)該選擇Co具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(6-1)對(duì)河流隔開的m塊陸地上建造的n座橋梁，若要找到走遍這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)不滿足上述條件(A)(B)(C)的圖也能找出滿足題目規(guī)定要求的路徑;答案：D解釋：本題考查問題及其數(shù)學(xué)建模的作用選擇(D),此題未要求回到原地，即起點(diǎn)和終點(diǎn)可以不是一個(gè)，那么可以有2個(gè)奇數(shù)點(diǎn)作

12、為起點(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ì)河流隔開的m塊陸地上建造的n座橋梁，若要找到走遍這n座橋且只許走過每座橋一次的路徑，則需滿足以下條件。(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)的度均

13、為偶數(shù)；(C)既需要滿足(A)又需要滿足(B);(D)不滿足上述條件(A)(B)(C)的圖也能找出滿足題目規(guī)定要求的路徑；答案：C解釋：本題考查問題及其數(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)該選擇Co具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(7)下面所示的圖(d)和圖(e),問能否找到走遍每一座橋，且每座橋僅走過一次的路徑呢?(

14、e)(A)圖(d)和圖(e)都一定不能找到；(B)圖(d)一定能夠找到；圖(e)一定不能找至ij;(C)圖(d)一定不能找到；圖(e)一定能夠找到;(D)圖(d)和圖(e)都一定能夠找到；答案：C解釋：本題考查問題及其數(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)該選擇Co具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(8)參見下圖，下列說(shuō)法正確的是(A)

15、卡寸A、B、C、X出發(fā)走遍每一座橋,O(B)對(duì)兩個(gè)頂點(diǎn)過一次，最后終止于(C)對(duì)兩個(gè)頂點(diǎn)過一次，最后終止于且每座橋僅走過一次，最后終止于和B,可以找到一條路徑，從A都可以找到一條路徑，從丫；出發(fā)走遍每一座橋，且每座橋僅走B；D和G,可以找到一條路徑，從DG;出發(fā)走遍每一座橋，且每座橋僅走X和丫；Y,都找不到一條路徑，從X(D)XA、B、C、D、E、F、G中的任意兩個(gè)頂點(diǎn)出發(fā)走遍每一座橋，且每座橋僅走過一次，最后終止于答案：C解釋：本題考查問題及其數(shù)學(xué)建模的作用選擇(C)根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1)圖形必須是連通的；2)途中的“奇點(diǎn)”(相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn))個(gè)

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

17、上述全部；答案：D解釋：本題考查問題及其數(shù)學(xué)建模的作用以上說(shuō)明都正確，對(duì)一個(gè)具體問題的求解，可先進(jìn)行數(shù)學(xué)建模，將具體問題轉(zhuǎn)化成抽象問題，再進(jìn)行判斷是否有解，若有解則計(jì)算，若無(wú)解則無(wú)需計(jì)算。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(10)哥尼斯堡七橋問題，推而廣之就是m個(gè)頂點(diǎn)n條邊的圖的“一筆畫”問題，我們可以給出一個(gè)算法來(lái)求解該問題，即“對(duì)河流隔開的m塊陸地上建造的n座橋梁，若要找到走遍這n座橋且只許走過每座橋一次的路徑”。關(guān)于該算法的基本思想，下列說(shuō)法正確的是(A)以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照?qǐng)D的“邊”的指示，找到按該邊與該頂點(diǎn)相連的下一

18、個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問”，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(B)以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照?qǐng)D的未訪問過“邊”的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問”，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(C)首先判斷該問題是否有解，若無(wú)解，則直接退出；若有解，則以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照?qǐng)D的未訪問過“邊”的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問”，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(D)首先判斷該問題是否有解，若無(wú)解，則直接退出；若有解，則選擇一個(gè)奇數(shù)度的頂點(diǎn)為起點(diǎn)，按照?qǐng)D的未

19、訪問過“邊”的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問”，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(E)上述都不正確。答案：D解釋：本題考查問題及其數(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。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。3、背包問題的定義是：給定一組物品，每種物品都有自己的重量

20、和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。背包問題的一個(gè)例子：應(yīng)該選擇哪些盒子，才能使價(jià)格盡可能地大，而保持重量小于或等于15kg?其示意圖如下：該背包問題的可能解的數(shù)量是。(A)5(B)10(C)32(D)64答案：C解釋：本題考查問題及其數(shù)學(xué)建模的作用1到15遍歷可由題意可知，只要可放入背包的狀態(tài)都算是可能解，可以按背包容量由能性。答案為(C)32個(gè)。具體內(nèi)容查閱背包問題相關(guān)資料。(2)假定求解該問題的一種貪心策略是：優(yōu)先選擇能裝下盒子中價(jià)格最高的，依據(jù)該算法策略所得到的解的總價(jià)值是。(A)16(B)15(C)1

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

22、,2,1,1,1/3,依次放入并驗(yàn)證是否超出背包重量限制：$10-4kg,$2-1kg,$1-1kg,$2-2kg,之后放不下$4-12kg的物品，到此總價(jià)值是15,所以選擇(B)。具體內(nèi)容查閱背包問題相關(guān)資料。(4)假定求解該問題的一種貪心策略是：最大程度地利用背包的容量(15kg),依據(jù)該算法策略所得到的解的總價(jià)值是。(A)8(B)15(C)14(D)13答案：A解釋：本題考查問題及其數(shù)學(xué)建模的作用由題意可知使用貪心算法，需要讓剩余空間最小，那么可以得到的組合是，12kg+2kg+1kg=15kg,重量得到最大利用，總價(jià)值是8,所以選擇(A)。具體內(nèi)容查閱背包問題相關(guān)資料。(5)使用遍歷算

23、法策略所得到的解的總價(jià)值是(A)8(B)15(C)14(D)13答案：B解釋：本題考查問題及其數(shù)學(xué)建模的作用用遍歷算法策略，狀態(tài)轉(zhuǎn)移方程：fv=maxfv,fv-ci+wi,即fiv表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值，第i件物品的重量是ci，價(jià)值是wi。將前i件物品放入容量為v的背包中”這個(gè)子問題，若只考慮第i件物品的策略(放或不放)，那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為前i-1件物品放入容量為v的背包中”，價(jià)值為fi-1v；如果放第i件物品，那么問題就轉(zhuǎn)化為前i-1件物品放入剩下的容量為v-ci的背包中”，此時(shí)能獲得的最大

24、價(jià)值就是fi-1v-ci再加上通過放入第i件物品獲得的價(jià)值wio按此方法，可得總價(jià)值是15,所以選擇(B)。具體內(nèi)容查閱背包問題相關(guān)資料。(6)假定有N個(gè)物品，其價(jià)值分別為V1,V2,.,VN,重量分別為W1,W2,.,WN,背包所能承受的總重量為Wmax,為物品i定義一個(gè)決策變量xi,其中xi=1表示選擇該物品，xi=0表示不選擇該物品。下面哪個(gè)描述共同構(gòu)成了該問題的數(shù)學(xué)模型。N(A)問題的目標(biāo)函數(shù)是maxXxiVi;i1N(B)問題的目標(biāo)函數(shù)是maxZxiWi；i1N(C)問題解所應(yīng)滿足的約束是£xW<Wmax；i1N(D)問題解所應(yīng)滿足的約束是工xiVi<Wmax；

25、i1(E)前述(A)和(C);答案：E解釋：本題考查問題及其數(shù)學(xué)建模的作用該問題有兩個(gè)條件：N1)物品不能超過背包所能承受的重量，即(C)選項(xiàng)：'、xiWi<Wmax1 4Nmax、xiVi2)背包內(nèi)物品價(jià)值最大，即(A)選項(xiàng)目標(biāo)函數(shù)為口(B)和(D)選項(xiàng)明顯錯(cuò)誤，將質(zhì)量和價(jià)值比較。所以選擇(E)。具體內(nèi)容查閱背包問題相關(guān)資料。4、TSP-旅行商問題，是一個(gè)經(jīng)典問題，如下圖所示，描述為“有n個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費(fèi)用最少”圍繞TSP

26、,回答下列問題。(1)關(guān)于TSP問題的遍歷算法和貪心算法，下列說(shuō)法正確的是。(A)對(duì)TSP問題而言，遍歷算法和貪心算法求得的解是一樣的，所不同的是貪心算法更快一些，而遍歷算法更慢一些；(B)對(duì)TSP問題而言，遍歷算法和貪心算法求得的解是一樣的，所不同的是遍歷算法更快一些，而貪心算法更慢一些；(C)對(duì)TSP問題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求近似解,執(zhí)行更快一些，而遍歷算法是求精確解，執(zhí)行更慢一些；(D)對(duì)TSP問題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求精確解,執(zhí)行更快一些，而遍歷算法是求近似解，執(zhí)行更慢一些；答案：C解釋：本題考查對(duì)貪心算法與遍歷算法的

27、簡(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è)過程白花費(fèi)為：14。于是，該貪心算法的解為14。而通過遍歷可知，該問題的最優(yōu)解為A-B-C-D-A,花費(fèi)為13?？梢?，貪心算法與遍歷算法的解不會(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)組合爆炸。故，相比之下，貪心算法

28、的計(jì)算速度更快。所以(C)選項(xiàng)是正確的。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。(2)關(guān)于TSP,下列說(shuō)法不正確的是。(A)TSP問題的一個(gè)可能解就是n個(gè)城市的一個(gè)組合t1,t2,，tn,其中任何兩個(gè)ti,tj都對(duì)應(yīng)不同的城市。若要求得最優(yōu)解，則必須對(duì)所有的組合，即所有可能解進(jìn)行比較。(B)TSP問題的難點(diǎn)是當(dāng)n值很大時(shí)，組合數(shù)目非常龐大(組合數(shù)目為n!),以致于計(jì)算機(jī)不能在有限時(shí)間內(nèi)完成所有的組合；(C)TSP問題的難點(diǎn)是當(dāng)n值很大時(shí)，組合數(shù)目非常龐大(組合數(shù)目為n!),雖如此，計(jì)算機(jī)仍然能夠在有限時(shí)間內(nèi)完成所有的組合；(D)上述思想-對(duì)所有組合進(jìn)行比較的思想，即

29、是所i1的遍歷算法策略，它僅僅對(duì)n值很小的TSP問題是能行的。答案：C解釋：本題考查對(duì)TSP組合優(yōu)化問題的理解對(duì)所有組合進(jìn)行比較的思想，即所謂的遍歷算法策略，其組合數(shù)目為n!o2001年解決了德國(guó)15112個(gè)城市的TSP問題，使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz的CompaqEV6Alpha處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。由此可見，當(dāng)n巨大時(shí)，用遍歷算法解決TSP問題是不現(xiàn)實(shí)的。所以(C)選項(xiàng)錯(cuò)誤。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。(3)關(guān)于TSP的貪心算法的求解思想，下列說(shuō)法不正確的是。(A)無(wú)

30、需對(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è)具體的TSP問題，每次執(zhí)行貪心算法，所求得的最終解可能是不同的。答案：C解釋：本題考查對(duì)TSP貪心算法的理解（A） （B）選項(xiàng)都是對(duì)貪心算法的描述，貪心算法的核心就是：只考慮當(dāng)前情況下

31、得最優(yōu)解。故（A）（B）正確。貪心算法得到的解釋可行解，但不一定是最優(yōu)解，故（C）錯(cuò)誤。在執(zhí)行貪心算法的過程中，會(huì)遇到下一步有兩個(gè)最優(yōu)選項(xiàng)的情況，所以每次執(zhí)行貪心算法的最終解的結(jié)果可能是不同的。故（D）正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。（4）下列哪些問題可應(yīng)用求解TSP的算法，正確的是。（A）電路板上需要鉆n個(gè)孔，選擇一條最短路徑使機(jī)器移動(dòng)并完成所有孔的鉆孔工作的問題（機(jī)器在電路板上鉆孔的調(diào)度問題）；（B） n個(gè)盤子在三個(gè)柱子上的移動(dòng)問題（梵天塔問題或者說(shuō)漢諾塔問題）；（C） n座橋，走過每座橋且僅走過一次的問題（圖的遍歷問題）；（D）上述（A）（B）（

32、C）都可以。答案：A解釋：本題考查對(duì)TSP問題抽象的理解求解TSP問題采用的是貪心算法。（A）選項(xiàng)所描述的問題其實(shí)就是TSP問題。（B）選項(xiàng)所描述的問題是梵天塔問題，應(yīng)該采用的是遞歸的思想。（C）選項(xiàng)所描述的圖的遍歷問題，主要有深度優(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，VjCV之間的距離記為：dviVj,問題的解是尋找所有城市的一個(gè)訪問順序T=t1,t2,tn,其中tiCV,使得min1

33、dtiti+1,這里假定除tn+1=t1外,ti豐tj（i書時(shí)）。（數(shù)學(xué)抽象II）電路元件記為：V=V1,V2,Vn,任意兩個(gè)元件Vi,VjCV之間的距離記為：dVjVj,問題的解是尋找所有元件之間的一個(gè)訪問順序T=t1,t2,tn,其中tiCV,使得min/dtiti+1,這里假定除tn+1=t1外,ti豐tj（用時(shí)）。（數(shù)學(xué)抽象III）圖的結(jié)點(diǎn)記為:V=V1,V2,Vn,任意兩個(gè)結(jié)點(diǎn)Vi,VjCV的邊的權(quán)值記為：dViVj,問題的解是尋找所有結(jié)點(diǎn)之間的一個(gè)訪問順序T=t1,t2,tn,其中tiCV,使得min/dtiti+1,這里假定除tn+1=t1外,t豐tj（用時(shí)）。（數(shù)學(xué)抽象IV）圖

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

35、問題的不同表述罷了，都是TSP問題，只是將城市換為了圖。四個(gè)數(shù)學(xué)抽象都可以被認(rèn)為是TSP問題。故選項(xiàng)(C)正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。5、數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)的重要步驟，針對(duì)不同問題的算法設(shè)計(jì)應(yīng)該選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，不同的數(shù)據(jù)結(jié)構(gòu)會(huì)使得解決問題的算法的性能有所不同?；卮鹣铝袉栴}。(1)關(guān)于數(shù)據(jù)結(jié)構(gòu)，下列說(shuō)法不正確的是。(A)數(shù)據(jù)結(jié)構(gòu)是問題域數(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é)

36、，便于算法按邏輯語(yǔ)義通過操控該名字來(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)及其操作的總稱，它提供了問題求解/算法的數(shù)據(jù)操縱機(jī)制。(A)(B)(C)(D)的說(shuō)法都沒有問題。所以(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ù)元素

37、的邏輯關(guān)系;(D)在樹結(jié)構(gòu)中，指針用于表達(dá)元素之間的邏輯關(guān)系一一父子關(guān)系，每個(gè)元素的指針指向其父節(jié)點(diǎn)，因此一個(gè)元素可以有一個(gè)或多個(gè)指針。答案：D解釋：本題考查對(duì)數(shù)據(jù)結(jié)構(gòu)的理解(A)正確。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(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)正確。在樹結(jié)構(gòu)中，如果每個(gè)元素的指針都指向其父節(jié)點(diǎn)，那么每個(gè)元素只能有一個(gè)指針。因?yàn)槊總€(gè)元素只有一個(gè)父親。故(D)錯(cuò)誤。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課

38、件。6.數(shù)據(jù)通常要存儲(chǔ)在存儲(chǔ)器中，存儲(chǔ)器是按地址訪問的存儲(chǔ)單元的集合，因此存儲(chǔ)器可被認(rèn)為是按線性方式組織數(shù)據(jù)。數(shù)組是高級(jí)語(yǔ)言中經(jīng)常使用的一種數(shù)據(jù)結(jié)構(gòu)，其按照不同的下標(biāo)可訪問數(shù)組的不同的元素。如下圖所示：二弱的95100009010070/80nDHI2LXUUJ(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ǔ)單元的地址

39、；(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)確。其余說(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ǔ)地址為。(A)0000000000000101;(B)0000000000001000;

40、(0)0000000000001010;(D)上述都不正確；答案：B解釋:本題考查對(duì)存儲(chǔ)器和數(shù)組的理解。圖中，二維數(shù)組中，D42對(duì)應(yīng)的元素是80,而且是第二個(gè)80.在存儲(chǔ)器中，找到第二個(gè)80的位置，其所對(duì)應(yīng)的地址為：0000000000001000;(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)系正確的為。(A) Dij元素的存儲(chǔ)地址=數(shù)組的起始地址+(i-1)*每行的列數(shù)+j-1)*單一元素占用存儲(chǔ)單元的數(shù)目(B) Dij元素的

41、存儲(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解釋:本題考查對(duì)存儲(chǔ)器和二維數(shù)組的理解。記住數(shù)組的下標(biāo)是從0開始編號(hào)的。(i-1)*每行的列數(shù)+j-1)得到二維數(shù)組中，所求的元素的下標(biāo)偏移量。(i-1)*每行的列數(shù)+j-1)*單一元素占用存儲(chǔ)單元的數(shù)目得到地址的偏移量。再加上數(shù)組的起始地址，便可得到所求元素的地址。(A)正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視

42、頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。7.“樹”是一種典型的數(shù)據(jù)結(jié)構(gòu)，在很多算法中都應(yīng)用樹來(lái)組織相關(guān)的數(shù)據(jù)。樹是組織層次型數(shù)據(jù)的一種存儲(chǔ)結(jié)構(gòu)，它將每一個(gè)數(shù)據(jù)稱為一個(gè)數(shù)據(jù)元素。見下圖I.示意，采用三個(gè)數(shù)組來(lái)存儲(chǔ)樹型數(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.,回答下列問題。存耕掉存儲(chǔ)內(nèi)容(如變M留)注理TreeElementOOMQMOOCOCHWlgQOMOO0U001M第1個(gè)疆裙元素100

43、OOMOOOO00000410O-OOOM0OM11001C鈍2個(gè)效用元東M00000040ocioaooiiOOOOMOO10100110第4個(gè)數(shù)板元素15?？贛OM。QdIM血口口oooonwwoimo第4個(gè)致松元素如0000DOCOGO0001010000000001000110第S個(gè)致幅元青70。口MOOWCKI4XH311Doowoooaoiiiiooo第E個(gè)豉據(jù)元素oooocooagdo口in.CHXXHMOD1C1CD000第7個(gè)教房兀定OOOOOOOOOGDOIOODOD<M<DO<N3dCDOlMlLeftpointerOOOOdOCKIM001QI。第1個(gè)

44、效據(jù)元豪的左信仰0000-0000OOODlOllOOOOOOiJOOOOOOIOO第2個(gè)最粗元*的左希時(shí)ODMdCKIOOODOIICpDDWODDi)DDDODDllD第3個(gè)數(shù)據(jù)元崇的左指號(hào)OOOOCOOCaODOUDlUmUlMUOiMKWUUO第4個(gè)費(fèi)能元量的左指針ODWOOttOMOIUODODIXiOOOOOOOOODO第5個(gè)數(shù)愜元卡的左幅40000000000001111()000000)IWOS知第6個(gè)獲幅元素的左指針OOWDOeoQODiOMd第7個(gè)效據(jù)范案的主用料00000000MH1DOOOOWOOWQd01OOI口RghtPointerOOMOHMtnkjudtwauw

45、uutuj第1個(gè)效松兀青的忐相仲00000(X)000-010100ooooaowoooootoa第2個(gè)強(qiáng)揖元素的古布什ODHOOMOCI010101第3個(gè)敷胃元親的右指珅OQMQMO010110LWtXXWiMMXXWO第4個(gè)熟片凡米的總括行OQMQOOOH010111QQOOQQO)ODOOOOOO第5個(gè)敷第元素的右指針oooocioeciMournooooaDMoooooao第6個(gè)依據(jù)元素晌右指針OOWDOCOOODUOQ1uDcmtwuuuxvuuo第T個(gè)數(shù)將元豪的右指行OOMflOCC00011010ODOOOOMQ0011011圖I.(1)關(guān)于“樹”這種數(shù)據(jù)結(jié)構(gòu)，下列說(shuō)法不正確的是

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

47、兩個(gè)數(shù)組組織樹形數(shù)據(jù)時(shí)，一個(gè)數(shù)組存放數(shù)據(jù)元素，另一個(gè)數(shù)組存儲(chǔ)對(duì)應(yīng)的父元素。用三個(gè)數(shù)組組織樹形數(shù)據(jù)時(shí)，一個(gè)數(shù)組存放數(shù)據(jù)元素，剩下的兩個(gè)數(shù)據(jù)，一個(gè)存放對(duì)應(yīng)的左兒子，一個(gè)存放對(duì)應(yīng)的右兒子。組織樹形數(shù)據(jù)時(shí)，可以把每個(gè)元素當(dāng)做一個(gè)節(jié)點(diǎn)，通過指針來(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í)，可以通過調(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ù)

48、據(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ì)樹結(jié)構(gòu)的理解?！皹洹奔刃枰鎯?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.

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

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

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

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

53、鏈結(jié)串行或陣列的一端（稱為堆棧頂端指針，top）進(jìn)行加入數(shù)據(jù)（push）或輸出數(shù)據(jù)（pop）的運(yùn)算。其示意圖如下所示。Push有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的說(shuō)法，不正確的是。(A)堆棧按照先進(jìn)先出(FIFO,FirstInFirstOut)的原理運(yùn)作;(B)堆棧按照后進(jìn)先出(LIFO,LastInFirstOut)的原理運(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)?/p>

54、結(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ù)，也是在堆棧的頂端彈出，數(shù)據(jù)個(gè)數(shù)減一，

55、棧頂指針減一，(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ù)。將棧底的元素彈出，則首先必須要使堆棧變空，需要連續(xù)十次彈出操作。再將其他9個(gè)元素壓入堆棧，需要9次推入操作。故（C）選項(xiàng)正確。詳細(xì)內(nèi)容請(qǐng)參