(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素。下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取i到j之间的一个数，包括i和j。

 

 (2)随机化快速排序是否能够消除最坏情况的发生? (10)。(是或否)

请阅读以下技术说明、类图及C++代码，根据要求将(1)～(7)空缺处的内容填写完整。

  [说明]

 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器面板如图1-16所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如图1-17所示。

 在图1-17中，类RomoteController的方法onPressButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight (int degree)方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel(int channel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。

 [C++代码]

 本试题应用命令模式能够有效让类(5)和类(6)、类(7)之间的耦合性降至最小。

请阅读以下技术说明、类图及Java代码，根据要求将(1)～(7)空缺处的内容填写完整。

1.  [说明]

 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器面板如图1-18所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如图1-19所示。

 在图1-19中，类RomoteController的方法onPressButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号；Command接口中on和off方法分别用于控制电器的开与关；Light中turnLight (int degree)方法用于调整电灯灯光的强弱，参数degree值为0时表示关灯，值为100时表示开灯并且将灯光亮度调整到最大；TV中setChannel(int channel)方法表示设置电视播放的频道，参数channel值为0时表示关闭电视，为1时表示开机并将频道切换为第1频道。

 [Java代码]

 本试题应用命令模式能够有效让类(5)和类(6)、类(7)之间的耦合性降至最小。

(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素。下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取i到j之间的一个数，包括i和j。

 (2)随机化快速排序是否能够消除最坏情况的发生? (10)。(是或否)

(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度(用 O记号)。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。

 (2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7)。 (最佳、平均、最坏)

请认真阅读以下函数说明、图及C程序，将程序段中(1)～(7)空缺处的语句填写完整。

  [说明]

 一般的树结构常采用孩子—兄弟表示法表示，即用二叉链表做树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，如图1-15(a)所示树的孩子—兄弟表示如图1-15(b)所示。

 函数LevelTraverse()的功能是对给定树进行层序遍历。例如，对如图1-15所示的树进行层序遍历时，节点的访问次序为D B A E F P C。

 对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表1-11所示。

 Bool、Status类型定义如下：

 树的二叉链表节点定义如下：

[C函数程序]

在系统的需求分析阶段，可以使用用例对系统需求建模。用例可以使用UML的用例图来表示。请分别用100字以内的文字解释UML用例图中扩展用例和抽象用例的内涵。

阅读以下算法说明，根据要求回答问题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)～(3)的内容填写完整。伪代码中的主要变量说明如下。

 A：待排序数组

 p,r：数组元素下标，从p到r

 q：划分的位置

 x：枢轴元素

 i：整型变量，用于描述数组下标。下标小于或等于i的元素的值，小于或等于枢轴元素的值

 j：循环控制变量，表示数组元素下标

序列图是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动，即显示了一组对象和由这组对象发送和接收的消息。如图2-26所示是用户成功开锁的序列图。依据上述说明中给出的词语，将图2-26中的(1)～(5)空缺处补充完整。

阅读以下某门禁控制系统的技术说明，根据要求回答问题1～问题3。

 [说明]

 门禁系统是楼宇安防系统的重要组成部分，也是大厦智能化管理的体现。其工作过程是，如果在入口处的读卡器上刷卡，锁控器(LockController)接收读卡器(FingerReader)的读卡信息并进一步识别，如果为有效卡，则触发控制电控锁(Lock)的继电器，让持卡人通过。锁控器还会将这些读卡及进出事件存储起来，并将相关事件记录传送给上位机。每个锁控器管理1～4个门，每5～8个锁控器接入1条RS-485总线，并转换成RS-232方式与管理主机的串行口。对锁控器进行相关设置后，允许它脱机独立对门禁点进行控制，管理主机或通信线路故障都不会影响它的正常运行。在普通场合通常会设置1个出门按钮，允许已进入的人员按动此按钮以打开电控锁；而对于一些重要场合通常会在门的内外安装两个读卡器，进出门时都需按预设方式进行刷卡。

 门禁系统中的每个电控锁都有一个唯一的编号。锁的状态有两种：“已锁住”和“未锁住”。在管理主机上可以设置每把锁的安全级别及用户的开锁权限。只有当用户的开锁权限大于或等于锁的安全级别并且锁处于“已锁住”状态时，才能将锁打开。用户的感应卡信息、开锁权限及锁的安全级别都保存在管理主机的数据库中。表2-19给出了门禁系统主要组成部件的作用。

软件开发公司A承担了该门禁控制系统的开发任务，其开发小组采用根据问题领域的模型建立系统结构的面向对象方法完成该系统的设计，系统中的类及类之间的关系用UML类图表示。

如图2-25所示是门禁控制系统的一个不完整类图，根据题干说明中给出的术语，请给出类Lock的主要属性。

在(2)～(5)空缺处填入对应关系的属性，完成逻辑结构设计。(参见本题[附])