文档介绍：中级软件设计师2 011下半年下午试题
试题一
阅读下列说明和图。
［说明］
某公司欲开发招聘系统以提高招聘效率，其主要功能如下：
⑴接受申请
验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申 请，给应聘使用。单次卡(Minitrip Card)在指定的行程内使用，且只能使用一次。其中，季卡和 单次卡都是预付卡(Prepaid Card),需要客户(Customer)预存一定的费用。
系统的主要功能有：客户注册、申请行驶卡、使用行驶卡行驶等。
使用常规卡行驶，在进入行程起点时，系统记录行程起点、进入时间(Date Of Entry) 等信息。在到达行程终点时，系统根据行驶的里程数和所持卡的里程单价(UnitPrice) 计算应付费用，并打印费用单(Invoice)。
季卡的使用流程与常规卡类似，但是不需要打印费用单，系统自动从卡中扣除应付 费用。
单次卡的使用流程与季卡类似，但还需要在行程的起点和终点上检查行驶路线是否 符合该卡所规定的行驶路线。
现采用面向对象方法开发该系统，使用UML进行建模。构建出的用例图和类图分别 如图3-1和图3-2所示。
客户
8、根据说明中的描述，给出图3-1中U1和U2所对应的用例，以及(1)所对应的关系。
Cuitomcr *tvgistcr to
I used
类圈
9、根据说明中的描述，给出图3-2中缺少的C1-C6所对应的类名以及(2) - (3)处所对应的多重度 (类名使用说明中给出的英文词汇)。
10、根据说明中的描述，给出Road Segment、Trajectory和Card所对应的类的关键属性(属性 名使用说明中给出的英文词汇)。
试题四
阅读下列说明和C代码，将应填入(n)处的字句。
[说明]
设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件 i具有重量咯,和价格J,。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
采用回溯法来求解该问题：
首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1, 2, m),
将解空间用树形结构表示。
接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点， 同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。 判断当前的机器价格(c1T)是否超过上限(cc),重量(wT1)是否比当前已知的解(最小重量)大，若是, 应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不 再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断 当前的机器价格(C11 + C21)是否超过上限(CC),重量(Wn+W,|)是否比当前已知的解(最小重量)大。若 是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来 的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无 活结点为止。
[C代码]
下面是该算法的C语言实现。
11变量说明
n：机器的部件数
m：供应商数
CC:价格上限
w[][]:二维数组，w[i] [j]表示第j个供应商供应的第i个部件的重量
c[][]：二维数组，c[i]
bestW：满足价格上限约束条件的最小机器重量
bestC：最小重量机器的价格
bestX []:最优解，一维数组，bestX [i]表示第i个部件来自哪个供应商
cw：搜索过程中机器的重量
cp：搜索过程中机器的价格
x[]：搜索过程中产生的解，x[i]表示第i个部件来自哪个供应商
i：当前考虑的部件，从Oiljn-l
j：循环变量
12 函数 backtrack
int n=3；
int m=3；
int cc=4;
int w[3] [3]=H1,2/3)z(3,2,1k(2,2,2)};
int c[3] [3]=((l,2/3}/(3,2,1},(2,2,2}};
int bestW=8；
int bestC=0；
int bestX[3]=(0, 0, 0};
int cw=0;
int cp=0；
int x [3] = ( 0, 0, 0 };
int backtrack (int i)(
int j =0；
int found=0；
if (i>n-l) { /*得到问题解*/
bestW=cw；
bestC=cp；
for (j =0 ； j <n； j + + ) {
H ；
}
return