2016年5月計(jì)算機(jī)技術(shù)與軟件《中級(jí)軟件設(shè)計(jì)師（下午卷）》試題（網(wǎng)友回憶版）

2016年5月計(jì)算機(jī)技術(shù)與軟件《中級(jí)軟件設(shè)計(jì)師（下午卷）》試題（網(wǎng)友回憶版）[問(wèn)答題]1.在一塊電路板的上下兩端分別有n個(gè)接線(xiàn)柱（江南博哥）。根據(jù)電路設(shè)計(jì)，用(i,π(i))表示將上端接線(xiàn)柱i與下端接線(xiàn)柱π(i)相連，稱(chēng)其為該電路板上的第i條連線(xiàn)。如圖4-1所示的π(i)排列為{8,7,4,2,5,1,9,3,10,6}。對(duì)于任何1≤ij≤n，第i條連線(xiàn)和第j條連線(xiàn)相交的充要條件是π(i)>π(j)。圖4-1電路布線(xiàn)示意在制作電路板時(shí)，要求將這n條連線(xiàn)分布到若干絕緣層上，在同一層上的連線(xiàn)不相交。現(xiàn)在要確定將哪些連線(xiàn)安排在一層上，使得該層上有盡可能多的連線(xiàn)，即確定連線(xiàn)集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。【分析問(wè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)分析，該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對(duì)規(guī)模為n的電路布線(xiàn)問(wèn)題，可以構(gòu)造如下遞歸式：【C代碼】下面是算法的C語(yǔ)言實(shí)現(xiàn)。（1）變量說(shuō)明size[i][j]：上下端分別有i個(gè)和j個(gè)接線(xiàn)柱的電路板的第一層最大不相交連接數(shù)pi[i]：π(i)，下標(biāo)從1開(kāi)始（2）C程序#include"stdlib.h"#includestdio.h>#defineN10/*問(wèn)題規(guī)模*/intm=0；/*記錄最大連接集合中的接線(xiàn)柱*/voidmaxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交連接數(shù)*/inti,j;for(j=0;jpi[1];j++)size[1][j]=0;/*當(dāng)jπ(1)時(shí)*/for(j=pi[1];j=n;j++)（1）;/*當(dāng)j>=π(1)時(shí)*/for(i=2;in;i++){for(j=0;jpi[i];j++)（2）;/*當(dāng)jpi[i]時(shí)*/for(j=pi[i];j=n；j++){/*當(dāng)j>=c[i]時(shí),考慮兩種情況*/size[i][j]=size[i-1][j]>=size[i-1][pi[i]-1]+1?size[i-1][j]:size[i-1][pi[i]-1]+1;}}/*最大連接數(shù)*/size[n][n]=size[n-1][n]>=size[n-1][pi[n]-1]+1?size[n-1][n]:size[n-1][pi[n]-1]+1;}/*構(gòu)造最大不相交連接集合，net[i]表示最大不相交子集中第i條連線(xiàn)的上端接線(xiàn)柱的序號(hào)*/voidconstructSet（intpi[],intsize[N+1][N+1],intn,intnet[n]）{inti,j=n;m=0；for(i=n;i>1;i--){/*從后往前*/if(size[i][j]!=size[i-1][j]){/*(i,pi[i])是最大不相交子集的一條連線(xiàn)*/（3）;/*將i記錄到數(shù)組net中，連接線(xiàn)數(shù)自增1*/j=pi[i]-1;/*更新擴(kuò)展連線(xiàn)柱區(qū)間*/}}if(j>=pi[1])net[m++]=1;/*當(dāng)i=1時(shí)*/}【問(wèn)題1】根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空（1）～（3）。【問(wèn)題2】據(jù)題干說(shuō)明和以上C代碼，算法采用了（4）算法設(shè)計(jì)策略。函數(shù)maxNum和constructSet的時(shí)間復(fù)雜度分別為（5）和（6）（用O表示）?！締?wèn)題3】若連接排列為{8,7,4,2,5,1,9,3,10,6}，即如圖4-1所示，則最大不相交連接數(shù)為（7），包含的連線(xiàn)為（8）（用(i,π(i))的形式給出）。參考答案：詳見(jiàn)解析參考解析：【問(wèn)題1】（1）size[i][j]=1；（2）size[i][j]=size[i-1][j]；（3）net[m++]=i;【問(wèn)題2】（4）動(dòng)態(tài)規(guī)劃算法；（5）O(n2)；（6）O(n)【問(wèn)題3】若連接排列為{8,7,4,2,5,1,9,3,10,6}，即如圖4-1所示，則最大不相交連接數(shù)為（7），包含的連線(xiàn)為（8）（用(i,π(i))的形式給出）。（7）4（8）(9，π(9)，（7，π(7))，（5，π（5）），（3，π（3））[問(wèn)答題]2.某銷(xiāo)售公司當(dāng)前的銷(xiāo)售業(yè)務(wù)為商城實(shí)體店銷(xiāo)售。現(xiàn)該公司擬開(kāi)展網(wǎng)絡(luò)銷(xiāo)售業(yè)務(wù)，需要開(kāi)發(fā)一個(gè)信息化管理系統(tǒng)。請(qǐng)根據(jù)公司現(xiàn)有業(yè)務(wù)及需求完成該系統(tǒng)的數(shù)據(jù)庫(kù)設(shè)計(jì)?！拘枨竺枋觥浚?）記錄公司所有員工的信息。員工信息包括工號(hào)、身份證號(hào)、姓名、性別、出生日期和電話(huà)，并只登記一部電話(huà)。（2）記錄所有商品的信息。商品信息包括商品名稱(chēng)、生產(chǎn)廠家、銷(xiāo)售價(jià)格和商品介紹。系統(tǒng)內(nèi)部用商品條碼唯一區(qū)別每種商品。（3）記錄所有顧客的信息。顧客信息包括顧客姓名、身份證號(hào)、登錄名、登錄密碼、和電話(huà)號(hào)碼。一位顧客只能提供一個(gè)電話(huà)號(hào)碼。系統(tǒng)自動(dòng)生成唯一的顧客編號(hào)。（4）顧客登錄系統(tǒng)之后，在網(wǎng)上商城購(gòu)買(mǎi)商品。顧客可將選購(gòu)的商品置入虛擬的購(gòu)物車(chē)內(nèi)，購(gòu)物車(chē)可長(zhǎng)期存放顧客選購(gòu)的所有商品。顧客可在購(gòu)物車(chē)內(nèi)選擇商品、修改商品數(shù)量后生成網(wǎng)購(gòu)訂單。訂單生成后，由顧客選擇系統(tǒng)提供的備選第三方支付平臺(tái)進(jìn)行電子支付，支付成功后系統(tǒng)需要記錄唯一的支付憑證編號(hào)，然后由商城根據(jù)訂單進(jìn)行線(xiàn)下配送。（5）所有的配送商品均由倉(cāng)庫(kù)統(tǒng)一出庫(kù)。為方便顧客，允許每位顧客在系統(tǒng)中提供多組收貨地址、收貨人及聯(lián)系電話(huà)。一份訂單所含的多個(gè)商品可能由多名分檢員根據(jù)商品所在倉(cāng)庫(kù)信息從倉(cāng)庫(kù)中進(jìn)行分揀操作，分揀后的商品交由配送員根據(jù)配送單上的收貨地址進(jìn)行配送。（6）新設(shè)計(jì)的系統(tǒng)要求記錄實(shí)體店的每筆銷(xiāo)售信息，包括營(yíng)業(yè)員、顧客、所售商品及其數(shù)量。【概念模型設(shè)計(jì)】根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖所示?！具壿嫿Y(jié)構(gòu)設(shè)計(jì)】根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式（不完整）：?jiǎn)T工（工號(hào)，身份證號(hào)，姓名，性別，出生日期，電話(huà)）商品（商品條碼，商品名稱(chēng)，生產(chǎn)廠家，銷(xiāo)售價(jià)格，商品介紹，（a））顧客（顧客編號(hào)，姓名，身份證號(hào)，登錄名，登錄密碼，電話(huà)）收貨地點(diǎn)（收貨ID，顧客編號(hào)，收貨地址，收貨人，聯(lián)系電話(huà)）購(gòu)物車(chē)（顧客編號(hào)，商品條碼，商品數(shù)量）訂單（訂單ID，顧客編號(hào)，商品條碼，商品數(shù)量，（b））分檢（分揀ID，分揀員工號(hào)，（c），分揀時(shí)間）配送（配送ID，分揀ID，配送員工號(hào)，收貨ID，配送時(shí)間，簽收時(shí)間，簽收快照）銷(xiāo)售（銷(xiāo)售ID，營(yíng)業(yè)員工號(hào)，顧客編號(hào)，商品條碼，商品數(shù)量）【問(wèn)題1】補(bǔ)充圖中的“配送”聯(lián)系所關(guān)聯(lián)的對(duì)象及聯(lián)系類(lèi)型?！締?wèn)題2】補(bǔ)充邏輯結(jié)構(gòu)設(shè)計(jì)中的（a）、（b）和（c）三處空缺。【問(wèn)題3】對(duì)于實(shí)體店銷(xiāo)售，若要增加送貨上門(mén)服務(wù)，由營(yíng)業(yè)員在系統(tǒng)中下訂單，與網(wǎng)購(gòu)的訂單進(jìn)行后續(xù)的統(tǒng)一管理。請(qǐng)根據(jù)該需求，對(duì)圖進(jìn)行補(bǔ)充，并修改訂單關(guān)系模式。參考答案：詳見(jiàn)解析參考解析：【問(wèn)題1】配送員--配送--地點(diǎn)，多對(duì)多聯(lián)系【問(wèn)題2】（a）商品數(shù)量，倉(cāng)庫(kù)信息（b）支付憑證編號(hào)（c）商品條碼，訂單ID【問(wèn)題3】在營(yíng)業(yè)員與訂單之間增加聯(lián)系“送貨上門(mén)”，并將聯(lián)系記錄于訂單關(guān)系中，即在訂單關(guān)系中增加屬性“營(yíng)業(yè)員ID”屬性作為外鍵。[問(wèn)答題]3.某會(huì)議中心提供舉辦會(huì)議的場(chǎng)地設(shè)施和各種設(shè)備，供公司與各類(lèi)組織機(jī)構(gòu)租用。場(chǎng)地包括一個(gè)大型報(bào)告廳、一個(gè)小型報(bào)告廳以及諸多會(huì)議室。這些報(bào)告廳和會(huì)議室可提供的設(shè)備有投影儀、白板、視頻播放/回放設(shè)備、計(jì)算機(jī)等。為了加強(qiáng)管理，該中心欲開(kāi)發(fā)一會(huì)議預(yù)訂系統(tǒng)，系統(tǒng)的主要功能如下。（1）檢查可用性?？蛻?hù)提交預(yù)訂請(qǐng)求后，檢查預(yù)訂表，判定所申請(qǐng)的場(chǎng)地是否在申請(qǐng)日期內(nèi)可用；如果不可用，返回不可用信息。（2）臨時(shí)預(yù)訂。會(huì)議中心管理員收到客戶(hù)預(yù)定請(qǐng)求的通知之后，提交確認(rèn)。系統(tǒng)生成新臨時(shí)預(yù)訂存入預(yù)訂表，并對(duì)新客戶(hù)創(chuàng)建一條客戶(hù)信息記錄加以保存。根據(jù)客戶(hù)記錄給客戶(hù)發(fā)送臨時(shí)預(yù)訂確認(rèn)信息和支付定金要求。（3）分配設(shè)施與設(shè)備。根據(jù)臨時(shí)預(yù)訂或變更預(yù)定的設(shè)備和設(shè)施需求，分配所需設(shè)備（均能滿(mǎn)足用戶(hù)要求）和設(shè)施，更新相應(yīng)的表和預(yù)訂表。（4）確認(rèn)預(yù)訂。管理員收到客戶(hù)支付定金的通知后，檢查確認(rèn)，更新預(yù)訂表，根據(jù)客戶(hù)記錄給客戶(hù)發(fā)送預(yù)訂確認(rèn)信息。（5）變更預(yù)訂?？蛻?hù)還可以在支付余款前提交變更預(yù)訂請(qǐng)求，對(duì)變更的預(yù)訂請(qǐng)求檢查可用性，如果可用，分配設(shè)施和設(shè)各；如果不可用，返回不可用信息。管理員確認(rèn)變更后，根據(jù)客戶(hù)記錄給客戶(hù)發(fā)送確認(rèn)信息。（6）要求付款。管理員從預(yù)訂表中查詢(xún)距預(yù)訂的會(huì)議時(shí)間兩周內(nèi)的預(yù)定，根據(jù)客戶(hù)記錄給滿(mǎn)足條件的客戶(hù)發(fā)送支付余款要求。（7）支付余款。管理員收到客戶(hù)余款支付的通知后，檢查確認(rèn)，更新預(yù)訂表中的已支付余款信息?，F(xiàn)采用結(jié)構(gòu)化方法對(duì)會(huì)議預(yù)定系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖（不完整）?！締?wèn)題1】使用說(shuō)明中的詞語(yǔ)，給出圖1-1中的實(shí)體E1～E2的名稱(chēng)。【問(wèn)題2】使用說(shuō)明中的詞語(yǔ)，給出圖1-2中的數(shù)據(jù)存儲(chǔ)D1～D4的名稱(chēng)?！締?wèn)題3】根據(jù)說(shuō)明和圖中術(shù)語(yǔ)，補(bǔ)充圖1-2之中缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)?！締?wèn)題4】如果發(fā)送給客戶(hù)的確認(rèn)信息是通過(guò)Email系統(tǒng)向客戶(hù)信息中的電子郵件地址進(jìn)行發(fā)送的，那么需要對(duì)圖1-1和1-2進(jìn)行哪些修改？用150字以?xún)?nèi)文字加以說(shuō)明。參考答案：詳見(jiàn)解析參考解析：【問(wèn)題1】E1：客戶(hù)E2：管理員【問(wèn)題2】D1：預(yù)定表D2：客戶(hù)信息記錄表D3：設(shè)施表D4：設(shè)備表【問(wèn)題3】預(yù)訂確認(rèn)信息起點(diǎn)：4確認(rèn)預(yù)定終點(diǎn)：E1客戶(hù)信息起點(diǎn)：E1終點(diǎn)：2臨時(shí)預(yù)定客戶(hù)記錄起點(diǎn)：D2終點(diǎn)：4確認(rèn)預(yù)定客戶(hù)記錄起點(diǎn)：D2終點(diǎn)：5變更預(yù)定預(yù)定信息起點(diǎn)：D1終點(diǎn)：6要求付款客戶(hù)記錄起點(diǎn)：D2終點(diǎn)：6要求付款【問(wèn)題4】圖1-1中：增加外部實(shí)體“第三方Email系統(tǒng)”，將臨時(shí)預(yù)訂/預(yù)訂/變更確認(rèn)信息終點(diǎn)均修改至“第三方Email系統(tǒng)”。圖1-2中：增加外部實(shí)體“第三方Email系統(tǒng)”，增加加工“發(fā)送郵件”，將臨時(shí)預(yù)訂/預(yù)訂/變更確認(rèn)信息終點(diǎn)均修改至“發(fā)送郵件”加工，并增加從D2到“發(fā)送郵件”加工的數(shù)據(jù)流“電子郵件地址”，再?gòu)陌l(fā)送郵件加工引出數(shù)據(jù)流，臨時(shí)預(yù)訂/預(yù)訂/變更確認(rèn)信息，終點(diǎn)為第三方Email系統(tǒng)。[問(wèn)答題]4.某軟件公司欲設(shè)計(jì)實(shí)現(xiàn)一個(gè)虛擬世界仿真系統(tǒng)。系統(tǒng)中的虛擬世界用于模擬現(xiàn)實(shí)世界中的不同環(huán)境（由用戶(hù)設(shè)置并創(chuàng)建），用戶(hù)通過(guò)操作仿真系統(tǒng)中的1~2個(gè)機(jī)器人來(lái)探索虛擬世界。機(jī)器人維護(hù)著兩個(gè)變量b1和b2，用來(lái)保存從虛擬世界中讀取的字符。該系統(tǒng)的主要功能描述如下：（1）機(jī)器人探索虛擬世界（RunRobots）。用戶(hù)使用編輯器（Editor）編寫(xiě)文件以設(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í)針?lè)较蛐D(zhuǎn)90度。③Read：機(jī)器人讀取其所在位置的字符，并將這個(gè)字符的值賦給b1；如果這個(gè)位置上沒(méi)有字符，則不改變b1的當(dāng)前值。④Write：將b1中的字符寫(xiě)入機(jī)器人當(dāng)前所在的位置，如果這個(gè)位置上已經(jīng)有字符，該字符的值將會(huì)被b1的值替代。如果這時(shí)b1沒(méi)有值，即在執(zhí)行Write動(dòng)作之前沒(méi)有執(zhí)行過(guò)任何Read動(dòng)作，那么需要提示用戶(hù)相應(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所示的初始類(lèi)圖。圖3-2中的類(lèi)“Interpreter”和“Parser”用于解析描述虛擬世界的文件以及機(jī)器人行為文件中的指令集?！締?wèn)題1】根據(jù)說(shuō)明中的描述，給出圖3-1中U1～U6所對(duì)應(yīng)的用例名?！締?wèn)題2】圖3-1中用例U1～U6分別與哪個(gè)（哪些）用例之間有關(guān)系，是何種關(guān)系？【問(wèn)題3】根據(jù)說(shuō)明中的描述，給出圖3-2中C1～C5所對(duì)應(yīng)的類(lèi)名。參考解析：【問(wèn)題1】U1、U2、U3、U4、U5、U6：Run、Step