文档介绍：11 / 12
2009年上半年软件设计师下午试卷
试题一（共 15 分）
阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。
【说明】
假设某大型商业企业由商品配送中心和连锁超市组成，其中商品配送中心包括【问题 3】（3 分）
为了使商场有紧急事务时能联系到轮休的员工，要求每位员工必需且只能登记一位紧急联系人的姓名和联系电话，不同的员工可以登记相同的紧急联系人。则在图 2-1 中还需添加的实体是（1），该实体和图 2-1 中的员工存在（2）联系（填写联系类型）。给出该实体的关系模式。
试题三（共 15 分）
阅读下列说明和图，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某银行安排开发一个自动存提款机模拟系统（ATM System）。系统通过读卡器CardReader）读取ATM卡；系统和客户（Customer ）的交互由客户限制台（CustomerConsole）实现；银行操作员（Operator）可限制系统的启动（System Startup）和停止（System Shutdown）；系统通过网络和银行系统（Bank）实现通信。当读卡器推断用户已将 ATM 卡插入后，创建会话（Session）。会话起先后，读卡器进行读卡，并要求客户输入个人验证码（PIN）。系统将卡号和个人验证码信息送到银行系统进行验证。验证通过后，客户可从菜单选择如下事务（Transaction）：
11 / 12
1. 从 ATM 卡账户取款（Withdraw）；
2. 向 ATM 卡账户存款（Deposit）；
3. 进行转账（Transfer）；
4. 查询（Inquire）ATM 卡账户信息。
一次会话可以包含多个事务，每个事务处理也会将卡号和个人验证码信息送到银行系统进行验证。若个人验证码错误，则转个人验证码错误处理（Invalid PIN Process）。每个事务完成后，客户可选择接着上述事务或退卡。选择退卡时，系统弹出 ATM 卡，会话结束。
系统采纳面对对象方法开发，运用 UML 进行建模。系统的顶层用例图如图 3-1 所示，一次会话的序列图（不考虑验证）如图 3-2 所示。消息名称参见表 3-1。
表 3-1 可能的消息名称列表
名称
说明
名称
说明
cardInserted( )
ATM 卡已插入
performTransaction( )
执行事务
performSession( )
执行会话
readCard( )
读卡
readPIN( )
读取个人验证码
PIN
个人验证码信息
creat(atm, this, card, pin)
为当前会话创建事务
create(this)
为当前 ATM 创建会话
card
ATM 卡信息
doAgain
执行下一个事务
ejectCard( )
弹出 ATM 卡
【问题 1】（7 分）
依据【说明】中的描述，给出图 3-1 中 A1 和 A2 所对应的参和者，U1 至 U3 所对应的用例，以及该图中空（1）所对应的关系。（U1 至 U3 的可选用例包括：Session、Transaction、Insert Card、Invalid PIN Process 和 Transfer）
【问题 2】（6 分）
依据【说明】中的描述，运用表 3-1 中的英文名称，给出图 3-2 中 6～9 对应的消息。
【问题 3】（2 分）
说明图 3-1 中用例 U3 和用例 Withdraw、Deposit 等四个用例之间的关系及其内涵。
5 / 14
图 3-1 ATM 系统顶层用例图
图 3-2 一次会话的序列图（无验证消息）
试题四（共 15 分）
11 / 12
阅读下列说明，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。
【说明】
现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路途，边上的权重表示该路途的长度。
现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先须要求出每个顶点到其它任一顶点的最短路径，即须要计算随意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最终，选择最短路径之和最小的顶点作为建大型超市的最佳位置。
【问题 1】（12 分）
本题采纳 Floyd-Warshall 算法求解随意两个顶点之间的最短路径。已知图 G 的顶点集合为V= {1