軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2024/8/2）在線(xiàn)測(cè)試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2024/8/2

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2024/8/2）

試題四
閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3，將解答填入對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
某機(jī)器上需要處理n個(gè)作業(yè)．job1，job2，…，jobn，其中：
(1)每個(gè)作jobi(1≤i≤n)的編號(hào)為i，jobi有一個(gè)收益值p[i]和最后期限值d[i]小
(2)機(jī)器在一個(gè)時(shí)刻只能處理一個(gè)作業(yè)，而且每個(gè)作業(yè)需要一個(gè)單位時(shí)間進(jìn)行處理，一旦作業(yè)開(kāi)始就不可中斷，每個(gè)作業(yè)的最后期限值為單位時(shí)間的正整數(shù)倍；
(3)job1～jobn的收益值呈非遞增順序排列，即p[1)≥P[2]≥…[n)：
(4)如果作業(yè)jobi在其期限之內(nèi)完成，則獲得收益9[i]；如果在其期限之后完成，則沒(méi)有收益。
為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖4*1是基于貪心策略求解該問(wèn)題的流程圖。
(1)整型數(shù)組J[]有n個(gè)存儲(chǔ)單元，變量k眾表示在期限之內(nèi)完成的作業(yè)J[1..k]存儲(chǔ)所有能夠在期限內(nèi)完成的作業(yè)編號(hào)，數(shù)組J[1..k]里的作業(yè)按其最后期限非遞減排序，即d[J[1]]≤…≤d[J[k]]。
(2)為了便于在數(shù)組J中加入作業(yè)，增加一個(gè)虛擬作業(yè)Job0，并令d[0]=0，j[0]=0。
(3)算法大致思想：先將作業(yè)．job1的編號(hào)1放入J[1]，然后，依次對(duì)每個(gè)作業(yè)．jobi (2≤i≤n)進(jìn)行判定，看其能否插入到數(shù)組J中。若能，則將其編號(hào)插入到數(shù)組J的適當(dāng)位置，并保證J中作業(yè)按其最后期限非遞減排列；否則不插入。
jobi能插入數(shù)組J的充要條件是：jobi和數(shù)組J中已有作業(yè)均能在其期限之內(nèi)完成。
(4)流程圖中的主要變量院明如下。
i：循環(huán)控制變量，表示作業(yè)的編號(hào)；
k：表示在期限內(nèi)完成的作業(yè)數(shù)：
r：若．jobi能插入數(shù)組J，則其在數(shù)組了中的位置為r+1：
q：循環(huán)控制變量，用于移動(dòng)數(shù)組J中的元素。
【問(wèn)題1】
請(qǐng)?zhí)畛鋱D4-1中的空缺(1)、(2)和(3)處。
【問(wèn)題2】
假設(shè)有6個(gè)作業(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)：
每個(gè)作業(yè)的處理期限數(shù)組d=(d[1]，d[2]，d[3]，d[4]，d[5]，d[6])=(1,2,1,3,4,3)。
請(qǐng)應(yīng)用試題中描述的貪心策略算法，給出在期限之內(nèi)處理的作業(yè)編號(hào)序列  (4)   (按作業(yè)處理的順序給出)，得到的總收益為  (5)  。
【問(wèn)題3】
對(duì)于本題的作業(yè)處理問(wèn)題，用圖4-1的貪心算法策略，能否求得最高收益?  (6)  。用貪心算法求解任意給定問(wèn)題時(shí)，是否一定能得到最優(yōu)解?  (7)  。

信管網(wǎng)cnitpm349536182：
i＜=6