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

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




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

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

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

以下C代碼采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)整數(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ù)。若棧為空，則返回機(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；
}
以上程序運(yùn)行時(shí)的輸出結(jié)果為：  (5)

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

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