2018上半年软件设计师上午试题参考答案

基础知识

D.O(n2)

A.4

C.6 D.7

试题三（共 15 分）
阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。
【说明】
某 ETC（ Electronic Toll Collection，不停车收费）系统在高速公路沿线的特定位置上设置一个横跨道路上空的龙门架（ Toll gantry），龙门架下包括 6 条车道
（ Trafic lanes），每条车道上安装有雷达传感器（ Radar sensor）、无线传输器
（ Radio transceiver）和数码相机（ Digital Camera）等用于不停车收费的设备，以完成正常行驶速度下的收费工作。该系统的基本工作过程如下：
（1）每辆汽车上安装有车载器，驾驶员（ Driver）将一张具有唯一识别码的磁卡插入车载器中。磁卡中还包含有驾驶员账户的当前信用记录。
（2）当汽车通过某条车道时，不停车收费设备识别车载器内的特有编码，判断车型， 将收集到的相关信息发送到该路段所属的区域系统（ Regional center）中，计算通行费用创建收费交易（ Transaction），从驾驶员的专用账户中扣除通行费用。如果驾驶员账户透支，则记录透支账户交易信息。区域系统再将交易后的账户信息发送到维护驾驶员账 户信息的中心系统（ Central system）
（3）车载器中的磁卡可以使用邮局的付款机进行充值。充值信息会传送至中心系统， 以更新驾驶员账户的余额。
（4）当没有安装车载器或者车载器发生故障的车辆通过车道时，车道上的数码相机将对车辆进行拍照，并将车辆照片及拍摄时间发送到区域系统，记录失败的交易信息；并将该交易信息发送到中心系统。
（5）区域系统会获取不停车收费设备所记录的交通事件（ Traffic events）；交通广播电台（ Traffic advice center）根据这些交通事件进行路况分析并播 路况。
现采用面向对象方法对上述系统进行分析与设计，得到如表 3－1 所示的用例列表以及如图 3－1 所示的用例图和图 3－2 所示的分析类图。

试题四（共 15 分）
阅读下列说明和 C 代码，回答问题 1 和问题 2，将解答填入答题纸的对应栏内。
【说明】
某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表 P，其中中 Pi（i＝1，2，…，m）表示长度为 i 英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假设长钢条的长度为 n 英寸，最佳切割方案的最左边切割段长度为 i 英寸，则继续求解剩余长度为 n－i 英寸钢条的最佳切割方案。考虑所有可能的 i，得到的最大收益 rn 对应的切割方案即为最佳切割方案。rn 的递归定义如下：
rn =max1≤ i ≤n(pi +rn-i) 对此递归式，给出自顶向下和自底向上两种实现方式
【C 代码】
/*常量和变量说明
n：长钢条的长度
P[]：价格数组
*/

【问题 1】（8 分）
根据说明，填充 C 代码中的空（1）～（4）。
【问题 2】（7 分）
根据说明和 C 代码，算法采用的设计练略为（5）。
求解时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）
（用 O 表示）。

从下列的 2 道试题(试题五至试题六)中任选 1 道解答。请在答题纸上的指定位置处将所选择试题的题 框涂黑。若多涂或者未涂题 框,则对题 最小的一道试题进行评分。

试题五(共 15 分)
阅读下列说明和 C++代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
生成器( Builder)模式的意图是将一个复杂对象的构建与它的表示分离,使得同样的

构建过程可以创建不同的表示。图 5-1 所示为其类图。

【说明】
生成器( Builder)模式的意图是将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。图 6-1 所示为其类图。

试题一、

问题 1：
E1：客户 E2: 医生 E3：主管问题 2：
D1：通用信息表
D2：预约表
D3：医生表
D4：出诊时间表
D5：药品库存表问题 3：

数据流名称 起点 终点
删除解聘医生的出诊安排 P2 D4
查询相关药品库存信息 P4 D2
更新预约表中治疗信息 D5 P4
更新所约医生出诊时间 P3 D4

预约处理分解为：安排出诊、创建预约、提交预约请求、发送预约通知。
即保持父图与子图之间的平衡：父图中某个加工的输入输出数据流必须与其子图的输入输出数据流在数量上和名字上相同。父图的一个输入（或输出）数据流对应于子图中几个输入（或输出）数据流，而子图中组成的这些数据流的数据项全体正好是父图中的这一个数据流。

试题二、

问题 1：

试题三、

问题 1：
A1：Central system 或中心系统
A2：Driver 或驾驶员
A3：Regional center 或区域系统
A4：Traffic advice center 或交通广播电台

其中 A3、A4 可以互换
问题 2：
U1：Underpaid transaction U2：Record Illegal use U3：Create transaction U4：Record traffic event U5：Charge card
其中 U1、U2 可以互换，用例名称必须为英文，因为表中的汉字是对用例的说明。问题 3：
C1：Center system C2：Traffic events C3：Toll gantry C4：Radar sensor C5：Radio transceiver C6：Digital Camera
其中 C4、C5、C6 可以互换

【解析】
问题 1：首先要识别出参与者，是人或组织。题干中表示参与者的有：驾驶员、区域系统、中心系统、交通广播电台。由问题 2 得出 A1 为中心系统。
问题 2：填写用例，要先找到突破口，本题有两个突破口，一个是 U1、U2 是 U3 的扩展， 而所给定的用例名称中，只有记录透支帐户交易信息和记录失败交易信息，是记录收费交易的扩展。二个是有一个孤立的用例，从题干中可知为记录交通事件，再加上问题 1 中的参与者，可以推出完整的用例图。

问题 3：先从 C4、C5、C6 与 C3 的一个多组合关系。题干中只有龙门架由三个部分组成。
C1 与 Regional Center 对应关系是 1 个对象对应多个对象，C1 只可能为中心系统。然后题干(5)中获取龙门架的所有记录叫交通事件。且一个 Regional Center 有多个 C2 对象与之对应。
试题四、

问题 1： (1)：i<=n (2)：i<=j
(3)：temp = (temp>=r[i]+r[j-i])emp:(r[i] + r[j – i])
(4)：r[j] = (temp>p[j])emp:p[j];
问题 2:
(5) 动态规划法
(6) O(2n)
(7) O(n2)

【解析】问题 2:
题干中提到说考虑所有可能的 i，得到最大收益的方式，而自底向上算法实现时，使用到数组把其中最优的解记录。是动态规划法。

试题五、

(1)virtual void buildPartA() = 0

(2)virtual Product * getResult() = 0

(3)product->setPartA

(4)product->setPartB

(5)builder->buildPartA();

builder->buildPartB();

Product* p = builder->getResult();
【解析】第 5 空，由于后面的代码省略，所以以上三个都可。

试题六、

(1)virtual void buildPartA()

(2)virtual Product getResult()

(3)product.setPartA

(4)product.setPartB

(5)builder.buildPartA();

builder.buildPartB();

Product p = builder.getResult();
【解析】第 5 空，由于后面的代码省略，所以以上三个都可。

下半年再见吧！

很遗憾，虽然明天还有期末考试，但从刚刚看到成绩出来，差4分过涛汹涌而焦灼的心久久不能平静下来。

什么原因，复习的不够吗个月的备考啊，虽然不是每一天都在复习做题，但是每周都在做啊，基础知识刷了一段时间，虽然不是都掌握了，但是基本上能达到50分了啊是为什么连基础知识都没过，白白浪费了这么多时间。

之前和老师谈过，都多大的人了，还没有给自己一个明确的方向，不知道自己该干什么，对得起谁，对得起自己吗/p>

为什么br> 难道自己真不适合走这条路吗br> 问问自己，这三个月时间都干了些什么，这一学期，最重要的两个考试，我是看的特别重要的，真的是希望能够过了，比做什么都值了，但凡事都是事与愿违，期望越大，失望就越大！！！
为了能够考过，我不惜逃过几堂课的时间来刷题，结果呢篮打水一场空。两头都没有好结果。
为了能够考过，我从4月份开始就放下了其他所有的事情，现在。。。

在其他人看来，我是一个所谓的学习好的同学，其实不然，那都是装出来的。
从今年开始，逐渐的不喜欢学习专业课知识了，慢慢的很少学习课本，基本上上完课之后都没怎么看过书，做作业不是找同学的作业抄，就是百度 上搜答案，现在考试也是抱着这种 能过就行 的态度，怎么会这样前从不会逃课，现在也开始逃课了，这些坏毛病全学会了。。。

皮了！！！的确实皮了好多，

静！！！
静！！！
静！！！
安安心心静下来吧！好好准备明天的考试！

目浴，灾戒，静心，养神！
左手拿一串木珠，右手拿一根木棍，边敲嘴里边默念，“阿弥陀佛，善哉，善哉！！！”