試題三
閱讀下列說明和圖，回答問題1至問題4，將解答填入對應(yīng)欄內(nèi)。
【說明】
某汽車停車場欲建立一個信息系統(tǒng)，已經(jīng)調(diào)查到的需求如下：
1．在停車場的入口和出口分別安裝一個自動欄桿、一臺停車卡打印機、一臺讀卡器和一個車輛通過傳感器，示意圖如下：

2．當(dāng)汽車到達(dá)入口時，駕駛員按下停車卡打印機的按鈕獲取停車卡。當(dāng)駕駛員拿走停車卡后，系統(tǒng)命令欄桿自動抬起；汽車通過入口后，入口處的傳感器通知系統(tǒng)發(fā)出命令，欄桿自動放下。
3．在停車場內(nèi)分布著若干個付款機器。駕駛員將在入口處獲取的停車卡插入付款機器，并繳納停車費。付清停車費之后，將獲得一張出場卡，用于離開停車場。
4．當(dāng)汽車到達(dá)出口時，駕駛員將出場卡插入出口處的讀卡器。如果這張卡是有效的，系統(tǒng)命令欄桿自動抬起；汽車通過出口后，出口傳感器通知系統(tǒng)發(fā)出命令，欄桿自動放下。若這張卡是無效的，系統(tǒng)不發(fā)出欄桿抬起命令而發(fā)出告警信號。
5．系統(tǒng)自動記錄停車場內(nèi)空閑的停車位的數(shù)量。若停車場當(dāng)前沒有車位，系統(tǒng)將在入口處顯示“車位已滿”信息。這時，停車卡打印機將不再出卡，只允許場內(nèi)汽車出場。
根據(jù)上述描述，采用面向?qū)ο蠓椒▽ζ溥M行分析與設(shè)計，得到了如下表所示的類/用例/狀態(tài)列表、下圖(a)所示的用例圖、圖(b)所示的初始類圖以及圖(c)所示的描述入口自動欄桿行為的UML狀態(tài)圖。




【問題1】
根據(jù)說明中的描述，使用上頁表給出的用例名稱，給出圖(a)中U1、U2和U3所對應(yīng)的用例。
【問題2】
根據(jù)說明中的描述，使用上頁表給出的類的名稱，給出圖(b)中的，A～D所對應(yīng)的類。
【問題3】
根據(jù)說明中的描述，使用上頁表給出的狀態(tài)名稱，給出圖(c)中S1~S4所對應(yīng)的狀態(tài)。
【問題4】
簡要解釋圖(a)中用例U1和U3之間的extend關(guān)系的內(nèi)涵。

試題四
閱讀下列說明，回答問題1至問題3，將解答填入對應(yīng)欄內(nèi)。
【說明】
快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組A[p..r]排序的3個步驟如下。
1．分解：選擇一個樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組A[p..r]劃分為兩個子數(shù)組 (可能為空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1)中的每個元素，小于 A[q+1..r]中的每個元素。q的值在劃分過程中計算。
2．遞歸求解：通過遞歸的調(diào)用快速排序，對子數(shù)組A[p..q-1]和A[q+1..r]分別排序。
3．合并：快速排序在原地排序，故不需合并操作。
【問題1】
下面是快速排序的偽代碼，請?zhí)钛a其中的空缺；偽代碼中的主要變量說明如下。
A：待排序數(shù)組
p，r: 數(shù)組元素下標(biāo)，從p到r
q: 劃分的位置
x：樞軸元素
i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值
j：循環(huán)控制變量，表示數(shù)組元素下標(biāo)
QUICKSORT (A，p，r){
if  (p ＜r){
q=PARTITION(A，p，r) ；
QUICKSORT(A，p，q-1)；
QUICKSORT(A，q+1，r)；
}
}
PARTITION(A，p，r){
x=A[r]；i=p-1；
for(j=p；j≤r-1；j++){
if  (A[j]≤x){
i=i+1；
交換A[i]和A[j]
}
}
交  (1)  和  (2)  //注：空(1)和空(2)答案可互換，但兩空全部答對方可得分 return   (3)
}
【問題2】
(1)假設(shè)要排序包含n個元素的數(shù)組，請給出在各種不同的劃分情況下，快速排序的時間復(fù)雜度，用O記號。最佳情況為  (4)  ，平均情況為  (5)  ，最壞情況為  (6)  。
(2)假設(shè)要排序的n個元素都具有相同值時，快速排序的運行時間復(fù)雜度屬于哪種情況?  (7)  。(最佳，平均、最壞)
【問題3】
(1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機地取出一個元素作為樞軸元素，下面是隨機化快速排序劃分的偽代碼——利用原有的快速排序的劃分操作，請?zhí)畛淦渲械目杖碧?。其中，RANDOM(i，j)表示隨機取i到j(luò)之間的一個數(shù)，包括i和j。
RANDOMIZED- PARTITION(A，p，r){
i=RANDOM(p，rl)；
交換  (8)  和  (9)  ；//注：空(8)和空(9)答案可互換，但兩空全部答對方可得分
return PARTITION (A，p，r)；
}
(2)隨機化快速排序是否能夠消除最壞情況的發(fā)生?  (10)  。(是或否)

試題五
閱讀下列說明和C代碼，將應(yīng)填入    處的字句寫在對應(yīng)欄內(nèi)。
【說明】
棧(Stack)結(jié)構(gòu)是計算機語言實現(xiàn)中的一種重要數(shù)據(jù)結(jié)構(gòu)。對于任意棧，進行插入和刪除操作的一端稱為棧頂(Stock Top)，而另一端稱為棧底(Stock Bottom)。棧的基本操作包括：創(chuàng)建棧(NewStack)、判斷棧是否為空(IsEmpty)、判斷棧是否已滿(IsFull)、獲取棧頂數(shù)據(jù)(Top)、壓棧/入棧(Push)、彈棧/出棧(Pop)。
當(dāng)設(shè)計棧的存儲結(jié)構(gòu)時，可以采取多種方式。其中，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧中各數(shù)據(jù)項不必連續(xù)存儲(如下圖所示)。

以下C代碼采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)一個整數(shù)棧操作。
【C代碼】
typedef struct List {
int data；                  //棧數(shù)據(jù)
struct List* next；         //上次入棧的數(shù)據(jù)地址
}List；
typedef struct Stack{
List* pTop；                //當(dāng)前棧頂指針
}Stack；
Stack* NewStack()  {return (Stack*) calloc(1/sizeof(Stack))；}
int IsEmpty(Stack* S){//判斷棧S是否為空棧
if(  (1)  )return 1;
return 0;
}
int Top(Stack* s){//獲取棧頂數(shù)據(jù)。若棧為空，則返回機器可表示的最小整數(shù)
if(IsEmpty(S))return INT_ MIN；
return  (2)  ；
}
void Push(Stack* S，int theData) {//將數(shù)據(jù)theData壓棧
List* newNode；
newNode=(List*)calloc(1/sizeof (List))；
newNode-＞data=theData；
newNode-＞next=S-＞pTop；
S-＞pTop=  (3)  ；
}
void Pop(Stack* S)  {//彈棧
List* lastTop；
if(IsEmpty(S)  )  return；
lastTop=S-＞pTop；
S-＞pTop=  (4)  ；
free(lastTop)；
}
#define MD(a)  a＜＜2
int main(){
int i;
Stack* myStack；
myStack= NewStack()；
Push(myStack，MD(1))；
Push(myStack，MD(2))；
Pop(myStack)；
Push(myStack，MD(3)+1)；
while( !IsEmpty(myStack)  ){
printf("%d"，Top(myStack))；
Pop(myStack)；
}
return 0；
}
以上程序運行時的輸出結(jié)果為：  (5)

試題七
閱讀下列說明和Java代碼，將應(yīng)填入  (n)  處的字句寫在對應(yīng)欄內(nèi)。
【說明】
已知某企業(yè)欲開發(fā)一家用電器遙控系統(tǒng)，即用戶使用一個遙控器即可控制某些家用電器的開與關(guān)。遙控器如下圖(a)所示。該遙控器共有4今按鈕，編號分別是0至3，按鈕0和2能夠遙控打開電器1和電器2，按鈕1和3則能遙控關(guān)閉電器1和電器2。由于遙控系統(tǒng)需要支持形式多樣的電器，因此，該系統(tǒng)的設(shè)計要求具有較高的擴展性?，F(xiàn)假設(shè)需要控制客廳電視和臥室電燈，對該遙控系統(tǒng)進行設(shè)計所得類圖如下圖(b)所示

圖(b)中，類RomoteController的方法onPrcssButton(int button)表示當(dāng)遙控器按鍵按下時調(diào)用的方法，參數(shù)為按鍵的編號；command接口中on和off方法分別用于控制電器的開與關(guān)；Light中turnLight(int degree)方法用于調(diào)整電燈燈光的強弱，參數(shù) degree值為0時表示關(guān)燈，值為100時表示開燈并且將燈光亮度調(diào)整到最大；TV中 sctChannel(int channel)方法表示設(shè)置電視播放的頻道，參數(shù)channel值為0時表示關(guān)閉電視，為1時表示開機并將頻道切換為第1頻道。
【Java代碼】
class Light{  //電燈類
public void trunLight(int degree){//調(diào)整燈光亮度，0表示關(guān)燈，100表示亮度最大}
}；
class TV{//電視機類
public void setChannel(int channel){//0表示關(guān)機，1表示開機并切換到1頻道}
}；
interface Command{//抽象命令類
void on()；
void off()；
}；
class RemoteController{  //遙控器類
protected Command  []commands=new Command[4]；
//遙控器有4個按鈕，按照編號分別對應(yīng)4個Command對象
public void onPressButton(int button){
//按鈕被按下時執(zhí)行命令對象中的命令
if(button  %  2 == 0)commands[button]. on()；
else commands[button]. off()；
}
public void setCommand(int button，  Command command){
(1)  =command；//設(shè)置每個按鈕對應(yīng)的命令對象
}
}；
class LightCommand implements Command{  //電燈命令類
protected Light light；  //指向要控制的電燈對象
public void on(){light. trunLight(100)；)；
public void off(){light.   (2)  ；)；
public LightCommand(Light light){this. light= light；)；
}；
class TVCommand implements Command{//電視機命令類
protected Tv tv；  //指向要控制的電視機對象
public void on(){tv.   (3)  ；}；
public void off(){tv. setChanne1(0)；}；
public TVCommand(TV  tv){this. tv= tv；}；
}；
public class rs {
public static void main(String [] args){
Light light= new Light()；  TV tv=new TV()；//創(chuàng)建電燈和電視對象
LightCommand lightCommand= new LightCommand(light)；
TVCommand tvCommand=new TVCommand(tv)；
RemoteController remoteController=new RemoteController()；
//設(shè)置按鈕和命令對象
remoteController. setCommand(0，  (4)  )；
... //此處省略設(shè)置按鈕1、按鈕2和按鈕3的命令對象代碼
}
}
本題中，應(yīng)用命令模式能夠有效讓類  (5)  和類  (6)  、類  (7)  之間的耦合性降至最小。