试题一：阅读以下说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。
【说明】
某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或web站点所下订单。其主要功能如下：
（1）增加客户记录。将新客户信息添加到客户文件，并分配一个客户号以备后续使用。
（2）查询商品信息。接收客户提交商品信息请求，从商品文件中查询商品的价格和可订购数量等商品信息，返回给客户。
（3）增加订单记录。根据客户的订购请求及该客户记录的相关信息，产生订单并添加到订单文件中。
（4）产生配货单。根据订单记录产生配货单，并将配货单发送给仓库进行备货；备好货后，发送备货就绪通知。如果现货不足，则需向供应商订货。
（5）准备发货单。从订单文件中获取订单记录，从客户文件中获取客户记录，并产生发货单。
（6）发货。当收到仓库发送的备货就绪通知后，根据发货单给客户发货；产生装运单并发送给客户。
（7）创建客户账单。根据订单文件中的订单记录和客户文件中的客户记录，产生并发送客户账单，同时更新商品文件中的商品数量和订单文件中的订单状态。
（8）产生应收账户。根据客户记录和订单文件中的订单信息，产生并发送给财务部门应收账户报表。
现采用结构化方法对订单处理系统进行分析与设计，获得如图1-1所示的顶层数据流图和图1-2所示0层数据流图。


【问题1】（3分）
使用说明中的词语，给出图1-1中的实体e1~e3的名称。
【问题2】（3分）
使用说明中的词语，给出图1-2中的数据存储d1~d3的名称。
【问题3】（9分）
（1）给出图1-2中处理（加工）p1和p2的名称及其相应的输入、输出流。
（2）除加工p1和p2的输入输出流外，图1-2还缺失了1条数据流，请给出其起点和终点。

查看答案

试题二：阅读下列说明和c代码，回答下列问题。

[说明]

用两台处理机a和b处理n个作业。设a和b处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系，对某些作业，在a上处理时间长，而对某些作业在b上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。算法步骤如下。

11确定候选解上界为r短的单台处理机处理所有作业的完成时间m，

12用p(x,y,k)=1表示前k个作业可以在a用时不超过x且在b用时不超过y时间内处理完成，则p(x,y,k)=p(x-ak,y,k-1)‖p(x,y-bk,k-1)(‖表示逻辑或操作)。

13得到最短处理时间为min(max(x,y))。

[c代码]

下面是该算法的c语言实现。

11常量和变量说明

n：作业数

m：候选解上界

a：数组，长度为n，记录n个作业在a上的处理时间，下标从0开始

b：数组，长度为n，记录n个作业在b上的处理时间，下标从0开始

k：循环变量

p：三维数组，长度为(m+1)*(m+1)*(n+1)

temp：临时变量

max：最短处理时间

12c代码

#include＜stdio.h＞

int  n,  m;

int a[60], b[60], p[100] [100] [60];

void read16 { …… /*输入n、 a、 b, 求出m, 代码略*/

void schedule16 {       /*求解过程*/

int  x, y, k;

for (x=0;x＜=m;x++){

for (y=0;y＜m;y++){

______

for (k=1;k＜n;k++)

p[x] [y] [k] =0;

}

}

for (k=1;k＜n;k++){

for (x=0;x＜=m;x++) {

for (y=0;y＜=m;y++){

if(x-a[k-1]＞=0)

______;

if(______)

p[x] [y] [k]=(p[x] [y] [k] ‖ p[x] [y-b[k-1]] [k-1]);

}

}

}

}

void write16 {   /*确定最优解并输出*/

int x, y, temp, max=m;

for (x=0;x＜=m;x++) {

for (y=0,y＜=m;y++){

if(______)

temp______:

if (temp＜max) max = temp;

}

}

}

print ("\n%d\n",max) ;

}

void main16 {

read16 ;

schedule16 ;

write16 ;

}

[问题1]

根据以上说明和c代码，填充c代码中的空缺处。

[问题2]

根据以上c代码，算法的时间复杂度为______(用o符号表示)。

[问题3]

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表2-7所示。该实例的最优解为______，最优解的值(即最短处理时间)为______。最优解用(x1，x2，x3，x4，x5，x6)表示，其中若第i个作业在a上处理，则xi=1，否则xi=2。如(1，1，1，1，2，2)表示作业1、2、3和4在a上处理，作业5和6在b上处理。

表2-7 各个作业在两台处理机上的处理时间

查看答案