試題二
閱讀下列說明，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)。
【說明】
某汽車維修站擬開發(fā)一套小型汽車維修管理系統(tǒng)，對車輛的維修情況進(jìn)行管理。
1．對于新客戶及車輛，汽車維修管理系統(tǒng)首先登記客戶信息，包括：客戶編號、客戶名稱、客戶性質(zhì)(個人、單位)、折扣率、聯(lián)系人、聯(lián)系電話等信息；還要記錄客戶的車輛信息，包括：車牌號、車型、顏色等信息。一個客戶至少有一臺車?？蛻艏败囕v信息如表2-1所示。

2．記錄維修車輛的故障信息。包括：維修類型(普通、加急)、作業(yè)分類(大、中、小修)、結(jié)算方式(自付、三包、索賠)等信息。維修廠的員工分為：維修員和業(yè)務(wù)員。車輛維修首先委托給業(yè)務(wù)員。業(yè)務(wù)員對車輛進(jìn)行檢查和故障分析后，與客戶磋商，確定故障現(xiàn)象，生成維修委托書。如表2-2所示。

3．維修車間根據(jù)維修委托書和車輛的故障現(xiàn)象，在已有的維修項(xiàng)目中選擇并確定一個或多個具體維修項(xiàng)目，安排相關(guān)的維修工及工時，生成維修派工單。維修派工單如表2-3所示。

4．客戶車輛在車間修理完畢后，根據(jù)維修項(xiàng)目單價和維修派工單中的工時計(jì)算車輛此次維修的總費(fèi)用，記錄在委托書中。
根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖(圖2-1)和關(guān)系模式(不完整)如下所示。圖2-1中業(yè)務(wù)員和維修工是員工的子實(shí)體。

【邏輯結(jié)構(gòu)設(shè)計(jì)】
客戶(  (5)  ，折扣率，聯(lián)系人，聯(lián)系電話)
車輛(車牌號，客戶編號，車型，顏色，車輛類別)
委托書(  (6)  ，維修類型，作業(yè)分類，結(jié)算方式，進(jìn)廠時間，
預(yù)計(jì)完工時間，登記日期，故障描述，總費(fèi)用)
維修項(xiàng)目(維修項(xiàng)目編號，維修項(xiàng)目，單價)
派工單(  (7)  ，工時)
員工(  (8)  ，工種，員工類型，級別)
【問題1】
根據(jù)問題描述，填寫圖2-1中(1)～(4)處聯(lián)系的類型。聯(lián)系類型分為一對一、一對多和多對多三種，分別使用1:1，1:n或1:*，m:n或*:*表示。
【問題2】
補(bǔ)充圖2-1中的聯(lián)系并指明其聯(lián)系類型。聯(lián)系名可為：聯(lián)系1，聯(lián)系2，…
【問題3】
根據(jù)圖2-1和說明，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空(5)～(8)補(bǔ)充完整。
【問題4】
根據(jù)問題描述，寫出客戶、委托書和派工單這三個關(guān)系的主鍵。

試題三
閱讀下列說明和圖，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)。
【說明】
已知某唱片播放器不僅可以播放唱片，而且可以連接電腦并把電腦中的歌曲刻錄到唱片上(同步歌曲)。連接電腦的過程中還可自動完成充電。
關(guān)于唱片，還有以下描述信息：
1．每首歌曲的描述信息包括：歌曲的名字、譜寫這首歌曲的藝術(shù)家以及演奏這首歌曲的藝術(shù)家。只有兩首歌曲的這三部分信息完全相同時，才認(rèn)為它們是同一首歌曲。藝術(shù)家可能是一名歌手或一支由2名或2名以上的歌手所組成的樂隊(duì)。一名歌手可以不屬于任何樂隊(duì)，也可以屬于一個或多個樂隊(duì)。
2．每張唱片由多條音軌構(gòu)成；一條音軌中只包含一首歌曲或?yàn)榭?，一首歌曲可分布在多條音軌上；同一首歌曲在一張唱片中最多只能出現(xiàn)一次。
3．每條音軌都有一個開始位置和持續(xù)時間。一張唱片上音軌的次序是非常重要的，因此對于任意一條音軌，播放器需要準(zhǔn)確地知道，它的下一條音軌和上——條音軌是什么 (如果存在的話)。
根據(jù)上述描述，采用面向?qū)ο蠓椒▽ζ溥M(jìn)行分析與設(shè)計(jì)，得到了如表3-1所示的類列表、如圖3-1所示的初始類圖以及如圖3-2所示的描述播放器行為的UML狀態(tài)圖。

【問題1】
根據(jù)說明中的描述，使用表3-1給出的類的名稱，給出圖3-1中的A～F所對應(yīng)的類。
【問題2】
根據(jù)說明中的描述，給山圖3-1中(1)～(6)處的多重度。
【問題3】
圖3-1中缺少了一條關(guān)聯(lián)，請指出這條關(guān)聯(lián)兩端所對應(yīng)的類以及每一端的多重度。


【問題4】
根據(jù)圖3-2所示的播放器行為UML狀態(tài)圖，給出從“關(guān)閉”狀態(tài)到“播放”狀態(tài)所經(jīng)過的最短事件序列(假設(shè)電池一開始就是有電的)。

試題四
閱讀下列說明和圖，回答問題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)  。