第3題： 閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對應欄內(nèi)。
【說明】
Pay&Drive系統(tǒng)（開多少付多少）能夠根據(jù)駕駛里程自動計算應付的費用。
系統(tǒng)中存儲了特定區(qū)域的道路交通網(wǎng)的信息。道路交通網(wǎng)由若干個路段（Road Segment）構(gòu)成，每個路段由兩個地理坐標點（Node）標定，其里程數(shù)（Distance）是已知的。在某些地理坐標點上安裝了訪問控制（Access Control）設備，可以自動掃描行駛卡（Card）。行程（Trajectory）由一組連續(xù)的路段構(gòu)成。行程的起點（Entry）和終點（Exit）都裝有訪問控制設備。
系統(tǒng)提供了3種行駛卡。常規(guī)卡（Regular Card）有效期（Valid Period）為一年，可以在整個道路交通網(wǎng)內(nèi)使用。季卡（Season Card）有效期為三個月，可以在整個道路交通網(wǎng)內(nèi)使用。單次卡（Minitrip Card）在指定的行程內(nèi)使用，且只能使用一次。其中，季卡和單次卡都是預付卡（Prepaid Card），需要客戶（Customer）預存一定的費用。
系統(tǒng)的主要功能有：客戶注冊、申請行駛卡、使用行駛卡行駛等。
使用常規(guī)卡行駛，在進入行程起點時，系統(tǒng)記錄行程起點、進入時間（Date Of Entry）等信息。在到達行程終點時，系統(tǒng)根據(jù)行駛的里程數(shù)和所持卡的里程單價（Unit Price）計算應付費用，并打印費用單（Invoice）。
季卡的使用流程與常規(guī)卡類似，但是不需要打印費用單，系統(tǒng)自動從卡中扣除應付費用。
單次卡的使用流程與季卡類似，但還需要在行程的起點和終點上檢查行駛路線是否符合該卡所規(guī)定的行駛路線。
現(xiàn)采用面向?qū)ο蠓椒ㄩ_發(fā)該系統(tǒng)，使用UML進行建模。構(gòu)建出的用例圖和類圖分別如圖3-1和圖3-2所示。

?【問題1】（4分）
根據(jù)說明中的描述，給出圖3-1中U1和U2所對應的用例，以及（1）所對應的關系。
?【問題2】（8分）
根據(jù)說明中的描述，給出圖3-2中缺少的C1～C6所對應的類名以及（2）～（3）處所對應的多重度（類名使用說明中給出的英文詞匯）。
?【問題3】（3分）
根據(jù)說明中的描述，給出Road Segment、Trajectory和Card所對應的類的關鍵屬性（屬性名使用說明中給出的英文詞匯）。
答案解析與討論：m.xiexiliangjiufa.com/st/381112738.html

第4題： 閱讀下列說明和C代碼，將應填入 (n) 處的字句寫在答題紙的對應欄內(nèi)。
【說明】
設某一機器由n個部件組成，每一個部件都可以從m個不同的供應商處購得。供應商j供應的部件i具有重量wij和價格cij。設計一個算法，求解總價格不超過上限cc的最小重量的機器組成。
采用回溯法來求解該問題：
首先定義解空間。解空間由長度為n的向量組成，其中每個分量取值來自集合{1，2，…，m}，將解空間用樹形結(jié)構(gòu)表示。
接著從根結(jié)點開始，以深度優(yōu)先的方式搜索整個解空間。從根結(jié)點開始，根結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點。向縱深方向考慮第一個部件從第一個供應商處購買，得到一個新結(jié)點。判斷當前的機器價格（c11）是否超過上限（cc），重量（w11）是否比當前已知的解（最小重量）大，若是，應回溯至最近的一個活結(jié)點；若否，則該新結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點，根結(jié)點不再是擴展結(jié)點。繼續(xù)向縱深方向考慮第二個部件從第一個供應商處購買，得到一個新結(jié)點。同樣判斷當前的機器價格（c11+c21）是否超過上限（cc），重量（w11+w21）是否比當前已知的解（最小重量）大。若是，應回溯至最近的一個活結(jié)點；若否，則該新結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點，原來的結(jié)點不再是擴展結(jié)點。以這種方式遞歸地在解空間中搜索，直到找到所要求的解或者解空間中已無活結(jié)點為止。
【C代碼】
下面是該算法的C語言實現(xiàn)。
（1）變量說明
n：機器的部件數(shù)
m：供應商數(shù)
cc：價格上限
w[][]：二維數(shù)組，w[i][j]表示第j個供應商供應的第i個部件的重量
c[][]：二維數(shù)組，c[i][j]表示第j個供應商供應的第i個部件的價格
bestW：滿足價格上限約束條件的最小機器重量
bestC：最小重量機器的價格
bestX[]：最優(yōu)解，一維數(shù)組，bestX[i]表示第i個部件來自哪個供應商
cw：搜索過程中機器的重量
cp：搜索過程中機器的價格
x[]：搜索過程中產(chǎn)生的解，x[i]表示第i個部件來自哪個供應商
i：當前考慮的部件，從0到n - 1
j：循環(huán)變量
（2）函數(shù)backtrack
int n = 3;
int m = 3;
int cc = 4;
int w[3][3] = {{1，2，3}，{3，2，1}，{2，2，2}};
int c[3][3] = {{1，2，3}，{3，2，1}，{2，2，2}};
int bestW = 8;
int bestC = 0;
int bestX[3] = {0，0，0};
int cw = 0;
int cp = 0;
int x[3] = {0，0，0};
int backtrack(int i){
int j = 0;
int found = 0;
if(i > n - 1){  /*得到問題解*/
bestW = cw;
bestC = cp;
for(j = 0; j < n; j++){
（1）  ;
}
return 1;
}
if(cp <= cc){ /*有解*/
found = 1;
}
for(j = 0;    （2）    ; j++){
/*第i個部件從第j個供應商購買*/
（3）    ;
cw = cw + w[i][j];
cp = cp + c[i][j];
if(cp <= cc && （4） ){ /*深度搜索，擴展當前結(jié)點*/
if(backtrack(i + 1)){   found = 1;  }
}
/*回溯*/
cw = cw - w[i][j];
（5） ;
}
return found;
}
答案解析與討論：m.xiexiliangjiufa.com/st/3811216937.html

第5題： 閱讀下列說明和C++代碼，將應填入(n)處的字句寫在答題紙的對應欄內(nèi)。
【說明】
某大型商場內(nèi)安裝了多個簡易的紙巾售賣機，自動出售2元錢一包的紙巾，且每次僅售出一包紙巾。紙巾售賣機的狀態(tài)圖如圖5-1所示。

采用狀態(tài)（State）模式來實現(xiàn)該紙巾售賣機，得到如圖5-2所示的類圖。其中類State為抽象類，定義了投幣、退幣、出紙巾等方法接口。類SoldState、SoldOutState、NoQuarterState和HasQuarterState分別對應圖5-1中紙巾售賣機的4種狀態(tài)：售出紙巾、紙巾售完、沒有投幣、有2元錢。

【C++代碼】
#include
using namespace std;
// 以下為類的定義部分
class TissueMachine;   // 類的提前引用
class State {
public:
virtual void insertQuarter() = 0;  //投幣
virtual void ejectQuarter() = 0;    //退幣
virtual void turnCrank()= 0;   //按下“出紙巾”按鈕
virtual void dispense() = 0;    //出紙巾
};
/* 類SoldOutState、NoQuarterState、HasQuarterState、SoldState的定義省略，每個類中均
定義了私有數(shù)據(jù)成員TissueMachine* tissueMachine; */
class TissueMachine {
private:
（1）   *soldOutState， *noQuarterState， *hasQuarterState，*soldState， *state ;
int count; //紙巾數(shù)
public:
TissueMachine(int numbers);
void setState(State* state);
State* getHasQuarterState();
State* getNoQuarterState();
State* getSoldState();
State* getSoldOutState();
int getCount();
// 其余代碼省略
};
// 以下為類的實現(xiàn)部分
void NoQuarterState ::insertQuarter() {
tissueMachine->setState(  （2）  );
}
void HasQuarterState ::ejectQuarter() {
tissueMachine->setState(  （3）  );
}
void SoldState ::dispense() {
if(tissueMachine->getCount() > 0) {
tissueMachine->setState(  （4）  );
}
else {
tissueMachine->setState(  （5）  );
}
}  // 其余代碼省略
答案解析與討論：m.xiexiliangjiufa.com/st/3811321878.html