試題一：閱讀以下說明和圖，回答問題1至問題3，將解答填入答題紙的對應欄內(nèi)。
【說明】
某時裝郵購提供商擬開發(fā)訂單處理系統(tǒng)，用于處理客戶通過電話、傳真、郵件或web站點所下訂單。其主要功能如下：
（1）增加客戶記錄。將新客戶信息添加到客戶文件，并分配一個客戶號以備后續(xù)使用。
（2）查詢商品信息。接收客戶提交商品信息請求，從商品文件中查詢商品的價格和可訂購數(shù)量等商品信息，返回給客戶。
（3）增加訂單記錄。根據(jù)客戶的訂購請求及該客戶記錄的相關(guān)信息，產(chǎn)生訂單并添加到訂單文件中。
（4）產(chǎn)生配貨單。根據(jù)訂單記錄產(chǎn)生配貨單，并將配貨單發(fā)送給倉庫進行備貨；備好貨后，發(fā)送備貨就緒通知。如果現(xiàn)貨不足，則需向供應商訂貨。
（5）準備發(fā)貨單。從訂單文件中獲取訂單記錄，從客戶文件中獲取客戶記錄，并產(chǎn)生發(fā)貨單。
（6）發(fā)貨。當收到倉庫發(fā)送的備貨就緒通知后，根據(jù)發(fā)貨單給客戶發(fā)貨；產(chǎn)生裝運單并發(fā)送給客戶。
（7）創(chuàng)建客戶賬單。根據(jù)訂單文件中的訂單記錄和客戶文件中的客戶記錄，產(chǎn)生并發(fā)送客戶賬單，同時更新商品文件中的商品數(shù)量和訂單文件中的訂單狀態(tài)。
（8）產(chǎn)生應收賬戶。根據(jù)客戶記錄和訂單文件中的訂單信息，產(chǎn)生并發(fā)送給財務部門應收賬戶報表。
現(xiàn)采用結(jié)構(gòu)化方法對訂單處理系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的頂層數(shù)據(jù)流圖和圖1-2所示0層數(shù)據(jù)流圖。


【問題1】（3分）
使用說明中的詞語，給出圖1-1中的實體e1~e3的名稱。
【問題2】（3分）
使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲d1~d3的名稱。
【問題3】（9分）
（1）給出圖1-2中處理（加工）p1和p2的名稱及其相應的輸入、輸出流。
（2）除加工p1和p2的輸入輸出流外，圖1-2還缺失了1條數(shù)據(jù)流，請給出其起點和終點。

查看答案

試題二：閱讀下列說明和c代碼，回答下列問題。

[說明]

用兩臺處理機a和b處理n個作業(yè)。設(shè)a和b處理第i個作業(yè)的時間分別為ai和bi。由于各個作業(yè)的特點和機器性能的關(guān)系，對某些作業(yè)，在a上處理時間長，而對某些作業(yè)在b上處理時間長。一臺處理機在某個時刻只能處理一個作業(yè)，而且作業(yè)處理是不可中斷的，每個作業(yè)只能被處理一次?，F(xiàn)要找出一個最優(yōu)調(diào)度方案，使得n個作業(yè)被這兩臺處理機處理完畢的時間(所有作業(yè)被處理的時間之和)最少。算法步驟如下。

11確定候選解上界為r短的單臺處理機處理所有作業(yè)的完成時間m，

12用p(x,y,k)=1表示前k個作業(yè)可以在a用時不超過x且在b用時不超過y時間內(nèi)處理完成，則p(x,y,k)=p(x-ak,y,k-1)‖p(x,y-bk,k-1)(‖表示邏輯或操作)。

13得到最短處理時間為min(max(x,y))。

[c代碼]

下面是該算法的c語言實現(xiàn)。

11常量和變量說明

n：作業(yè)數(shù)

m：候選解上界

a：數(shù)組，長度為n，記錄n個作業(yè)在a上的處理時間，下標從0開始

b：數(shù)組，長度為n，記錄n個作業(yè)在b上的處理時間，下標從0開始

k：循環(huán)變量

p：三維數(shù)組，長度為(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 {   /*確定最優(yōu)解并輸出*/

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]

根據(jù)以上說明和c代碼，填充c代碼中的空缺處。

[問題2]

根據(jù)以上c代碼，算法的時間復雜度為______(用o符號表示)。

[問題3]

考慮6個作業(yè)的實例，各個作業(yè)在兩臺處理機上的處理時間如表2-7所示。該實例的最優(yōu)解為______，最優(yōu)解的值(即最短處理時間)為______。最優(yōu)解用(x1，x2，x3，x4，x5，x6)表示，其中若第i個作業(yè)在a上處理，則xi=1，否則xi=2。如(1，1，1，1，2，2)表示作業(yè)1、2、3和4在a上處理，作業(yè)5和6在b上處理。

表2-7 各個作業(yè)在兩臺處理機上的處理時間

查看答案