計科教材練習(xí)05

1、測試試卷：計科教材練習(xí)【05】一、判斷題，共9題，總分:9分。請直接點擊選擇True or False.不同時間運行同一個產(chǎn)生隨機正整數(shù)的算法，會輸出不同的隨機正整數(shù)。這表明算法的確 定性在某些情況下是不成立的。（至）迭代和遞歸是兩種表示重復(fù)做某件事情的算法描述手段，理論上說，遞歸總可以改造成迭 代來完成相應(yīng)的工作。（直）迭代和遞歸是兩種表示重復(fù)做某件事情的算法描述手段，迭代往往是由小及大地循環(huán)解決 問題，而遞歸通常是由大到小考慮問題的解決。（_!）分治法的解決問題的思想和用遞歸來描述算法有著某種內(nèi)在的聯(lián)系。（直）在1000個大小有序的列表中查找某給定元素。用順序查找法至多需要比較1000次（

2、平均 需要500次）可以找到該元素或確定列表中不存在該元素（需要比較1000次），而用折半 查找法至多10次比較就可以找到該元素或者確定列表中不存在該元素。由此可以知，折半 查找的效率比順序查找的效率至少高50倍。（空）貪心法用于求解某目標函數(shù)在一定約束條件的最優(yōu)解。它是從一個可行解（滿足約束條件， 但未必能使目標函數(shù)最優(yōu)）出發(fā)，逐步改進解，以求得最優(yōu)解的思想方法。但使用貪心法未 必一定能夠找到最優(yōu)解。（直）如果0-1背包問題如教材表5-1所示，另假設(shè)可選的5種物品的個數(shù)不限，背包的體積為 19,則達到最優(yōu)解的物品組合不止一種。（史）動態(tài)規(guī)劃法的思想是把大問題歸結(jié)為大量不同規(guī)模子問題，而子問題

3、的求解采用一次計算 并保存，以后查表的方法來解決，從而節(jié)約計算量。因此可以說，動態(tài)規(guī)劃方法是以空間換 時間的方法。（_E）假如金塊問題共有32個金塊，那么用分治法找到最大和最小金塊需要46次比較。（_T）二、單選題，共16題，總分:16分。請四個中選擇一個是正確的答案。為解決問題而米用的方法和（D）就是算法。過程B.代碼C.語言D.步驟從解決問題的角度看，一個計算機程序就是與其對應(yīng)的（虺）的實現(xiàn)。算法B.代碼C.語言D.過程相對于計算機硬件，計算機軟件就是算法以及實現(xiàn)算法的（衛(wèi)）。過程B.偽代碼C.語言D.方法算法是求解問題步驟的有序集合，它能夠產(chǎn)生（業(yè)）并在有限時間內(nèi)結(jié)束。顯示B.代碼C.過

4、程D.結(jié)果按照算法所涉及的對象，算法可分成兩大類（衛(wèi)）。邏輯算法和算術(shù)算法數(shù)值算法和非數(shù)值算法遞歸算法和迭代算法排序算法和查找算法算法可以有0n（設(shè)n、m為正整數(shù)）個輸入，有（_C）個輸出。0m B.0 C.1m D.1算法是三種結(jié)構(gòu)，也是程序的三種邏輯結(jié)構(gòu)是（衛(wèi)）。A.順序、條件、分支順序、分支、循環(huán)順序、條件、遞歸順序、分支、迭代在一組數(shù)據(jù)中找到某一個數(shù)據(jù)或者確認該數(shù)據(jù)不在這組數(shù)據(jù)中的算法是（_C）OA.求最大值B.求最小值C.查找D.排序?qū)で?位水仙花數(shù)的算法通常采用（衛(wèi)）方法。A.遞歸B.迭代C.排序D.查找如果使用循環(huán)結(jié)構(gòu)實現(xiàn)計算n！的算法是（四）。A.遞歸B.迭代C.排序D.查找一

5、組無序的數(shù)據(jù)中確定某一個數(shù)據(jù)的位置，只能使用（業(yè)）算法。A.順序查找B.折半查找C.樹形查找D.散列查找（址）是算法的自我調(diào)用。A.迭代B.遞歸C.排序D.查找將一個較大規(guī)模的問題分解為較小規(guī)模的子問題，求解子問題、合并子問題的解得到整 個問題的解的算法是（衛(wèi)）。A.貪心法B.分治法C.動態(tài)規(guī)劃法D.回朔法把大問題分解成子問題，且子問題有大量重合的問題求解，較好的算法是（_C）OA.貪心法B.分治法C.動態(tài)規(guī)劃法D.回朔法假定某問題的解由多個分量構(gòu)成，各分量滿足特定約束條件，某求解的過程采用擴展解 的各個分量的方法。其簡單歸納為“向前走，碰壁就回頭，換一條路走”的算法叫做（衛(wèi)）O A.貪心法B

6、.分治法C.動態(tài)規(guī)劃法D.回朔法回溯法可以使用（二）方法實現(xiàn)。A.迭代或遞歸B.僅遞歸C.僅迭代D.查找或排序三、選擇性填空題，共4題，總分:12分。先點擊要填寫的位置，再選擇一個正確的答案。假如待排序的初始序列是（6，12, 33, 5, 56，15, 22，18），用選擇法將該序列從小到 大排序，當把元素6定位的時候，元素5所在的位置是A），當把元素15定位的時候，元 素33所在的位置是也，當把元素22定位的時候，元素56所在的位置是M o TOC o 1-5 h z 12345678假如待排序的初始序列是（6，12, 33, 5, 56，15, 22，18），用冒泡法將該序列從小到 大排序，當?shù)谝槐閽呙璋言?定位的時候，元素18所在的位置是G），當?shù)诙閽呙璋?元素6定位的時候，元素15所在的位置是也，當?shù)谒谋閽呙璋言?5定位的時候，元 素22所在的位詈是（F） o1234 TOC o 1-5 h z 5678假如在有序序列（3, 5, 6, 8, 9, 13, 16, 20, 23）中，用折半查找法尋找元素20,第 一比較元素（E），第二次比較元素（G），第三次比較元素（A）。205689131623對0-1背包問題，假設(shè)4種物品的體積和價值分別是：（物品A,3,4）,（物品B,4,7）, （物品C,7,13）,（物品D,9,16），可選的4種物品