2008年上半年 软件设计师 下午试题

试题二（共15分）
阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。
【需求分析结果】

1．登记参赛。球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。

2．安排球队的训练信息。比赛组织者为球队提供了若干块场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如下表所示。系统记录训练场地安排的信息。
 

球队名称	场地名称	训练时间
解放军	一号球场	2008-06-09 14:00－18:00
解放军	一号球场	2008-06-12 09:00－12:00
解放军	二号球场	2008-06-11 14:00－18:00
山西	一号球场	2008-06-10 09:00－12:00

3．安排比赛。该赛事聘请专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则，首先分组，然后根据球队、场地和裁判情况，安排比赛（每场比赛的对阵双方分别称为甲队和乙队）。记录参赛球队名称、比赛时间、比分、比赛场地等信息，如下表所示。
A组：
 

甲队——乙队	场地名称	比赛时间	裁判	比分
解放军——北京	一号球场	2008-06-17 15:00	李大明
天津——山西	一号球场	2008-06-17 19:00	胡学梅

   
B组：
 

甲队——乙队	场地名称	比赛时间	裁判	比分
上海——安徽	二号球场	2008-06-17 15:00	丁鸿平
山东——辽宁	二号球场	2008-06-17 19:00	郭爱琪

  
 
4．所有球员、教练和裁判可能出现重名情况。
【概念模型设计】

根据需求阶段收集的信息，设计的实体联系图和关系模式（不完整）如下：
1．实体联系图（图2-1）
   
2．关系模式
教练（教练编号，姓名，年龄）
队员（队员编号，姓名，年龄，身高，体重， （a） ）
球队（球队名称，代表地区，成立时间， （b） ）
场地（场地名称，场地规模，位置）
训练记录（ （c） ）
裁判（裁判编号，姓名，年龄，级别）
比赛记录（ （d） ）

【问题1】
根据问题描述，补充联系及其类型，完善实体联系图2-1。（联系及其类型的书写格式参照教练与球队之间的联系描述，联系名称也可使用联系1、联系2、……）

【问题2】
根据实体联系图，填充关系模式中的（a）、（b）、（c）和（d），并给出训练记录和比赛记录关系模式的主键和外键。

【问题3】
如果考虑记录一些特别资深的热心球迷的情况，每个热心球迷可能支持多个球队。热心球迷包括：姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改上图的实体联系图，给出修改后的关系模式（仅给出增加的关系模式描述）。

试题三（共15分）
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。
【说明】
某汽车停车场欲建立一个信息系统，已经调查到的需求如下：

1．在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下：
   
2．当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。

3．在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。

4．当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。

5．系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示"车位已满"信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。
根据上述描述，采用面向对象方法对其进行分析与设计，得到了如下表所示的类/用例/状态列表、下图（a）所示的用例图、图（b）所示的初始类图以及图（c）所示的描述入口自动栏杆行为的UML状态图。
类/用例/状态列表
 

用 例 名	说 明	类 名	说 明	状 态 名	说 明
Car entry	汽车进入停车场	CentralComputer	停车场信息系统	Idle	空闲状态，汽车可以进入停车场
Car exit	汽车离开停车场	PaymentMachine	付款机器	Disable	没有车位
Report Statistics	记录停车场的相关信息	CarPark	停车场，保存车位信息	Await Entry	等待汽车进入
		Barrier	自动护栏	Await Ticket Take	等待打印停车卡
Car entry when full	没有车位时，汽车请求进入停车场	EntryBarrier	入口的护栏	Await Enable	等待停车场内有空闲车位
		ExitBarrier	出口的护栏

       

【问题1】
根据说明中的描述，使用上页表给出的用例名称，给出图（a）中U1、U2和U3所对应的用例。

【问题2】
根据说明中的描述，使用上页表给出的类的名称，给出图（b）中的A～D所对应 的类。

【问题3】
根据说明中的描述，使用上页表给出的状态名称，给出图（c）中S1～S4所对应的状态。

【问题4】
简要解释图（a）中用例U1和U3之间的extend关系的内涵。

试题四（共15分）
阅读下列说明，回答问题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】
下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。
A：待排序数组
p, r：数组元素下标，从p到r
q：划分的位置
x：枢轴元素
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
j：循环控制变量，表示数组元素下标
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）答案可互换，但两空全部答对方可得分
return  （3）
}

【问题2】
（1） 假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为 （4） ，平均情况为 （5） ，最坏情况为 （6） 。
（2） 假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况？ （7） 。（最佳、平均、最坏）

【问题3】
（1）待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码--利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM（i，j）表示随机取i到j之间的一个数，包括i和j。
RANDOMIZED-PARTITION(A,p,r){
i = RANDOM(p,r);
交换  （8）  和 （9） ;//注：空（8）和空（9）答案可互换，但两空全部答对方可得分
return PARTITION(A,p,r);
}
2）随机化快速排序是否能够消除最坏情况的发生？ （10） 。（是或否）

试题五（共15分）
阅读下列说明和C代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
栈（Stack）结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶（Stack Top），而另一端称为栈底（Stack Bottom）。栈的基本操作包括：创建栈（NewStack）、 判断栈是否为空（IsEmpty）、判断栈是否已满（IsFull）、获取栈顶数据（Top）、压栈/入栈（Push）、弹栈/出栈（Pop）。
当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储（如下图所示）。
  
以下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){ //获取栈顶数据。若栈为空，则返回机器可表示的最小整数
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("%d", Top(myStack));
Pop(myStack);
}
return 0;
}
以上程序运行时的输出结果为： （5）

试题六（共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{ //电视机类
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） 之间的耦合性降至最小。

试题七（共15分）
阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图（a）所示。该遥控器共有4个按钮，编号分别是0至3，按钮0和2能够遥控打开电器1和电器2，按钮1和3则能遥控关闭电器1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。 现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如下图（b）所示。
   

图（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）之间的耦合性降至最小。