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

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


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

試題四
閱讀下列說明和圖，回答問題1至問題3，將解答填入對應欄內(nèi)。
【說明】
某機器上需要處理n個作業(yè)．job1，job2，…，jobn，其中：
(1)每個作jobi(1≤i≤n)的編號為i，jobi有一個收益值p[i]和最后期限值d[i]小
(2)機器在一個時刻只能處理一個作業(yè)，而且每個作業(yè)需要一個單位時間進行處理，一旦作業(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)進行判定，看其能否插入到數(shù)組J中。若能，則將其編號插入到數(shù)組J的適當位置，并保證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】
假設有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)。
請應用試題中描述的貪心策略算法，給出在期限之內(nèi)處理的作業(yè)編號序列  (4)   (按作業(yè)處理的順序給出)，得到的總收益為  (5)  。
【問題3】
對于本題的作業(yè)處理問題，用圖4-1的貪心算法策略，能否求得最高收益?  (6)  。用貪心算法求解任意給定問題時，是否一定能得到最優(yōu)解?  (7)  。

試題五
閱讀以下說明和C代碼，將應填入  (n)  處的字句寫在的對應欄內(nèi)。
【說明】
在一個簡化的繪圖程序中，支持的圖形種類有點(point)和圓(circle)，在設計過程中采用面向?qū)ο笏枷?，認為所有的點和圓都是一種圖形(shape)，并定義了類型shape t、 point t和circle t分別表示基本圖形、點和圓，并且點和圓具有基本圖形的所有特征。
【C代碼】
typedef enum { point,circle } shape type;   /* 程序中的兩種圖形：點和圓 */
typedef struct {             /* 基本的圖形類型 */
shape_type  type;        /* 圖形中類標識：點或者圓*/
void (*destroy) ();       /* 銷毀圖形操作的函數(shù)指針*/
void (*draw) ();          /* 繪制圖形操作的函數(shù)指針*/
} shape_t;
typedef struct {  shape_t common;  int x;  iht y;  } point_t;  /* 定義點類
型, x, y為點坐標*/
void destroyPoint (point_t* this)  { free (this); printf ("Point destoryed!
\n"); } )  /* 銷毀點對象*/
void drawPoint(point_t* this)  { printf("P(%d,%d)", this->x, this->y);  }
/* 繪制點對象*/
shape_t* createPoint (va_list* ap)  (/* 創(chuàng)建點對象，并設置其屬性*/
point_t*  p_point;
if ( (p_point= (point_t*)malloc (sizeof (point_t)) ) ==NULL) returnNULL;
p_point-＞common, type = point; p_point->common, destroy = destroyPoint;
p_point-＞common.draw = drawPoint;
p_point-＞x = va_arg(*ap, int);       /* 設置點的橫坐標*/
p_point-＞y = va_arg(*ap, int);       /* 設置點的縱坐標*/
return  (shape_t*)p_ooint;               /*返回點對象指針*/
}
typedef struct {    /*定義圓類型*/
shape_t  common;
point_t  4center;     /*圓心點*/
int   radius;          /*圓半徑*/
} circle_t;
void destroyCircle(circle_t* this){
free(  (1)  );        free(this);      printf("Circle destoryed!\n");
}
void drawCircle(circle_t* this)  {
print f ("C (");
(2)  .draw(this-＞center);   /*繪制圓心*/
printf(",%d) ",  this-＞radius);
}
shape_t* createCircle(va_list4 ap)  {     /*創(chuàng)建一個圓，并設置其屬性*/
circle_t4  p circle;
if ((p_circle = (circle_t4)malloc (sizeof (circle_t)) ) ==NULL ) return NULL;
p_circle-＞common.type = circle; p_circle-＞common.destroy = destroy
Circle;
p_circle-＞common.draw = drawCircle;
(3)    = createPoint(ap);      /* 設置圓心*/
p_circle-＞radius = va_arg(*ap, int);     /* 設置圓半徑*/
return  p_circle;
}
shape_t* createShape(shape_type st, "')  {    /* 創(chuàng)建某一種具體的圖形*/
va_list   ap;                      /*可變參數(shù)列表*/
shape_t4  p_shape = NULL;
(4)   (ap, st);
if( st == point )   p shape = createPoint(&ap);   /* 創(chuàng)建點對象*/
if( st == circle )  p shape = createCircle(&ap);   /*創(chuàng)建圓對象*/
va_end (ap);
return p_shape;
}
int main( )  {
int i;                  /* 循環(huán)控制變量，用于循環(huán)計數(shù)*/
shape_t* shapes[2];     /* 圖形指針數(shù)組，存儲圖形的地址*/
shapes[0] = createShape( point, 2, 3);       /* 橫坐標為2，比值坐標為3*/
shapes[ii = createShape( circle, 20,  40, 10);   /* 圓心坐標(20,40),
半徑為 10*/
for(i=0 i＜2; i++) { shapes[i]-＞draw(shapes[i]);  printf("\n");  } /*
縱制數(shù)組中圖形*/
for( i = 1; i ＞= 0; i-- )  shapes[i]-＞destroy(shapes[i]);   /* 銷毀
數(shù)組中圖形*/
return 0;
}
【運行結果】
P(2,3)
(5)
Circle destoryed !
Point destoryed !

試題七
閱讀下列說明和Java代碼，將應填入  (n)  處的字句寫在對應欄內(nèi)。
【說明】
已知某企業(yè)的采購審批是分級進行的，即根據(jù)采購金額的不同由不同層次的主管人員來審批，主任可以審批5萬元以下(不包括5萬元)的采購單，副董事長可以審批5萬元至10萬元(不包括10萬元)的采購單，董事長可以審批10萬元至50萬元(不包括50萬元)的采購單，50萬元及以上的采購單就需要開會討論決定。
采用責任鏈設計模式(Chain of Responsibility)對上述過程進行設計后得到的類圖如圖7-1所示。

【Java 代碼】
class PurchaseRequest {
public  double Amount;       // 一個采購的金額
public  int Number;           // 采購單編號
public  String Purpose;      // 采購目的
};
class Approver {          // 審批者類
public   Approver() {     successor = null;    }
public  void ProcessRequest(PurchaseRequest aRequest){
if (successor != null){ successor.   (1)  ;  }
}
public  void SetSuccesser(Approver aSuccesssor){ successor = aSuccesssor; }
private    (2)   successor;
};
class Congress extends Approver {
public  void ProcessRequest(PurchaseRequest aRequest) {
if(aRequest,Amount ＞= 500000){  // 決定是否審批的代碼省略}
else  (3)   .ProcessRequest(aRequest);
}
};
class Director extends Approver {
public  void ProcessRequest(PurchaseRequest aRequest){ // 此處代碼省略  }
};
class President extends Approver {
public  void ProcessRequest(PurchaseRequest aRequest) {  // 此處代碼省略 }
};
class VicePresident extends Approver {
public  void ProcessRequest(PurchaseRequest aRequest) {  // 此處代碼省略 }
};
public class rs {
public static void main(String[]  args)  throws IOException {
Congress Meeting = new Congress();
VicePresident Sam = new VicePresident();
Director Larry = new Director();
President Tammy = new President();
// 構造責任鏈
Meeting. SetSuccessor(null);      Sam. SetSuccessor(  (4)  );
Tammy. SetSuccessor(  (5)  );    Larry. SetSuccessor(  (6)  );
//構造一采購審批請求
PurchaseRequest aRequest = new PurchaseRequest();
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
aRequest.Amount = Double.parseDouble(br.readLine());
(7)   .ProcessRequest(aRequest);   // 開始審批
return ;
}
}