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】（5分）
（1）假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。
最佳情况为（4），平均情况为（5），最坏情况为（6）。
（2）假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况？
（7）。
（最佳、平均、最坏）
【问题3】（4分）
（1）待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。
有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码—利用原有的快速排序的划分操作，请填充其中的空缺处。
其中，RANDOM（i,j）表示随机取i到j之间的一个数，包括i和j。
RANDOMIZED-PARTITION（A,p,r）{
i=RANDOM（p,r）;
交换（8）和（9）;//注：
空（8）和空（9）答案可互换，但两空全部答对方可得分
returnPARTITION（A,p,r）;
}
（2）随机化快速排序是否能够消除最坏情况的发生？
（10）。
（是或否）
从下列的3道试题（试题五至试题七）中任选1道解答。
如果解答的试题数超过1道，则题号小的1道解答有效。
试题五（共15分）
阅读下列说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
栈（Stack）结构是计算机语言实现中的一种重要数据结构。
对于任意栈，进行插入和删除操作的一端称为栈顶（StackTop），而另一端称为栈底（StackBottom）。
栈的基本操作包括：
创建栈（NewStack）、判断栈是否为空（IsEmpty）、判断栈是否已满（IsFull）、获取栈顶数据（Top）、压栈/入栈（Push）、弹栈/出栈（Pop）。
当设计栈的存储结构时，可以采取多种方式。
其中，采用链式存储结构实现的栈中各数据项不必连续存储（如图5-1）。
以下C代码采用链式存储结构实现一个整数栈操作。
【C代码】
typedefstructList{
intdata;//栈数据
structList*next;//上次入栈的数据地址
}List;
typedefstructStack{
List*pTop;//当前栈顶指针
}Stack;
Stack*NewStack（）{return（Stack*）calloc（1,sizeof（Stack））;}
intIsEmpty（Stack*S）{//判断栈S是否为空栈
if（
（1））return1;
return0;
}
intTop（Stack*S）{//获取栈顶数据。
若栈为空，则返回机器可表示的最小整数
if（IsEmpty（S））returnINT_MIN;
return
（2）;
}
voidPush（Stack*S,inttheData）{//将数据theData压栈List*newNode;
newNode=（List*）calloc（1,sizeof（List））;
newNode->data=theData;newNode->next=S->pTop;S->pTop=（3）;
}
voidPop（Stack*S）{//弹栈List*lastTop;
if（IsEmpty（S））return;
lastTop=S->pTop;S->pTop=（4）;free（lastTop）;
}
#defineMD（a）a<<2
intmain（）{
inti;
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）;
}
return0;
}
以上程序运行时的输出结果为：
（5）
试题六（共15分）
阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。
遥控器如图6-1所示。
该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。
由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。
现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如6-2所示。
图6-2中，类RomoteController的方法onPressButton（intbutton）表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight（intdegree）方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel（intchannel）方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。
【C++代码】
classLight{//电灯类
public:
voidturnLight（intdegree）{//调整灯光亮度，0表示关灯，100表示亮度最大};
};
classTV{//电视机类
public:
voidsetChannel（intchannel）{//调整电视频道，0表示关机，1表示开机并切换到1频道};
};
classCommand{//抽象命令类
public:
virtualvoidon（）=0;
virtualvoidoff（）=0;
};
classRemoteController{//遥控器类
protected:
Command*commands[4];//遥控器有4个按钮，按照编号分别对应4个Command对象
public:
voidonPressButton（intbutton）{//按钮被按下时执行命令对象中的命令
if（button%2==0）commands[button]->on（）;
elsecommands[button]->off（）;
}
voidsetCommand（intbutton,Command*command）{
（1）=command;//设置每个按钮对应的命令对象
}
};
classLightCommand:
publicCommand{//电灯命令类
protected:
Light*light;//指向要控制的电灯对象
public:
voidon（）{light->turnLight（100）;};
voidoff（）{light->
（2）;};
LightCommand（Light*light）{this->light=light;};
};
classTVCommand:
publicCommand{//电视机命令类
protected:
TV*tv;//指向要控制的电视机对象
public:
voidon（）{tv->（3）;};
voidoff（）{tv->setChannel（0）;};
TVCommand（TV*tv）{this->tv=tv;};
};
voidmain（）{
Lightlight;TVtv;//创建电灯和电视对象
LightCommandlightCommand（&light）;
TVCommandtvCommand（&tv）;
RemoteControllerremoteController;
remoteController.setCommand（0,（4））;//设置按钮0的命令对象
…//此处省略设置按钮1、按钮2和按钮3的命令对象代码
}
本题中，应用命令模式能够有效让类（5）和类（6）、类（7）之间的耦合性降至最小。
试题七（共15分）
阅读下列说明和Java代码，将应填入（n）处的字句写在答题纸的对应栏内。
【说明】
已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。
遥控器如图7-1所示。
该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。
由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。
现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如7-2所示。
图7-2中，类RomoteController的方法onPressButton（intbutton）表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight（intdegree）方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel（intchannel）方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。
【Java代码】
classLight{//电灯类
publicvoidturnLight（intdegree）{//调整灯光亮度，0表示关灯，100表示亮度最大}
};
classTV{//电视机类
publicvoidsetChannel（intchannel）{//0表示关机，1表示开机并切换到1频道}
};
interfaceCommand{//抽象命令类
voidon（）;
voidoff（）;
};
classRemoteController{//遥控器类
protectedCommand[]commands=newCommand[4];
//遥控器有4个按钮，按照编号分别对应4个Command对象
publicvoidonPressButton（intbutton）{
//按钮被按下时执行命令对象中的命令
if（button%2==0）commands[button].on（）;
elsecommands[button].off（）;
}
publicvoidsetCommand（intbutton,Commandcommand）{
（1）=command;//设置每个按钮对应的命令对象
}
};
classLightCommandimplementsCommand{//电灯命令类
protectedLightlight;//指向要控制的电灯对象
publicvoidon（）{light.turnLight（100）;};
publicvoidoff（）{light.
（2）;};
publicLightCommand（Lightlight）{this.light=light;};
};
classTVCommandimplementsCommand{//电视机命令类
protectedTVtv;//指向要控制的电视机对象
publicvoidon（）{tv.（3）;};
publicvoidoff（）{tv.setChannel（0）;};
publicTVCommand（TVtv）{this.tv=tv;};
};
publicclassrs{
publicstaticvoidmain（String[]args）{
Lightlight=newLight（）;TVtv=newTV（）;//创建电灯和电视对象
LightCommandlightCommand=newLightCommand（light）;
TVCommandtvCommand=newTVCommand（tv）;
RemoteControllerremoteController=newRemoteController（）;
//设置按钮和命令对象
remoteController.setCommand（0,（4））;
…//此处省略设置按钮1、按钮2和按钮3的命令对象代码
}
}
本题中，应用命令模式能够有效让类（5）和类（6）、类（7）之间的耦合性降至最小。
升级会员 