試題四
閱讀下列說(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è)開始就不可中斷，每個(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)  。

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

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

【C++代碼】
#include ＜string＞
#include ＜iostream＞
using namespace std;
class PurchaseRequest  {
public:
double Amount;       /*一個(gè)采購(gòu)的金額*/
int Number;          /*采購(gòu)單編號(hào)*/
string Purpose;      /*采購(gòu)目的*/
};
class Approver {          /*審批者類*/
public:
Approver() { successor = NULL;    }
virtual void ProcessRequest(PurchaseRequest aRequest){
if  (successor  != NULL){  successor-＞  (1)   ;     }
}
void SetSuccessor(Approver *aSuccesssor) { successor = aSuccesssor; } private:
(2)  successor; };
class Congress  : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest) {
if(aRequest.Amount ＞= 500000){  /*決定是否審批的代碼少略*/    }
else  (3)  ProcessRequest(aRequest);
}
class Director : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest){   /*此處代碼省略*/
}
};
class President : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest)    /*此處代碼省略*/  }
};
class VicePresident : public Approver {
public:
void ProcessRequest(PurchaseRequest aRequest)    /*此處代碼省略*/   }
};
void main(){
Congress Meeting;  VicePresident Sam;  Director Larry ;  President
Tammy;
Meeting. SetSuccessor(NULL);      Sam. SetSuccessor(  (4)  );
Tammy. SetSuccessor(  (5)  );         Larry. SetSuccessor(  (6)  );
PurchaseRequest aRequest;   /*構(gòu)造一采購(gòu)審批請(qǐng)求*/
cin ＞＞ aRequest.Amount;      /*輸入采購(gòu)請(qǐng)求的金額*/
(7)   .ProcessRequest(aRequest);   /*開始審批*/
return  ;
}