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


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

查看答案

試題二：閱讀下列說(shuō)明和c代碼，回答下列問(wèn)題。

[說(shuō)明]

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

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

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

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

[c代碼]

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

11常量和變量說(shuō)明

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

m：候選解上界

a：數(shù)組，長(zhǎng)度為n，記錄n個(gè)作業(yè)在a上的處理時(shí)間，下標(biāo)從0開(kāi)始

b：數(shù)組，長(zhǎng)度為n，記錄n個(gè)作業(yè)在b上的處理時(shí)間，下標(biāo)從0開(kāi)始

k：循環(huán)變量

p：三維數(shù)組，長(zhǎng)度為(m+1)*(m+1)*(n+1)

temp：臨時(shí)變量

max：最短處理時(shí)間

12c代碼

#include＜stdio.h＞

int  n,  m;

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

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

void schedule16 {       /*求解過(guò)程*/

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 ;

}

[問(wèn)題1]

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

[問(wèn)題2]

根據(jù)以上c代碼，算法的時(shí)間復(fù)雜度為_(kāi)_____(用o符號(hào)表示)。

[問(wèn)題3]

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

表2-7 各個(gè)作業(yè)在兩臺(tái)處理機(jī)上的處理時(shí)間

查看答案