xx一分析

本题考查数据流图的设计和应用。

根据题目说明，本系统的外部实体仅仅涉及到客户，因此系统的顶层数据流图中E1应该对应为客户。

题目的第二个问题在于识别系统中的数据文件D1～D4，根据0层数据流图中的数据文件与处理之间的关系分析可以得知：

D1为创建新客户加工的输出，并且为加工1、6和7的输入，再根据题目中的描述，客户信息文件与创建客户信息、预约、归还和履行预约都相关，因此D1便是客户信息文件。同理可分析出D2为音像制品信息文件、D3为租借记录文件、D4为预约记录文件。

图（b）中缺少了3条数据流，我们先检查顶层数据流图和0层数据流是否一致。首先，从顶层数据流图中可以看出，与E1直接相关的数据流共有9条，而在0层数据流图中与E1直接关联的只有7条，因此可以直接断定，图（b）中至少缺少直接与E1相关的两条数据流：新客户创建请求和预约流水号。新客户创建请求通过创建新客户加工将客户的信息写入客户信息文件中，因此其起点和终点分别为：E1和4。同理，预约流水号的起点和终点为5和E1。在说明中，客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。因此，在客户归还和履行预约服务之间存在着数据上的联系。

面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。

参考答案

【问题1】

E1：客户

【问题2】

D1: 客户信息文件 D2: 音像制品信息文件

D3: 租借记录文件 D4: 预约记录文件

【问题3】

注意：3条数据流无前后顺序区分。

【问题4】

面向数据结构的设计方法以数据结构作为设计的基础，它根据输入/输出数据结构导出程序的结构。

面向数据结构的设计方法用于规模不大的数据处理系统。

xx二（共15分）

xx二分析

本题考查数据库概念结构设计及向逻辑结构转换的基本方法。

此类题目要求认真阅读题目对现实问题的描述，经过分类、聚集、概括等方法，从中确定实体及其联系。题目已经给出了4个实体，需要根据需求描述，给出实体间的联系。

由"每个球队有一个教练负责管理球队，一个教练仅负责一个球队。"知球队与教练间为1∶1联系；球队与队员之间应为1∶N联系；多个球队使用多个训练场地，球队与场地之间为M∶M联系；比赛是球队、场地与裁判之间的联系，一个球队会与同组的其他多个队之间比赛，有多个场地和裁决，一位裁判会对多场比赛判罚，一个场地会有多场比赛，涉及多个球队和裁判，因此球队、场地与裁判之间的比赛关系为M∶N∶P联系。

根据补充后的E-R图，球队与球员之间的1∶N联系应通过将1端实体（球员）的主码（球队名称）加入到N端实体（球员）对应的关系中来表达。这类联系也可通过独立的一个关系来表达，如球队-球员（球队名称，队员编号），这样会对查询增加多余的连接操作，因此一般不采用这种方法。

同样，球队与教练之间的1∶1联系也应通过将一方的主码增加到另一方实体对应的关系中，来表达联系。

训练和比赛为多对多联系，只能独立成一个关系模式，取与该联系相关联的各实体的码及联系自有的属性构成。例如，比分和分组应该是比赛的属性，再加上球队、裁判、场地的码，即构成"比赛记录"的关系模式。

同理，训练是球队和场地的多对多联系，训练开始时间和结束时间为训练的属性，加上球队的码和场地的码，构成"训练记录"关系模式。

球迷与球队之间为多对多联系，需新增球迷实体和球迷与球队之间的支持联系。

参考答案

【问题1】

（对联系名称不做要求，但不能出现重名，图中的M、N、P也可表示为*）

【问题2】

（1）球队名称

（2）教练编号

（3）球队名称，场地名称，开始时间，结束时间

（4）甲队，乙队，比赛时间，场地名称，比分，裁判，分组

【问题3】

关系模式：

热心球迷（球迷编号，姓名，住址，俱乐部）

支持球队（球迷编号，球队）

xx三（共15分）

xx三分析

本题考查面向对象设计基本知识和方法。

题目给出了4个用例，在4个用例中，两个用例表示汽车进入停车场，一个用例表示汽车退出停车场，另一个用例表示记录停车场相关信息。经分析得出，前3个用例的参与者都是驾驶员，因此U1、U2和U3对应进入和退出停车场。U1和U3之间存在扩展关系，而用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模。通过这种方式，可以把可选行为从必需的行为中分离出来。Car entry when full 和 Car entry之间就可以使用extend关系进行建模。

类图问题的回答比较容易，因为首先可以判断Barrier、EntryBarrier和ExitBarrier之间存在继承关系，而类图中表示继承关系的部分只有一处，因此这3个类分别对应B、C和D，而剩下的空A只有选择类CarPark了。

在状态图中，Idle表示有空闲车位，Disable表示没有空闲车位，因此在其之间存在双向的状态迁移，因此状态图上的状态S1为Idle状态。当停车场存在空闲车位时，汽车请求进入停车场，根据说明描述"当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡"，可知在该动作正对应于状态图上的S1和状态S2之间的迁移，因此，状态S2表示的含义应该是按下按钮后状态，此时，驾驶员等待打印停车卡，所以，状态S2为Await Ticket Take。同理可分析出状态S3和状态S4。

参考答案

【问题1】

U1：Car entry   U2：Car exit   U3：Car entry when full

【问题2】

A：CarPark B：Barrier C：EntryBarrier

D：ExitBarrier

其中，C、D的答案可以互换

【问题3】

S1：Idle   S2：Await Ticket Take   S3：Await Enable   S4：Await Entry

【问题4】

用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模。通过这种方式，可以把可选行为从必需的行为中分离出来。

xx四（共15分）

xx四分析

本题考查算法的设计与分析技术。

问题1考查快速排序算法的伪代码，快速排序最核心的处理是进行划分，即PARTITION操作，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以{zh1}一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图4-1所示：

在问题1给出的伪代码中，当循环结束后，A[p..i]中的值应小于等于枢轴元素值x，而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是{dy}个比A[r]大的元素，因此A[r]与A[i+1]交换，得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置，因此返回值为i+1。

问题2考查的是快速排序算法的时间复杂度分析。当每次能作均匀划分时，算法为{zj0}情况，此时时间复杂度可以通过计算递归式

得到时间复杂度为 当每次为极端不均匀划分时，即长度为n的数组划分后一个子数组为n-1，一个为0，算法为最坏情况，此时时间复杂度可以通过计算递归式 得到时间复杂度为

平均情况的分析较为复杂，我们可以假设数组每次划分为

此时时间复杂度可以通过计算递归式

问题3中，由于随机化的快速排序的划分调用了传统的快速排序算法的PARTITION操作，而传统的划分每次以数组的{zh1}一个元素作为枢轴元素，因此，随机化的划分操作中每次先随机获得一个元素，将其与{zh1}一个元素交换。随机化的快速排序xx了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。

参考答案

【问题1】

（1）A[i + 1]    （2）A[r]    （3）i + 1   

注：空（1）和空（2）答案可以互换

【问题2】

【问题3】

（8）A[i]     （9）A[r] （10）否

注：空（8）和空（9）答案可以互换

xx五（共15分）

xx五分析

本题考查基本程序设计能力。

堆栈是软件设计中常使用的一种经典数据结构，题目给出的操作都是任何堆栈都具有的基本操作。堆栈的存储结构通常采用数组或链表形式，但无论采用哪种存储结构，整体上呈现的是后进先出的特点，即后进入堆栈的元素先出栈。题目中给出的结构体Stack仅包含一个指向栈顶元素的指针（栈顶指针），当且仅当堆栈中没有元素时，该指针应为NULL。当向堆栈中增加元素时，首先需要动态创建该元素的存储区，并且栈顶指针指向该元素。当元素出栈时，栈顶指针则指向出栈元素的紧前一个元素。结构体List表示栈中元素，包含对应的数据和指向紧上次入栈的元素指针next，对于第1个入栈的元素，指针next为NULL,而其他元素中的指针next一定不为NULL。

C语言中，如果用一个整数型表达式表示条件判定语句的话，该表达式的值为0则表示假，非0表示真。从给定程序代码可以看出，对于函数IsEmpty，若其返回值为0则表示堆栈非空，否则表示堆栈为空。因此，对于空（1），必须填写可表示堆栈为空的判定语句：S==NULL||S->pTop==NULL，这2个条件中只要有1个条件满足，则表明堆栈S为空。对于空（2），此时需要返回栈顶元素中的数据，而栈顶元素为S->pTop，所以对应的数据应该为S->pTop->data。

对于压栈操作Push，在为新元素获取存储空间后，必须调整堆栈的栈顶指针S->pTop指向新元素的存储区，即S->pTop=newNode。对于弹栈操作Pop，弹出栈顶元素lastTop后，需要调整栈顶指针，使其指向被弹出元素的下一个元素，即S->pTop=S->pTop->next，或S->pTop=lastTop->next。

对于main函数中宏MD(x)，在程序预编译时会按字符替换为 "x<<2"。所以在main函数中，首先入栈的元素为"1<<2"，即整数4，第2个入栈的元素为"2<<2"，即整数8，其次将8弹出，然后再将"3<<2+1"入栈，C语言中 "+"优先级高于"<<"，所以此时入栈者为整数24，而此时堆栈中有2个元素，其中栈顶元素为24，下一元素为4。{zh1}，若堆栈非空，则循环完成显示栈顶元素的值、弹出栈顶元素的操作，直至堆栈为空。所以程序执行时的输出内容为"24 4"。

参考答案

（1）S == NULL || S->pTop == NULL   （2）S->pTop->data   （3）newNode

（4）S->pTop->next，或 lastTop->next （5）24 4

xx六（共15分）

xx六分析

本题考查的是设计模式中的命令模式。

设计时，为了保证遥控器和家用电器之间的独立性，定义了Command类，当用户按下遥控器上的按钮时，触发Command上的On或者Off方法，因此，一对按钮分别对应一个Command对象。题目中的LightCommand以及与TVCommand分别为Command的子类，该子类用于控制实际的Light以及TV对象，将On与Off方法委托给Light以及TV实现。空（1）表示要设置遥控器上按钮控制的对象，其参数传递的是某一个命令对象，因此只需将该命令对象存储下来即可；空（2）表示关闭电灯，根据说明，关闭电灯的方法为turnLight(0)；空（3）表示打开电视机，因此需要调用打开电视的方法。空（4）表示将按钮0和相应的Command对象相关联，根据题目描述，按钮0用于控制灯或者电视，因此，应该设置灯或者电视的命令对象。本题中应用命令模式的目的是为了使为了让遥控器和类Light与TV之间的耦合性降至{zd1}。

参考答案

（1）commands[button]   （2）trunLight(0)   （3）setChannel(1)

（4）&lightCommand   （5）RemoteController （6）Light   （7）TV

xx七（共15分）