試題四
閱讀以下說明和圖，填補流程圖中的空缺。
【說明】
某汽車制造工廠有兩條裝配線。汽車裝配過程如圖10-6所示，即汽車底盤進入裝配線，零件在多個工位裝配，結束時汽車自動完成下線工作。

(1)e0和e1表示底盤分別進入裝配線0和裝配線1所需要的時間。
(2)每條裝配線有n個工位，第一條裝配線的工位為S0,0，S0,1，…，S0,n-0，第二條裝配線的工位為S1,0，S1,1，…，S1,n-1。其中S0,k和S1,k(0≤k≤n-1)完成相同的任務，但所需時間可能不同。
(3)aij表示在工位Sij處的裝配時間，其中i表示裝配線(i=0或i=1)，j表示工位號(0≤j≤n-1)。
(4)tij表示從Sij處裝配完成后轉移到另一條裝配線下一個工位的時間。
(5)X0和X1表示裝配結束后，汽車分別從裝配線0和裝配線1下線所需要的時間。
(6)在同一條裝配線上，底盤從一個工位轉移到其下一個工位的時間可以忽略不計。
圖10-7所示的流程圖描述了求最短裝配時間的算法，該算法的輸入為；
n：        表示裝配線上的工位數(shù)；
e[i]：     表示e1和e2，i取值為0或1：
a[i][j]：  表示ai,j，i的取值為0或1，j的取值范圍為0～n-1；
t[i][j]：  表示ti,j，i的取值為0或1，j的取值范圍為0～n-1；
x[i]：     表示X0和X1，i取值為0或1。
算法的輸出為：
fi：最短的裝配時間；
li：獲得最短裝配時間的下線裝配線號(0或者1)。
算法中使用的f[i][j]表示從開始點到Si,j處的最短裝配時間。

試題五
閱讀以下說明、圖和C代碼。
【說明】
一般的樹結構常采用孩子-兄弟表示法表示，即用二叉鏈表作樹的存儲結構，鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。例如，圖10-8(a)所示的樹的孩子-兄弟表示如圖10-8(b)所示。

函數(shù)LevelTraverse()的功能是對給定樹進行層序遍歷。例如，對圖10-1所示的樹進行層序遍歷時，結點的訪問次序為D B A E F P C。
對樹進行層序遍歷時使用了隊列結構，實現(xiàn)隊列基本操作的函數(shù)原型如下表所示：



Bool、Status類型定義如下：
typedef enum { FALSE=0，TRUE=1 } Bool；
typedef enum { OVERFLOW=-2，UNDERFLOW=-1，ERROR=0，OK=1}Status；
樹的二叉鏈表結點定義如下：
typedef struct Node {
char data；
struct Node *firstchild，*nextbrother；
} Node，*TreeNode；
【函數(shù)】
Status LevelTraverse ( TreeNode root )
{ /*層序遍歷樹，樹采用孩子-兄弟表示法，root是樹根結點的指針*/
Queue tempQ；
TreeNode ptr，brotherptr；
if (! root)
return ERROR；
InitQueue(&tempQ)；
(1)  ；
brotherptr = root -＞ nextbrother；
while (brotherptr) {
EnQueue(&tempQ，brotherptr)；
(2)  ；
}/*end-while*/
while(  (3)  ){
(4)  ；
printf("%c＼t"，ptr-＞data)；
if(  (5)  )continue；
(6)  ；
brotherptr = ptr-＞firstchild-＞nextbrother；
while (brotherptr) {
EnQueue(&tempQ，brotherptr)；
(7)  ；
}/*end-while*/
}/*end-while*/
return OK；
}/*LevelTraverse*/

試題六
閱讀以下說明和C++代碼。
【說明】
傳輸門是傳輸系統(tǒng)中的重要裝置。傳輸門具有Open(打開)、Closed(關閉)、Opening (正在打開)、StayOpen(保持打開)和Closing(正在關閉)五種狀態(tài)。觸發(fā)傳輸門狀態(tài)轉換的事件有click、complete和timeout三種。事件與其相應的狀態(tài)轉換如下圖所示。

下面的C++代碼1與C++代碼2分別用兩種不同的設計思路對傳輸門進行狀態(tài)模擬，請?zhí)钛a代碼中的空缺。
【C++代碼1】
const int CLOSED=1；   const int OPENING=2；
const int OPEN=3；     const int CLOSING=4；
const int STAYOPEN=5；  //定義狀態(tài)變量，用不同整數(shù)表示不同狀態(tài)
class Door {
Private：
int state；  //傳輸門當前狀態(tài)
void setState(int state){ this-＞state=state；}  //設置當前狀態(tài)
public：
Door()：state(CLOSED.{}；
void getState(){    //根據(jù)當前狀態(tài)輸出相應的字符串
switch(state){
case OPENING： cout＜＜"OPENING"＜＜endl；    break；
case CLOSED：  cout＜＜"CLOSED"＜＜endl；     break；
case OPEN：    cout＜＜"OPEN"＜＜endl；       break；
case CLOSING： cout＜＜"CLOSING"＜＜endl；    break；
case STAYOPEN：cout＜＜"STAYOPEN"＜＜endl；   break；
}
};
void click()  {    //發(fā)生click事件時進行狀態(tài)轉換
if (  (1)  )    setState(OPENING.；
else if (  (2)  )    setState(CLOSING.；
else if (  (3)  )    setState(STAYOPEN)；
}
void timeout(){    //發(fā)生timeout事件時進行狀態(tài)轉換
if (state == OPEN)  setState(CLOSING.；
}
void complete(){    //發(fā)生complete事件時進行狀態(tài)轉換
if (state == OPENING.    setState(OPEN)；
else if (state == CLOSING.  setState(CLOSED.；
}
};
int main(){
Door aDoor；
aDoor.getState()；aDoor.click()；    aDoor.getState()；
aDoor.complete()；aDoor.getState()； aDoor.click()；
aDoor.getState()；aDoor.click()；    aDoor.getState()；    return 0；
}
【C++代碼2】
class Door {
public：
DoorState *CLOSED，*OPENING，*OPEN，*CLOSING，*STAYOPEN，*state；
Door()；
virtual～Door(){……//釋放申請的內存，此處代碼省略)；
void setState(DoorState *state)  { this-＞state = state；}
void getState(){
//此處代碼省略，本方法輸出狀態(tài)字符串，
//例如，當前狀態(tài)為CLOSED時，輸出字符串為“CLOSED”
}；
void click()；
void timeout()；
void complete()；
}；
Door::Door(){
CLOSED = new DoorClosed(this)；    OPENING = new DoorOpening(this)；
OPEN = new DoorOpen(this)；        CLOSING = new DoorClosing(this)；
STAYOPEN = new DoorStayOpen(this)；state = CLOSED；
}
void Door :: click() {  (4)  ；)
void Door :: timeout() {  (5)  ；)
void Door :: complete() {  (6)  ；}
class DoorState//定義一個抽象的狀態(tài)，它是所有狀態(tài)類的基類
{
protected：Door *door；
public：
DoorState(Door *door) {this-＞door = door；}
virtual～DoorState(void)；
virtual void click()  {}
virtual void complete()  {}
virtual void timeout()  {}
}；
class DoorClosed :public DoorState{//定義一個基本的Closed狀態(tài)
public：
DoorClosed(Door *door) :DoorState(door)  {}
virtual ～ DoorClosed(){}
void click()；
}；
void DoorClosed :: click() {  (7)  ；}
//其他狀態(tài)類的定義與實現(xiàn)代碼省略
int main() {
Door aDoor；
aDoor.getState()；aDoor.click()；aDoor.getState()；aDoor.complete()；
aDoor.getState()；aDoor.timeout()；aDoor.getState()；return 0；
}