女人久久久www免费人成看片,国内自拍偷拍网,国产一区二区三区免费在线观看,欧美精品三区四区,91久久国产综合久久91,欧美成人精品第一区二区三区 ,美女成人在线观看

軟題庫 學(xué)習(xí)課程
試卷年份2009年下半年
試題題型【分析簡答題】
試題內(nèi)容

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

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

對于表4-1的實例,若采用窮舉法搜索整個解空間,則搜索樹的結(jié)點數(shù)為 (7) ,而用了上述回溯法,搜索樹的結(jié)點數(shù)為 (8) 。

查看答案

相關(guān)試題

1題: 閱讀以下說明和數(shù)據(jù)流圖,回答問題1至問題4,將解答填入答題紙的對應(yīng)欄內(nèi)。
【說明】
現(xiàn)準(zhǔn)備為某銀行開發(fā)一個信用卡管理系統(tǒng)CCMS,該系統(tǒng)的基本功能為:
1.信用卡申請。非信用卡客戶填寫信用卡申請表,說明所要申請的信用卡類型及申請者的基本信息,提交CCMS。如果信用卡申請被銀行接受,CCMS將記錄該客戶的基本信息,并發(fā)送確認(rèn)函給該客戶,告知客戶信用卡的有效期及信貸限額;否則該客戶將會收到一封拒絕函。非信用卡客戶收到確認(rèn)函后成為信用卡客戶。
2.信用卡激活。信用卡客戶向CCMS提交激活請求,用信用卡號和密碼激活該信用卡。激活操作結(jié)束后,CCMS將激活通知發(fā)送給客戶,告知客戶其信用卡是否被成功激活。
3.信用卡客戶信息管理。信用卡客戶的個人信息可以在CCMS中進行在線管理。每位信用卡客戶可以在線查詢和修改個人信息。
4.交易信息查詢。信用卡客戶使用信用卡進行的每一筆交易都會記錄在CCMS中。信用卡客戶可以通過CCMS查詢并核實其交易信息(包括信用卡交易記錄及交易額)。
圖1-1和圖1-2分別給出了該系統(tǒng)的頂層數(shù)據(jù)流圖和0層數(shù)據(jù)流圖的初稿。

【問題1】(3分)
根據(jù)【說明】,將圖1-1中的E1~E3填充完整。
?【問題2】(3分)
圖1-1中缺少三條數(shù)據(jù)流,根據(jù)【說明】,分別指出這三條數(shù)據(jù)流的起點和終點。(注:數(shù)據(jù)流的起點和終點均采用圖中的符號和描述)
?【問題 3】(5分)
圖1-2中有兩條數(shù)據(jù)流是錯誤的,請指出這兩條數(shù)據(jù)流的名稱,并改正。(注:數(shù)據(jù)流的起點和終點均采用圖中的符號和描述)
?【問題4】(4分)

根據(jù)【說明】,將圖1-2中P1~P4的處理名稱填充完整。

答案解析與討論:m.xiexiliangjiufa.com/st/3808413365.html

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

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

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

?【問題1】(2分)
根據(jù)【說明】中的描述,給出圖3-1中A1和A2所對應(yīng)的參與者。
?【問題2】(8分)
根據(jù)【說明】中的描述,給出圖3-1中缺少的四個用例及其所對應(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

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


答案解析與討論:m.xiexiliangjiufa.com/st/3808810811.html

6題: 閱讀下列說明和Java代碼,將應(yīng)填入 (n) 處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
現(xiàn)欲構(gòu)造一文件/目錄樹,采用組合(Composite)設(shè)計模式來設(shè)計,得到的類圖如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è)耄瑥腂方向鐵軌駛出,一旦車廂進入車站(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):將一個整數(shù)壓棧,棧中元素數(shù)目增1。 void Pop (STACK *s):棧頂元素出棧,棧中元素數(shù)目減1。
int Top (STACK s):返回非空棧的棧頂元素值,棧中元素數(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; ){  /*檢查輸出序列中的每個車廂號state[i]是否能從棧中獲取*/
if( (2) ){    /*當(dāng)棧不為空時*/
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)棧為空時*/
begin=maxNo;
for(j=begin; j<=state[i];j++) {
Push(&station, j);

maxNo= (5)


printf("OK");
return 0;
答案解析與討論:m.xiexiliangjiufa.com/st/3809024974.html