1、2008年上半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷及答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 阅读以下说明和图，回答问题 1至问题 4，将解答填入对应栏内。【说明】 某音像制品出租商店欲开发一个音像管理信息系统，管理音像制品的租借业务。需求如下： 1系统中的客户信息文件保存了该商店的所有客户的用户名、密码等信息。对于首次来租借的客户，系统会为其生成用户名和初始密码。 2系统中音像制品信息文件记录了商店中所有音像制品的详细信息及其库存数量。 3根据客户所租借的音像 制品的品种，会按天收取相应的费用。音像制品的最长租借周期为 1周，每位客户每次最多只能租
2、借 6件音像制品。 4客户租借某种音像制品的具体流程如下。 (1)根据客户提供的用户名和密码，验证客户身份。 (2)若该客户是合法客户，查询音像制品信息文件，查看商店中是否还有这种音像制品。 (3)若还有该音像制品，且客户所要租借的音像制品数小于等于 6个，就可以将该音像制品租借给客户。这时，系统给出相应的租借确认信息，生成一条新的租借记录并将其保存在租借记录文件中。 (4)系统计算租借费用，将费用信息保存在租借记录文件中并 告知客户。 (5)客户付清租借费用之后，系统接收客户付款信息，将音像制品租借给该客户。 5当库存中某音像制品数量不能满足客户的租借请求数量时，系统可以接受客户网上预约租借
3、某种音像制品。系统接收到预约请求后，检查库存信息，验证用户身份，创建相应的预约记录，生成预约流水号给该客户，并将信息保存在预约记录文件中。 6客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件 ，通知相关客户前来租借音像制品。1 图 (a)中只有一个外部实体 E1。使用【说明】中的词语，给出 E1的名称。 2 使用【说明】中的词语，给出图 (b)中的数据存储 D1 D4的名称。 3 数据流图 (b)缺少了 3条数据流，根据说明及数据流图 (a)提供的
4、信息，分别指出这3条数据流的起点和终点。 4 在进行系统分析与设计时，面向数据结构的设计方法 (如 Jackson方法 )也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。 5 阅读下列说明，回答问题 1至问题 3，将解答填入对应栏内。【说 明】 某地区举行篮球比赛，需要开发一个比赛信息管理系统来记录比赛的相关信息。【需求分析结果】 1登记参赛。球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员的姓名、年龄、身高、体重等信息。每个球队有一个教练负责管理球队，一个教练仅负责一个球队。系统记录教练的姓名、年龄等信息。 2安排球队的训练信息。比赛组织者为球队提
5、供了若干块场地，供球队进行适应性训练。系统记录现有的场地信息，包括：场地名称、场地规模、位置等信息。系统可为每个球队安排不同的训练场地，如下表所示。系统记录训练场地安 排的信息。 3安排比赛。该赛事聘请专职裁判，每场比赛只安排一个裁判。系统记录裁判的姓名、年龄、级别等信息。系统按照一定的规则，首先分组，然后根据球队、场地和裁判情况，安排比赛 (每场比赛的对阵双方分别称为甲队和乙队 )。记录参赛球队名称、比赛时间、比分、比赛场地等信息，如下表所示。4所有球员、教练和裁判可能出现重名情况。【概念模型设计】 根据需求阶段收集的信息，设计的实体联系图和关系模式 (不完整 )如下： 1实体联系图 (图
6、2-1) 2关系模式 教练 (教练编号，姓名，年龄 ) 队员 (队员编号，姓名，年龄， 身高，体重， (a) 球队(球队名称，代表地区，成立时间， (b) 场地 (场地名称，场地规模，位置 ) 训练记录(c) 裁判 (裁判编号，姓名，年龄，级别 ) 比赛记录 (d) 5 根据问题描述，补充联系及其类型，完善实体联系图 2-1。 (联系及其类型的书写格式参照教练与球队之间的联系描述，联系名称也可使用联系 1、联系 2、 ) 6 根据实体联系图，填充关系模式中的 (a)、 (b)、 (c)和 (d)，并给出训练记录和比赛记录关系模式的主键和外键。 7 如果考虑记录一些特别资深的热心球迷的情况，每个
7、热心 球迷可能支持多个球队。热心球迷包括：姓名、住址和喜欢的俱乐部等基本信息。根据这一要求修改上图的实体联系图，给出修改后的关系模式 (仅给出增加的关系模式描述 )。 8 阅读下列说明和图，回答问题 1至问题 4，将解答填入对应栏内。【说明】 某汽车停车场欲建立一个信息系统，已经调查到的需求如下： 1在停车场的入口和出口分别安装一个自动栏杆、一台停车卡打印机、一台读卡器和一个车辆通过传感器，示意图如下： 2当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡。当驾驶员拿走停车卡后，系统命令栏杆自动抬起；汽车通 过入口后，入口处的传感器通知系统发出命令，栏杆自动放下。 3在停车场内分布着若干
8、个付款机器。驾驶员将在入口处获取的停车卡插入付款机器，并缴纳停车费。付清停车费之后，将获得一张出场卡，用于离开停车场。 4当汽车到达出口时，驾驶员将出场卡插入出口处的读卡器。如果这张卡是有效的，系统命令栏杆自动抬起；汽车通过出口后，出口传感器通知系统发出命令，栏杆自动放下。若这张卡是无效的，系统不发出栏杆抬起命令而发出告警信号。 5系统自动记录停车场内空闲的停车位的数量。若停车场当前没有车位，系统将在入口处显示 “车位已满 ”信息。这时，停车卡打印机将不再出卡，只允许场内汽车出场。 根据上述描述，采用面向对象方法对其进行分析与设计，得到了如下表所示的类 /用例 /状态列表、下图 (a)所示的用
9、例图、图 (b)所示的初始类图以及图 (c)所示的描述入口自动栏杆行为的 UML状态图。8 根据说明中的描述，使用上页表给出的用例名称，给出图 (a)中 U1、 U2和 U3所对应的用例。 9 根据说明中的描述，使用上页表给出的类的名称，给出图 (b)中的， A D所对应的类。 10 根据说明中的描述，使用上页表给出的状态名称，给出图 (c)中 S1S4所对应的状态。 11 简要解释图 (a)中用例 U1和 U3之间的 extend关系的内涵。 12 阅读下列说明，回答问题 1至问题 3，将解答填入对应栏内。 【说明】 快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3个步骤如
10、下。 1分解：选择一个枢轴 (pivot)元素划分数组。将数组 Apr划分为两个子数组 (可能为空 )Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1)中的每个元素，小于 Aq+1r中的每个元素。 q的值在划分过程 中计算。 2递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。 3合并：快速排序在原地排序，故不需合并操作 12 下面是快速排序的伪代码，请填补其中的空缺；伪代码中的主要变量说明如下。 A：待排序数组 p， r: 数组元素下标，从 p到 r q: 划分的位置 x：枢轴元素 i：整型变量，用于描述数组下标。下标小于或等于 i的元素的值小于或等于枢轴
11、元素的值 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) i=i+1； 交换 Ai和 Aj 交 (1)和 (2)/注：空 (1)和空 (2)答案可互换，但两空全部答对方可得分 return (3) 13 (1)假设要排序包含 n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O
12、记号。最佳情况为 (4)，平均情况为 (5)，最坏情况为 (6)。 (2)假设要排序的 n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况 ?(7)。 (最佳，平均、最坏 ) 14 (1)待排序数组 是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码 利用原有的快速排序的划分操作，请填充其中的空缺处。其中， RANDOM(i， j)表示随机取 i到 j之间的一个数，包括 i和 j。 RANDOMIZED- PARTITION(A， p， r) i=RANDOM(p，
13、rl)； 交换 (8)和 (9)； /注：空 (8)和空 (9)答案可互换，但两空全部答对方可得分 return PARTITION (A， p， r)； (2)随机化快速排序是否能够消除最坏情况的发生 ?(10)。 (是或否 ) 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。 15 阅读下列说明和 C代码，将应填入 (n)处的字句写在对应栏内。 【说明】 栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶 (Stock Top)，而另一端称为栈底 (
14、Stock Bottom)。栈的基本 操作包括：创建栈 (NewStack)、判断栈是否为空 (IsEmpty)、判断栈是否已满 (IsFull)、获取栈顶数据 (Top)、压栈 /入栈 (Push)、弹栈 /出栈 (Pop)。 当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如下图所示 )。 以下 C代码采用链式存储结构实现一个整数栈操作。【 C代码】 typedef struct List int data； /栈数据 struct List* next； /上次入栈的数据地址 List； typedef struct Stack List*
15、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*
16、)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
17、(2)； Pop(myStack)； Push(myStack， MD(3)+1)； while( !IsEmpty(myStack) ) printf(“%d“， Top(myStack)； Pop(myStack)； return 0； 以上程序运行时的输出结果为 :(5) 16 阅读下列说明和 C+代码，将应填入 (n)处的字句写在对应栏内。 【说明】 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如左下所示。该遥控器共有 4个按钮，编号分别是 0至 3，按钮0和 2能够遥控打开电器 1和电器 2，按钮 1和 3则能遥控关闭电器 1和电器 2
18、。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如右下所示。 右上图中，类 RomoteController的方法 onPressButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号； Command接口中 on和 off方法分别用于控制电器的开与关； Light中 turnLight(int degree)方法用于调整电灯灯光的强弱，参数 degree值为 0时表示关灯，值为 100时表示开灯并且将灯光亮度调整到最大； TV中 setChannel(int chann
19、el)方法表示设置电视播放的频道，参数 channel值为0时表示关闭电视，为 1时表示开机并将频道切换 为第 1频道。【 C+代码】 class Light /电灯类 public： void trunLight(int degree)/调整灯光亮度， 0表示关灯，100表示亮度最大 )； ； class TV/电视机类 public： vold setChannel(int channel/调整电视频道， 0表示关机， 1表示开机并切换到 1频道 ； ； class Command/抽象命令类 public： virtual void on()=0； virtual void off()=
20、0； ； class RemoteController /遥控器类 protected： Command* commands 4； /遥控器有 4个按钮，按照编号分别对应 4个 Command对象 public： void onPressButton(int button) /按钮被按下时执行命令对象中的命令 if(button % 2=0)commandsbutton- on()； else commandsbutton- off()； void setCommand(int button， Command* command) (1)=command； /设置每个按钮对应的命令对象 ； cl
21、ass 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(
22、)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)和类
23、 (6)、类 (7)之间的耦合性降至最小。 17 阅读下列说明和 Java代码，将应填入 (n)处的字句写在对应栏内。【说明】 已知某企业欲开发一家用电器遥控系统，即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如下图 (a)所示。该遥控器共有 4今按钮 ，编号分别是 0至 3，按钮 0和 2能够遥控打开电器 1和电器 2，按钮 1和 3则能遥控关闭电器 1和电器2。由于遥控系统需要支持形式多样的电器，因此，该系统的设计要求具有较高的扩展性。现假设需要控制客厅电视和卧室电灯，对该遥控系统进行设计所得类图如下图 (b)所示。 图 (b)中，类 RomoteController的方法 on
24、PrcssButton(int button)表示当遥控器按键按下时调用的方法，参数为按键的编号； command接口中 on和 off方法分别用于控制电器的开与关； Light中 turnLight(int degree)方法用于调整电灯灯光的强弱，参数 degree值为 0时表示关灯，值为 100时表示开灯并且将灯光亮度调整到最大； TV中 sctChannel(int channel)方法表示设置电视播放的频道，参数 channel值为 0时表示关闭电视，为 1时表示开机并将频道切换为第 1频道。【 Java代码】 class Light /电灯类 public void trunLig
25、ht(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 Command4； /遥控器有 4个按钮，按照编号分别对应 4个 Command对象 public void onPressButton(int bu
26、tton)/按钮被按下时执行命令对象中的命令 if(button % 2 = 0)commandsbutton. on()； else commandsbutton. off()； public void setCommand(int button， Command command) (1)=command； /设置每个按钮对应的命令对象 ； class LightCommand implements Command /电灯命令类 protected Light light； /指向要控制的电灯对象 public void on()light. trunLight(100)； )； publi
27、c 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. setChanne1(0)； ； public TVCommand(TV tv)this. tv= tv； ； ； public class rs public static void main(
28、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的命令对象代码 本题中，应用
29、命令模式能够有效让类 (5)和类 (6)、类 (7)之间的耦合性降至最小。 2008年上半年软件水平考试（中级）软件设计师下午（应用技术）试题真题试卷答案与解析 一、必答题（共 4道大题，每道大题 15分） 1 【正确答案】 E1：客户 2 【正确答案】 D1：客户信息文件 D2：音像制品信息文件 D3：租借记录文件 D4：预约记录文件 3 【正确答案】 注意： 3条数据流无前后顺序区分。 【试题解析】 4 【正确答案】 面向数据结构的设计方法以数据结构作为设计的基础，它根据输入 /输出数据结构导出程序的结构。 面向数据结构的设计方法用于规模不大的数据处理系统。 【试题解析】 本题考查数据流图
30、的设计和应用。 根据题目说明，本系统的外部实体仅仅涉及到客户，因此系统的顶层数据流图中E1应该对应为客户。 题目的第二个问题在于识别系统中的数据文件 D1 D4，根据 0层数据流图中的数据文件与处 理之间的关系分析可以得知： D1为创建新客户加工的输出，并且为加工 1、 6和 7的输入，再根据题目中的描述，客户信息文件与创建客户信息、预约、归还和履行预约都相关，因此 D1便是客户信息文件。同理可分析出 D2为音像制品信息文件、 D3为租借记录文件、 D4为预约记录文件。 图 (b)中缺少了 3条数据流，我们先检查顶层数据流图和。层数据流是否一致。首先，从顶层数据流图中可以看出，与 E1直接相关
31、的数据流共有 9条，而在 0层数据流图中与 E1直接关联的只有 7条，因此可以直接断定，图 (b)中至少缺少直接与 E1相关的两条 数据流：新客户创建请求和预约流水号。新客户创建请求通过创建新客户加工将客户的信息写入客户信息文件中，因此其起点和终点分别为： E1和 4。同理，预约流水号的起点和终点为 5和 E1。在说明中，客户归还到期的音像制品，系统修改租借记录文件，并查询预约记录文件和客户信息文件，判定是否有客户预约了这些音像制品。若有，则生成预约提示信息，通知系统履行预约服务，系统查询客户信息文件和预约记录文件，通知相关客户前来租借音像制品。因此，在客户归还和履行预约服务之间存在着数据上的
32、联系。 面向数据结构的设计方法以数据结构作为设 计的基础，它根据输入 /输出数据结构导出程序的结构。面向数据结构的设计方法用于规模不大的数据处理系统。 5 【正确答案】 6 【正确答案】 (1)球队名称 (2)教练编号 (3)球队名称，场地名称，开始时间，结束时间 (4)甲队，乙队，比赛时间，场地名称，比分，裁判，分组7 【正确答案】 关系模式：热心球迷 (球迷编号，姓名，住址，俱乐部 )支持球队 (球迷编号，球队 ) 【试题解析】 本题考查数据库概念结构设计及向逻辑结构转换的基本方法。 此类题目要求认真阅读题目对现实问题的描述，经过分类、聚 集、概括等方法，从中确定实体及其联系。题目已经给出
33、了 4个实体，需要根据需求描述，给出实体间的联系。 由 “每个球队有一个教练负责管理球队，一个教练仅负责一个球队。 ”知球队与教练间为 1： 1联系；球队与队员之间应为 1： N联系；多个球队使用多个训练场地，球队与场地之间为 M： M联系；比赛是球队、场地与裁判之间的联系，一个球队会与同组的其他多个队之间比赛，有多个场地和裁决，一位裁判会对多场比赛判罚，一个场地会有多场比赛，涉及多个球队和裁判，因此球队、场地与裁判之间的比赛关系为 M： N： P联系。 根据补充后的 E-R图，球队与球员之间的 1： N联系应通过将 1端实体 (球员 )的主码 (球队名称 )加入到 N端实体 (球员 )对应的
34、关系中来表达。这类联系也可通过独立的一个关系来表达，如球队 球员 (球队名称，队员编号 )，这样会对查询增加多余的连接操作，因此一般不采用这种方法。 同样，球队与教练之间的 1： 1联系也应通过将一方的主码增加到另一方实体对应的关系中，来表达联系。 训练和比赛为多对多联系，只能独立成一个关系模式，取与该联系相关联的各实体的码及联系自有的属性构成。例如，比分和分组应该是比赛的属性，再加上球队、裁判、场地 的码，即构成 “比赛记录 ”的关系模式。 同理，训练是球队和场地的多对多联系，训练开始时间和结束时间为训练的属性，加上球队的码和场地的码，构成 “训练记录 ”关系模式。 球迷与球队之间为多对多联
35、系，需新增球迷实体和球迷与球队之间的支持联系。 8 【正确答案】 U1： Car entry U2： Car exit U3： Car entry when full 9 【正确答案】 A： CarPark B： Barrier C： EntryBarrier D： ExiBarrier 其中 ， C、 D的答案可以互换 10 【正确答案】 S1： Idle S2： Await Ticket Take S3： Await Enable S4： Await Entry 11 【正确答案】 用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模。通过这种方式，可以把可选行为从必需的行为
36、中分离出来。 【试题解析】 本题考查面向对象设计基本知识和方法。 题目给出了 4个用例，在 4个用例中，两个用例表示汽车进入停车场，一个用例表示汽车退出停车场，另一个用例表示记录停车场相 关信息。经分析得出，前 3个用例的参与者都是驾驶员，因此 U1、 U2和 U3对应进入和退出停车场。 U1和U3之间存在扩展关系，而用例之间的延伸关系用于对被用户看作是可选系统行为的用例的一部分建模通过这种方式，可以把可选行为从必需的行为中分离出来。Car entry when full和 Car entry之间就可以使用 extend关系进行建模。 类图问题的回答比较容易，因为首先可以判断 Barrier、
37、 EntryBarrier和ExitBarrier之间存在继承关系，而类图中表示继承关系的部分只有一处，因此这3个类分别对应 B、 C和 D，而剩下的空 A只有选择类 CarPark了。 在状态图中， Idle表示有空闲车位， Disable表示没有空闲车位，因此在其之间存在双向的状态迁移，因此状态图上的状态 31为 Idle状态。当停车场存在空闲车位时，汽车请求进入停车场，根据说明描述 “当汽车到达入口时，驾驶员按下停车卡打印机的按钮获取停车卡 ”，可知在该动作正对应于状态图上的 S1和状态 S2之间的迁移，因此，状态 S2表示的含义应该是按下按钮后状态，此时，驾驶员等待打印停车卡，所以，状
38、态日 2为 Await Ticket Take。同 理可分析出状态 S3和状态S4。 12 【正确答案】 (1)Ai+1 (2)Ar (3)i+1 注：空 (1)和空 (2)答案可以互换 13 【正确答案】 (4)O(nlgn)或 O(log2n) (5)O(nlgn)或 O(nlog2n) (6)O(n2) (7)最坏 14 【正确答案】 (8)Ai (9)Ar (10)否 注；空 (8)和空 (9)答案可以互换 【试题解析】 本题考查算法的设计与分析技术。 问题 1考查快速排序算法的伪代码，快速排序最核心的处理是进行划 分，即 PARTITION操作，根据枢轴元素的值，把一个较大的数组分成
39、两个较小的子数组，一个子数组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。划分时，以最后一个元素为枢轴元素，从左到右依次访问数组的每一个元素，判断其与枢轴元素的大小关系，并进行元素的交换，如图 4-1所示： 在问题 1给出的伪代码中，当循环结束后， Api中的值应小于等于枢轴元素值x，而 Ai+1r-1中的值应大于枢轴元素值 x。此时 Ai+1)是第一个比 Ar大的元素，因 此 A闭与 Ai+1交换，得到划分后的两个子数组。 PARTITION操作返回枢轴元素的位置，因此返回值为 i+1。 问题 2考查的是快速排序算法的时间复杂度分析。当
40、每次能作均匀划分时，算法为最佳情况，此时时间复杂度可以通过计算递归式 T(n)=2T(n/2)+O(n)，得到时间复杂度为 O(nlgn)：当每次为极端不均匀划分时，即长度为 n的数组划分后一个子数组为 n-1，一个为 0，算法为最坏情况，此时时间复杂度可以通过计算递归式 T(n)=T(n-1)+O(n)，得到时间复杂度为O(n2)；平均情况的分析较为复杂，我 们可以假设数组每次划分为 9/10： 1/10，此时时间复杂度可以通过计算递归式 T(n)=T(9/10)+T(1/10)+O(n)，得到时间复杂度为 O(nlgn)，因此在平均情况下快速排序仍然有较好的性能，时间复杂度为 O(nlgn
41、)。当所有的 n个元素具有相同的值时，可以认为数组已经有序，此时每次都划分为长度为 n-1和 0的两个子数组，属于最坏情况。 问题 3中，由于随机化的快速排序的划分调用了传统的快速排序算法的 PARTITION操作，而传统的划分每次以数组的最后一个元素作为枢轴元素，因此，随机化的划分操作中每 次先随机获得一个元素，将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。 二、选答题（共 3道大题，每道大题 15分） 从下列 3道试题中任选 1道解答，如果解答的试题数超过 1道，则仅题号小的 1道题解答有效。
42、 15 【正确答案】 (1)S=NULL S- pTop =NULL (2)S- pTop- data (3)newNode (4)S- pTop- next，或 lastTop- next (5)244 【试题解析】 本题考查基本程序设计能力。 堆栈是软件设计中常使用的一种经典数据结构，题目给出的操作都是任何堆栈都具有的基本操作。堆栈的存储结构通常采用数组或链表形式，但无论采用哪种存储结构，整体上呈现的是后进先出的特点，即后进入堆栈的元素先出栈。题目中给出的结构体 Stack仅包含一个指向栈顶元素的指针 (栈顶指针 )，当且仅当堆栈中没有元素时，该指针应为 NULL。当向堆栈中增加元素时，首
43、先需要动态创建该元素的存储区，并且栈顶指针指向该元素。当元素出栈时，栈顶指针则指向出栈元素的紧前一个元 素。结构体 List表示栈中元素，包含对应的数据和指向紧上次入栈的元素指针 next，对于第 1个入栈的元素，指针 next为 NULL,而其他元素中的指针 next一定不为 NULL。 C语言中，如果用一个整数型表达式表示条件判定语句的话，该表达式的值为。则表示假，非 0表示真。从给定程序代码可以看出，对于函数 IsEmpty，若其返回值为 0则表示堆栈非空，否则表示堆栈为空。因此，对于空 (1)，必须填写可表示堆栈为空的判定语句： S=NULL S- p)Top=NULL，这 2个条件中
44、只要有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”。所以在m
45、ain函数中，首先入栈的元素为 “1 2”，即整数 4，第 2个入栈的元素为 “2 2”，即整数 8，其次将 8弹出，然后再将 “3 2+1”入栈， C语言中 “+”优先级高于 “ ”，所以此时入栈者为整数 24，而此时堆栈中有 2个元素，其中栈顶元素为 24，下一元素为 4。最后，若堆栈非空，则循环完成显示栈顶元素的值、弹出栈顶元素的操作，直至堆栈为空。所以程序执行时的输出内容为 “244”。 16 【正确答案】 (1)commandsbutton (2)trunLight(0) (3)setChaunel(1) (4)&lightCommand (5)RemoteController (6
46、)Light (7)TV 【试题解析】 本题考查的是设计模式中的命令模式。 设计时，为了保证遥控器和家用电器之间的独立性，定义了 Command类，当用户按下遥控器上的按钮时，触发 Command上的 On或者 Off方法，因此，一对按钮分别对应一个 Command对象。题目中的 LightCommand以及与 TVCommand分别为 Command的子类，该子类 用于控制实际的 Light以及 TV对象，将 On与Off方法委托给 Light以及 TV实现。空 (1)表示要设置遥控器上按钮控制的对象，其参数传递的是某一个命令对象，因此只需将该命令对象存储下来即可；空 (2)表示关闭电灯，根
47、据说明，关闭电灯的方法为 turnLight(0)；空 (3)表示打开电视机，因此需要调用打开电视的方法。空 (4)表示将按钮 0和相应的 Command对象相关联，根据题目描述，按钮 0用于控制灯或者电视，因此，应该设置灯或者电视的命令对象。本题中应用命令模式的目的是为了使为了让遥控器和类 Light与 TV之间的耦合性降至最低。 17 【正确答案】 (1)commandsbutton (2)trunLight(0) (3)setChanne1(1) (4)lightCommand (5)RemoteController (6)Light (7)TV 【试题解析】 本题考查的是设计模式中的命
48、令模式。 在设计时，为了保证遥控器和家用电器之间的独立性，定义了 Command类，当用户按下遥控器上的按钮时，触发 Command上的 On或者 Off方法，因此，一对按钮分别对应一个 Command对象。题目中的 LightCommand以及与TVCommand分别为 Command的子类，该子类用于控制实际的 Light以及 TV对象，将 On与 Off方法委托给 Light以及 TV实现。空 (1)表示要设置遥控器上按钮控制的对象，其参数传递的是某一个命令对象，因此只需将该命令对象存储下来即可；空 (2)表示关闭电灯，根据说明，关闭电灯的方法为 turnLight(0)；空 (3)表示打开电视机，因此需要调用打开电视的方法。空 (4)表示将按钮。和相应的Command对象相关联，根据题目描述，按钮 0用于控制灯或 者电视，因此，应该设置灯或者电视的命令对象。本题中应用命令模式的目的是为了使为了让遥控器和类 Light与 TV之间的耦合性降至最低。
