為幫助廣大軟考中級軟件設(shè)計師考生更好備考，信管網(wǎng)特整理匯總了軟件設(shè)計師部分下午真題、答案及解析供考生查閱，并提供免費(fèi)在線模擬答題、歷年真題免費(fèi)下載等服務(wù)，了解軟件設(shè)計師更多備考信息請關(guān)注信管網(wǎng)。

相關(guān)推薦：

點擊查看/下載：軟件設(shè)計師歷年真題匯總

點擊查看：軟件設(shè)計師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)

閱讀下列說明和圖，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。

【說明】

某機(jī)器上需要處理n個作業(yè).job1，job2，…，jobn，其中：

(1)每個作jobi(1≤i≤n)的編號為i，jobi有一個收益值p[i]和最后期限值d[i]小

(2)機(jī)器在一個時刻只能處理一個作業(yè)，而且每個作業(yè)需要一個單位時間進(jìn)行處理，一旦作業(yè)開始就不可中斷，每個作業(yè)的最后期限值為單位時間的正整數(shù)倍;

(3)job1～jobn的收益值呈非遞增順序排列，即p[1)≥p[2]≥…[n)：

(4)如果作業(yè)jobi在其期限之內(nèi)完成，則獲得收益9[i];如果在其期限之后完成，則沒有收益。

為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖4*1是基于貪心策略求解該問題的流程圖。

(1)整型數(shù)組j[]有n個存儲單元，變量k眾表示在期限之內(nèi)完成的作業(yè)j[1..k]存儲所有能夠在期限內(nèi)完成的作業(yè)編號，數(shù)組j[1..k]里的作業(yè)按其最后期限非遞減排序，即d[j[1]]≤…≤d[j[k]]。

(2)為了便于在數(shù)組j中加入作業(yè)，增加一個虛擬作業(yè)job0，并令d[0]=0，j[0]=0。

(3)算法大致思想：先將作業(yè).job1的編號1放入j[1]，然后，依次對每個作業(yè).jobi (2≤i≤n)進(jìn)行判定，看其能否插入到數(shù)組j中。若能，則將其編號插入到數(shù)組j的適當(dāng)位置，并保證j中作業(yè)按其最后期限非遞減排列;否則不插入。

jobi能插入數(shù)組j的充要條件是：jobi和數(shù)組j中已有作業(yè)均能在其期限之內(nèi)完成。

(4)流程圖中的主要變量院明如下。

i：循環(huán)控制變量，表示作業(yè)的編號;

k：表示在期限內(nèi)完成的作業(yè)數(shù)：

r：若.jobi能插入數(shù)組j，則其在數(shù)組了中的位置為r+1：

q：循環(huán)控制變量，用于移動數(shù)組j中的元素。

【問題1】

請?zhí)畛鋱D4-1中的空缺(1)、(2)和(3)處。

【問題2】

假設(shè)有6個作業(yè)job1，job2，…，job6;

完成作業(yè)的收益數(shù)組p=(p[1]，p[2]，p[3]，p[4]，p[5]，p[6])=(90,80,50,30,20,10)：

每個作業(yè)的處理期限數(shù)組d=(d[1]，d[2]，d[3]，d[4]，d[5]，d[6])=(1,2,1,3,4,3)。

請應(yīng)用試題中描述的貪心策略算法，給出在期限之內(nèi)處理的作業(yè)編號序列 (4) (按作業(yè)處理的順序給出)，得到的總收益為 (5) 。

【問題3】

對于本題的作業(yè)處理問題，用圖4-1的貪心算法策略，能否求得最高收益? (6) 。用貪心算法求解任意給定問題時，是否一定能得到最優(yōu)解? (7) 。

查看答案及解析：www.xomuzic.com/st/245608949.html