試題四
閱讀下列說明，回答問題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)

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

右上圖中，類RomoteController的方法onPressButton(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中 setChannel(int channel)方法表示設(shè)置電視播放的頻道，參數(shù)channel值為0時(shí)表示關(guān)閉電視，為1時(shí)表示開機(jī)并將頻道切換為第1頻道。
【C++代碼】
class Light{  //電燈類
public：
void trunLight(int degree){//調(diào)整燈光亮度，0表示關(guān)燈，100表示亮度最大)；
}；
class TV{//電視機(jī)類
public：
vold setChannel(int channel]{//調(diào)整電視頻道，0表示關(guān)機(jī)，1表示開機(jī)并切換到1頻道}；
}；
class Command{//抽象命令類
public：
virtual void on()=0；
virtual void off()=0；
}；
class RemoteController{  //遙控器類
protected：
Command* commands [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()；
}
void setCommand(int button，Command* command){
(1)  =command；//設(shè)置每個(gè)按鈕對(duì)應(yīng)的命令對(duì)象
}
}；
class LightCommand：public Command{  //電燈命令類
protected：    Light* light；  //指向要控制的電燈對(duì)象
public：
void On(){light-＞trunLight(100)；)；
void off()[light-＞  (2)  ；)；
LightCommand(Light * light){this-＞light=light；)；
}；
class TVCommand：public Command{//電視機(jī)命令類
protected：    TV*tv；  //指向要控制的電視機(jī)對(duì)象
public：
void on(){tv-＞  (3)  ；}；
void off(){tv-＞setChannel(0)；)；
TVCommand(TV *tv){this-＞tv=tv；)；
}；
void main(){
Light light；    TV tv；//創(chuàng)建電燈和電視對(duì)象
LightCommand lightCommand (&light)；
TVCommand tVCommand(&tv)；
RemoteController remoteController；
remoteController. setCommand(0，  (4)  )；  //設(shè)置按鈕0的命令對(duì)象
…//此處省略設(shè)置按鈕1、按鈕2和按鈕3的命令對(duì)象代碼
}
本題中，應(yīng)用命令模式能夠有效讓類  (5)  和類  (6)  、類  (7)  之間的耦合性降至最小。