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

./第7章算法:程序與計(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í)行的運(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)于算法的命題,下列說法不正確的是_____。<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分別是對(duì)算法的有窮性,輸入輸出性和確定性的正確描述。具體內(nèi)容參考第七章視頻之"算法與算法類問題的求解"以及第七章課件。<3>關(guān)于算法與程序、計(jì)算機(jī)語(yǔ)言之間的關(guān)系,下列說法不正確的是_____。<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ī)則、標(biāo)準(zhǔn)的集合是人和計(jì)算機(jī)都能理解的語(yǔ)言,不僅是高級(jí)語(yǔ)言。因此〔C選項(xiàng)錯(cuò)誤。其余選項(xiàng),〔A正確,解決問題的算法可以有多個(gè)?！睟選項(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)造算法來解決,"是否會(huì)編程序"本質(zhì)上章是"能否想出求解該問題的算法"；<C>一個(gè)算法不僅可以解決一個(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)睛的效果?！睞〔B〔C選項(xiàng)描述正確。具體內(nèi)容參考第七章視頻之"算法與算法類問題的求解"以及第七章課件。2、哥尼斯堡七橋問題,是一個(gè)經(jīng)典問題,如下圖<a>所示,描述為"由河流隔開的四塊陸地上建造了七座橋,尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點(diǎn)的路徑"。關(guān)于哥尼斯堡七橋問題,著名數(shù)學(xué)家歐拉對(duì)該問題做了一個(gè)抽象："頂點(diǎn)"為陸地,"邊"為連接兩塊陸地的橋梁。這個(gè)抽象被稱為"圖",并定義了頂點(diǎn)的"度"為連接一個(gè)頂點(diǎn)的邊的數(shù)量。關(guān)于此問題回答下列問題。//本題考查問題及其數(shù)學(xué)建模的作用<a><b><1>哥尼斯堡七橋問題的路徑能夠找到嗎？_____。<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é)建模與算法策略設(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)容參考第七章視頻之"算法與算法類問題的求解,第七章課件或查閱歐拉回路相關(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è)。該問題中將m個(gè)島抽象成m個(gè)點(diǎn),每條橋抽象成邊,因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之"數(shù)學(xué)建模與算法策略設(shè)計(jì)--算法思想",第七章課件或查閱歐拉回路相關(guān)資料。<4>下面所示的圖<c>,能否找到走遍每一座橋,且每座橋僅走過一次、最后又回到原出發(fā)點(diǎn)的路徑呢？<c><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,不符合要求,因此應(yīng)該選擇B。具體內(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間增加一條邊,將寄點(diǎn)數(shù)變成0可滿足要求,因此應(yīng)該選擇C。具體內(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)作為起點(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)的度均為偶數(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)該選擇C。具體內(nèi)容參考第七章視頻之"數(shù)學(xué)建模與算法策略設(shè)計(jì)--算法思想",第七章課件或查閱歐拉回路相關(guān)資料。<7>下面所示的圖<d>和圖<e>,問能否找到走遍每一座橋,且每座橋僅走過一次的路徑呢？<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圖有FG兩個(gè)奇點(diǎn),一定能找到,因此應(yīng)該選擇C。具體內(nèi)容參考第七章視頻之"數(shù)學(xué)建模與算法策略設(shè)計(jì)--算法思想",第七章課件或查閱歐拉回路相關(guān)資料。<8>參見下圖<f>,下列說法正確的是_____。<f><A>對(duì){A、B、C、D、E、F、G}中的任意兩個(gè)頂點(diǎn)X和Y,都可以找到一條路徑,從X出發(fā)走遍每一座橋,且每座橋僅走過一次,最后終止于Y；<B>對(duì)兩個(gè)頂點(diǎn)A和B,可以找到一條路徑,從A出發(fā)走遍每一座橋,且每座橋僅走過一次,最后終止于B；<C>對(duì)兩個(gè)頂點(diǎn)D和G,可以找到一條路徑,從D出發(fā)走遍每一座橋,且每座橋僅走過一次,最后終止于G；<D>對(duì){A、B、C、D、E、F、G}中的任意兩個(gè)頂點(diǎn)X和Y,都找不到一條路徑,從X出發(fā)走遍每一座橋,且每座橋僅走過一次,最后終止于Y；答案：C解釋：本題考查問題及其數(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>哥尼斯堡七橋問題,給我們的啟示是_____。<A>一個(gè)具體問題應(yīng)該進(jìn)行數(shù)學(xué)抽象,基于數(shù)學(xué)抽象進(jìn)行問題求解；<B>一個(gè)具體問題的求解,進(jìn)行數(shù)學(xué)建模后,通過模型中的性質(zhì)分析可以判斷該問題是否有解,如果有解,則可以進(jìn)行計(jì)算；而如果無解,則無需進(jìn)行計(jì)算；<C>一個(gè)具體問題的求解方法,進(jìn)行數(shù)學(xué)建模后,可反映出一類問題的求解方法,例如哥尼斯堡七橋問題的求解方法,建立"圖"后,可反映任意n座橋的求解方法；<D>上述全部；答案：D解釋：本題考查問題及其數(shù)學(xué)建模的作用以上說明都正確,對(duì)一個(gè)具體問題的求解,可先進(jìn)行數(shù)學(xué)建模,將具體問題轉(zhuǎn)化成抽象問題,再進(jìn)行判斷是否有解,若有解則計(jì)算,若無解則無需計(jì)算。具體內(nèi)容參考第七章視頻之"數(shù)學(xué)建模與算法策略設(shè)計(jì)--算法思想",第七章課件或查閱歐拉回路相關(guān)資料。<10>哥尼斯堡七橋問題,推而廣之就是m個(gè)頂點(diǎn)n條邊的圖的"一筆畫"問題,我們可以給出一個(gè)算法來求解該問題,即"對(duì)河流隔開的m塊陸地上建造的n座橋梁,若要找到走遍這n座橋且只許走過每座橋一次的路徑"。關(guān)于該算法的基本思想,下列說法正確的是_____。<A>以任何一個(gè)頂點(diǎn)為起點(diǎn),按照?qǐng)D的"邊"的指示,找到按該邊與該頂點(diǎn)相連的下一個(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>首先判斷該問題是否有解,若無解,則直接退出；若有解,則以任何一個(gè)頂點(diǎn)為起點(diǎn),按照?qǐng)D的未訪問過"邊"的指示,找到按該邊與該頂點(diǎn)相連的下一個(gè)頂點(diǎn),并標(biāo)記該邊為"已訪問",依次循環(huán),直到所有的邊都被訪問過為止,便可找到給定問題的解；<D>首先判斷該問題是否有解,若無解,則直接退出；若有解,則選擇一個(gè)奇數(shù)度的頂點(diǎn)為起點(diǎn),按照?qǐng)D的未訪問過"邊"的指示,找到按該邊與該頂點(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),若無,則任意,因此〔A〔B〔C,因此應(yīng)該選擇D。具體內(nèi)容參考第七章視頻之"數(shù)學(xué)建模與算法策略設(shè)計(jì)--算法思想",第七章課件或查閱歐拉回路相關(guān)資料。3、背包問題的定義是：給定一組物品,每種物品都有自己的重量和價(jià)格,在限定的總重量?jī)?nèi),我們?nèi)绾芜x擇,才能使得物品的總價(jià)格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。背包問題的一個(gè)例子：應(yīng)該選擇哪些盒子,才能使價(jià)格盡可能地大,而保持重量小于或等于15kg？其示意圖如下：<1>該背包問題的可能解的數(shù)量是_____。<A>5<B>10<C>32<D>64答案：C解釋：本題考查問題及其數(shù)學(xué)建模的作用由題意可知,只要可放入背包的狀態(tài)都算是可能解,可以按背包容量由1到15遍歷可能性。答案為〔C32個(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)超過了背包的限度,所以不可放入,接下來放入其余的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,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>使用遍歷算法策略所得到的解的總價(jià)值是_____。<A>8<B>15<C>14<D>13答案：B解釋：本題考查問題及其數(shù)學(xué)建模的作用用遍歷算法策略,狀態(tài)轉(zhuǎn)移方程：f[v]=max{f[v],f[v-c[i]]+w[i]},即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值,第i件物品的重量是c[i],價(jià)值是w[i]。"將前i件物品放入容量為v的背包中"這個(gè)子問題,若只考慮第i件物品的策略〔放或不放,那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問題。如果不放第i件物品,那么問題就轉(zhuǎn)化為"前i-1件物品放入容量為v的背包中",價(jià)值為f[i-1][v]；如果放第i件物品,那么問題就轉(zhuǎn)化為"前i-1件物品放入剩下的容量為v-c[i]的背包中",此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價(jià)值w[i]。按此方法,可得總價(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é)模型_____。<A>問題的目標(biāo)函數(shù)是；<B>問題的目標(biāo)函數(shù)是；<C>問題解所應(yīng)滿足的約束是；<D>問題解所應(yīng)滿足的約束是；<E>前述<A>和<C>；答案：E解釋：本題考查問題及其數(shù)學(xué)建模的作用該問題有兩個(gè)條件：1物品不能超過背包所能承受的重量,即〔C選項(xiàng)：2背包內(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,回答下列問題。<1>關(guān)于TSP問題的遍歷算法和貪心算法,下列說法正確的是_____。<A>對(duì)TSP問題而言,遍歷算法和貪心算法求得的解是一樣的,所不同的是貪心算法更快一些,而遍歷算法更慢一些；<B>對(duì)TSP問題而言,遍歷算法和貪心算法求得的解是一樣的,所不同的是遍歷算法更快一些,而貪心算法更慢一些；<C>對(duì)TSP問題而言,遍歷算法和貪心算法求得的解是不一樣的,貪心算法是求近似解,執(zhí)行更快一些,而遍歷算法是求精確解,執(zhí)行更慢一些；<D>對(duì)TSP問題而言,遍歷算法和貪心算法求得的解是不一樣的,貪心算法是求精確解,執(zhí)行更快一些,而遍歷算法是求近似解,執(zhí)行更慢一些；答案：C解釋：本題考查對(duì)貪心算法與遍歷算法的簡(jiǎn)單理解貪心算法：一定要做當(dāng)前情況下的最好選擇,否則將來可能會(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)組合爆炸。故,相比之下,貪心算法的計(jì)算速度更快。所以<C>選項(xiàng)是正確的。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<2>關(guān)于TSP,下列說法不正確的是_____。<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)行比較的思想,即是所謂的遍歷算法策略,它僅僅對(duì)n值很小的TSP問題是能行的。答案：C解釋：本題考查對(duì)TSP組合優(yōu)化問題的理解對(duì)所有組合進(jìn)行比較的思想,即所謂的遍歷算法策略,其組合數(shù)目為n!。2001年解決了德國(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的貪心算法的求解思想,下列說法不正確的是_____。<A>無需對(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看來是最優(yōu)的>組合起來的路徑,該路徑從全局角度也一定是最優(yōu)的；<D>對(duì)一個(gè)具體的TSP問題,每次執(zhí)行貪心算法,所求得的最終解可能是不同的。答案：C解釋：本題考查對(duì)TSP貪心算法的理解〔A<B>選項(xiàng)都是對(duì)貪心算法的描述,貪心算法的核心就是：只考慮當(dāng)前情況下得最優(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)問題<梵天塔問題或者說漢諾塔問題>；<C>n座橋,走過每座橋且僅走過一次的問題<圖的遍歷問題>；<D>上述<A><B><C>都可以。答案：A解釋：本題考查對(duì)TSP問題抽象的理解求解TSP問題采用的是貪心算法。<A>選項(xiàng)所描述的問題其實(shí)就是TSP問題?！睟選項(xiàng)所描述的問題是梵天塔問題,應(yīng)該采用的是遞歸的思想?！睠選項(xiàng)所描述的圖的遍歷問題,主要有深度優(yōu)先搜索,和廣度優(yōu)先搜索兩種解決方法,不是貪心算法。綜上,〔A選項(xiàng)正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<5>關(guān)于下列四個(gè)數(shù)學(xué)抽象,說法正確的是_____。<數(shù)學(xué)抽象I>城市記為：V={v1,v2,…,vn},任意兩個(gè)城市vi,vj∈V之間的距離記為：dvivj,問題的解是尋找所有城市的一個(gè)訪問順序T={t1,t2,<數(shù)學(xué)抽象II>電路元件記為：V={v1,v2,…,vn},任意兩個(gè)元件vi,vj∈V之間的距離記為：dvivj,問題的解是尋找所有元件之間的一個(gè)訪問順序T={t1,t2,<數(shù)學(xué)抽象III>圖的結(jié)點(diǎn)記為：V={v1,v2,…,vn},任意兩個(gè)結(jié)點(diǎn)vi,vj∈V的邊的權(quán)值記為：dvivj,問題的解是尋找所有結(jié)點(diǎn)之間的一個(gè)訪問順序T={t1,t2,<數(shù)學(xué)抽象IV>圖的結(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,使得minmini=1ndtiti+1,這里假定除tn+1=t1外,<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>上述說法都不正確。答案：C解釋：本題考查對(duì)TSP問題抽象的理解I就是對(duì)最原始的TSP問題的抽象描述。II也是對(duì)TSP問題的描述,只是將城市換成了電子元件。III和IV是對(duì)同一問題的不同表述罷了,都是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),下列說法不正確的是_____。<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é),便于算法按邏輯語(yǔ)義通過操控該名字來操控該數(shù)據(jù)結(jié)構(gòu)； <D>數(shù)據(jù)結(jié)構(gòu)包含了數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其操作； <E>上述說法有不正確的。答案：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>的說法都沒有問題。所以〔E是不正確的。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<2>關(guān)于數(shù)據(jù)結(jié)構(gòu),下列說法不正確的是______________？<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ì)位置來表示數(shù)據(jù)元素的邏輯關(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)的理解數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其操作的總稱?！睞正確。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也就是在反映數(shù)據(jù)邏輯關(guān)系的原則下,數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方式?！睟正確。向量確實(shí)是使用順序存儲(chǔ)結(jié)構(gòu),并且借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(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)之靈魂"與第七章課件。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ù)組的不同的元素。如下圖所示：<1>關(guān)于數(shù)組和存儲(chǔ)器,下列說法不正確的是_____。<A>和存儲(chǔ)器一樣,數(shù)組是按線性方式組織數(shù)據(jù)； <B>和存儲(chǔ)器一樣,一維數(shù)組是按線性方式組織數(shù)據(jù),一個(gè)數(shù)據(jù)元素需要一個(gè)存儲(chǔ)單元來存儲(chǔ),一個(gè)下標(biāo)即相當(dāng)于一個(gè)存儲(chǔ)單元的地址； <C>和存儲(chǔ)器一樣,一維數(shù)組是按線性方式組織數(shù)據(jù),一個(gè)數(shù)據(jù)元素需要一個(gè)或多個(gè)存儲(chǔ)單元來存儲(chǔ),一個(gè)下標(biāo)即相當(dāng)于一個(gè)存儲(chǔ)單元的地址；<D>和存儲(chǔ)器一樣,一維數(shù)組是按線性方式組織數(shù)據(jù),一個(gè)數(shù)據(jù)元素需要一個(gè)或多個(gè)存儲(chǔ)單元來存儲(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>的說法不準(zhǔn)確。其余說法都對(duì)。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<2>請(qǐng)對(duì)照上圖的左子圖和右子圖來觀察,右子圖的二維數(shù)組是按左圖的形式存儲(chǔ)在存儲(chǔ)器中。則D[4][2]元素所對(duì)應(yīng)的存儲(chǔ)單元的存儲(chǔ)地址為_____。<A>0000000000000101； <B>0000000000001000； <C>0000000000001010；<D>上述都不正確；答案：B解釋：本題考查對(duì)存儲(chǔ)器和數(shù)組的理解。圖中,二維數(shù)組中,D[4][2]對(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)參照上圖的左子圖和右子圖來觀察,右子圖的二維數(shù)組是按左圖的形式存儲(chǔ)在存儲(chǔ)器中。則D[i][j]元素,與對(duì)應(yīng)存儲(chǔ)單元的存儲(chǔ)地址的轉(zhuǎn)換關(guān)系正確的為_____。<A>D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+<<i-1>*每行的列數(shù)+j-1>*單一元素占用存儲(chǔ)單元的數(shù)目； <B>D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+<i-1>*每行的列數(shù)+j-1；此公式在任何情況下都正確； <C>D[i][j]元素的存儲(chǔ)地址=數(shù)組的起始地址+<<j-1>*每行的列數(shù)+i-1>*單一元素占用存儲(chǔ)單元的數(shù)目；<D>D[i][j]元素的存儲(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ù)組的起始地址,便可得到所求元素的地址?！睞正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。7."樹"是一種典型的數(shù)據(jù)結(jié)構(gòu),在很多算法中都應(yīng)用樹來組織相關(guān)的數(shù)據(jù)。樹是組織層次型數(shù)據(jù)的一種存儲(chǔ)結(jié)構(gòu),它將每一個(gè)數(shù)據(jù)稱為一個(gè)數(shù)據(jù)元素。見下圖I.示意,采用三個(gè)數(shù)組來存儲(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.,回答下列問題。圖I.<1>關(guān)于"樹"這種數(shù)據(jù)結(jié)構(gòu),下列說法不正確的是_____。<A>"樹"既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù),還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系；<B>"樹"可以采用兩個(gè)數(shù)組來組織樹型數(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解釋：本題考查對(duì)樹結(jié)構(gòu)的理解。"樹"既需要存儲(chǔ)數(shù)據(jù)元素本身即數(shù)據(jù),還需要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系?！睞的說法沒有問題。用兩個(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),通過指針來指向其兒子。故〔B〔C〔D正確?！睧不正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<2>參照上圖<I>,下列說法不正確的是_____。<A>當(dāng)數(shù)據(jù)元素不發(fā)生變化,而只是數(shù)據(jù)元素之間的關(guān)系發(fā)生變化時(shí),可以通過調(diào)整數(shù)據(jù)元素對(duì)應(yīng)的左指針數(shù)組或右指針數(shù)組中的值來完成；<B>當(dāng)數(shù)據(jù)元素不發(fā)生變化,而只是數(shù)據(jù)元素之間的關(guān)系發(fā)生變化時(shí),既需要調(diào)整數(shù)據(jù)元素本身,又需要調(diào)整其對(duì)應(yīng)的左指針數(shù)組或右指針數(shù)組中的值來完成； <C>相同的數(shù)據(jù)元素,不同的左指針和右指針可以反映數(shù)據(jù)元素之間不同的關(guān)系； <D>圖<a>說明,一個(gè)數(shù)據(jù)元素最多只能有兩個(gè)子元素,一個(gè)是左子元素,一個(gè)是右子元素； <E>上述說法有不正確的。答案：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ò)誤。其余說法均正確。詳細(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ì)樹結(jié)構(gòu)的理解。第一個(gè)元素值為100。其左指針指向的存儲(chǔ)單元的內(nèi)容為地址：0000000000000010。該地址存儲(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)系,操作正確的是_____。圖III.<A>將0000000000001000號(hào)存儲(chǔ)單元的值修改0000000001101110<即十進(jìn)制的110>；<B>將0000000000011010號(hào)存儲(chǔ)單元的值修改為0000000000000111； <C>將0000000000010001號(hào)存儲(chǔ)單元的值修改為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元素的左兒子為空。這是〔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)容卻是不正確的。不正確的是_____。圖IV.<A>將0000000000001000號(hào)存儲(chǔ)單元的值修改為0000000001010101；<B>將0000000000010010號(hào)存儲(chǔ)單元的值修改為0000000000000010； <C>將0000000000011010號(hào)存儲(chǔ)單元的值修改為0000000000000000<即Null>； <D>將0000000000001010號(hào)存儲(chǔ)單元的值修改為0000000000001000；答案：B解釋：本題考查對(duì)樹結(jié)構(gòu)的理解。 <A>的操作是在存儲(chǔ)表中增加85這個(gè)元素?！睠的操作是將85的右兒子設(shè)為NULL?！睤的操作是將100的左指針指向85元素的地址?！睟是對(duì)0000000000010010地址進(jìn)行操作。而改地址在整個(gè)過程中,通過其它選項(xiàng)來看,不會(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)的說法,不正確的是_____。<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)先出?！睞不正確,〔B正確。堆?？梢允鬼樞虼鎯?chǔ)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來實(shí)現(xiàn)。〔C〔D正確。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。<2>有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算,說法不正確的是_____。<A>推入是將數(shù)據(jù)放入堆棧的頂端,堆棧頂端指針top加一；<B>彈出是將堆棧頂端的數(shù)據(jù)取出,堆棧頂端指針top減一；<C>如果堆棧頂端指針top為0,則堆棧為空；<D>如果是固定長(zhǎng)度的堆棧,當(dāng)堆棧頂端指針top與長(zhǎng)度相等時(shí),堆棧是滿的。<E>上述說法有不正確的；答案：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)度,則堆棧是滿的?！睠<D>均正確。故〔E的說法不正確。詳細(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)參考第七章視頻"算法,程序與計(jì)算系統(tǒng)之靈魂"與第七章課件。9.程序流程圖是表達(dá)算法控制結(jié)構(gòu)或者說算法步驟的重要方法?；卮鹣铝袉栴}：<1>觀察下圖I.,沒有錯(cuò)誤的流程圖為_________。圖I.<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)該用菱形判斷,所以流程圖<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ò)誤。詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<II>"與第七章課件。<2>觀察下圖II.,該流程圖中存在錯(cuò)誤,下列說法最完整準(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解釋：本題考查流程圖的知識(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ī)則或語(yǔ)句",所以該圖中不止AB兩個(gè)錯(cuò)誤,正確答案選D；詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<II>"與第七章課件。10.閱讀下列算法,回答：Startofthealgorithm<算法開始><1>輸入N的值；<2>設(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é)果。Endofthealgorithm<算法結(jié)束>上述算法_________。 <A>能夠正確地計(jì)算sum=1+2+3+4+…+N； <B>不能正確地計(jì)算sum=1+2+3+4+…+N；答案：B解釋：本題考查步驟描述法；在上述步驟中,主要欠缺的是程序的初始化,雖然有將i的初始值設(shè)為1,但sum的初始值確忽略了,這樣,沒辦法正確計(jì)算sum=1+2+3….+N,應(yīng)該把sum初始值設(shè)為0；詳細(xì)內(nèi)容請(qǐng)參考第七章視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<II>"與第七章課件。11.閱讀下列算法,回答：Startofthealgorithm<算法開始><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é)果。Endofthealgorithm<算法結(jié)束>算法執(zhí)行的結(jié)果為_________。 <A>24；<B>26；<C>55；<D>45；<E>46；答案：B解釋：本題考查步驟敘述法；由題意,可畫出如圖所示的流程圖：所以,當(dāng)i為奇數(shù)時(shí),sum=sum+i；i=3,sum=5；i=5,sum=10；i=7,sum=17；i=9,sum=26；綜上所述,結(jié)果為26,選B；具體內(nèi)容請(qǐng)參考課堂視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<III>"和第七章課件；12.TSP算法流程圖如下圖I.示意,回答下列問題：圖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)容請(qǐng)參考課堂視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<III>"和第七章課件；<2>中層循環(huán)<K變量控制的循環(huán)>的作用是_________。<A>用于判斷某個(gè)城市是否是已訪問過的城市；<B>用于尋找距當(dāng)前城市距離最近的城市；<C>用于完整地產(chǎn)生一個(gè)路徑；<D>上述都不是；答案：B解釋：本題考查學(xué)生是否能讀懂流程圖以及TSP流程；圖中中層循環(huán),K從第2個(gè)城市至第N個(gè)城市循環(huán),判斷D[K,S[I-1]]是否是最小值,j記錄了最小距離的城市號(hào)K；所以,正確答案選B；具體內(nèi)容請(qǐng)參考課堂視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<III>"和第七章課件；<3>外層循環(huán)<I變量控制的循環(huán)>的作用是_________。<A>用于判斷某個(gè)城市是否是已訪問過的城市；<B>用于尋找距當(dāng)前城市距離最近的城市；<C>用于完整地產(chǎn)生一個(gè)路徑；<D>上述都不是；答案：C解釋：本題考查學(xué)生是否能讀懂流程圖以及TSP流程；圖中外層循環(huán),I從2至N循環(huán)；I-1個(gè)城市已訪問過,正在找與第I-1個(gè)城市最近距離的城市；已訪問過的城市號(hào)存儲(chǔ)在S[]中；所以,正確答案選C；具體內(nèi)容請(qǐng)參考課堂視頻"算法設(shè)計(jì)算法思想的精確表達(dá)<III>"和第七章課件；13.一般而言,算法設(shè)計(jì)完成后,需要進(jìn)行算法的模擬與分析。關(guān)于算法的模擬與分析回答下列問題：<1>通常從哪些方面,進(jìn)行算法的模擬與分析？_________。<A>算法的正確性問題,即一個(gè)算法求得的解是滿足問題約束的正確的解嗎？<B>算法的效果評(píng)價(jià)問題,即算法輸出的是最優(yōu)解還是可行解,其可行解與最優(yōu)解的偏差有多大？<C>算法的時(shí)間效率問題<時(shí)間復(fù)雜性>,即算法執(zhí)行所需要的時(shí)間是多少？<D>算法的空間效率問題<空間復(fù)雜性>,即算法執(zhí)性所需要的空間是多少？ <E>上述全部。答案：E解釋：本題考查算法分析和算法復(fù)雜性；當(dāng)對(duì)一個(gè)算法進(jìn)行模擬與分析時(shí),有以下幾個(gè)方面要判斷：〔1問題求解的過程、方法——算法是正確的嗎？算法的輸出是問題的解嗎？〔2算法的輸出是最優(yōu)解還是可行解？如果是可行解,與最優(yōu)解的偏差多大？〔3算法獲得結(jié)果的時(shí)間有多長(zhǎng)?即分為時(shí)間復(fù)雜性和空間復(fù)雜性；所以,答案應(yīng)選E；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<2>算法的時(shí)間復(fù)雜性,可以表達(dá)為關(guān)于問題規(guī)模n的一個(gè)函數(shù)T<n>,T<n>可以用大O表示法來處理。問T<n>=O<f<n>>是什么意思？正確的是_________。<A>T<n>是關(guān)于f<n>的一個(gè)函數(shù)；<B>T<n>是與f<n>同數(shù)量級(jí)的函數(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ù)。"O"表示量級(jí)<order>,允許使用"="代替"≈",如n2+n+1=Ο<n2>,所以正確答案選B；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<3>算法的時(shí)間復(fù)雜性T<n>,可以通過計(jì)算算法基本語(yǔ)句的執(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á)正確的是_________。<A>O<n>；<B>O<1>；<C>O<n2>；<D>O<n!>；答案：B解釋：本題考查時(shí)間復(fù)雜性,和大"O"記法；具體分析如下：K=0； 1次I=2；1次While<I<=8>8次{K=K+I；8次I=I+2；8次} T<n>=1+1+8×3=O<1>,所以答案選B；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<4>算法的時(shí)間復(fù)雜性T<n>,可以通過計(jì)算算法基本語(yǔ)句的執(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á)正確的是_________。<A>O<n>；<B>O<n2>；<C>O<n3>；<D>上述都不對(duì)；答案：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>=2n3+n2+n+1=O<n3>,所以正確答案選C；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<5>算法的時(shí)間復(fù)雜性T<n>,可以通過計(jì)算算法基本語(yǔ)句的執(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<=5;k++><50> sum=sum+1；該程序時(shí)間復(fù)雜性表達(dá)正確的是_________。<A>O<n>；<B>O<n2>；<C>O<n3>；<D>上述都不對(duì)；答案：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++>5n2次<50> sum=sum+1；5n2次T<n>=11n2+n+1=O<n2>,所以正確答案選B；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<6>閱讀下面的程序,其時(shí)間復(fù)雜度為_________?A.O<1>B.O<n>C.O<n2>D.O<n*logn>intindex=5;intcondition=1;if<condition==1>thenindex++;elseindex--；fori=1to100forj=1to200index=index+2;答案：A解釋：本題考查時(shí)間復(fù)雜性,和大"O"記法；具體分析如下：intindex=5;1次intcondition=1;1次if<condition==1>then1次 index++;1次else index--；fori=1to100100次forj=1to200200×100次 index=index+2;200×100次 所以T<n>=O<1>,正確答案選A；具體內(nèi)容請(qǐng)參考課堂視頻"高級(jí)問題初探:算法分析與計(jì)算復(fù)雜性"和第七章課件；<7>為什么要評(píng)估算法的復(fù)雜性？下列說法不正確的是_________。<A>當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為多項(xiàng)式函數(shù)時(shí),計(jì)算機(jī)是能夠完成計(jì)算的；<B>當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為非多項(xiàng)式函數(shù)時(shí),如指數(shù)函數(shù)、階乘函數(shù)時(shí),計(jì)算機(jī)是不能夠完成計(jì)算的；<C>當(dāng)算法的時(shí)間復(fù)雜性量級(jí)為非多項(xiàng)式函數(shù)時(shí),如指數(shù)函數(shù)、階乘函數(shù)時(shí),對(duì)于大規(guī)