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

1、第7章算法算法:程序與計(jì)算系統(tǒng)之靈魂程序與計(jì)算系統(tǒng)之靈魂1、算法就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特定類型問題的一個(gè)運(yùn)算序列。回答下列問題。(1)關(guān)于算法的特性，下列說法不正確的是_____。(A)算法必須有明確的結(jié)束條件，即算法應(yīng)該能夠結(jié)束，此即算法的有窮性；(B)算法的步驟必須要確切地定義，不能有歧義性，此即算法的確定性；(C)算法可以有零個(gè)或多個(gè)輸入，也可以有零個(gè)或多個(gè)輸出，此即算法的輸入輸出性；(D)算法中有待執(zhí)行

2、的運(yùn)算和操作必須是相當(dāng)基本的，可以由機(jī)器自動(dòng)完成，進(jìn)一步，算法應(yīng)能在有限時(shí)間內(nèi)完成，此即算法的能行性；(E)上述說法有不正確的；答案：C解釋：本題考查對(duì)算法基本性質(zhì)的理解（C）算法的輸出性：算法有一個(gè)或多個(gè)的輸出結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。因此（C）選項(xiàng)錯(cuò)誤。其余選項(xiàng)，（A）（B）（D）分別是對(duì)算法的有窮性，確定性和能行性的正確描述。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(2)關(guān)于算法的命題，下列說法不

3、正確的是_____。(A)算法規(guī)定了任務(wù)執(zhí)行問題求解的一系列、有限的步驟。(B)算法所規(guī)定的計(jì)算處理步驟是有限的，但算法實(shí)際執(zhí)行的計(jì)算處理步驟可以是無限的。(C)算法可以沒有輸入，但必須有輸出。(D)算法的每一個(gè)步驟必須確切地定義，且其運(yùn)算和操作必須相當(dāng)基本，可以由機(jī)器自動(dòng)完成。答案：B解釋：本題考查對(duì)算法基本性質(zhì)的理解（B）違反了算法的有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。因此（B）選項(xiàng)錯(cuò)誤。其余選項(xiàng)，（A）（C）（D）分別是

4、對(duì)算法的有窮性，輸入輸出性和確定性的正確描述。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解”以及第七章課件。(3)關(guān)于算法與程序、計(jì)算機(jī)語言之間的關(guān)系，下列說法不正確的是_____。(A)算法是解決問題的步驟，某個(gè)問題可能有多個(gè)求解算法；(B)算法不能直接由計(jì)算機(jī)執(zhí)行，必須將其轉(zhuǎn)換為程序才能夠由計(jì)算機(jī)執(zhí)行；(A)一定能夠找到；(B)一定不能找到；(C)不確定能不能找到。答案：B解釋：本題考查問題及其數(shù)學(xué)建模的作用選擇（B），根據(jù)歐拉

5、回路關(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é)建模與算法策略設(shè)計(jì)算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。(2)對(duì)河流隔開的m塊陸地上建造的n座橋梁，能否找到走遍這n座橋且只許走過每座橋一次最后又回到原出發(fā)點(diǎn)的路徑呢？

6、_____。(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)容參考第七章視頻之“算法與算法類

7、問題的求解，第七章課件或查閱歐拉回路相關(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)