1、计算机水平考试中级软件设计师 2008 年上半年下午真题及答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读以下说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某音像制品出租商店欲开发一个音像管理信息系统，管理音像制品的租借业务。需求如下：1系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。2系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。3根据客户所租借的音像制品的品种，会按天收取相应的费用。音像制品的最长租借周期为 1 周，每位客户
2、每次最多只能租借 6 件音像制品。4客户租借某种音像制品的具体流程如下。(1)根据客户提供的用户名和密码，验证客户身份。(2)若该客户是合法客户，查询音像制品信息文件，查看商店中是否还有这种音像制品。(3)若还有该音像制品，且客户所要租借的音像制品数小于等于 6 个，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。(4)系统计算租借费用，将费用信息保存在租借记录文件中并告知客户。(5)客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。5当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租
3、借某种音像制品。系统接收到预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流水号给该客户，并将信息保存在预约记录文件中。6客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。（分数：15.00）(1).【问题 1】图(a)中只有一个外部实体 E1。使用【说明】中的词语，给出 E1 的名称。（分数：3.75）_(2).【问题 2】使用【说明】中的词语，给出图(b)中的数据存储 D1D4 的名称。（分数：
4、3.75）_(3).【问题 3】数据流图(b)缺少了 3 条数据流，根据说明及数据流图(a)提供的信息，分别指出这 3 条数据流的起点和终点。 起点 终点（分数：3.75）_(4).【问题 4】在进行系统分析与设计时，面向数据结构的设计方法(如 Jackson 方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。（分数：3.75）_二、B试题二/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。【需求分析结果】1登记参赛。球队的信息。记录球队的名称、代表
5、地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。2安排球队的训练信息。比赛组织者为球队提供了若干块场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如下表所示。系统记录训练场地安排的信息。 球队名称 场地名称 训练时间解放军 一号球场 2008-06-09 14:00-18:00解放军 一号球场 2008-06-12 09:00-12:00解放军 二号球场 2008-06-11 14:00-1800山西 一
6、号球场 2008-06-10 09:00-12:003安排比赛。该赛事聘请专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则，首先分组，然后根据球队、场地和裁判情况，安排比赛(每场比赛的对阵双方分别称为甲队和乙队)。记录参赛球队名称、比赛时间、比分、比赛场地等信息，如下表所示。A 组： 甲队乙队 场地名称 比赛时间 裁判 比分解放军北京 一号球场 2008-06-17 15:00 李大明天津山西 一号球场 2008-06-17 19:00 胡学梅B 组：甲队乙队 场地名称 比赛时间 裁判 比分上海安徽 二号球场 2008-06-17 15:00 丁鸿平山
7、东辽宁 二号球场 2008-06-17 19:00 郭爱琪4所有球员、教练和裁判可能出现重名情况。【概念模型设计】根据需求阶段收集的信息，设计的实体联系图和关系模式(不完整)如下：1实体联系图(图 2-1)（分数：15.00）(1).【问题 1】根据问题描述，补充联系及其类型，完善实体联系图 2-1。(联系及其类型的书写格式参照教练与球队之间的联系描述，联系名称也可使用联系 1、联系2、)（分数：5.00）_(2).【问题 2】根据实体联系图，填充关系模式中的(a)、(b)、(c)和(d)，并给出训练记录和比赛记录关系模式的主键和外键。（分数：5.00）_(3).【问题 3】如果考虑记录一些特
8、别资深的热心球迷的情况，每个热心球迷可能支持多个球队。热心球迷包括：姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改上图的实体联系图，给出修改后的关系模式(仅给出增加的关系模式描述)。（分数：5.00）_三、B试题三/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某汽车停车场欲建立一个信息系统，已经调查到的需求如下：1在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下：2当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过
9、入口后，入口处的传感器通知系统发出命令，栏杆自动放下。3在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。4当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。5系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示“车位已满”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。根据上述描述，采用面向对象方法对其进行分析与设
10、计，得到了如下表所示的类/用例/状态列表、下图(a)所示的用例图、图(b)所示的初始类图以及图(c)所示的描述入口自动栏杆行为的 UML 状态图。B类/用例/状态列表/B（分数：15.00）(1).【问题 1】根据说明中的描述，使用上页表给出的用例名称，给出图(a)中 U1、U2 和 U3 所对应的用例。（分数：3.75）_(2).【问题 2】根据说明中的描述，使用上页表给出的类的名称，给出图(b)中的，AD 所对应的类。（分数：3.75）_(3).【问题 3】根据说明中的描述，使用上页表给出的状态名称，给出图(c)中 S1S4 所对应的状态。（分数：3.75）_(4).【问题 4】简要解释图
11、(a)中用例 U1 和 U3 之间的 extend 关系的内涵。（分数：3.75）_四、B试题四/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。1分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组 (可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1)中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。2递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。3合并：快速排序在原
12、地排序，故不需合并操作。（分数：15.00）(1).【问题 1】下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r: 数组元素下标，从 p 到 rq: 划分的位置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=Ar；i=p-1；for(j=p；jr-1；j+)if (Ajx)
13、i=i+1；交换 Ai和 Aj交U (1) /U和U (2) /U/注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return U(3) /U（分数：5.00）_(2).【问题 2】(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为U (4) /U，平均情况为U (5) /U，最坏情况为U (6) /U。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况?U (7) /U。(最佳，平均、最坏)（分数：5.00）_(3).【问题 3】(1)待排序数组是否能被较均匀地划分对快速排序的性能有
14、重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i，j)表示随机取 i 到 j 之间的一个数，包括 i 和 j。RANDOMIZED- PARTITION(A，p，r)i=RANDOM(p，rl)；交换U (8) /U和U (9) /U；/注：空(8)和空(9)答案可互换，但两空全部答对方可得分return PARTITION (A，p，r)；(2)随机化快速排序是否能够消除最坏情况的发生?U (10) /U。(是或否)（分数：5.00）_五、
15、B试题五/B(总题数：1，分数：15.00)1.【说明】 栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stock Top)，而另一端称为栈底(Stock Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。 当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示)。 （分数：15.00）_六、B试题六/B(总题数：1，分数：15.00)2.【
16、说明】 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如左下所示。该遥控器共有 4 个按钮，编号分别是 0 至 3，按钮 0 和 2 能够遥控打开电器 1和电器 2，按钮 1 和 3 则能遥控关闭电器 1 和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如右下所示。 （分数：15.00）_七、B试题七/B(总题数：1，分数：15.00)3.【说明】 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图(
17、a)所示。该遥控器共有 4 今按钮，编号分别是 0 至 3，按钮 0 和 2 能够遥控打开电器 1 和电器 2，按钮 1 和 3 则能遥控关闭电器 1 和电器 2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如下图(b)所示。 （分数：15.00）_计算机水平考试中级软件设计师 2008 年上半年下午真题答案解析(总分：105.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)阅读以下说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某音像制品出租商店欲开发一个
18、音像管理信息系统，管理音像制品的租借业务。需求如下：1系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。2系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。3根据客户所租借的音像制品的品种，会按天收取相应的费用。音像制品的最长租借周期为 1 周，每位客户每次最多只能租借 6 件音像制品。4客户租借某种音像制品的具体流程如下。(1)根据客户提供的用户名和密码，验证客户身份。(2)若该客户是合法客户，查询音像制品信息文件，查看商店中是否还有这种音像制品。(3)若还有该音像制品，且客户所要租借的音像制品数小于等于
19、 6 个，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。(4)系统计算租借费用，将费用信息保存在租借记录文件中并告知客户。(5)客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。5当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租借某种音像制品。系统接收到预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流水号给该客户，并将信息保存在预约记录文件中。6客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若
20、有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。（分数：15.00）(1).【问题 1】图(a)中只有一个外部实体 E1。使用【说明】中的词语，给出 E1 的名称。（分数：3.75）_正确答案：()解析：E1：客户(2).【问题 2】使用【说明】中的词语，给出图(b)中的数据存储 D1D4 的名称。（分数：3.75）_正确答案：()解析：D1：客户信息文件 D2：音像制品信息文件 D3：租借记录文件 D4：预约记录文件(3).【问题 3】数据流图(b)缺少了 3 条数据流，根据说明及数据流图(a)提供的信息，分别指出这 3 条数据
21、流的起点和终点。 起点 终点（分数：3.75）_正确答案：()解析：起点 终点E1 或 客户 4 或 创建新客户5 或 创建预约记录 E1 或 客户6 或 归还音像制品7 或 履行预约服务注意：3 条数据流无前后顺序区分。(4).【问题 4】在进行系统分析与设计时，面向数据结构的设计方法(如 Jackson 方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。（分数：3.75）_正确答案：()解析：面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。 试题一分析 本题考查数据流图的设计和应
22、用。 根据题目说明，本系统的外部实体仅仅涉及到客户，因此系统的顶层数据流图中 E1 应该对应为客户。题目的第二个问题在于识别系统中的数据文件 D1D4，根据 0 层数据流图中的数据文件与处理之间的关系分析可以得知： D1 为创建新客户加工的输出，并且为加工 1、6 和 7 的输入，再根据题目中的描述，客户信息文件与创建客户信息、预约、归还和履行预约都相关，因此 D1 便是客户信息文件。同理可分析出 D2 为音像制品信息文件、D3 为租借记录文件、D4 为预约记录文件。 图(b)中缺少了 3 条数据流，我们先检查顶层数据流图和。层数据流是否一致。首先，从顶层数据流图中可以看出，与 E1 直接相关
23、的数据流共有 9 条，而在 0 层数据流图中与 E1 直接关联的只有 7 条，因此可以直接断定，图(b)中至少缺少直接与 E1 相关的两条数据流：新客户创建请求和预约流水号。新客户创建请求通过创建新客户加工将客户的信息写入客户信息文件中，因此其起点和终点分别为：E1 和 4。同理，预约流水号的起点和终点为 5 和E1。在说明中，客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。因此，在客户归还和履行预约服务之间存在着数
24、据上的联系。 面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。二、B试题二/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。【需求分析结果】1登记参赛。球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。2安排球队的训练信息。比赛组织者为球队提
25、供了若干块场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如下表所示。系统记录训练场地安排的信息。 球队名称 场地名称 训练时间解放军 一号球场 2008-06-09 14:00-18:00解放军 一号球场 2008-06-12 09:00-12:00解放军 二号球场 2008-06-11 14:00-1800山西 一号球场 2008-06-10 09:00-12:003安排比赛。该赛事聘请专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则，首先分组，然后根据球队、场地和裁判情
26、况，安排比赛(每场比赛的对阵双方分别称为甲队和乙队)。记录参赛球队名称、比赛时间、比分、比赛场地等信息，如下表所示。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-
27、1)（分数：15.00）(1).【问题 1】根据问题描述，补充联系及其类型，完善实体联系图 2-1。(联系及其类型的书写格式参照教练与球队之间的联系描述，联系名称也可使用联系 1、联系2、)（分数：5.00）_正确答案：()解析：(对联系名称不做要求，但不能出现重名，图中的 M、N、P 也可表示为。) (2).【问题 2】根据实体联系图，填充关系模式中的(a)、(b)、(c)和(d)，并给出训练记录和比赛记录关系模式的主键和外键。（分数：5.00）_正确答案：()解析：(1)球队名称(2)教练编号(3)球队名称，场地名称，开始时间，结束时间(4)甲队，乙队，比赛时间，场地名称，比分，裁判，分组
28、 主键 (球队，开始时间)或(场地名称，开始时间)或(球队，结束时间)或(场地名称，结束时间)训练记录外键 球队名称，场地名称主键 (甲队，比赛时间)或(场地名称，比赛时间)或 (裁判，比赛时间)或(乙队，比赛时间)比赛记录外键 甲队，乙队，场地名称，裁判(3).【问题 3】如果考虑记录一些特别资深的热心球迷的情况，每个热心球迷可能支持多个球队。热心球迷包括：姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改上图的实体联系图，给出修改后的关系模式(仅给出增加的关系模式描述)。（分数：5.00）_正确答案：()解析： 关系模式： 热心球迷(球迷编号，姓名，住址，俱乐部) 支持球队(球迷编号，球
29、队) 试题二分析 本题考查数据库概念结构设计及向逻辑结构转换的基本方法。 此类题目要求认真阅读题目对现实问题的描述，经过分类、聚集、概括等方法，从中确定实体及其联系。题目已经给出了 4 个实体，需要根据需求描述，给出实体间的联系。 由“每个球队有一个教练负责管理球队，一个教练仅负责一个球队。”知球队与教练间为 1：1 联系；球队与队员之间应为 1：N 联系；多个球队使用多个训练场地，球队与场地之间为 M：M 联系；比赛是球队、场地与裁判之间的联系，一个球队会与同组的其他多个队之间比赛，有多个场地和裁决，一位裁判会对多场比赛判罚，一个场地会有多场比赛，涉及多个球队和裁判，因此球队、场地与裁判之间
30、的比赛关系为 M：N：P 联系。 根据补充后的 E-R 图，球队与球员之间的 1：N 联系应通过将 1 端实体(球员)的主码(球队名称)加入到 N 端实体(球员)对应的关系中来表达。这类联系也可通过独立的一个关系来表达，如球队球员(球队名称，队员编号)，这样会对查询增加多余的连接操作，因此一般不采用这种方法。 同样，球队与教练之间的 1：1 联系也应通过将一方的主码增加到另一方实体对应的关系中，来表达联系。 训练和比赛为多对多联系，只能独立成一个关系模式，取与该联系相关联的各实体的码及联系自有的属性构成。例如，比分和分组应该是比赛的属性，再加上球队、裁判、场地的码，即构成“比赛记录”的关系模式
31、。 同理，训练是球队和场地的多对多联系，训练开始时间和结束时间为训练的属性，加上球队的码和场地的码，构成“训练记录”关系模式。 球迷与球队之间为多对多联系，需新增球迷实体和球迷与球队之间的支持联系。三、B试题三/B(总题数：1，分数：15.00)阅读下列说明和图，回答问题 1 至问题 4，将解答填入对应栏内。【说明】某汽车停车场欲建立一个信息系统，已经调查到的需求如下：1在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下：2当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通过入口后，入
32、口处的传感器通知系统发出命令，栏杆自动放下。3在停车场内分布着若干个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。4当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。5系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示“车位已满”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。根据上述描述，采用面向对象方法对其进行分析与设计，得到了
33、如下表所示的类/用例/状态列表、下图(a)所示的用例图、图(b)所示的初始类图以及图(c)所示的描述入口自动栏杆行为的 UML 状态图。B类/用例/状态列表/B（分数：15.00）(1).【问题 1】根据说明中的描述，使用上页表给出的用例名称，给出图(a)中 U1、U2 和 U3 所对应的用例。（分数：3.75）_正确答案：()解析：U1：Car entry U2：Car exit U3：Car entry when full(2).【问题 2】根据说明中的描述，使用上页表给出的类的名称，给出图(b)中的，AD 所对应的类。（分数：3.75）_正确答案：()解析：A：CarPark B：Bar
34、rier C：EntryBarrier D：ExiBarrier 其中，C、D 的答案可以互换(3).【问题 3】根据说明中的描述，使用上页表给出的状态名称，给出图(c)中 S1S4 所对应的状态。（分数：3.75）_正确答案：()解析：S1：Idle S2：Await Ticket Take S3：Await Enable S4：Await Entry(4).【问题 4】简要解释图(a)中用例 U1 和 U3 之间的 extend 关系的内涵。（分数：3.75）_正确答案：()解析：用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模。通过这种方式，可以把可选行为从必需的行为中
35、分离出来。 试题三分析 本题考查面向对象设计基本知识和方法。 题目给出了 4 个用例，在 4 个用例中，两个用例表示汽车进入停车场，一个用例表示汽车退出停车场，另一个用例表示记录停车场相关信息。经分析得出，前 3 个用例的参与者都是驾驶员，因此 U1、U2 和 U3 对应进入和退出停车场。U1 和 U3 之间存在扩展关系，而用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模通过这种方式，可以把可选行为从必需的行为中分离出来。Car entry when full 和Car entry 之间就可以使用 extend 关系进行建模。 类图问题的回答比较容易，因为首先可以判断Barr
36、ier、EntryBarrier 和 ExitBarrier 之间存在继承关系，而类图中表示继承关系的部分只有一处，因此这 3 个类分别对应 B、C 和 D，而剩下的空 A 只有选择类 CarPark 了。 在状态图中，Idle 表示有空闲车位，Disable 表示没有空闲车位，因此在其之间存在双向的状态迁移，因此状态图上的状态 31 为 Idle 状态。当停车场存在空闲车位时，汽车请求进入停车场，根据说明描述“当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡”，可知在该动作正对应于状态图上的 S1 和状态 S2 之间的迁移，因此，状态 S2 表示的含义应该是按下按钮后状态，此时，驾驶
37、员等待打印停车卡，所以，状态日 2 为 Await Ticket Take。同理可分析出状态 S3 和状态 S4。四、B试题四/B(总题数：1，分数：15.00)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。【说明】快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下。1分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组 (可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1)中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。2递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r
38、分别排序。3合并：快速排序在原地排序，故不需合并操作。（分数：15.00）(1).【问题 1】下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。A：待排序数组p，r: 数组元素下标，从 p 到 rq: 划分的位置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=Ar；i=p-1；for(j=p；j
39、r-1；j+)if (Ajx)i=i+1；交换 Ai和 Aj交U (1) /U和U (2) /U/注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return U(3) /U（分数：5.00）_正确答案：()解析：(1)Ai+1 (2)Ar (3)i+1 注：空(1)和空(2)答案可以互换(2).【问题 2】(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为U (4) /U，平均情况为U (5) /U，最坏情况为U (6) /U。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况?U (7) /U。(最佳，平均、最坏)（分数：5.00）_正确答案：()解析：(4)O(nlgn)或 O(log2n) (5)O(nlgn)或 O(nlog2n)(6)O(n2) (7)最坏(3).【问题 3】(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中
