試題一
閱讀以下說明和圖，回答問題1至問題4，將解答填入對應欄內。
【說明】
某音像制品出租商店欲開發(fā)一個音像管理信息系統(tǒng)，管理音像制品的租借業(yè)務。需求如下：
1．系統(tǒng)中的客戶信息文件保存了該商店的所有客戶的用戶名、密碼等信息。對于首次來租借的客戶，系統(tǒng)會為其生成用戶名和初始密碼。
2．系統(tǒng)中音像制品信息文件記錄了商店中所有音像制品的詳細信息及其庫存數量。
3．根據客戶所租借的音像制品的品種，會按天收取相應的費用。音像制品的最長租借周期為1周，每位客戶每次最多只能租借6件音像制品。
4．客戶租借某種音像制品的具體流程如下。
1根據客戶提供的用戶名和密碼，驗證客戶身份。
2若該客戶是合法客戶，查詢音像制品信息文件，查看商店中是否還有這種音像制品。
3若還有該音像制品，且客戶所要租借的音像制品數小于等于6個，就可以將該音像制品租借給客戶。這時，系統(tǒng)給出相應的租借確認信息，生成一條新的租借記錄并將其保存在租借記錄文件中。
4系統(tǒng)計算租借費用，將費用信息保存在租借記錄文件中并告知客戶。
5客戶付清租借費用之后，系統(tǒng)接收客戶付款信息，將音像制品租借給該客戶。
5．當庫存中某音像制品數量不能滿足客戶的租借請求數量時，系統(tǒng)可以接受客戶網上預約租借某種音像制品。系統(tǒng)接收到預約請求后，檢查庫存信息，驗證用戶身份，創(chuàng)建相應的預約記錄，生成預約流水號給該客戶，并將信息保存在預約記錄文件中。
6．客戶歸還到期的音像制品，系統(tǒng)修改租借記錄文件，并查詢預約記錄文件和客戶信息文件，判定是否有客戶預約了這些音像制品。若有，則生成預約提示信息，通知系統(tǒng)履行預約服務，系統(tǒng)查詢客戶信息文件和預約記錄文件，通知相關客戶前來租借音像制品。

【問題1】
圖(a)中只有一個外部實體E1。使用【說明】中的詞語，給出E1的名稱。
【問題2】
使用【說明】中的詞語，給出圖(b)中的數據存儲D1～D4的名稱。
【問題3】
數據流圖(b)缺少了3條數據流，根據說明及數據流圖(a)提供的信息，分別指出這3條數據流的起點和終點。



【問題4】
在進行系統(tǒng)分析與設計時，面向數據結構的設計方法(如Jackson方法)也被廣泛應用。簡要說明面向數據結構設計方法的基本思想及其適用場合。

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

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




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

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

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

以下C代碼采用鏈式存儲結構實現一個整數棧操作。
【C代碼】
typedef struct List {
int data；                  //棧數據
struct List* next；         //上次入棧的數據地址
}List；
typedef struct Stack{
List* pTop；                //當前棧頂指針
}Stack；
Stack* NewStack()  {return (Stack*) calloc(1/sizeof(Stack))；}
int IsEmpty(Stack* S){//判斷棧S是否為空棧
if(  (1)  )return 1;
return 0;
}
int Top(Stack* s){//獲取棧頂數據。若棧為空，則返回機器可表示的最小整數
if(IsEmpty(S))return INT_ MIN；
return  (2)  ；
}
void Push(Stack* S，int theData) {//將數據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；
}
以上程序運行時的輸出結果為：  (5)