图 3-1 ORS 用例图
图 3-2 提交稿件过程的活动图 【问题1】（4 分）
根据【说明】中的描述，使用表3-1中的英文名称，给出图3-1中A1～A4所对应的参与者。
【问题2】（3 分）
根据【说明】中的描述，使用表3-2中的英文名称，给出图3-1中U1～U3所对应的用例。
【问题3】（4 分）
根据【说明】中的描述，给出图3-1中（1）和（2）所对应的关系。 【问题4】（4 分）
根据【说明】中的描述，使用表3-2和表3-3中的英文名称，给出图3-2中Action1～Action4对应的活动。
试题四（共15 分）
阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。 【说明】
希赛公司供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，?，mn，每项食物mi的营养价值为vi，价格为pi，其中i=1,2,?,n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。 【问题1】（9 分）
下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。 伪代码中的主要变量说明如下： n： 总的食物项数；
v： 营养价值数组，下标从1到n，对应第1到第n项食物的营养价值； p： 价格数组，下标从1到n，对应第1到第n项食物的价格； M：总价格标准，即套餐的价格不超过M；
x：解向量（数组），下标从1到n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中；
nv：n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。 伪代码如下：
MaxNutrientValue(n, v, p, M, x) 1 for i = 0 to n 2 nv[i][0] = 0 3 for j = 1 to M 4 nv[0][j] = 0 5 for i = 1 to n 6 for j = 1 to M
7 if j < p[i] //若食物mi不能加入到套餐中
8 nv[i][j] = nv[i - 1][j] 9 else if （1）
10 nv[i][j] = nv[i - 1][j] 11 else
12 nv[i][j] = nv[i - 1][j–p[i]] + v[i] 13 j = M
14 for i = n downto 1 15 if （2） 16 x[i] = 0 17 else
18 x[i] = 1 19 （3） 20 return x and nv[n][M] 【问题2】（4 分）
现有5项食物，每项食物的营养价值和价格如表4-1所示。 表 4-1 食物营养价值及价格表
编码 m1 m2 m3 m4 m5 营养价值 200 180 225 200 50 价格 50 30 45 25 5 若要求总价格不超过100的营养价值最大的套餐，则套餐应包含的食物有（4）（用食物项的编码表示），对应的最大营养价值为 （5）。 【问题3】（2 分）
【问题1】中伪代码的时间复杂度为（6）（用Ο符号表示）。 从下列的3道试题（试题五至试题七）中任选1道解答。 如果解答的试题数超过1道，则题号小的1道解答有效。
试题五（共15 分）
阅读下列说明和C函数，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】
已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5，10，20，15，25，30}，集合B={5，15，35，25}，如图5-1(a)所示，运算完成后的结果如图5-1(b)所示。
图5-1 集合A、B运算前后示意图 链表结点的结构类型定义如下： typedef struct Node{ ElemType elem; struct Node *next; }NodeType; 【C 函数】
void Difference(NodeType **LA, NodeType *LB) {
NodeType *pa, *pb, *pre, *q; pre = NULL; （1） ; while (pa) { pb = LB; while ( （2） ) pb = pb->next; if ( （3） ) { if (!pre) *LA = （4） ;
else
（5） = pa->next; q = pa; pa = pa->next; free(q); }
else { （6） ; pa = pa->next; } } }
试题六（共15 分）
阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】
已知某类库开发商提供了一套类库，类库中定义了Application类和Document类，它们之间的关系如图6-1所示，其中，Application类表示应用程序自身，而Document类则表示应用程序打开的文档。Application类负责打开一个已有的以外部形式存储的文档，如一个文件，一旦从该文件中读出信息后，它就由一个Document对象表示。
图 6-1 Application与Document关系图
当开发一个具体的应用程序时，开发者需要分别创建自己的 Application 和 Document子类，例如图6-1中的类 MyApplication 和类 MyDocument，并分别实现 Application 和Document类中的某些方法。