2020智慧樹(shù)知到《算法分析與設(shè)計(jì)》章節(jié)測(cè)試完整答案

答案：錯(cuò)答案：對(duì)答案：對(duì)答案：錯(cuò)5、算法與程序的區(qū)別是()B:輸出C:確定性D:有窮性A:如果一個(gè)算法能應(yīng)用于問(wèn)題的任意實(shí)例，并保證得到正確解D:算法是一個(gè)過(guò)程，計(jì)算機(jī)每次求解是針對(duì)問(wèn)題的一個(gè)實(shí)例求A:最大團(tuán)10、給定兩張喜歡列表，穩(wěn)定匹配問(wèn)題的輸出是()。C:最大匹配11、問(wèn)題變換的目的有()。(1)復(fù)雜變隱式變顯式(4)難解變易解(5)以上都是。12、按照霍納法則，計(jì)算p(x)=anxn+3、如果對(duì)于X的任意實(shí)例，通過(guò)多項(xiàng)式次的計(jì)算步驟，加多項(xiàng)式次調(diào)用Y的算法，可解決X,則X可多項(xiàng)式時(shí)間歸約到Y(jié)。5、下面關(guān)于NP問(wèn)題說(shuō)法正確的是()B:P類(lèi)問(wèn)題包含在NP類(lèi)問(wèn)題中6、P類(lèi)問(wèn)題可以()。A:多項(xiàng)式時(shí)間計(jì)算7、下面屬于NP完全問(wèn)題的是()D:旅行商問(wèn)題A:IfX多項(xiàng)式時(shí)間歸約到Y(jié)andY多項(xiàng)式時(shí)間歸約到Z,thenX多項(xiàng)式時(shí)間歸約到Z.5、從資源劃分，算法的復(fù)雜度分為()和()。A:時(shí)間復(fù)雜度空間復(fù)雜度B:空間復(fù)雜度平均復(fù)雜度C:最好復(fù)雜度最壞復(fù)雜度D:時(shí)間復(fù)雜度平均復(fù)雜度答案：時(shí)間復(fù)雜度空間復(fù)雜度6、算法復(fù)雜度分析的兩種基本方法為()和()。A:結(jié)構(gòu)化方法面向?qū)ο蠓椒˙:事后統(tǒng)計(jì)事前分析C:幾何復(fù)雜度平均復(fù)雜度D:平攤復(fù)雜度平滑復(fù)雜度答案：事后統(tǒng)計(jì)事前分析第三章1、0-1背包問(wèn)題的枚舉算法的時(shí)間復(fù)雜度為0(2n)3、分塊查找一般設(shè)分塊的長(zhǎng)度是n/2.C:二進(jìn)制法6、從所有候選答案中去搜索正確的解，這是()算法。A:蠻力B:枚舉C:遞推行，1年可以計(jì)算的問(wèn)題規(guī)模估計(jì)是?C:優(yōu)化數(shù)據(jù)結(jié)構(gòu)10、下面那些算法的時(shí)間復(fù)雜度為0()?D:冒泡排序2、貪心選擇通過(guò)一步步選擇得到問(wèn)題的解3、問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心4、如果圖G中每條邊的權(quán)重都是互不相同的，圖G必定只有一6、貪心算法基本要素有()和最優(yōu)子結(jié)構(gòu)性質(zhì)。A:分解合并性質(zhì)B:獨(dú)立子問(wèn)題性質(zhì)A:領(lǐng)先B:優(yōu)化C:交換論證第五章B:正推C:倒推D:迭代A:差消迭代C:直接迭代A:邊界條件B:遞歸方程C:迭代D:輸入B:遞推C:尾遞歸D:循環(huán)D:迭代問(wèn)題10、主方法可以求解滿(mǎn)足T(n)=aT(n/b)+f(n)形式的遞推方B:對(duì)于系數(shù)b,必須滿(mǎn)足b>1C:若對(duì)于常數(shù)ε>0,f(n)=0(y),則T(n)=Θ(x)般為2)5、設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用()法。B:快速排序6、堆排序的時(shí)間復(fù)雜度是0()。7、以下不可以使用分治法求解的是()。8、改進(jìn)分治算法的方法有()和改進(jìn)劃分的對(duì)稱(chēng)性。A:減少子問(wèn)題數(shù)B:備忘錄C:擬陣原理A:分解B:解決C:合并D:選擇1、動(dòng)態(tài)規(guī)劃算法把原問(wèn)題分為交叉的子問(wèn)題2、0/1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法是多項(xiàng)式時(shí)間算3、對(duì)于稀疏圖，F(xiàn)loyd算法的效率要高于執(zhí)行n次DijksA:動(dòng)態(tài)規(guī)劃B:貪心算法C:分治算法6、動(dòng)態(tài)規(guī)劃算法的基本要素有()和最優(yōu)子結(jié)構(gòu)性質(zhì)。A:多重選擇B:增加變量3、回溯法的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空2、分支限界法找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條4、優(yōu)先隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則，選取下一5、下列算法中不能解決0/1背包問(wèn)題的是B:動(dòng)態(tài)規(guī)劃C:回溯法B:排列樹(shù)A:先進(jìn)先出B:后進(jìn)先出C:結(jié)點(diǎn)的優(yōu)先級(jí)D:隨機(jī)C:對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同D:存儲(chǔ)空間的要求不同B:分支限界C:動(dòng)態(tài)規(guī)劃D:貪心算法3、存在割(A,B)使流值v(f)=割的容量cap(A,B).,則割4、給定連通圖G,BFS遍歷得到層次圖，邊相連，則G是二分圖。7、如果每條邊的最大容量為1,則時(shí)間復(fù)雜度是0(nm)的網(wǎng)絡(luò)流A:FF算法B:容量縮放算法A:最大獨(dú)立數(shù)9、改進(jìn)FF網(wǎng)絡(luò)流算法，可以通過(guò)選擇()增廣路，降低時(shí)間復(fù)A:最大容量D:邊數(shù)最少10、帶需求的流通必須滿(mǎn)足供給和=需求和3、借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法，僅對(duì)其輸4、隨機(jī)算法共同點(diǎn)是計(jì)算時(shí)間越多或運(yùn)行次數(shù)越多，正確性越高.B:拉斯維加斯算法C:舍伍德算法B:拉斯維加斯算法8、在一般輸入數(shù)據(jù)的程序里，輸入多少會(huì)影響到算法的計(jì)算復(fù)雜度，為了消除這種影響可用()對(duì)輸入進(jìn)行預(yù)處理。B:拉斯維加斯算法9、()肯定獲得最優(yōu)解。B:貪心算法C:隨機(jī)算法1、給定問(wèn)題p,若有算法A,存在一個(gè)常數(shù)K>=0,使得問(wèn)題4、絕大多數(shù)NP-hard問(wèn)題存在多項(xiàng)式時(shí)間絕對(duì)近似算法5、若P不等于NP,則最大獨(dú)立集問(wèn)題存在多項(xiàng)式時(shí)間絕6、最大優(yōu)化問(wèn)題的近似性能比小于1,越接近1越說(shuō)明算法好7、多項(xiàng)式時(shí)間近似方案的近似性能比是1+q,q>0.8、多項(xiàng)式時(shí)間近似方案的時(shí)間復(fù)雜度是P(n,1/q),