第2題： 閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
某公司擬開發(fā)一多用戶電子郵件客戶端系統(tǒng)，部分功能的初步需求分析結(jié)果如下：
（1）郵件客戶端系統(tǒng)支持多個(gè)用戶，用戶信息主要包括用戶名和用戶密碼，且系統(tǒng)中的用戶名不可重復(fù)。
（2）郵件帳號信息包括郵件地址及其相應(yīng)的密碼，一個(gè)用戶可以擁有多個(gè)郵件地址  （如userl＠123.com）。
（3）一個(gè)用戶可擁有一個(gè)地址薄，地址簿信息包括聯(lián)系人編號、姓名、電話、單位、地址、郵件地址1、郵件地址2、郵件地址3等信息。地址薄中一個(gè)聯(lián)系人只能屬于一個(gè)用戶，且聯(lián)系人編號唯一標(biāo)識一個(gè)聯(lián)系人。
（4）一個(gè)郵件帳號可以含有多封郵件，一封郵件可以含有多個(gè)附件。郵件主要包括郵件號、發(fā)件人地址、收件人地址、郵件狀態(tài)、郵件主題、郵件內(nèi)容、發(fā)送時(shí)間、接收時(shí)間。其中，郵件號在整個(gè)系統(tǒng)內(nèi)唯一標(biāo)識一封郵件，郵件狀態(tài)有己接收、待發(fā)送、已發(fā)送和已刪除4種，分別表示郵件是屬于收件箱、發(fā)件箱、己發(fā)送箱和廢件箱。一封郵件可以發(fā)送給多個(gè)用戶。附件信息主要包括附件號、附件文件名、附件大小。一個(gè)附件只屬于一封郵件，附件號僅在一封郵件內(nèi)唯一。
?【問題1】（5分）
根據(jù)以上說明設(shè)計(jì)的E-R圖如圖2-1所示，請指出地址簿與用戶、電子郵件帳號與郵件、郵件與附件之間的聯(lián)系類型。

?【問題2】（4分）
該郵件客戶端系統(tǒng)的主要關(guān)系模式如下，請?zhí)钛a(bǔ)(a) ~ (c)的空缺部分。
用戶（用戶名，用戶密碼）
地址簿（  （a）  ，聯(lián)系人編號，姓名，電話，單位地址，郵件地址1，郵件地址2，郵件地址3）
郵件帳號（郵件地址，郵件密碼，用戶名）
郵件（  （b）  ，收件人地址，郵件狀態(tài)，郵件主題，郵件內(nèi)容，發(fā)送時(shí)間，接收時(shí)間）
附件（  （c）  ，附件號，附件文件名，附件大小）
?【問題3】（6分）
（1）請指出【問題2】中給出的地址簿、郵件和附件關(guān)系模式的主鍵，如果關(guān)系模式存在外鍵請指出。
（2）附件屬于弱實(shí)體嗎？請用50字以內(nèi)的文字說明原因。
答案解析與討論：m.xiexiliangjiufa.com/st/3808523823.html

第3題： 閱讀下列說明和UML圖，回答問題1至問題4，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
某企業(yè)為了方便員工用餐，餐廳開發(fā)了一個(gè)訂餐系統(tǒng)（COS：Cafeteria Ordering System），企業(yè)員工可通過企業(yè)內(nèi)聯(lián)網(wǎng)使用該系統(tǒng)。
企業(yè)的任何員工都可以查看菜單和今日特價(jià)。
系統(tǒng)的顧客是注冊到系統(tǒng)的員工，可以訂餐（如果未登錄，需先登錄）、注冊工資支付、預(yù)約規(guī)律的訂餐，在特殊情況下可以覆蓋預(yù)訂。
餐廳員工是特殊顧客，可以進(jìn)行備餐、生成付費(fèi)請求和請求送餐，其中對于注冊工資支付的顧客生成付費(fèi)請求并發(fā)送給工資系統(tǒng)。
菜單管理員是餐廳特定員工，可以管理菜單。
送餐員可以打印送餐說明，記錄送餐信息（如送餐時(shí)間）以及記錄收費(fèi)（對于沒有注冊工資支付的顧客，由送餐員收取現(xiàn)金后記錄）。
顧客訂餐過程如下：
1．顧客請求查看菜單；
2．系統(tǒng)顯示菜單和今日特價(jià)；
3．顧客選菜；
4．系統(tǒng)顯示訂單和價(jià)格；
5．顧客確認(rèn)訂單；
6．系統(tǒng)顯示可送餐時(shí)間；
7．顧客指定送餐時(shí)間、地點(diǎn)和支付方式；
8．系統(tǒng)確認(rèn)接受訂單，然后發(fā)送Email給顧客以確認(rèn)訂餐，同時(shí)發(fā)送相關(guān)訂餐信息通  知給餐廳員工。
系統(tǒng)采用面向?qū)ο蠓椒ㄩ_發(fā)，使用UML進(jìn)行建模。系統(tǒng)的頂層用例圖和一次訂餐的活動圖初稿分別如圖3-1和圖3-2所示。

?【問題1】（2分）
根據(jù)【說明】中的描述，給出圖3-1中A1和A2所對應(yīng)的參與者。
?【問題2】（8分）
根據(jù)【說明】中的描述，給出圖3-1中缺少的四個(gè)用例及其所對應(yīng)的參與者。
?【問題3】（4分）
根據(jù)【說明】中的描述，給出圖3-2中（1）~（4）處對應(yīng)的活動名稱或圖形符號。
?【問題4】（1分）
指出圖3-1中員工和顧客之間是什么關(guān)系，并解釋該關(guān)系的內(nèi)涵。
答案解析與討論：m.xiexiliangjiufa.com/st/3808624030.html

第4題： 閱讀下列說明，回答問題1至問題2，將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
0-1背包問題可以描述為：有n個(gè)物品，對i=1，2，…，n，第i個(gè)物品價(jià)值為vi ，重量為wi（vi，和wi為非負(fù)數(shù)），背包容量為W（W為非負(fù)數(shù)），選擇其中一些物品裝入背包，使裝入背包物品的總價(jià)值最大，即，且總重量不超過背包容量，即，其中，xi∈{0，1}，xi=0表示第i個(gè)物品不放入背包，xi=1表示第i個(gè)物品  放入背包。
?【問題1】（8分）
用回溯法求解此0-1背包問題，請?zhí)畛湎旅鎮(zhèn)未a中（1）~（4）處空缺。
回溯法是一種系統(tǒng)的搜索方法。在確定解空間后，回溯法從根結(jié)點(diǎn)開始，按照深度優(yōu)先策略遍歷解空間樹，搜索滿足約束條件的解。對每一個(gè)當(dāng)前結(jié)點(diǎn)，若擴(kuò)展該結(jié)點(diǎn)己經(jīng)不滿足約束條件，則不再繼續(xù)擴(kuò)展。為了進(jìn)一步提高算法的搜索效率，往往需要設(shè)計(jì)一個(gè)限界函數(shù)，判斷并剪枝那些即使擴(kuò)展了也不能得到最優(yōu)解的結(jié)點(diǎn)。現(xiàn)在假設(shè)已經(jīng)設(shè)計(jì)了BOUND（v，w，k，W）函數(shù)，其中v， w， k和W分別表示當(dāng)前已經(jīng)獲得的價(jià)值、當(dāng)前背包的重量、己經(jīng)確定是否選擇的物品數(shù)和背包的總?cè)萘?。對?yīng)于搜索樹中的某個(gè)結(jié)點(diǎn)，該函數(shù)值表示確定了部分物品是否選擇之后，對剩下的物品在滿足約束條件的前提下進(jìn)行選擇可能獲得的最大價(jià)值，若該價(jià)值小于等于當(dāng)前已經(jīng)得到的最優(yōu)解，則該結(jié)點(diǎn)無需再擴(kuò)展。
下面給出0-1背包問題的回溯算法偽代碼。
函數(shù)參數(shù)說明如下：
W：背包容量；n：物品個(gè)數(shù)；w：重量數(shù)組；v：價(jià)值數(shù)組；fw：獲得最大價(jià)值時(shí)背包的重量；fp：背包獲得的最大價(jià)值；X：問題的最優(yōu)解。
變量說明如下：
cw：當(dāng)前的背包重量；cp：當(dāng)前獲得的價(jià)值；k：當(dāng)前考慮的物品編號；Y：當(dāng)前已獲得的部分解。

?【問題2】（7分）
考慮表4-1的實(shí)例，假設(shè)有3個(gè)物品，背包容量為22。圖4-1中是根據(jù)上述算法構(gòu)造的搜索樹，其中結(jié)點(diǎn)的編號表示了搜索樹生成的順序，邊上的數(shù)字1/0分別表示選擇／不選擇對應(yīng)物品。除了根結(jié)點(diǎn)之外，每個(gè)左孩子結(jié)點(diǎn)旁邊的上下兩個(gè)數(shù)字分別表示當(dāng)前背包的重量和已獲得的價(jià)值，右孩子結(jié)點(diǎn)旁邊的數(shù)字表示擴(kuò)展了該結(jié)點(diǎn)后最多可能獲得的價(jià)值。為獲得最優(yōu)解，應(yīng)該選擇物品 （5） ，獲得的價(jià)值為 （6） 。

對于表4-1的實(shí)例，若采用窮舉法搜索整個(gè)解空間，則搜索樹的結(jié)點(diǎn)數(shù)為 （7） ，而用了上述回溯法，搜索樹的結(jié)點(diǎn)數(shù)為 （8） 。
答案解析與討論：m.xiexiliangjiufa.com/st/3808721842.html

第6題： 閱讀下列說明和Java代碼，將應(yīng)填入 （n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
現(xiàn)欲構(gòu)造一文件／目錄樹，采用組合（Composite）設(shè)計(jì)模式來設(shè)計(jì)，得到的類圖如6-1所示：

答案解析與討論：m.xiexiliangjiufa.com/st/38089467.html

第7題： 閱讀以下說明和C程序，將應(yīng)填入 （n） 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
現(xiàn)有n（n<1000）節(jié)火車車廂，順序編號為1,2,3,?,n，按編號連續(xù)依次從A方向的鐵軌駛?cè)?，從B方向鐵軌駛出，一旦車廂進(jìn)入車站（Station）就不能再回到A方向的鐵軌上；一旦車廂駛?cè)隑方向鐵軌就不能再回到車站，如圖7-1所示，其中Station為棧結(jié)構(gòu)，初始為空且最多能停放1000節(jié)車廂。

下面的C程序判斷能否從B方向駛出預(yù)先指定的車廂序列，程序中使用了棧類型STACK，關(guān)于?；静僮鞯暮瘮?shù)原型說明如下：
void InitStack(STACK *s)：初始化棧。
void Push (STACK *s，int e）：將一個(gè)整數(shù)壓棧，棧中元素?cái)?shù)目增1。 void Pop (STACK *s)：棧頂元素出棧，棧中元素?cái)?shù)目減1。
int Top (STACK s)：返回非空棧的棧頂元素值，棧中元素?cái)?shù)目不變。 int IsEmpty (STACK s)：若是空棧則返回1，否則返回0。
【C程序】
#include
／*此處為棧類型及其基本操作的定義，省略*／
int main()｛
STACK station;
int state[1000];
int n;                                ／*車廂數(shù)*／
int begin, i, j, maxNo;           ／*maxNo為A端正待入棧的車廂編號*／
printf("請輸入車廂數(shù)：");
scanf("%d",&n);
printf(“請輸入需要判斷的車廂編號序列（以空格分隔）：”);
if（n＜1）return-1;
for (i＝0; iscanf("%d",&state[i]);
（1） ／*初始化棧*／
maxNo＝1;
for(i=0; i＜n; ){  ／*檢查輸出序列中的每個(gè)車廂號state[i]是否能從棧中獲取*／
if( （2） ){    ／*當(dāng)棧不為空時(shí)*／
if (state[i]=Top(station)) {    ／*棧頂車廂號等于被檢查車廂號*／
printf("%d",Top(station));
Pop(&station);i++;
｝
else
if ( （3） ) {
printf(“error\n”）;
return 1;
｝
else｛
begin= （4）
for(j=begin+l;j <=state [i];j++) {
Push(&station, j);
}
｝
｝
else｛   ／*當(dāng)棧為空時(shí)*／
begin＝maxNo；
for(j＝begin; j<=state[i];j++) {
Push(&station, j);
｝
maxNo＝ （5）
｝
｝
printf("OK");
return 0;
｝答案解析與討論：m.xiexiliangjiufa.com/st/3809024974.html