計(jì)科教材練習(xí)05

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

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

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

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

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

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