return PARTITION(A,p,r); } 2）随机化快速排序是否能够消除最坏情况的发生？ （10） 。（是或否） 试题四分析
本题考查算法的设计与分析技术。 问题1考查快速排序算法的伪代码，快速排序最核心的处理是进行划分，即PARTITION操作，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图4-1所示： 每次先随机获得一个元素，将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。
参考答案【问题1】（1）A[i + 1] （2）A[r] （3）i + 1 注：空（1）和空（2）答案可以互换 【问题2】
图4-1 PARTITION操作 在问题1给出的伪代码中，当循环结束后，A[p..i]中的值应小于等于枢轴元素值x，而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素，因此A[r]与A[i+1]交换，得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置，因此返回值为i+1。
问题2考查的是快速排序算法的时间复杂度分析。当每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式
【问题3】
（8）A[i] （9）A[r] （10）否 注：空（8）和空（9）答案可以互换 试题五（共15分）
阅读下列说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】
栈（Stack）结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶（Stack Top），而另一端称为栈底（Stack Bottom）。栈的基本操作包括：创建栈（NewStack）、 判断栈是否为空（IsEmpty）、判断栈是否已满（IsFull）、获取栈顶数据（Top）、压栈/入栈（Push）、弹栈/出栈（Pop）。
当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各 数据项不必连续存储（如下图所示）。
得到时间复杂度为 当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式
得到时间复杂度为
析较为复杂，我们可以假设数组每次划分为算递归式
平均情况的分
此时时间复杂度可以通过计
得到时间复杂度为
因此在平均情况下快速排序仍然有较好的性能，时间复杂度为
当所有的n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为n-1和0的两个子数组，属于最坏情况。
问题3中，由于随机化的快速排序的划分调用了传统的快速排序算法的PARTITION操作，而传统的划分每次以数组的最后一个元素作为枢轴元素，因此，随机化的划分操作中
以下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){ //获取栈顶数据。若栈为空，则返回机器可表示的最36
小整数 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(\Pop(myStack); } return 0; } 以上程序运行时的输出结果为： （5） 试题五分析
本题考查基本程序设计能力。
堆栈是软件设计中常使用的一种经典数据结构，题目给出的操作都是任何堆栈都具有的基本操作。堆栈的存储结构通常采用数组或链表形式，但无论采用哪种存储结构，整体上呈现的是后进先出的特点，即后进入堆栈的元素先出栈。题目中给出的结构体Stack仅包含一个指向栈顶元素的指针（栈顶指针），当且仅当堆栈中没有元素时，该指针应为NULL。当向堆栈中增加元素时，首先需要动态创建该元素的存储区，并且栈顶指针指向该元素。当元素出栈时，栈顶指针则指向出栈元素的紧前一个元素。结构体List表示栈中元素，包
含对应的数据和指向紧上次入栈的元素指针next，对于第1个入栈的元素，指针next为NULL,而其他元素中的指针next一定不为NULL。
C语言中，如果用一个整数型表达式表示条件判定语句的话，该表达式的值为0则表示假，非0表示真。从给定程序代码可以看出，对于函数IsEmpty，若其返回值为0则表示堆栈非空，否则表示堆栈为空。因此，对于空（1），必须填写可表示堆栈为空的判定语句：S==NULL||S->pTop==NULL，这2个条件中只要有1个条件满足，则表明堆栈S为空。对于空（2），此时需要返回栈顶元素中的数据，而栈顶元素为S->pTop，所以对应的数据应该为S->pTop->data。
对于压栈操作Push，在为新元素获取存储空间后，必须调整堆栈的栈顶指针S->pTop指向新元素的存储区，即S->pTop=newNode。对于弹栈操作Pop，弹出栈顶元素lastTop后，需要调整栈顶指针，使其指向被弹出元素的下一个元素，即S->pTop=S->pTop->next，或S->pTop=lastTop->next。
对于main函数中宏MD(x)，在程序预编译时会按字符替换为 \。所以在main函数中，首先入栈的元素为\，即整数4，第2个入栈的元素为\，即整数8，其次将8弹出，然后再将\入栈，C语言中 \优先级高于\，所以此时入栈者为整数24，而此时堆栈中有2个元素，其中栈顶元素为24，下一元素为4。最后，若堆栈非空，则循环完成显示栈顶元素的值、弹出栈顶元素的操作，直至堆栈为空。所以程序执行时的输出内容为\。
参考答案
（1）S == NULL || S->pTop == NULL （2）S->pTop->data （3）newNode （4）S->pTop->next，或 lastTop->next （5）24 4 试题六（共15分）
阅读下列说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】
已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如左下所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如右下所示。
右上图中，类RomoteController的方法onPressButton（int button）表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight（int degree）方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel（int channel）方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。
【C++代码】 class Light{ //电灯类 public: void trunLight(int degree){ //调整灯光亮度，0表示关灯，100表示亮度最大}; }; class TV{ //电视机类 37
public: void setChannel(int channel){//调整电视频道，0表示关机，1表示开机并切换到1 频道}; }; class Command{ //抽象命令类 public: virtual void on()=0; virtual void off()=0; }; class RemoteController{ //遥控器类 protected: Command *commands[4]; //遥控器有4个按钮，按照编号分别对应4个Command对象 public: void onPressButton(int button){ //按钮被按下时执行命令对象中的命令 if(button % 2 == 0)commands[button]->on(); else commands[button]->off(); } void setCommand(int button,Command * command){ （1） = command; //设置每个按钮对应的命令对象 } }; class LightCommand : public Command{ //电灯命令类 protected: Light *light; //指向要控制的电灯对象 public: void on(){light->trunLight(100);}; void off(){light->（2）;}; LightCommand(Light * light){this->light = light;}; }; class TVCommand : public Command{ //电视机命令类 protected: TV * tv; //指向要控制的电视机对象 public: void on(){tv->（3）;}; void off(){tv->setChannel(0);}; TVCommand(TV * tv){ this->tv = tv; }; }; void main(){ Light light; TV tv; //创建电灯和电视对象 LightCommand lightCommand(&light); TVCommand tvCommand(&tv); RemoteController remoteController; remoteController.setCommand(0, （4）); //设置按钮0的命令对象 ?//此处省略设置按钮1、按钮2和按钮3的命令对象代码 } 本题中，应用命令模式能够有效让类 （5）和类 （6 、类 （7） 之间的耦合性降至最小。
试题六分析
本题考查的是设计模式中的命令模式。
设计时，为了保证遥控器和家用电器之间的独立性，定义了Command类，当用户按下遥控器上的按钮时，触发Command上的On或者Off方法，因此，一对按钮分别对应一个Command对象。题目中的LightCommand以及与TVCommand分别为Command的子类，该子类用于控制实际的Light以及TV对象，将On与Off方法委托给Light以及TV实现。空（1）表示要设置遥控器上按钮控制的对象，其参数传递的是某一个命令对象，因此只需将该命令对象存储下来即可；空（2）表示关闭电灯，根据说明，关闭电灯的方法为turnLight(0)；空（3）表示打开电视机，因此需要调用打开电视的方法。空（4）表示将按钮0和相应的Command对象相关联，根据题目描述，按钮0用于控制灯或者电视，因此，应该设置灯或者电视的命令对象。本题中应用命令模式的目的是为了使为了让遥控器和类Light与TV之间的耦合性降至最低。
参考答案
（1）commands[button] （2）trunLight(0) （3）setChannel(1) （4）&lightCommand （5）RemoteController （6）Light （7）TV 试题七（共15分）
阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】
已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图（a）所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如下图（b）所示。
（点击查看大图）（a） 38
图（b）中，类RomoteController的方法onPressButton（int button）表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight（int degree）方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel（int channel）方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。
【Java代码】 class Light{ //电灯类 public void trunLight(int degree){ //调整灯光亮度，0表示关灯，100表示亮度最大} }; class TV{ //电视机类 public void setChannel(int channel){// 0表示关机，1表示开机并切换到1频道 } }; interface Command{ //抽象命令类 void on(); void off(); }; class RemoteController{ //遥控器类 protected Command []commands = new Command[4]; //遥控器有4个按钮，按照编号分别对应4个Command对象
public void onPressButton(int button){ //按钮被按下时执行命令对象中的命令 if(button % 2 == 0)commands[button].on(); else commands[button].off(); } public void setCommand(int button, Command command){ （1） = command; //设置每个按钮对应的命令对象 } }; 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.setChannel(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();//创建电灯和电视对象 LightCommand lightCommand = new LightCommand(light); TVCommand tvCommand = new TVCommand(tv); RemoteController remoteController = new RemoteController(); //设置按钮和命令对象 remoteController.setCommand(0, （4）); ?//此处省略设置按钮1、按钮2和按钮3的命令对象代码 } } 本题中，应用命令模式能够有效让类 （5） 和类 （6） 、类 （7）之间的耦合性降至最小。
试题七分析
本题考查的是设计模式中的命令模式。
在设计时，为了保证遥控器和家用电器之间的独立性，定义了Command类，当用户按下遥控器上的按钮时，触发Command上的On或者Off方法，因此，一对按钮分别对应一个Command对象。题目中的LightCommand以及与TVCommand分别为Command的子类，该子类用于控制实际的Light以及TV对象，将On与Off方法委托给Light以及TV实现。空（1）表示要设置遥控器上按钮控制的对象，其参数传递的是某一个命令对象，因此只需将该命令对象存储下来即可；空（2）表示关闭电灯，根据说明，关闭电灯的方法为turnLight(0)；空（3）表示打开电视机，因此需要调用打开电视的方法。空（4）表示将按钮0和相应的
39
Command对象相关联，根据题目描述，按钮0用于控制灯或者电视，因此，应该设置灯或者电视的命令对象。本题中应用命令模式的目的是为了使为了让遥控器和类Light与TV之间的耦合性降至最低。
参考答案
（1）commands[button] （2）trunLight(0) （3）setChannel(1) （4）lightCommand （5）RemoteController （6）Light （7）TV
40
相关推荐：
loading