【正文】 算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。該圖奇點(diǎn)為G和D，因此可以找到一條歐拉回路，并且只能以此兩點(diǎn)作為起點(diǎn)和終點(diǎn)，因此應(yīng)該選擇C。具體內(nèi)容查閱背包問(wèn)題相關(guān)資料。(6) 假定有N個(gè)物品，其價(jià)值分別為V1, V2, ..., VN，重量分別為W1, W2, ..., WN，背包所能承受的總重量為Wmax，為物品i定義一個(gè)決策變量xi，其中xi=1表示選擇該物品，xi=0表示不選擇該物品。可見(jiàn)，貪心算法與遍歷算法的解不會(huì)總是完全相同。(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è)具體的TSP問(wèn)題，每次執(zhí)行貪心算法，所求得的最終解可能是不同的。(數(shù)學(xué)抽象I)城市記為：V={v1,v2,…,vn}，任意兩個(gè)城市vi,vj∈V之間的距離記為：dvivj，問(wèn)題的解是尋找所有城市的一個(gè)訪問(wèn)順序T={t1,t2,…,tn}，其中ti∈V，使得mini=1ndtiti+1，這里假定除tn+1=t1外，ti 185。III和IV是對(duì)同一問(wèn)題的不同表述罷了，都是TSP問(wèn)題，只是將城市換為了圖。（B）正確。(A)00000000 00000101； (B)00000000 00001000； (C)00000000 00001010； (D)上述都不正確；答案：B解釋：本題考查對(duì)存儲(chǔ)器和數(shù)組的理解。圖I.(1)關(guān)于“樹(shù)”這種數(shù)據(jù)結(jié)構(gòu)，下列說(shuō)法不正確的是_____。(B)錯(cuò)誤。這是（A）的操作。而改地址在整個(gè)過(guò)程中，通過(guò)其它選項(xiàng)來(lái)看，不會(huì)有涉及到（B）中的地址。(A) 推入是將數(shù)據(jù)放入堆棧的頂端，堆棧頂端指針top加一；(B) 彈出是將堆棧頂端的數(shù)據(jù)取出，堆棧頂端指針top減一；(C) 如果堆棧頂端指針top為0，則堆棧為空；(D) 如果是固定長(zhǎng)度的堆棧，當(dāng)堆棧頂端指針top與長(zhǎng)度相等時(shí)，堆棧是滿的。再將其他9個(gè)元素壓入堆棧，需要9次推入操作。(A)用于判斷某個(gè)城市是否是已訪問(wèn)過(guò)的城市；(B)用于尋找距當(dāng)前城市距離最近的城市；(C)用于完整地產(chǎn)生一個(gè)路徑； (D)上述都不是； 答案：B解釋：本題考查學(xué)生是否能讀懂流程圖以及TSP流程；圖中中層循環(huán)， K從第2個(gè)城市至第N個(gè)城市循環(huán), 判斷D[K, S[I1]]是否是最小值，j記錄了最小距離的城市號(hào)K；所以，正確答案選B；具體內(nèi)容請(qǐng)參考課堂視頻“算法設(shè)計(jì)算法思想的精確表達(dá)(III)”和第七章課件；(3)外層循環(huán)(I變量控制的循環(huán))的作用是_________。 j++) n2次(40) For(k=1。 i=n。 1次else index； for i = 1 to 100 100次 for j = 1 to 200 200100次 index=index+2。(11) 如果K=N，轉(zhuǎn)步驟(5)。答案：E解釋： 本題考查算法問(wèn)題求解的基本步驟；求解一個(gè)算法問(wèn)題，首先要進(jìn)行數(shù)學(xué)建模，用數(shù)學(xué)語(yǔ)言對(duì)問(wèn)題進(jìn)行抽象，A正確；進(jìn)行數(shù)學(xué)建模后，要判斷該問(wèn)題是否有解，所以B也正確；之后要根據(jù)數(shù)學(xué)模型，設(shè)計(jì)出求解的算法，C正確；對(duì)于一個(gè)數(shù)學(xué)模型，我們可以用不同的數(shù)學(xué)方法設(shè)計(jì)出不同的解法，所以D也正確；綜上所述，正確答案選E； 具體內(nèi)容請(qǐng)參考第七章所有視頻和課件；(2)對(duì)于算法類問(wèn)題求解，下列說(shuō)法正確的是_________。 /*I層的循環(huán)，即下列步驟為每次找出一個(gè)城市，I從2到n，即從找出第2個(gè)城市一直到找出第n個(gè)城市(2) I=2。else index； for i = 1 to 100 for j = 1 to 200 index=index+2。 j++)(40) For(k=1。分析下列程序的時(shí)間復(fù)雜性。11. 閱讀下列算法，回答： Start of the algorithm(算法開(kāi)始)(1) N=10； (2) i=2；sum=2； (3) 如果 i=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(8)步執(zhí)行； (4) 如果i / 2 ==0 則轉(zhuǎn)到第(6)步執(zhí)行；(5) sum = sum + i； (6) i = i+1； (7) 返回到第(3)步繼續(xù)執(zhí)行； (8) 輸出sum的結(jié)果。(A) 1，1 (B) 2，1 (C) 10，9 (D) 10，0 (E) 11，8答案：C解釋：本題考查對(duì)堆棧結(jié)構(gòu)的理解。堆?？梢允鬼樞虼鎯?chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來(lái)實(shí)現(xiàn)。 (A)的操作是在存儲(chǔ)表中增加85這個(gè)元素。(4)如想使圖(I)，改變?yōu)榇鎯?chǔ)下圖III所示的邏輯關(guān)系，操作正確的是_____。(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ō)法有不正確的。7.“樹(shù)”是一種典型的數(shù)據(jù)結(jié)構(gòu)，在很多算法中都應(yīng)用樹(shù)來(lái)組織相關(guān)的數(shù)據(jù)。其余說(shuō)法都對(duì)。(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è)指針。j時(shí))。（C）選項(xiàng)所描述的圖的遍歷問(wèn)題，主要有深度優(yōu)先搜索，和廣度優(yōu)先搜索兩種解決方法，不是貪心算法。由此可見(jiàn)，當(dāng)n巨大時(shí)，用遍歷算法解決TSP問(wèn)題是不現(xiàn)實(shí)的。最后回到A?！皩⑶癷件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i1件物品的問(wèn)題。問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。d圖有FGE三個(gè)奇點(diǎn)，一定不能找到，而e圖有FG兩個(gè)奇點(diǎn)，一定能找到，因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之“數(shù)學(xué)建模與算法策略設(shè)計(jì)算法思想”，第七章課件或查閱歐拉回路相關(guān)資料。答案：B解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用選擇（B），根據(jù)歐拉回路關(guān)系可知，要是一個(gè)圖形可以一筆畫(huà)，需要滿足：1）圖形必須是連通的；2）途中的“奇點(diǎn)”（相連的邊的個(gè)數(shù)為奇數(shù)的點(diǎn)）個(gè)數(shù)是0或2（該題中應(yīng)為0個(gè)）。因此（C）選項(xiàng)錯(cuò)誤。(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）算法的輸出性：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。答案：B解釋：本題考查對(duì)算法基本性質(zhì)的理解 （B）違反了算法的有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。具體內(nèi)容參考第七章視頻之“算法與算法類問(wè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)上述條件還不夠，還需滿足更多條件。具體內(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塊陸地上建造的n座橋梁，若要找到走遍這n座橋且只許走過(guò)每座橋一次的路徑”。(A) 16 (B) 15 (C) 14 (D) 13答案：B解釋：本題考查問(wèn)題及其數(shù)學(xué)建模的作用由題意可知使用貪心算法，從單位價(jià)值最高的開(kāi)始放入，五個(gè)物品單位價(jià)值從大到小依次為：,2,1,1,1/3，依次放入并驗(yàn)證是否超出背包重量限制：$104kg, $21kg,$11kg,$22kg，之后放不下$412kg的物品，到此總價(jià)值是15，所以選擇（B）。TSP旅行商問(wèn)題，是一個(gè)經(jīng)典問(wèn)題，如下圖所示，描述為“有n個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過(guò)每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市，問(wèn)如何事先確定好一條最短的路線使其旅行的費(fèi)用最少”。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。故(D)正確。j時(shí))。回答下列問(wèn)題。 詳細(xì)內(nèi)容請(qǐng)參考第七章視頻“算法，程序與計(jì)算系統(tǒng)之靈魂”與第七章課件。(A)D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+((i1)*每行的列數(shù)+j1)*單一元素占用存儲(chǔ)單元的數(shù)目； (B)D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+(i1)*每行的列數(shù)+j1；此公式在任何情況下都正確； (C)D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+((j1)*每行的列數(shù)+i1)*單一元素占用存儲(chǔ)單元的數(shù)目； (D)D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+(j1)*每行的列數(shù)+i1；此公式在任何情況下都正確；答案：A解釋：本題考查對(duì)存儲(chǔ)器和二維數(shù)組的理解。用兩個(gè)數(shù)組組織樹(shù)形數(shù)據(jù)時(shí)，一個(gè)數(shù)組存放數(shù)據(jù)元素，另一個(gè)數(shù)組存儲(chǔ)對(duì)應(yīng)的父元素。 第一個(gè)元素值為100。這是（C）的操作。(1)有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的說(shuō)法，不正確的是_____。棧頂指針的值代表了堆棧中數(shù)據(jù)的個(gè)數(shù)。圖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ò)誤。問(wèn)T(n)=O(f(n))是什么意思？正確的是_________。 j++)(40) For(k=1。 i=n。 n次(30) For(j=1。分析下列算法的時(shí)間復(fù)雜性。/*I層的循環(huán)結(jié)束(16) Sum=Sum+D[1, j]；(17) 逐個(gè)輸出S[N]中的全部元素。End of the Al