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

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

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

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

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

5、一個(gè)具體問題， 它可以在變換輸入輸出的情況下， 求解一個(gè) 問題系列；(D) 問題求解都可以歸結(jié)到算法的構(gòu)造與設(shè)計(jì)，系統(tǒng)和算法的關(guān)系是：算法是龍，而系 統(tǒng)是睛，畫龍要點(diǎn)睛。(E) 上述說法有不正確的；答案：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)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后

6、又回到原出發(fā)點(diǎn)的路徑。關(guān)于哥尼斯堡七橋問題，著名數(shù)學(xué)家歐拉對該問題做了一個(gè)抽象：“頂點(diǎn)為陸地，“邊為連接兩塊陸地的橋梁。這個(gè)抽象被稱為“圖，并定義了頂點(diǎn)的“度為連接一個(gè)頂點(diǎn)的邊的數(shù)量。關(guān)于此問題答復(fù)以下問題。/此題考查問題及其數(shù)學(xué)建模的作用哥尼斯堡七橋問題的路徑能夠找到嗎?(A) 一定能夠找到；(B) 一定不能找到；(C)不確定能不能找到。(a)(b)答案：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)，每條

7、橋抽象成邊，可知圖中奇點(diǎn)個(gè)數(shù)是 4 個(gè)，因此不可能 找到。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想，第七章課件或查閱歐拉回路相關(guān)資料。2對河流隔開的 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)?起點(diǎn)和終點(diǎn)是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè)。該問題中將 m 個(gè)島抽象成

8、m 個(gè)點(diǎn)，每條橋 抽象成邊，但圖中奇點(diǎn)個(gè)數(shù)未知，因此不能做判斷。具體內(nèi)容參考第七章視頻之“算法與算法類問題的求解，第七章課件或查閱歐拉回路相 關(guān)資料。3對河流隔開的 m 塊陸地上建造的 n 座橋梁，假設(shè)要找到走遍這 n 座橋且只許走過每座橋一 次最后又回到原出發(fā)點(diǎn)的路徑，那么需滿足以下條件。Am 個(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途中的“奇

9、點(diǎn)相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)個(gè)數(shù)是 0 或 2該題中因?yàn)?起點(diǎn)和終點(diǎn)是一個(gè)，所以奇點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè)。該問題中將 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該題

10、中因?yàn)?起點(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參見圖c,增加哪些邊，使得能夠找到走遍每一座橋，且每座橋僅走過一次、最后又回 到原出發(fā)點(diǎn)的路徑呢？ABG 邊； BAG 邊；CCG 邊；DAD 邊； EDE 邊。答案：C解釋：此題考查問題及其數(shù)學(xué)建模的作用選擇C根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫，需要滿足：1圖形必須是連通的；2途中的“奇點(diǎn)相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)個(gè)數(shù)是 0 或 2該題中因?yàn)?起點(diǎn)和終點(diǎn)是一個(gè)， 所以奇

11、點(diǎn)個(gè)數(shù)應(yīng)為 0 個(gè)。圖中奇點(diǎn)是 C 與 G,個(gè)數(shù)為 2,不符合要求， 因此在 CG 間增加一條邊，將寄點(diǎn)數(shù)變成 0 可滿足要求，因此應(yīng)該選擇 Co 具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想，第七章課件或查閱歐拉回路相關(guān)資料。6-1對河流隔開的 m 塊陸地上建造的 n 座橋梁，假設(shè)要找到走遍這n 座橋且只許走過每座橋一次的路徑，那么需滿足以下條件。Am 個(gè)頂點(diǎn) n 條邊的圖應(yīng)是連通的，即由一個(gè)頂點(diǎn)出發(fā)可沿邊到達(dá)任何一個(gè)其他頂點(diǎn)；B每個(gè)頂點(diǎn)的度應(yīng)為偶數(shù)；C既需要滿足A又需要滿足B;(c)(D)不滿足上述條件(A)(B)(C)的圖也能找出滿足題目規(guī)定要求的路徑;答案：D解釋：此題考

12、查問題及其數(shù)學(xué)建模的作用選擇(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)對河流隔開的 m 塊陸地上建造的 n 座橋梁，假設(shè)要找到走遍這n 座橋且只許走過每座橋一次的路徑，那么需滿足以下條件。(A) m 個(gè)頂

13、點(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ù)；(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)容參考第七章視頻之

14、“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想，第七章課件或查閱歐拉回路相關(guān)資料。(7)下面所示的圖(d)和圖(e),問能否找到走遍每一座橋，且每座橋僅走過一次的路徑呢？(A) 圖(d)和圖(e)都一定不能找到；(B) 圖(d) 一定能夠找到；圖(e)一定不能找到;(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 圖有

15、 FG 兩個(gè)奇點(diǎn)，一定能找到，因此應(yīng)該選擇 Co具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想，第七章課件或查閱歐拉回路相關(guān)資料。(8)參見以下圖(f)，以下說法正確的選項(xiàng)是D、E、F、G中的任意兩個(gè)頂點(diǎn) X 和 Y,都可以找到一條路徑，從X 出發(fā) 走遍每一座橋，且每座橋僅走過一次，最后終止于Y;(B) 對兩個(gè)頂點(diǎn) A 和 B,可以找到一條路徑，從 過一次，最后終止于 B;(C) 對兩個(gè)頂點(diǎn) D 和 G,可以找到一條路徑，從 過一次，最后終止于 G;(D)對(A、B、C、D、E、F、G中的任意兩個(gè)頂點(diǎn) 出發(fā)走遍每一座橋，且每座橋僅走過一次，最后終止于答案：C解釋：此題考查問題及其數(shù)

16、學(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)該選擇 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ì)算；而如果無解，那么

17、無需進(jìn)行計(jì)算；(C) 一個(gè)具體問題的求解方法，進(jìn)行數(shù)學(xué)建模后，可反映出一類問題的求解方法，例如(A)對(A、B、C、A 出發(fā)走遍每一座橋，且每座橋僅走D 出發(fā)走遍每一座橋，且每座橋僅走X 和丫；Y,都找不到一條路徑，從 X哥尼斯堡七橋問題的求解方法，建立“圖后，可反映任意n 座橋的求解方法;(D)上述全部；答案：D解釋：此題考查問題及其數(shù)學(xué)建模的作用以上說明都正確，對一個(gè)具體問題的求解， 可先進(jìn)行數(shù)學(xué)建模， 將具體問題轉(zhuǎn)化成抽象 問題，再進(jìn)行判斷是否有解，假設(shè)有解那么計(jì)算，假設(shè)無解那么無需計(jì)算。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)-算法思想，第七章課件或查閱歐拉回路相關(guān)資料。(10

18、)哥尼斯堡七橋問題，推而廣之就是m 個(gè)頂點(diǎn) n 條邊的圖的“一筆畫問題，我們可以給出一個(gè)算法來求解該問題，即“對河流隔開的m 塊陸地上建造的 n 座橋梁，假設(shè)要找到走遍這 n 座橋且只許走過每座橋一次的路徑。關(guān)于該算法的根本思想，以下說法正確的選項(xiàng)是(A) 以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照圖的“邊的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給 定問題的解；(B) 以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照圖的未訪問過“邊的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(C

19、) 首先判斷該問題是否有解，假設(shè)無解，那么直接退出；假設(shè)有解，那么以任何一個(gè)頂點(diǎn)為起點(diǎn)，按照圖的未訪問過“邊的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo)記該邊為“已訪問，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(D) 首先判斷該問題是否有解，假設(shè)無解，那么直接退出；假設(shè)有解，那么選擇一個(gè)奇數(shù)度的頂 點(diǎn)為起點(diǎn)，按照圖的未訪問過“邊的指示，找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn)，并標(biāo) 記該邊為“已訪問，依次循環(huán)，直到所有的邊都被訪問過為止，便可找到給定問題的解；(E) 上述都不正確。答案：D解釋：此題考查問題及其數(shù)學(xué)建模的作用選擇(D)根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆

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

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

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

23、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)使用遍歷算法策略所得到的解的總價(jià)值是(A) 8(B) 15(C) 14(D) 13答案：B解釋：此題考查問題及其數(shù)學(xué)建模的作用用遍歷算法策略，狀態(tài)轉(zhuǎn)移方程：

24、fv=maxfv,fv-ci+wi ，即 fiv表示前 i 件物品恰放入一個(gè)容量為 v 的背包可以獲得的最大價(jià)值，第 i 件物品的重量是 ci,價(jià)值是 wi。將前 i 件物品放入容量為 v 的背包中這個(gè)子問題，假設(shè)只考慮第 i 件物品的策略(放或不放)， 那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1 件物品的問題。如果不放第i 件物品，那么問題就轉(zhuǎn)化為前 i-1 件物品放入容量為 v 的背包中，價(jià)值為 fi-1v；如果放第 i 件物品，那么問題就 轉(zhuǎn)化為 前 i-1 件物品放 入剩下的容量為v-ci的背包中，此時(shí)能獲得的最大價(jià)值就是fi-1v-ci再加上通過放入第 i 件物品獲得的價(jià)值 wi。按此方法，

25、可得總價(jià)值是15,所以選擇(B)。具體內(nèi)容查閱背包問題相關(guān)資料。 假定有 N 個(gè)物品，其價(jià)值分別為 V1, V2, ., VN，重量分別為 W1, W2, ., WN ,背包所 能承受的總重量為 Wmax,為物品 i 定義一個(gè)決策變量 xi,其中 xi=1 表示選擇該物品，xi=0 表示不選擇該物品。下面哪個(gè)描述共同構(gòu)成了該問題的數(shù)學(xué)模型。(A) 問題的目標(biāo)函數(shù)是 maxmax x xi iV Vi;i=1(B) 問題的目標(biāo)函數(shù)是 maxmax Z Z xWxW ；i=1N(C) 問題解所應(yīng)滿足的約束是z x Wmax;i JN(D) 問題解所應(yīng)滿足的約束是zxMMWmax;i 4(E) 前述

26、(A)和(C);答案：E解釋：此題考查問題及其數(shù)學(xué)建模的作用該問題有兩個(gè)條件：N1)物品不能超過背包所能承受的重量，即(C)C)選項(xiàng)：、x xiW Wi 000( CKI4XH311Doowoooa oiiiiooo第E個(gè)畋聘元素UQOOOOCOOa MDDD11J.CHXXHMOD 1C1CD000jft 7個(gè)數(shù)房兀素旺3OOOOOOOOOGDOIOODODMDON3 dCDOlMlLeftpointerDOOOQOg口wmimxJtw iwcxwio第1個(gè)皴幅元*的互拒機(jī)0000-0000 OOODlOll0(XXXX)00 OOOOOIOO第2個(gè)蛇?無米的A指奸OOMdCKIO OODO

27、IICPDDWODDDDDDODD11D第3個(gè)數(shù)械元素的左招鐘OOOOCOOC aODOUDl第4個(gè)景搖元蠹的左揩針OOMDOOO 00001110000(X000 OOOOOODO第5個(gè)寂屆元肅的在悔時(shí)00000000 00001111ooooaoa) wootw第&個(gè)裁展元素的左芋敘OOWDOeo QODiOMd第7個(gè)敷JH處素的左惜H00000000 MH1D00OOWOOW QdDlOOlDRight PointerOOMOHMtnkjudtw auwuutu 00000(X)0 00-010100ooaxxotjo 000)0104第個(gè)歌留元素的右將甘ODHOOM OCI01

28、0101第 m 個(gè)敷胃無素的右指辨oooococo mmoiwLWtXXW iMMXXWO第4個(gè)數(shù)輯兀素的是稻普OQ0M040 H010111QQOOQQO) ODOOOOOO第5個(gè)瓶蝸元素的看悟時(shí)oooocioeci Mournarnoftw aowotw第&個(gè)巍唇元素的右痛針OOWDOCO OODUOQ1uDcmtwu uuxvuuo第?元曩的右格時(shí)OOMflOCC 00011010ODOOOOM Q0 011011圖 I.(1)關(guān)于“樹這種數(shù)據(jù)結(jié)構(gòu)，以下說法不正確的選項(xiàng)是。(A) “樹既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系；(B) “樹可以采用兩個(gè)數(shù)組來組織樹

29、型數(shù)據(jù)，其中一個(gè)數(shù)組用于存儲(chǔ)數(shù)據(jù)元素本身, 另一個(gè)數(shù)組用于存儲(chǔ)與該數(shù)據(jù)元素發(fā)生某種關(guān)系的另一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置；(C) “樹可以采用三個(gè)數(shù)組來組織樹型數(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) 上述說法有不正確的。答案：E解釋：此題考查對樹結(jié)構(gòu)的理解?！皹浼刃枰鎯?chǔ)數(shù)據(jù)元素本身即數(shù)據(jù)，還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。(A)的說法沒有問題。用兩個(gè)數(shù)組組織樹形數(shù)據(jù)時(shí)，一個(gè)數(shù)組存放數(shù)據(jù)元素，另一個(gè)數(shù)組存儲(chǔ)對應(yīng)的父元素。用三個(gè)數(shù)組組織樹形數(shù)據(jù)時(shí)，一個(gè)數(shù)組

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

31、不同的左指針和右指針可以反映數(shù)據(jù)元素之間不同的關(guān)系；(D) 圖(a)說明，一個(gè)數(shù)據(jù)元素最多只能有兩個(gè)子元素，一個(gè)是左子元素，一個(gè)是右子元 素；(E) 上述說法有不正確的。答案：B解釋：此題考查對樹結(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ò)誤。其余說法均正確。詳細(xì)內(nèi)容請參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂與第七章課件。上圖表示的數(shù)據(jù)的邏輯關(guān)系，以下正確的選項(xiàng)是。(A) 圖 II.(a);(B) 圖 II.(b);(C) 圖 II.(c);(D) 圖 II.(d)

32、;答案：D解釋：此題考查對樹結(jié)構(gòu)的理解。第一個(gè)元素值為 100。其左指針指向的存儲(chǔ)單元的內(nèi)容為地址：00000000 00000010。該地址存儲(chǔ)的數(shù)據(jù)為 50。故第一個(gè)元素 100 的左兒子為 50。一次類推，可以畫出(d)中的樹。故(D)正確。詳細(xì)內(nèi)容請參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂與第七章課件。(A) 將 00000000 00001000 號(hào)存儲(chǔ)單元的值修改(B) 將 00000000 00011010 號(hào)存儲(chǔ)單元的值修改為(C) 將 00000000 00010001 號(hào)存儲(chǔ)單元的值修改為(D) 將 00000000 00010011 號(hào)存儲(chǔ)單元的值修改為(E) 上述(A

33、)(B)(C)(D)都需要正確完成；00000000 01101110即十進(jìn)制的 110;00000000 00000111;00000000 00000000即 Null;00000000 00001000 ;圖II.(4)如想使圖(I),改變?yōu)榇鎯?chǔ)以下圖 III 所示的邏輯關(guān)系，操作正確的選項(xiàng)是答案：E解釋：此題考查對樹結(jié)構(gòu)的理解。想要得到題目要求，那么需要改變的是100 的右兒子的值。首先，增加 110 這個(gè)元素。這是A的操作。很容易知道，110 這個(gè)元素對應(yīng)的左指針指向00000000 00010001 ,將該單元的存儲(chǔ)內(nèi)容改為 NULL，增加了 110 元素的左兒子為空。這是C的操作

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

35、：此題考查對樹結(jié)構(gòu)的理解。A的操作是在存儲(chǔ)表中增加 85 這個(gè)元素。C的操作是將 85 的右兒子設(shè)為 NULL。D的操作是將 100 的左指針指向 85 元素的地址。B是對 00000000 00010010 地址進(jìn) 行操作。而改地址在整個(gè)過程中， 通過其它選項(xiàng)來看，不會(huì)有涉及到B中的地址。故B 不正確。詳細(xì)內(nèi)容請參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂與第七章課件。8.堆棧stack是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，其特殊支出在于只能允許在鏈結(jié)串行或陣 列的一端稱為堆棧頂端指針，top進(jìn)行參加數(shù)據(jù)push或輸出數(shù)據(jù)pop的運(yùn)算。其示意圖 如下所示。00000000 01010101 ;000

36、00000 00000010;00000000 00000000即 Null;00000000 00001000;(1)有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的說法，不正確的選項(xiàng)是。(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解釋：此題考查對堆棧結(jié)構(gòu)的理解。在堆棧中，先進(jìn)棧的元素被保存在堆棧下部。在彈出元素時(shí)，棧頂?shù)脑叵缺粡棾?。故堆棧運(yùn)行的原理是后進(jìn)先出。(A)不正確，(B)正確。堆

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

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

39、頂指針的值代表了堆棧中數(shù)據(jù)的個(gè)數(shù)。 將棧底的元素 彈出，那么首先必須要使堆棧變空，需要連續(xù)十次彈出操作。再將其他9 個(gè)元素壓入堆棧，需要 9 次推入操作。故(C)選項(xiàng)正確。詳細(xì)內(nèi)容請參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂與第七章課件。9.程序流程圖是表達(dá)算法控制結(jié)構(gòu)或者說算法步驟的重要方法。答復(fù)以下問題：(1)觀察以下圖 I.,沒有錯(cuò)誤的流程圖為。(A) 流程圖(a)無錯(cuò)誤；(B) 流程圖(b)無錯(cuò)誤；(C) 流程圖(c)無錯(cuò)誤；(D) 沒有無錯(cuò)誤的流程圖;答案：D解釋：此題考查流程圖的知識(shí)點(diǎn)；圖(a)中，在進(jìn)行“循環(huán)控制條件成立？ 這一判斷時(shí)，不應(yīng)該使用方向，而應(yīng)該用菱 形判斷，所以流程

40、圖(a)錯(cuò)誤；圖(b)中，當(dāng)判斷循環(huán)控制條件成立為是后，修改局部的返回 箭頭不應(yīng)該指向初始化局部，而應(yīng)該返回判斷“循環(huán)控制條件成立？ ，所以流程圖(b)錯(cuò)誤;圖(c)中，有兩處錯(cuò)誤，一是在判斷“循環(huán)控制條件成立？ 時(shí)，沒有標(biāo)明兩個(gè)箭頭方向是“是還是“否，二是同圖(b)一樣，返回箭頭不應(yīng)該標(biāo)在初始化局部，所以流程圖(c)錯(cuò)誤;綜上所述，三個(gè)圖當(dāng)中都有錯(cuò)誤。(開始)* 居皆環(huán)執(zhí)行的 規(guī)蚪成語句“ 即， 施環(huán)體1結(jié)束)(b)圖 I.(0修改局部詳細(xì)內(nèi)容請參考第七章視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(II)與第七章課件(2)觀察以下圖 II.,該流程圖中存在錯(cuò)誤，以下說法最完整準(zhǔn)確的是圖 II.(A)

41、 條件判斷框不應(yīng)為矩形，而應(yīng)為菱形或六角形；(B) 條件判斷框中引出的箭頭應(yīng)標(biāo)記Yes(是)或 No(否)，說明條件滿足或不滿足時(shí)的程序走向；(C) 僅僅包含錯(cuò)誤(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ī)那么或語句，所以該圖中不止 AB 兩個(gè)錯(cuò)誤，正確答案選 D;詳細(xì)內(nèi)容請參考第

42、七章視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(II)與第七章課件。10.閱讀以下算法，答復(fù)：Start of the algorithm(算法開始)(1)輸入N的值；設(shè)i的值為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解釋：此題考查步驟描述法；在上述步驟中

43、，主要欠缺的是程序的初始化，雖然有將i 的初始值設(shè)為 1,但 sum 的初始值確忽略了，這樣，沒方法正確計(jì)算sum=1+2+3 -.+N，應(yīng)該把 sum 初始值設(shè)為 0;詳細(xì)內(nèi)容請參考第七章視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(II)與第七章課件。11.閱讀以下算法，答復(fù)：Start of the algorithm(算法開始)(1) N=10 ;(2) i=2 ; sum=2;(3)如果i*L=l1;N如如DK即即-1DtempMj-K； Utemp-DfK.SII-1)；* K = K4-1;-Sl| = j; I = 1+1； Sum=SuiM+Dtcm|)i-Sum = Suni+D1t

44、j|;逐個(gè)輸出逐個(gè)輸出EN中中的全部元素：的全部元素：輸出輸出Num;fei圖 i.(1)最內(nèi)層循環(huán)(L 變量控制的循環(huán))的作用是。(A) 用于判斷某個(gè)城市是否是已訪問過的城市；(B) 用于尋找距當(dāng)前城市距離最近的城市；(C) 用于完整地產(chǎn)生一個(gè)路徑；(D) 上述都不是；答案：A解釋：此題考查學(xué)生是否能讀懂流程圖以及TSP 流程；圖中最內(nèi)層循環(huán)，L 從 1 至 I-1,循環(huán)判斷第 K 個(gè)城市是否是已訪問過的城市，如是那么 不參加最小距離的比擬；所以，正確答案選 A;具體內(nèi)容請參考課堂視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(III) 和第七章課件;(2)中層循環(huán)(K 變量控制的循環(huán))的作用是(A)

45、用于判斷某個(gè)城市是否是已訪問過的城市；(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)容請參考課堂視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(III) 和第七章課件；(3)外層循環(huán)(I 變量控制的循環(huán))的作用是(A) 用于判斷某個(gè)城市是否是已訪問過的城市；(B) 用于尋找距當(dāng)前城市距離最近的城市；(C) 用于完整地產(chǎn)生一個(gè)路徑；(D) 上述都不是；答

46、案：C解釋：此題考查學(xué)生是否能讀懂流程圖以及TSP 流程；圖中外層循環(huán)，I 從 2 至 N 循環(huán)；I-1 個(gè)城市已訪問過，正在找與第 I-1 個(gè)城市最近距離 的城市；已訪問過的城市號(hào)存儲(chǔ)在S中；所以，正確答案選 C;具體內(nèi)容請參考課堂視頻“算法設(shè)計(jì)-算法思想的精確表達(dá)(III) 和第七章課件；13.一般而言，算法設(shè)計(jì)完成后，需要進(jìn)行算法的模擬與分析。關(guān)于算法的模擬與分析答復(fù) 以下問題：(1)通常從哪些方面，進(jìn)行算法的模擬與分析？。(A) 算法的正確性問題，即一個(gè)算法求得的解是滿足問題約束的正確的解嗎？(B) 算法的效果評價(jià)問題，即算法輸出的是最優(yōu)解還是可行解，其可行解與最優(yōu)解的偏 差有多大？(

47、C) 算法的時(shí)間效率問題(時(shí)間復(fù)雜性)，即算法執(zhí)行所需要的時(shí)間是多少？(D) 算法的空間效率問題(空間復(fù)雜性)，即算法執(zhí)性所需要的空間是多少？(E) 上述全部。答案：E解釋：此題考查算法分析和算法復(fù)雜性；當(dāng)對一個(gè)算法進(jìn)行模擬與分析時(shí)，有以下幾個(gè)方面要判斷：(1)問題求解的過程、方法算法是正確的嗎？算法的輸出是問題的解嗎？ (2)算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？(3)算法獲得結(jié)果的時(shí)間有多長 ？即分為時(shí)間復(fù)雜性和空間復(fù)雜性；所以，答案應(yīng)選E;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件；(2)算法的時(shí)間復(fù)雜性，可以表達(dá)為關(guān)于問題規(guī)模n 的

48、一個(gè)函數(shù) T(n), T(n)可以用大。表示法來處理。問 T(n)=O(f(n)是什么意思？正確的選項(xiàng)是。(A) T(n)是關(guān)于 f(n)的一個(gè)函數(shù)；(B) T(n)是與 f(n)同數(shù)量級的函數(shù)；(C) T(n)是將函數(shù) f(n)代入 O(x)中所形成的新函數(shù)；(D) T(n)是依據(jù) f(n)計(jì)算出來的；答案：B解釋：此題考查時(shí)間復(fù)雜性，和大“ O記法；時(shí)間復(fù)雜性是指如果一個(gè)問題的規(guī)模是n,解這一問題的某一算法所需要的時(shí)間為T(n),它是 n 的某一函數(shù)，T(n)稱為這一算法的時(shí)間復(fù)雜性。大 O 記法：根本參數(shù) n 表示問題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n 的函數(shù)?！癘 表示量級(ord

49、er),允許使用“=代替“卞如 n2+n+1 =O(n2)，所以正確答案選 B;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件；(3)算法的時(shí)間復(fù)雜性 T(n),可以通過計(jì)算算法根本語句的執(zhí)行次數(shù)來獲得。分析以下程序的時(shí)間復(fù)雜性。(10)K = 0;(20)I = 2 ;(30)While (I=8)(40)( K =K + I ;(50)I = I + 2 ; 該程序時(shí)間復(fù)雜性表達(dá)正確的選項(xiàng)是。(A) O(n);(B) O(1)(C) O(n 2);(D) O(n!);答案：B解釋：此題考查時(shí)間復(fù)雜性，和大“ O記法；具體分析如下:K = 0 ; 1 次I = 2 ;

50、1 次While (I=8)8 次(K = K + I ; 8 次I = I + 2 ; 8 次T(n)=1 + 1+8 X 3= O(1)，所以答案選 B;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件;(4)算法的時(shí)間復(fù)雜性 T(n),可以通過計(jì)算算法根本語句的執(zhí)行次數(shù)來獲得。分析以下程序的時(shí)間復(fù)雜性。(10) sum=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á)正確的選項(xiàng)是。(A) O(n);(B) O(n2)(C) O(n3)

51、;(D) 上述都不對；答案：C解釋：此題考查時(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=j; k+)n3次(50)sum=sum+1; n3次T(n) = 2 n3+ n2+ n + 1 = O(n3),所以正確答案選 C;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件;(5)算法的時(shí)間復(fù)雜性 T(n),可以通過計(jì)算算法根本語句的執(zhí)行次數(shù)來獲得。分析以下程序 的時(shí)間復(fù)雜性。(10) sum=0;(20) For(

52、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á)正確的選項(xiàng)是。(A) O(n);(B) O(n2) ；(C) O(n 3);(D) 上述都不對;答案：B解釋：此題考查時(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+)5n次2(50)sum=sum+1;5 n 次T(n)= 11n2+ n + 1 = O(n2)，所以正

53、確答案選 B;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件;(6)閱讀下面的程序，其時(shí)間復(fù)雜度為 ?A. O(1) B. O(n) C. O(n2)D. O(n*log n)int index = 5;int condition=1;if (condition=1) thenindex+;elseindex-；for i = 1 to 100for j = 1 to 200index=index+2;答案：A解釋：此題考查時(shí)間復(fù)雜性，和大“O記法；具體分析如下：int index = 5;1 次int condition=1;1 次if (condition=1) t

54、hen 1 次index+;1 次elseindex-；for i = 1 to 100100 次for j = 1 to 200200 x100 次index=index+2; 200 x 100 次所以 T(n)=O(1)，正確答案選 A;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件;(7) 為什么要評估算法的復(fù)雜性？以下說法不正確的選項(xiàng)是(A) 當(dāng)算法的時(shí)間復(fù)雜性量級為多項(xiàng)式函數(shù)時(shí)，計(jì)算機(jī)是能夠完成計(jì)算的；(B) 當(dāng)算法的時(shí)間復(fù)雜性量級為非多項(xiàng)式函數(shù)時(shí)，如指數(shù)函數(shù)、階乘函數(shù)時(shí)，計(jì)算機(jī)是 不能夠完成計(jì)算的；(C) 當(dāng)算法的時(shí)間復(fù)雜性量級為非多項(xiàng)式函數(shù)時(shí)，如指數(shù)函數(shù)

55、、階乘函數(shù)時(shí)，對于大規(guī) 模問題，計(jì)算機(jī)是不能夠完成計(jì)算的；(D) 上述說法有不正確的；答案：B解釋：此題考查算法分析與計(jì)算復(fù)雜性；當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式時(shí)，如O(n2)時(shí)，那么計(jì)算機(jī)對于大規(guī)模問題是可以處理的。當(dāng)算法的時(shí)間復(fù)雜度是用指數(shù)函數(shù)表示時(shí)，如 O(2n)，當(dāng) n 很大(如 10000)時(shí)計(jì)算機(jī)是無法處理的，在計(jì)算復(fù)雜性中將這一類問題被稱為難解性問題。所以對于B 的表達(dá)，只有當(dāng) n 很大時(shí)，屬于大規(guī)模問題時(shí)，計(jì)算機(jī)才不能完成，表達(dá)不精確，所以正確答 案為 B;具體內(nèi)容請參考課堂視頻“高級問題初探：算法分析與計(jì)算復(fù)雜性和第七章課件；(*8)算法的時(shí)間復(fù)雜性 T(n),可以通過評估算法根本語句的執(zhí)行次數(shù)來獲得。分析以下算法 的時(shí)間復(fù)雜性。Start of the algorithm(算法開始)(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ì)算該路徑