試題二（共15分）
閱讀下列說明，回答問題1至問題3；將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某銷售公司當(dāng)前的銷售業(yè)務(wù)為商城實(shí)體店銷售。現(xiàn)該公司擬開展網(wǎng)絡(luò)銷售業(yè)務(wù)，需要開發(fā)一個(gè)信息化管理系統(tǒng)。請(qǐng)根據(jù)公司現(xiàn)有業(yè)務(wù)及需求完成該系統(tǒng)的數(shù)據(jù)庫設(shè)計(jì)。
【需求描述】
（1）記錄公司所有員工的信息。員工信息包括工號(hào)、身份證號(hào)、姓名、性別、出生日期和電話，并只登記一部電話。
（2）記錄所有商品的信息。商品信息包括商品名稱、生產(chǎn)廠家、銷售價(jià)格和商品介紹。系統(tǒng)內(nèi)部用商品條碼唯一區(qū)別每種商品。
（3）記錄所有顧客的信息。顧客信息包括顧客姓名、身份證號(hào)、登錄名、登錄密碼、和電話號(hào)碼。一位顧客只能提供一個(gè)電話號(hào)碼。系統(tǒng)自動(dòng)生成唯一的顧客編號(hào)。
（4）顧客登錄系統(tǒng)之后，在網(wǎng)上商城購買商品。顧客可將選購的商品置入虛擬的購物車內(nèi)，購物車可長(zhǎng)期存放顧客選購的所有商品。顧客可在購物車內(nèi)選擇商品、修改商品數(shù)量后生成網(wǎng)購訂單。訂單生成后，由顧客選擇系統(tǒng)提供的備選第三方支付平臺(tái)進(jìn)行電子支付，支付成功后系統(tǒng)需要記錄唯一的支付憑證編號(hào)，然后由商城根據(jù)訂單進(jìn)行線下配送。
（5）所有的配送商品均由倉庫統(tǒng)一出庫。為方便顧客，允許每位顧客在系統(tǒng)中提供多組收貨地址、收貨人及聯(lián)系電話。一份訂單所含的多個(gè)商品可能由多名分檢員根據(jù)商品所在倉庫信息從倉庫中進(jìn)行分揀操作，分揀后的商品交由配送員根據(jù)配送單上的收貨地址進(jìn)行配送。
（6）新設(shè)計(jì)的系統(tǒng)要求記錄實(shí)體店的每筆銷售信息，包括營(yíng)業(yè)員、顧客、所售商品及其數(shù)量。
【概念模型設(shè)計(jì)】
根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖2-1所示。



【邏輯結(jié)構(gòu)設(shè)計(jì)】
根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式（不完整）：
員工（工號(hào)，身份證號(hào)，姓名，性別，出生日期，電話）
商品（商品條碼，商品名稱，生產(chǎn)廠家，銷售價(jià)格，商品介紹，（a））
顧客（顧客編號(hào)，姓名，身份證號(hào)，登錄名，登錄密碼，電話）
收貨地點(diǎn)（收貨ID，顧客編號(hào)，收貨地址，收貨人，聯(lián)系電話）
購物車（顧客編號(hào)，商品條碼，商品數(shù)量）
訂單（訂單ID，顧客編號(hào)，商品條碼，商品數(shù)量，（b））
分檢（分揀ID，分揀員工號(hào)，（c），分揀時(shí)間）
配送（配送ID，分揀ID，配送員工號(hào)，收貨ID，配送時(shí)間，簽收時(shí)間，簽收快照）
銷售（銷售ID，營(yíng)業(yè)員工號(hào)，顧客編號(hào)，商品條碼，商品數(shù)量）
?【問題1】（4分）
補(bǔ)充圖2-1中的“配送”聯(lián)系所關(guān)聯(lián)的對(duì)象及聯(lián)系類型。
?【問題2】（6分）
補(bǔ)充邏輯結(jié)構(gòu)設(shè)計(jì)中的（a）、（b）和（c）三處空缺。
?【問題3】（5分）
對(duì)于實(shí)體店銷售，若要增加送貨上門服務(wù)，由營(yíng)業(yè)員在系統(tǒng)中下訂單，與網(wǎng)購的訂單進(jìn)行后續(xù)的統(tǒng)一管理。請(qǐng)根據(jù)該需求，對(duì)圖2-1進(jìn)行補(bǔ)充，并修改訂單關(guān)系模式。

試題三（共15分）
閱讀下列說明和圖，回答問題1至問題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某軟件公司欲設(shè)計(jì)實(shí)現(xiàn)一個(gè)虛擬世界仿真系統(tǒng)。系統(tǒng)中的虛擬世界用于模擬現(xiàn)實(shí)世界中的不同環(huán)境（由用戶設(shè)置并創(chuàng)建），用戶通過操作仿真系統(tǒng)中的1~2個(gè)機(jī)器人來探索虛擬世界。機(jī)器人維護(hù)著兩個(gè)變量b1和b2，用來保存從虛擬世界中讀取的字符。
該系統(tǒng)的主要功能描述如下：
（1）機(jī)器人探索虛擬世界（RunRobots）。用戶使用編輯器（Editor）編寫文件以設(shè)置想要模擬的環(huán)境，將文件導(dǎo)入系統(tǒng)（LoadFile）從而在仿真系統(tǒng)中建立虛擬世界（SetupWorld）。機(jī)器人在虛擬世界中的行為也在文件中進(jìn)行定義，建立機(jī)器人的探索行為程序（SetupProgram）。機(jī)器人在虛擬世界中探索時(shí)（RunProgram），有2種運(yùn)行模式：
①自動(dòng)控制（Run）：事先編排好機(jī)器人的動(dòng)作序列（指令（Instruction）），執(zhí)行指令，使機(jī)器人可以連續(xù)動(dòng)作。若干條指令構(gòu)成機(jī)器人的指令集（InstructionSet）。
②單步控制(Step)：自動(dòng)控制方式的一種特殊形式，只執(zhí)行指定指令中的一個(gè)動(dòng)作。
（2）手動(dòng)控制機(jī)器人（ManipulateRobots）。選定1個(gè)機(jī)器人后（SelectRobot），可以采用手動(dòng)方式控制它。手動(dòng)控制有4種方式：
①M(fèi)ove：機(jī)器人朝著正前方移動(dòng)一個(gè)交叉點(diǎn)。
②Left：機(jī)器人原地沿逆時(shí)針方向旋轉(zhuǎn)90度。
③Read：機(jī)器人讀取其所在位置的字符，并將這個(gè)字符的值賦給b1；如果這個(gè)位置上沒有字符，則不改變b1的當(dāng)前值。
④Write：將b1中的字符寫入機(jī)器人當(dāng)前所在的位置，如果這個(gè)位置上已經(jīng)有字符，該字符的值將會(huì)被b1的值替代。如果這時(shí)b1沒有值，即在執(zhí)行Write動(dòng)作之前沒有執(zhí)行過任何Read動(dòng)作，那么需要提示用戶相應(yīng)的錯(cuò)誤信息（ShowErrors）。
手動(dòng)控制與單步控制的區(qū)別在于，單步控制時(shí)執(zhí)行的是指令中的動(dòng)作，只有一種控制方式，即執(zhí)行下個(gè)動(dòng)作；而手動(dòng)控制時(shí)有4種動(dòng)作。
現(xiàn)采用面向?qū)ο蠓椒ㄔO(shè)計(jì)并實(shí)現(xiàn)該仿真系統(tǒng)，得到如圖3-1所示的用例圖和圖3-2所示的初始類圖。圖3-2中的類“Interpreter”和“Parser”用于解析描述虛擬世界的文件以及機(jī)器人行為文件中的指令集。






?【問題1】（6分）
根據(jù)說明中的描述，給出圖3-1中U1～U6所對(duì)應(yīng)的用例名。
?【問題2】（4分）
圖3-1中用例U1～U6分別與哪個(gè)（哪些）用例之間有關(guān)系，是何種關(guān)系？
?【問題3】（5分）
根據(jù)說明中的描述，給出圖3-2中C1～C5所對(duì)應(yīng)的類名。

試題四（共15分）
閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
在一塊電路板的上下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，用(i,π(i))表示將上端接線柱i與下端接線柱π(i)相連，稱其為該電路板上的第i條連線。如圖4-1所示的π(i)排列為{8,7,4,2,5,1,9,3,10,6}。對(duì)于任何1≤iπ(j)。



在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上，在同一層上的連線不相交?，F(xiàn)在要確定將哪些連線安排在一層上，使得該層上有盡可能多的連線，即確定連線集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。
【分析問題】
記N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集為MNS(i,j)，size(i,j)=|MNS(i,j)|。
經(jīng)分析，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對(duì)規(guī)模為n的電路布線問題，可以構(gòu)造如下遞歸式：



【C代碼】
下面是算法的C語言實(shí)現(xiàn)。
（1）變量說明
size[i][j]：上下端分別有i個(gè)和j個(gè)接線柱的電路板的第一層最大不相交連接數(shù)
pi[i]：π(i)，下標(biāo)從1開始
（2）C程序
#include"stdlib.h"
#include
#define N 10/*問題規(guī)模*/
Int m=0；/*牢記錄最大連接集合中的接線柱*/
Void maxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交連接數(shù)*/
int i,j;
for(j=0;j for(j=pi[i];j<=n;j++)（1）;/*當(dāng)j>=π(1)時(shí)*/
for(i=2;ifor(j=0;j for(j=pi[i];j<=n；j++){/*當(dāng)j>=c[i]時(shí),考慮兩種情況*/
size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+1?size[i-l][j]:size[i-l][pi[i]-l]+l;
}
}
/*最大連接數(shù)*/
size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+1?size[n-l][n]:size[n-l][pi[n]-l]+l;
}
/*構(gòu)造最大不相交連接集合，net[i]表示最大不相交子集中第i條連線的上端接線柱的序號(hào)*/
void constructSet（int pi[],int size[N+1][N+1],int n,int net[n]）{
int i,j=n;
m=0；
for(i=n；i>1;i--){/*從后往前*/
if(size[i][j]!=size[i-l][j]){/*(i,pi[i])是最大不相交子集的一條連線*/
（3）;/*將i記錄到數(shù)組net中，連接線數(shù)自增1*/
j=pi[i]-1;/*更新擴(kuò)展連線柱區(qū)間*/
}
}
if(j>=pi[l])net[m++]=l;/*當(dāng)i=1時(shí)*/
}
?【問題1】（6分）
根據(jù)以上說明和C代碼，填充C代碼中的空（1）~（3）。
?【問題2】（6分）
根據(jù)題干說明和以上C代碼，算法采用了（4）算法設(shè)計(jì)策略。
函數(shù)maxNum和constructSet的時(shí)間復(fù)雜度分別為（5）和（6）（用O表示）。
?【問題3】（3分）
若連接排列為{8,7,4,2,5,1,9,3,10,6}，即如圖4-1所示，則最大不相交連接數(shù)為（7），包含的連線為（8）（用(i,π(i))的形式給出）。

閱讀下列說明和Java代碼，將應(yīng)填入（n）處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
某軟件系統(tǒng)中，已設(shè)計(jì)并實(shí)現(xiàn)了用于顯示地址信息的類Address（如圖6-1所示），現(xiàn)要求提供基于Dutch語言的地址信息顯示接口。為了實(shí)現(xiàn)該要求并考慮到以后可能還會(huì)出現(xiàn)新的語言的接口，決定采用適配器（Adapter）模式實(shí)現(xiàn)該要求，得到如圖6-1所示的類圖。



【Java代碼】
import java.util.*;
Class Address{
public void street(){//實(shí)現(xiàn)代碼省略}
public void zip(){//實(shí)現(xiàn)代碼省略}
public void city(){//實(shí)現(xiàn)代碼省略}
∥其他成員省略
}
class DutchAddress{
public void straat(){//實(shí)現(xiàn)代碼省略}
public void postcode(){//實(shí)現(xiàn)代碼省略}
public void plaats(){//實(shí)現(xiàn)代碼省略}
//其他成員省略
}
class DutchAddressAdapter extends DutchAddress{
private（1）;
public DutchAddressAdapter(Addressaddr){
address=addr;
}
public void straat(){
（2）;
}
public void postcode(){
（3）;
}
public void plaats(){
（4）;
}
//其他成員省略
}
class Test{
public static void main(String[]args){
Address addr=new Address();
（5）;
System.out.println("\n The DutchAddress\n");
testDutch(addrAdapter);
}
Static void testDutch(DutchAddressaddr){
addr.straat();
addr.postcode();
Addr.plaats();
}
}