试题二
阅读下列说明，回答问题1至问题3，将解答填入对应栏内。
【说明】
某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。
【需求分析结果】
1．登记参赛。球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。
2．安排球队的训练信息。比赛组织者为球队提供了若干块场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如下表所示。系统记录训练场地安排的信息。

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



4．所有球员、教练和裁判可能出现重名情况。
【概念模型设计】
根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如下：
1．实体联系图(图2-1)



2．关系模式
教练(教练编号，姓名，年龄)
队员(队员编号，姓名，年龄，身高，体重，  (a)  )
球队(球队名称，代表地区，成立时间，  (b)  )
场地(场地名称，场地规模，位置)
训练记录(  (c)  )
裁判(裁判编号，姓名，年龄，级别)
比赛记录(  (d)  )
【问题1】
根据问题描述，补充联系及其类型，完善实体联系图2-1。(联系及其类型的书写格式参照教练与球队之间的联系描述，联系名称也可使用联系1、联系2、……)
【问题2】
根据实体联系图，填充关系模式中的a.、b.、c.和d.，并给出训练记录和比赛记录关系模式的主键和外键。
【问题3】
如果考虑记录一些特别资深的热心球迷的情况，每个热心球迷可能支持多个球队。热心球迷包括：姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改上图的实体联系图，给出修改后的关系模式(仅给出增加的关系模式描述)。

试题三
阅读下列说明和图，回答问题1至问题4，将解答填入对应栏内。
【说明】
某汽车停车场欲建立一个信息系统，已经调查到的需求如下：
1．在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下：

2．当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。
3．在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。
4．当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。
5．系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示“车位已满”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。
根据上述描述，采用面向对象方法对其进行分析与设计，得到了如下表所示的类/用例/状态列表、下图(a)所示的用例图、图(b)所示的初始类图以及图(c)所示的描述入口自动栏杆行为的UML状态图。




【问题1】
根据说明中的描述，使用上页表给出的用例名称，给出图(a)中U1、U2和U3所对应的用例。
【问题2】
根据说明中的描述，使用上页表给出的类的名称，给出图(b)中的，A～D所对应的类。
【问题3】
根据说明中的描述，使用上页表给出的状态名称，给出图(c)中S1~S4所对应的状态。
【问题4】
简要解释图(a)中用例U1和U3之间的extend关系的内涵。

试题四
阅读下列说明，回答问题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，rl)；
交换  (8)  和  (9)  ；//注：空(8)和空(9)答案可互换，但两空全部答对方可得分
return PARTITION (A，p，r)；
}
(2)随机化快速排序是否能够消除最坏情况的发生?  (10)  。(是或否)