假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度（用 O记号)

字以内的文字解释UML用例图中扩展用例和抽象用例的内涵。

请阅读以下技术说明、类图及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代码，将应填入(n)处的字句写在对应栏内。

【说明】

已知某类库开发商捉供了一套类库，类库中定义了Application类和Document类，它们之间的关系如下图所示，其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。

当开发一个具体的应用程序时，开发者需要分别创建自己的Application和Document子类，例如上图中的类MyApplication和类MyDocument，并分别实现Application和 Document类中的某些方法。

已知Application类中的openDocument方法采用了模板方法(Template Method)设计模式，该方法定义了打开文档的每一个主要步骤，如下所示：

1．首先检查文档是否能够被打开，若不能打开，则给出出错信息并返回；

2．创建文档对象；

3．通过文档对象打开文档；

4．通过文档对象读取文档信息；

5．将文档对象加入到Application的文档对象集合中。

【Java代码】

abstract class Document{

public void save(){/*存储文档数据，此处代码省略*/ )

public void open(String docName){ /*打开文档，此处代码省略*/)

public void close(){ /*关闭文档，此处代码省略*/)

public abstract void read(String docName)；

}；

abstract class Appplication{

private Vector＜(1)＞ docs； /*文档对象集合*/

public boolean canOpenDocument(String docName){

/*判断是否可以打开指定文档，返回真值时表示可以打开，

返回假值表示不可打开，此处代码省略*/

}

public void addDocument(Document aDocument){

/*将文档对象添加到文档对象集合中*/

docs．add((2))；

}

public abstract Document doCreateDocument()；/*创建一个文档对象*/

public void openDocument(String docName){/*打开文档*/

if ((3)) {

System．out．println(“文档无法打开!”)；

return；

}

(4) adoc＝(5)；

(6)；

(7)；

(8)；

}

}；

阅读以下说明和C代码，将应填入(n)处。

[说明]

在一公文处理系统中，开发者定义了一个公文结构OfficeDoc，其中定义了公文应该具有的属性(字段)。当公文的内容或状态发生变化时，与之相关联的DocExplorer结构的值都需要发生改变。一个OfficeDoc结构能够关联一组DocExplorer结构。当OfficeDoc结构的内容或状态发生变化时，所有与之相关联的DocExplorer结构都将被更新，这种应用被称为观察者模式。以下代码采用C语言实现，能够正确编译通过。

[C代码]

include ＜stdio.h＞

define OBS_MAXNUM 20 /*一个OfficeDoc变量最多能够关联的*/

/*DoeExplorer变量的个数*/

typedef void((1))(struct OfficeDoc*,street DocExplorer*);

struct DocExplorer{

func update;/* DocExplorer结构采用的更新函数*/

/*其他的结构字段省略*/

};

struct OfficeDoc{

(2) myObs[OBS_MAXNUM];

/*存储所有与OfficeDoc相关联的DoeExplorer结构指针*/

int index;/*与OfficeDoc结构变量相关联的DocExplorer结构变量的个数*/

};

void attach(struet OfficeDoc *doc, struet DocExplorer *ob){

/*关联Obersver结构ob与OfficeDoe结构doc*/

int loop=0;

if(doc-＞index ＞=OBS_MAXNUM || b==NULL) return;

for(loop=0; loop ＜doc-＞index; loop++)

if(doc-＞myObs[loop]==ob)return;

doc-＞myObs[doe-＞index]=ob;

doc-＞index++;

)

void detach(struct OfficeDoc *doc, struct DocExplorer *ob){

/*解除doc结构与ob结构间的关系*/

int loop;

if(ob==NULL)return;

for(loop=0; loop ＜doc-＞index; loop6++){

if(doc-＞myObs[loop]==ob){

if(loop＜=doc-＞index-2)

doe-＞myObs[loop]=doc-＞myObs[ (3) ];

doc-＞myObs[doe-＞indox-1]=NULL;

doe-＞index--;

break;

}

}

}

void updatel(struct OfficeDoc *doc,struct DocExplorer *ob){

/*更新ob结构的值，更新代码省略*/

}

void update2(stmct OfficeDoc *doc, struct DocExplorer *ob){

/*更新ob结构的值，更新代码省略*/

}

void notifyObs(struet OfficeDoc *doc){

/*当doc结构的值发生变化时，通知与之关联的所有DocExplorer结构变量*/

int loop;

for(loop=0; loop ＜doc-＞index; loop++){

(doc-＞myObs[loop])-＞update((4));

}

}

void main(){

stmct OfficeDoc doc;/*定义一OfficeDoc变量*/

struct DocExplorer explorer1, explorer2;/*定义两个DocExplorer变量*/

/*初始化与OfficeDoc变量相关的DocExplorer变量个数为0*/

doc.index=0;

explorer1.update=update1;/*设置explorer1变量的更新函数*/

explorer2.update=update2;/*设置explorer2变量的更新函数*/

attaeh(&doc,&explorer1);/*关联explorer1与doc对象*/

attach(&doc,&explorer2);/*关联explorer2与doc对象*/

/*其他代码省略*/

(5);/*通知与OfficeDoc相关的所有DocExplorer变量*/

return;

}

明这样做的理由。

阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。

[说明]

某公司计划与客户通过Internet交换电子邮件和数据(以下统一称为“消息”)。为保障安全，在对传输的数据进行加密的同时，还要对参与通信的实体进行身份认证。因此，需同时使用对称与非对称密钥体系。图3-1描述了接收者B使用非对称密钥体系对发送者A进行认证的过程。

[图3-1]

图3-2描述了发送和接收消息的过程，其中的认证过程使用了图3-1中的方法。图3—1中的方框a和方框b与图3-2中的方框a和方框b相同。

[图3-2]

图3-2中发送和接收消息的过程是：

1)发送者A使用与接收者B共享的对称密钥体系的密钥加密将要发送的消息。

2)为了实现身份认证，A使用与B共享的摘要算法生成消息摘要，并使用公钥密码体系把生成的消息摘要加密后发送给B(这里假设A和B都能通过安全的方法获得对方的公钥)。

3)B使用非对称密钥体系解密收到的消息摘要，使用与A共享的对称密钥体系的密钥解密加密后的消息，再使用与A共享的摘要算法针对解密后的消息生成消息摘要。

4)B对比自己生成的消息摘要与接收到的A发送的消息摘要是否相同，从而验证发送者A的身份。

请在下列选项中选择合适的答案，填入图3-1、图3-2的方框a和方框b。

B的公钥，B的私钥，摘要算法，A的私钥，A的公钥，会话密钥

联系1，联系2，联系3，……。

之处。

阅读以下说明和C函数，将(1)～(5)空缺处的字句填写完整。

[说明]

计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式“46+5*120-37)”的后缀表达式形式为“46 5 120 37-*+”。

计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式“46 5 120 37-*+”的计算过程如下：

a．依次将46、5、120、37压入栈中；

b．遇到“-”，取出37、120，计算120-37=83，将其压入栈中；

c．遇到“*”，取出83、5，计算5×83=415，将其压入栈中；

d．遇到“+”，取出415、46，计算46+415=461，将其压入栈中；

e．表达式结束，则计算过程完成。

函数computing(char expr[],int*result)的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组 expr)的值，并通过参数result返回该值。函数的返回值为-1/0，分别表示表达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加(“+”)、减(“-”)、乘(“*”)、除(“＼”)。

函数computing中所用栈的基本操作的函数原型说明如下。

● void InitStack(STACK*s)：初始化栈。

● void Push(STACK*s,int e)：将一个整数压栈，栈中元素数目增1。

● void Pop(STACK*s)：栈顶元素出栈，栈中元素数目减1。

● int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

● int IsEmpty(STACKs)：若s是空栈，则返回1；否则返回0。

[C函数]