在線網(wǎng)課知道智慧《算法設(shè)計(jì)與分析（山盟-山東交通學(xué)院）》單元測試考核答案

第一章單元測試1【單選題】(2分)解決一個(gè)問題通常有多種方法。若說一個(gè)算法“有效”是指()A.（這個(gè)算法能在一定的時(shí)間和空間資源限制內(nèi)將問題解決）和（這個(gè)算法比其他已知算法都更快地將問題解決）B.這個(gè)算法比其他已知算法都更快地將問題解決C.這個(gè)算法能在人的反應(yīng)時(shí)間內(nèi)將問題解決D.這個(gè)算法能在一定的時(shí)間和空間資源限制內(nèi)將問題解決2【單選題】(2分)農(nóng)夫帶著狼、羊、白菜從河的左岸到河的右岸，農(nóng)夫每次只能帶一樣?xùn)|西過河，而且，沒有農(nóng)夫看管，狼會(huì)吃羊，羊會(huì)吃白菜。請(qǐng)問農(nóng)夫能不能過去？（）A.不一定B.不能過去C.能過去3【單選題】(2分)下述（）不是是算法的描述方式。A.E-R圖B.自然語言C.程序設(shè)計(jì)語言D.偽代碼4【單選題】(2分)有一個(gè)國家只有6元和7元兩種紙幣，如果你是央行行長，你會(huì)設(shè)置（）為自動(dòng)取款機(jī)的取款最低限額。A.30B.42C.40D.295【判斷題】算法是一系列解決問題的明確指令。（）A.對(duì)B.錯(cuò)6【判斷題】程序=數(shù)據(jù)結(jié)構(gòu)+算法（）A.對(duì)B.錯(cuò)7【判斷題】同一個(gè)問題可以用不同的算法解決，同一個(gè)算法也可以解決不同的問題。（）A.錯(cuò)B.對(duì)8【判斷題】算法中的每一條指令不需有確切的含義，對(duì)于相同的輸入不一定得到相同的輸出。()A.錯(cuò)B.對(duì)9【判斷題】可以用同樣的方法證明算法的正確性與錯(cuò)誤性()A.錯(cuò)B.對(duì)10【判斷題】求解2個(gè)數(shù)的最大公約數(shù)至少有3種方法。()A.對(duì)B.錯(cuò)11【判斷題】沒有好的算法，就編不出好的程序。（）A.對(duì)B.錯(cuò)12【判斷題】算法與程序沒有關(guān)系。()A.對(duì)B.錯(cuò)13【判斷題】我將來不進(jìn)行軟件開發(fā)，所以學(xué)習(xí)算法沒什么用。()A.錯(cuò)B.對(duì)14【判斷題】gcd(m,n)=gcd(n,mmodn)并不是對(duì)每一對(duì)正整數(shù)(m,n)都成立。()A.錯(cuò)B.對(duì)15【判斷題】既然程序設(shè)計(jì)語言可以描述算法，所以算法就是程序。()A.錯(cuò)B.對(duì)第二章單元測試1【判斷題】并不是所有的算法，規(guī)模更大的輸入需要更長的運(yùn)行時(shí)間。()A.錯(cuò)B.對(duì)2【判斷題】算法效率分析框架主要關(guān)心一個(gè)算法的基本操作次數(shù)的增長次數(shù)，并把它作為算法效率的主要指標(biāo)。()A.錯(cuò)B.對(duì)3【判斷題】當(dāng)算法由兩個(gè)連續(xù)執(zhí)行部分組成時(shí)，該算法的整體效率等于較大增長次數(shù)＋較小增長次數(shù)。()A.錯(cuò)B.對(duì)4【判斷題】O表示算法效率的下界。()A.對(duì)B.錯(cuò)5【單選題】(2分)4個(gè)盤子的漢諾塔，至少要執(zhí)行移動(dòng)操作的次數(shù)為()。A.17次B.11次C.13次D.15次6【單選題】(2分)Fibonacci數(shù)列的第8項(xiàng)為()。A.3B.21C.34D.137【單選題】(2分)若f(n)=+4n+2，則有f(n)∈（）A.O()B.O(n)C.O(1)D.O()第三章單元測試1【單選題】(2分)以下哪種排序用的是蠻力法？()A.合并排序B.計(jì)數(shù)排序C.拓?fù)渑判駾.冒泡排序2【單選題】(2分)集合｛Ａ，Ｂ｝的冪集合為()。A.{｛Ａ，Ｂ｝，｛Ａ｝，｛Ｂ｝，Φ}B.｛Ａ｝，｛Ｂ｝，ΦC.{｛Ａ｝，｛Ｂ｝}D.｛Ａ｝，｛Ｂ｝3【單選題】(2分)可以用（）求得一個(gè)圖的連通分量。A.拓?fù)渑判駼.回溯C.分支界限D(zhuǎn).深度優(yōu)先查找4【判斷題】蠻力法是一種簡單直接地解決問題的方法。()A.對(duì)B.錯(cuò)5【判斷題】對(duì)于同樣的輸入，選擇排序和冒泡排序比較的次數(shù)是一樣的。()A.對(duì)B.錯(cuò)6【判斷題】蠻力字符串匹配算法將文本中的字符從右向左比較不會(huì)比從左向右比較更有優(yōu)勢(shì)。()A.錯(cuò)B.對(duì)7【判斷題】最近對(duì)問題的輸入規(guī)模為集合中點(diǎn)的個(gè)數(shù)n，基本操作是計(jì)算歐幾里得距離，該問題的蠻力算法的時(shí)間復(fù)雜度除依賴于n外，還依賴于輸入。()A.對(duì)B.錯(cuò)8【判斷題】如果S是凸的，它的凸包是它本身。()A.錯(cuò)B.對(duì)9【判斷題】一根直線將平面分成兩個(gè)半平面，其中一個(gè)半平面中的點(diǎn)都滿足：ax+by≥c，而另一個(gè)半平面的點(diǎn)都滿足：ax+by≥c。()A.錯(cuò)B.對(duì)10【判斷題】蠻力法生成整數(shù)1,2,…,n的全部排列的算法時(shí)間復(fù)雜度為O(n!)。()A.錯(cuò)B.對(duì)第四章單元測試1【判斷題】減治法的減常量形式中，每次迭代總是從實(shí)例中減去相同的常量。但是這個(gè)常量并不固定，減多少無跡可尋。()A.錯(cuò)B.對(duì)2【判斷題】減治法的減常因子技術(shù)意味著在算法的每次迭代中，總是從實(shí)例的規(guī)模中減去一個(gè)相同的常數(shù)因子，在大多數(shù)應(yīng)用中，這個(gè)常數(shù)因子等于1。()A.對(duì)B.錯(cuò)3【判斷題】插入排序的比較和移動(dòng)次數(shù)不只依賴于輸入規(guī)模，還依賴于特定輸入。()A.對(duì)B.錯(cuò)4【判斷題】插入排序和拓?fù)渑判蚨紝儆跍p治法的減常量形式。()A.錯(cuò)B.對(duì)5【判斷題】執(zhí)行一次DFS遍歷，并記住頂點(diǎn)變成死端(即退出遍歷棧)的順序。該次序就是拓?fù)渑判蛞粋€(gè)解。()A.錯(cuò)B.對(duì)6【單選題】(2分)求n個(gè)數(shù)的最小值至少需要（）次比較A.n-2B.n+1C.n-1D.n7【單選題】(2分)有9只杯口向上的杯子放在桌子上，每次將其中四只杯子同時(shí)“翻轉(zhuǎn)”，使其杯口向下，經(jīng)過()次“翻轉(zhuǎn)”后，使9只杯口全部向下？A.都不對(duì)B.8C.10D.98【單選題】(2分)下列()不是對(duì)數(shù)據(jù)表{26，99，20，45，15，29，65，35，20，72}用冒泡法進(jìn)行排序的中間結(jié)果。A.15202629203545657299B.20261529456520357299C.20152629352045657299D.262045152965352072999【單選題】(2分)5門必修課的一個(gè)集合{C1,C2,C3,C4,C5}，一個(gè)在職學(xué)生必須在某個(gè)階段修完這幾門課程?？梢园凑杖魏未涡?qū)W習(xí)這些課程，只要滿足下面的先決條件：C1和C2沒有任何先決條件，修完C1和C2才能修C3，修完C3才能修C4，而修完C3和C4才能修C5，這個(gè)學(xué)生每個(gè)學(xué)期只能修一門課程，該學(xué)生不能按照()順序?qū)W習(xí)這門課程。A.（C1C2C3C4C5）和（C2C1C3C4C5）B.C2C1C3C4C5C.C2C3C4C5C1D.C1C2C3C4C5第五章單元測試1【單選題】(2分)兩個(gè)十進(jìn)制n位數(shù)的積最少能擁有()位數(shù)。A.2n-1B.n-1C.2n-2D.n2【單選題】(2分)快速排序算法是利用()的算法。A.回溯法B.貪心法C.動(dòng)態(tài)規(guī)劃法D.分治法3【單選題】(2分)以下不可以使用分治法求解的是（）A.查找問題B.最近對(duì)問題C.0/1背包問題D.排序問題4【單選題】(2分)Strassen矩陣乘法是利用（）實(shí)現(xiàn)的算法A.分治法B.動(dòng)態(tài)規(guī)劃法C.回溯法D.貪心法5【單選題】(2分)用分治法解決最近點(diǎn)對(duì)問題的時(shí)間復(fù)雜度為（）A.O(logn)B.O(n)C.O()D.O(nlogn)6【單選題】(2分)快速排序是穩(wěn)定的嗎？()A.不是B.不一定C.是7【判斷題】合并排序是一個(gè)穩(wěn)定的排序算法。（）A.錯(cuò)B.對(duì)8【判斷題】對(duì)二叉搜索樹進(jìn)行前序遍歷即可得到一個(gè)有序數(shù)列。（）A.錯(cuò)B.對(duì)9【判斷題】在分治法中，將一個(gè)問題劃分為同一類型的若干子問題，子問題最好規(guī)模相同。（）A.對(duì)B.錯(cuò)10【判斷題】應(yīng)用分治法的兩個(gè)前提是問題的可分解性和解的復(fù)雜性。（）A.對(duì)B.錯(cuò)11【判斷題】能否利用分治法完全取決于該問題分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。（）A.對(duì)B.錯(cuò)12【判斷題】對(duì)于分治法，子問題只能細(xì)分一次，不能繼續(xù)細(xì)分。（）A.錯(cuò)B.對(duì)13【單選題】(2分)一個(gè)嚴(yán)格遞增的數(shù)組是快速排序的()。A.最優(yōu)輸入B.都不是C.最差輸入第六章單元測試1【單選題】(2分)１、對(duì)數(shù)組中的元素先進(jìn)行合并排序，再檢查連續(xù)元素來檢驗(yàn)數(shù)組中元素的唯一性，直到找到兩個(gè)相等的元素或所有相鄰的元素都檢查一遍為止。該算法的復(fù)雜性是（）。A.O()B.O(2n)C.O（nlogn）D.O(logn)2【單選題】(2分)AVL樹的旋轉(zhuǎn)中，存在()種旋轉(zhuǎn).A.右左雙轉(zhuǎn)B.右單轉(zhuǎn)C.其他選項(xiàng)都對(duì)D.左單轉(zhuǎn)3【單選題】(2分)有3對(duì)夫妻過河，但是只有一條能容納兩人的小船，這3對(duì)夫妻中，丈夫愛吃醋，妻子不在自己身邊時(shí)，不允許有其他男人在妻子身邊。那么這3對(duì)夫妻能過河嗎？（）A.能B.不能C.不確定4【判斷題】查找n個(gè)可排列數(shù)值時(shí)，折半查找通常比順序查找快。（）A.錯(cuò)B.對(duì)5【判斷題】雙向右左旋轉(zhuǎn)是在一個(gè)新的鍵插入到樹的右子女的左子樹后發(fā)生的，在插入以前，這棵樹的根的平衡因子是-1。()A.對(duì)B.錯(cuò)6【判斷題】2-3樹要求樹中的所有葉子必須位于同一層。()A.錯(cuò)B.對(duì)7【判斷題】一個(gè)具有最多節(jié)點(diǎn)的高度為h的2-3樹是一棵全部由2節(jié)點(diǎn)構(gòu)成的滿樹。（）A.錯(cuò)B.對(duì)8【判斷題】最大堆的根總是堆的最大元素。（）A.錯(cuò)B.對(duì)9【判斷題】對(duì)于相同的輸入，自頂向下算法和自底向上算法產(chǎn)生完全相同的堆。()A.對(duì)B.錯(cuò)10【單選題】(2分)如果用合并排序做預(yù)排序，折半查找做查找，要做()次查找才能使得一個(gè)由1000000個(gè)元素組成的數(shù)組所做的預(yù)排序是有意義的。A.20B.40C.30D.10第七章單元測試1【判斷題】計(jì)數(shù)排序算法在一種情況下還是卓有成效的，即待排序元素的值都來自一個(gè)已知的小集合。()A.對(duì)B.錯(cuò)2【判斷題】Horspool算法的最差效率Θ(mn)()A.錯(cuò)B.對(duì)3【單選題】(2分)用Horspool算法在一個(gè)1000個(gè)0構(gòu)成的二進(jìn)制文本中查找00001時(shí)，要進(jìn)行（）次字符比較。A.996B.995C.5*996D.5*9954【單選題】(2分)()不使用額外的存儲(chǔ)來交換兩個(gè)變量的數(shù)值，例如m和n.A.不確定B.可以C.不可以5【單選題】(2分)在Horspool字符串匹配算法中，輸入0001是000000000000的最差輸入嗎？（）A.不是B.是C.不確定6【單選題】(2分)對(duì)于模式BAOBAB，A,B,O的移動(dòng)距離分別為()。A.1,2,3B.2,1,3C.3,1,2D.2,3,1第八章單元測試1【單選題】(2分)幣值最大化問題的一個(gè)實(shí)例是5,1,2,10,16，則最大金額為（）A.32B.23C.17D.202【單選題】(2分)Floyd算法的時(shí)間效率是（）A.O()B.O()C.O(n)D.O(logn)3【單選題】(2分)貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（）。A.構(gòu)造最優(yōu)解B.貪心選擇性質(zhì)C.最優(yōu)子結(jié)構(gòu)D.定義最優(yōu)解4【判斷題】動(dòng)態(tài)規(guī)劃法分解的子問題是有重疊的，分治法分解的子問題是相互獨(dú)立的。（）A.對(duì)B.錯(cuò)5【判斷題】動(dòng)態(tài)規(guī)劃法不是隨機(jī)化算法。（）A.對(duì)B.錯(cuò)6【判斷題】動(dòng)態(tài)規(guī)劃算法適用于解具有某種最優(yōu)性質(zhì)的問題。（）A.對(duì)B.錯(cuò)第九章單元測試1【單選題】(2分)不屬于貪婪技術(shù)的算法是（）A.Dijkstra算法B.Floyd算法C.Kruskal算法D.哈夫曼編碼2【單選題】(2分)如果e是加權(quán)連通圖中權(quán)重最小的邊，它（）圖的一棵最小生成樹的邊。A.不一定是B.必定不是C.必定是3【單選題】(2分)對(duì)于包含負(fù)權(quán)重邊的圖，Prim算法()正確工作。A.不一定能B.不能C.能D.不確定4【判斷題】如果加權(quán)連通圖中每條邊的權(quán)重是都是互不相同的，該圖必定只有一棵最小生成樹。()A.對(duì)B.錯(cuò)5【判斷題】哈夫曼編碼頻率相同的所有字符都具有相同的碼長。()A.對(duì)B.錯(cuò)6【判斷題】頻率較高的字符的碼長不一定小于頻率較低的字符的碼長。()A.對(duì)B.錯(cuò)7【判斷題】Prim算法總是通過把離樹中頂點(diǎn)最近的頂點(diǎn)包含進(jìn)來，從而生成一棵最小生成樹。()A.錯(cuò)B.對(duì)8【判斷題】對(duì)于包含負(fù)權(quán)重邊的圖，Kruskal算法可能會(huì)無效。()A.對(duì)B.錯(cuò)9【判斷題】對(duì)于包含負(fù)權(quán)重邊的圖，Dijkstra算法也是正確有效的。()A.對(duì)B.錯(cuò)10【判斷題】Dijkstra算法是解決單起點(diǎn)最短路徑問題的。()A.對(duì)B.錯(cuò)11【判斷題】Dijkstra算法和Floyd算法采用了相同的算法設(shè)計(jì)技術(shù)。()A.對(duì)B.錯(cuò)12【判斷題】Dijkstra算法和Floyd算法都是是解決完全最短路徑問題的。()A.錯(cuò)B.對(duì)13【判斷題】貪婪算法在對(duì)問題求解時(shí)，總是做出當(dāng)前看來最好的選擇。()A.錯(cuò)B.對(duì)14【判斷題】哈夫曼編碼的壓縮率通常在20%～80%之間。()A.錯(cuò)B.對(duì)15【判斷題】哈夫曼編碼總是最優(yōu)前綴碼。()A.錯(cuò)B.對(duì)第十章單元測試1【單選題