2023(下半年)試題及答案(下午)資料

第8章軟件設(shè)計師下午試題分析與解答

試題一

閱讀下列說明和圖，回答問題1至問題4,將解答填入答

題紙的對應(yīng)欄內(nèi)。

［說明］

某公司欲開發(fā)聘請系統(tǒng)以提高聘請效率，其主要功能如

下：

(1)接受申請

驗證應(yīng)聘者所供應(yīng)的自身信息是否完整，是否說明白應(yīng)

聘職位，受理驗證合格的申請，給應(yīng)聘者發(fā)送致謝信息。

(2)評估應(yīng)聘者

依據(jù)部門經(jīng)理設(shè)置的職位要求，審查已經(jīng)受理的申請;

對未被錄用的應(yīng)聘者進行謝絕處理，將未被錄用的應(yīng)聘者信

息存入未錄用的應(yīng)聘者表，并給其發(fā)送謝絕決策；對錄用的

應(yīng)聘者進行職位支配評價,將評價結(jié)果存入評價結(jié)果表，并

給其發(fā)送錄用決策，發(fā)送錄用職位和錄用者信息給工資系

統(tǒng)。

現(xiàn)采納結(jié)構(gòu)化方法對聘請系統(tǒng)進行分析與設(shè)計，獲得如

圖1T所示的頂層數(shù)據(jù)流圖、圖『2所示0層數(shù)據(jù)流圖和圖

1-3所示1層數(shù)據(jù)流圖。

應(yīng)聘職位

ElE2

錄用者信息

X

E3

求用職位

圖1“頂層數(shù)據(jù)流圖

螂聊1

EI

町?2OOffl

應(yīng)灼職位_______/---------

]1J、一證合格一112）致謝信息」

P1J~的申請，受理中諳

入J\____/

應(yīng)聘者信息

X

錄用決策

職位要求

7r

2.1錄用的2.3

P3

P2應(yīng)聘占品者信息

巳受理丁、____/

的申請未錄用的應(yīng)聘者

「工22

謝絕h加若D1D2

留L31層數(shù)據(jù)流圖

[問題1]

運用說明中的術(shù)語，給出圖中E1?E3所對應(yīng)的實體名

稱。

答:

E1:應(yīng)聘者E2:部門經(jīng)理E3:工資系統(tǒng)

[問題2]

運用說明中的術(shù)語，給出圖中D1?D2所對應(yīng)的數(shù)據(jù)存儲

答：

D1:未錄用的應(yīng)聘者表D2:評價結(jié)果表

[問題3]

運用說明和圖中的術(shù)語，給出圖1-3中加工P1?P3的名

稱。

答：

P1:驗證申請P2:審查申請P3:職位支配評價

[問題4]

說明說明圖『2和圖『3是否保持平衡，若不平衡請按

如下格式補充圖1-3中數(shù)據(jù)流的名稱以及數(shù)據(jù)流的起點或終

點，使其平衡（運用說明中的術(shù)語或圖中符號）。

答:

數(shù)據(jù)流名稱起點

錄用職位P3或2.3職位

支配評價

已受理的申請1.2受理申請

謝絕決策2.2謝絕應(yīng)聘者

試題二

閱讀下列說明，回答問題1至問題3,將解答填入答題紙

的對應(yīng)欄內(nèi)。

［說明］

某物流公司為了整合上游供應(yīng)商與下游客戶，縮短物流

過程，降低產(chǎn)品庫存，須要構(gòu)建一個信息系統(tǒng)以便利管理其

業(yè)務(wù)運作活動。

［需求分析結(jié)果］

(1)物流公司包含若干部門，部門信息包括部門號、部門

名稱、經(jīng)理、電話和郵箱。一個部門可以有多名員工處理部

門的日常事務(wù)，每名員工只能在一個部門工作。每個部門有

一名經(jīng)理，只需負責管理本部門的事務(wù)和人員。

(2)員工信息包括員工號、姓名、職位、電話號碼和工

資；其中，職位包括：經(jīng)理、業(yè)務(wù)員等。業(yè)務(wù)員依據(jù)托運申

請負責支配承運貨物事宜，例如：裝貨時間、到達時間等。

一個業(yè)務(wù)員可以支配多個托運申請，但一個托運申請只由一

個業(yè)務(wù)員處理。

(3)客戶信息包括客戶號、單位名稱、通信地址、所屬省

份、聯(lián)系人、聯(lián)系電話、銀行賬號，其中，客戶號唯一標識

客戶信息的每一個元組。每當客戶要進行貨物托運時，先要

提出貨物托運申請。托運申請信息包括申請?zhí)?、客戶號、?/p>

物名稱、數(shù)量、運費、動身地、目的地。其中，一個申請?zhí)?/p>

對應(yīng)唯一的一個托運申請；一個客戶可以有多個貨物托運申

請，但一個托運申請對應(yīng)唯一的一個客戶號。

［概念模型設(shè)計］

依據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖和關(guān)系模

式（不完整）如圖2-1所示。

修申請||部門

員工

一戶|||業(yè)務(wù)員||||二一

圖2-1實體聯(lián)系圖

［關(guān)系模式設(shè)計］

部門（部門號，部門名稱，經(jīng)理，電話，郵箱）

員工（員工號，姓名，職位，電話號碼，工資，_（a）_部

門號_）

客戶（（b）,單位名稱，通信地址，所屬省份，聯(lián)系

人，聯(lián)系電話，銀行賬號）

托運申請（（c）,貨物名稱，數(shù)量，運費，動身地，目

的地）申請?zhí)枴⒖蛻籼?、貨物名稱、數(shù)量、運費、動身地、

目的地

支配承運（（d）,裝貨時間，到達時間，業(yè)務(wù)員）

[問題1]

依據(jù)問題描述，補充四個聯(lián)系、聯(lián)系的類型，以及實體

與子實體的聯(lián)系，完善圖2-1所示的實體聯(lián)系圖。

答：

[問題2]

依據(jù)實體聯(lián)系圖，將關(guān)系模式中的空⑸?（d）補充完

整。分別指出部門、員工和支配承運關(guān)系模式的主鍵和外

鍵。

答：⑴

a:部門號

b:客戶號

c:申請?zhí)?、客戶?/p>

d:申請?zhí)?/p>

(2)

部門：主鍵：部門號外鍵：無

員工：主鍵：員工號外鍵：部門號

支配承運：主鍵：申請?zhí)柾怄I：無

[問題3]

若系統(tǒng)新增需求描述如下：

為了數(shù)據(jù)庫信息的平安性，公司要求對數(shù)據(jù)庫操作設(shè)置

權(quán)限管理功能，當員工登錄系統(tǒng)時，系統(tǒng)須要檢查員工的權(quán)

限。權(quán)限的設(shè)置人是部門經(jīng)理。為滿意上述須要，應(yīng)如何修

改(或補充)圖2T所示的實體聯(lián)系圖，請給出修改后的實體

聯(lián)系圖和關(guān)系模式。

答：

試題二分析

本題考查數(shù)據(jù)庫系統(tǒng)中實體聯(lián)系模型（E-R模型）和關(guān)系模

式設(shè)計方面的應(yīng)用學問。

[問題1]

兩個實體集之間的聯(lián)系類型分為三類：一對一（1：1）聯(lián)

系、一對多（1：n）聯(lián)系和多對多（m:n）聯(lián)系。

依據(jù)題意，每名員工只能在一個部門工作，所以部門和

員工之間有一個l：n的“所屬”聯(lián)系；由于每個部門有一名

經(jīng)理，只需負責管理本部門的事務(wù)和人員，因此部門和經(jīng)理

之間有一個1:1的“管理”聯(lián)系；由于一個業(yè)務(wù)員可以支配

多個托運申請，但一個托運申請只由一個業(yè)務(wù)員處理，故業(yè)

務(wù)員和托運申請之間有一個l:n的“托運”聯(lián)系；又由于一

個客戶可以有多個貨物托運申請，但一個托運申請對應(yīng)唯一

的一個客戶號，故客戶和托運申請之間有一個l：n的“申

請”聯(lián)系。

依據(jù)上述分析，完善圖27所示的實體聯(lián)系圖可參見參

考答案。

[問題2]

依據(jù)題意，部門和員工之間有一個l：n的“所屬”聯(lián)系

須要將一端的碼并入多端，故員工關(guān)系模式中的空⑸應(yīng)填寫

部門號；在客戶關(guān)系模式中，客戶號為主鍵，故空(b)應(yīng)填寫

客戶號；在托運申請關(guān)系模式中，申請?zhí)?、客戶號為主鍵，

故空⑹應(yīng)填寫申請?zhí)?、客戶號；又由于一個業(yè)務(wù)員可以支配

多個托運申請，但一個托運申請只由一個業(yè)務(wù)員處理，因此

在支配承運關(guān)系模式中，申請?zhí)枮橹麈I，故空(d)應(yīng)填寫申請

號。

部門關(guān)系模式中的部門號為主鍵，經(jīng)理為外鍵；因為經(jīng)

理來自員工關(guān)系。員工關(guān)系模式中的員工號為主鍵，部門號

為外鍵，因為部門號來自部門關(guān)系。支配承運關(guān)系模式中的

申請?zhí)枮橹麈I，業(yè)務(wù)員為外鍵，因為業(yè)務(wù)員來自員工關(guān)系。

[問題3]

依據(jù)題意，權(quán)限的設(shè)置人是部門經(jīng)理，因此，須要建立

一個權(quán)限關(guān)系模式，以及經(jīng)理到權(quán)限之間的l：n的“設(shè)置”

聯(lián)系。修改后的實體聯(lián)系圖和關(guān)系模式參見參考答案。

參考答案

[問題1]

[問題2]

(a)部門號

⑹客戶號

(c)申請?zhí)枺蛻籼?/p>

(d)申請?zhí)?/p>

主鍵：部外鍵：經(jīng)

部門

門號理

主鍵：員外鍵：部

員工

工號門號

支配主鍵：申外鍵：業(yè)

承運請?zhí)杽?wù)員

[問題3]

關(guān)系模式：

權(quán)限(員工號，權(quán)限，設(shè)置人)

或權(quán)限(員工號，權(quán)限，部門經(jīng)理)

試題三

閱讀下列說明和圖，回答問題1至問題3,將解答填入答

題紙的對應(yīng)欄內(nèi)。

［說明］

Pay&Drive系統(tǒng)(開多少付多少)能夠依據(jù)駕駛里程自動計

算應(yīng)付的費用。

系統(tǒng)中存儲了特定區(qū)域的道路交通網(wǎng)的信息。道路交通

網(wǎng)由若干個路段(RoadSegment)構(gòu)成，每個路段由兩個地理坐

標點(Node)標定，其里程數(shù)(Distance)是已知的。在某些地

理坐標點上安裝了訪問限制(AccessControl)設(shè)備，可以自

動掃描行駛卡(Card)。行程(Trajectoiy)由一組連續(xù)的路段

構(gòu)成。行程的起點(Entry)和終點(Exit)都裝有訪問限制設(shè)

備。

系統(tǒng)供應(yīng)了3種行駛卡。常規(guī)卡(RegularCard)有效期

(ValidPeriod)為一年，可以在整個道路交通網(wǎng)內(nèi)運用。季

卡(SeasonCard)有效期為三個月，可以在整個道路交通網(wǎng)內(nèi)

運用。單次卡(MinitripCard)在指定的行程內(nèi)運用，且只能

運用一次。其中，季卡和單次卡都是預付卡(Prepaid

Card),須要客戶(Customer)預存確定的費用。

系統(tǒng)的主要功能有：客戶注冊、申請行駛卡、運用行駛

卡行駛等。

運用常規(guī)卡行駛，在進入行程起點時，系統(tǒng)記錄行程起

點、進入時間(DateOfEntry)等信息。在到達行程終點時,

系統(tǒng)依據(jù)行駛的里程數(shù)和所持卡的里程單價(UnitPrice)計

算應(yīng)付費用，并打印費用單(Invoice)。

季卡的運用流程與常規(guī)卡類似，但是不須要打印費用

單，系統(tǒng)自動從卡中扣除應(yīng)付費用。

單次卡的運用流程與季卡類似，但還須要在行程的起點

和終點上檢查行駛路途是否符合該卡所規(guī)定的行駛路途。

現(xiàn)采納面對對象方法開發(fā)該系統(tǒng)，運用UML進行建模。

構(gòu)建出的用例圖和類圖分別如圖3-1和圖3-2所示。

[問題1]

依據(jù)說明中的描述，給出圖3-1中U1和U2所對應(yīng)的用

例，以及⑴所對應(yīng)的關(guān)系。

答：

U1:運用常規(guī)卡行駛U2：運用單次卡行駛

(1)：〈〈extend〉〉

[問題2]

依據(jù)說明中的描述，給出圖3-2中缺少的C1?C6所對應(yīng)

的類名以及⑵?⑶處所對應(yīng)的多重度（類名運用說明中給出

的英文詞匯）。

答：C1:RoadSegmentC2:Trajectory

C3:CardC4:RegularCard

C5:PrepaidCardC6:MinitripCard

(2):1

(3):l-3

[問題3]

依據(jù)說明中的描述，給出RoadSegment>Trajectory和

Card所對應(yīng)的類的關(guān)鍵屬性（屬性名運用說明中給出的英文詞

匯）。

答：

RoadSegment的屬性：Distance

Trajectory的屬性：Entry、Exit>DateOfEntry

Card的屬性：UnitPrice>ValidPeriod

試題三分析

本題屬于經(jīng)典的考題，主要考查面對對象分析方法以及

UML的用例圖和類圖的相關(guān)學問。

[問題1]

本問題要求將圖3-1所給出的用例圖補充完整。用例圖

的構(gòu)成要素有：參加者、用例以及用例之間的關(guān)系。圖中缺

少了兩個用例，以及一個用例關(guān)系。解答此題時，首先應(yīng)從

說明中找到全部的用例。

用例表示系統(tǒng)的一個單一業(yè)務(wù)功能。從題目的描述中可

以看出，系統(tǒng)的主要功能就是申請行駛卡，以及運用行駛卡

行駛。由于行駛卡分為三種，所以在說明中具體描述了三種

行駛卡的運用方法。再結(jié)合用例圖來看，缺少的兩個用例與

用例”運用季卡行駛”有關(guān)聯(lián)關(guān)系，由此可以推斷出，須要

補充的這兩個用例必定與另外兩種行駛卡相關(guān)，分別為“運

用常規(guī)卡行駛”和“運用單次卡行駛”。

下面須要解決的問題是這兩個用例與U1和U2的對應(yīng)關(guān)

系。這就須要細致考查一下用例圖所給出的用例關(guān)系。由圖

3-1可知，U1和“運用季卡行駛”之間是泛化

(generalization)關(guān)系。當多個用例共同擁有一種類似的結(jié)

構(gòu)和行為時，可以將它們的共性抽象為父用例，其他的用例

作為泛化關(guān)系中的子用例。在用例的泛化關(guān)系中，子用例是

父用例的一種特別形式，子用例繼承了父用例全部的結(jié)構(gòu)、

行為和關(guān)系。依據(jù)說明中的“季卡的運用流程與常規(guī)卡類

似，但是不須要打印費用單，系統(tǒng)自動從卡中扣除應(yīng)付費

用”可知，U1應(yīng)當對應(yīng)著用例“運用常規(guī)卡行駛”。由此不

難得出U2對應(yīng)著用例“用單次卡行駛”。

現(xiàn)在圖中只剩下⑴處的用例關(guān)系沒有確定。用例之間的

關(guān)系在用例圖上只有三種：包含(include)、擴展(extend)和

泛化(generalization)。

包含關(guān)系是指當多個用例中存在相同事務(wù)流時，可以把

這些公共事務(wù)流抽象成為公共用例，這個公共用例稱為抽象

用例，而原始用例稱為基礎(chǔ)用例?；A(chǔ)用例和抽象用例之間

是包含關(guān)系。

假如一個用例明顯地混合了兩種或兩種以上的不同場

景，則可以將這個用例分為一個基本用例和多個擴展用例。

擴展關(guān)系用“《extend》”表示，箭頭指向基本用例。

包含關(guān)系和擴展關(guān)系的區(qū)分在于，抽象用例中的事務(wù)流

確定要插入到基本用例中去，并且插入點只有一個，通常抽

象用例不能脫離基本用例而獨立存在。擴展用例的事務(wù)流往

往可以抽象為基本用例的備選事務(wù)流，在擴展關(guān)系中，可以

依據(jù)確定的條件來確定是否將擴展用例的事務(wù)流插入到基本

用例的事務(wù)流中，并且插入點可以有多個。

依據(jù)以上分析可知，（1）處的用例關(guān)系選擇

“《extend》”最為合適。

[問題2]

本問題考查的是類圖建模。解題的重點在于依據(jù)類圖中

供應(yīng)的類及類之間的關(guān)聯(lián)關(guān)系，推斷出剩余的類。

可以先視察一下類圖?？梢钥吹剑氁a充的類基本上

集中在兩個結(jié)構(gòu)上：聚集結(jié)構(gòu)（類C1和C2）以及繼承結(jié)構(gòu)（類

C3?C6）。繼承結(jié)構(gòu)是比較簡單辨識的類之間的關(guān)聯(lián)關(guān)系，圖

上給出了其中的一個子類SeasonCard。以這個類為線索，回

到說明中找尋與類SeasonCard相關(guān)的其他類。從說明中可

知，”系統(tǒng)供應(yīng)了3種卡”，常規(guī)卡、季卡、單次卡，而

“季卡和單次卡都是預付卡”。這些描述示意，“季卡”、

“單次卡”與“預付卡”之間存在著特別/一般關(guān)系，即

“is-a”關(guān)系，這是繼承結(jié)構(gòu)的典型標記。由此可以得出類

C5和C6應(yīng)當分別對應(yīng)PrepaidCard(預付卡)和

MinitripCard(單次卡)。依據(jù)C5和C6所對應(yīng)的類，可以推

斷出，C4和C3必定也是與行駛卡相關(guān)的類。三種卡中，已經(jīng)

有兩種卡有了對應(yīng)的類，還剩下一種卡即“常規(guī)卡”。而

“常規(guī)卡”只能是與“預付卡”同層次的概念，所以只能對

應(yīng)于C4,C3表示的是能代表全部這幾種卡的公共概念。所以

C3和C4應(yīng)分別對應(yīng)于Card和RegularCardo確定了C3之

后,就可以識別出(2)和(3)處的多重度。Customer和Card之

間是持有和被持有的關(guān)系，由于系統(tǒng)中只有3種卡，所以一

個客戶最多只能有3種卡，所以(3)處應(yīng)填L.3。而對于任何

一張卡來說，只能有唯一地一個所屬人，因此⑵處應(yīng)填1。

現(xiàn)在還剩下類C1和C2沒有確定。由于這兩個類之間是

聚集關(guān)系，所以須要在說明中找尋具有“部分一整體”關(guān)系

的概念。由說明中的“行程(Trajectory)由一組連續(xù)的路段

構(gòu)成”可知，Cl和C2應(yīng)分別對應(yīng)于RoadSegment和

Trajectory。

[問題3]

本問題考查類的關(guān)鍵屬性的識別。由說明中給出的描述

可知，類RoadSegment的屬性至少應(yīng)包括Distance；類

Trajectory的屬性至少應(yīng)包括Entry、Exit和DateOfEntry;

類Card的屬性至少應(yīng)包括UnitPrice>ValidPeriodo

參考答案

[問題1]

U1：運用常規(guī)卡行駛U2：運用單次卡行駛(1)：extend

[問題2]

Cl：RoadSegmentC2：TrajectoryC3：Card

C4：RegularCardC5：PrepaidCardC6：MinitripCard

(2)1(3)1..3

[問題3]

RoadSegment的屬性：Distance

Trajectory的屬性：Entry>Exit、DateOfEntry

Card的屬性：UnitPrice>ValidPeriod

試題四

閱讀下列說明和C代碼，將應(yīng)填入（n）處的字句寫在答

題紙的對應(yīng)欄內(nèi)。

［說明］

設(shè)某一機器由n個部件組成，每一個部件都可以從m個

不同的供應(yīng)商處購得。供應(yīng)商j供應(yīng)的部件i具有重量明」和

價格頻。設(shè)計一個算法，求解總價格不超過上限cc的最小重

量的機器組成。

采納回溯法來求解該問題：

首先定義解空間。解空間由長度為n的向量組成，其中

每個重量取值來自集合｛1,2,…，m）,將解空間用樹形結(jié)構(gòu)

表示。

接著從根結(jié)點起先，以深度優(yōu)先的方式搜尋整個解空

間。從根結(jié)點起先，根結(jié)點成為活結(jié)點，同時也成為當前的

擴展結(jié)點。向縱深方向考慮第一個部件從第一個供應(yīng)商處購

買，得到一個新結(jié)點。推斷當前的機器價格（C”）是否超過上

限（CC）,重量（Wu）是否比當前已知的解（最小重量）大，若

是，應(yīng)回溯至最近的一個活結(jié)點；若否，則該新結(jié)點成為活

結(jié)點，同時也成為當前的擴展結(jié)點，根結(jié)點不再是擴展結(jié)

點。接著向縱深方向考慮其次個部件從第一個供應(yīng)商處購

買，得到一個新結(jié)點。同樣推斷當前的機器價格（CU+C2I）是否

超過上限（CC）,重量（W3W2I）是否比當前已知的解（最小重量）

大。若是，應(yīng)回溯至最近的一個活結(jié)點；若否，則該新結(jié)點

成為活結(jié)點，同時也成為當前的擴展結(jié)點，原來的結(jié)點不再

是擴展結(jié)點。以這種方式遞歸地在解空間中搜尋，直到找到

所要求的解或者解空間中已無活結(jié)點為止。

[C代碼]

下面是該算法的C語言實現(xiàn)。

（1）變量說明

n：機器的部件數(shù)

m：供應(yīng)商數(shù)

cc：價格上限

w[][]：二維數(shù)組，表示第j個供應(yīng)商供應(yīng)的第i

個部件的重量

c[]□：二維數(shù)組，表示第j個供應(yīng)商供應(yīng)的第i

個部件的價格

bestW：滿意價格上限約束條件的最小機器重量

bestC：最小重量機器的價格

bestX[]：最優(yōu)解，一維數(shù)組，bestX[i]表示第i個部件

來自哪個供應(yīng)商

CW：搜尋過程中機器的重量

CP：搜尋過程中機器的價格

x[]：搜尋過程中產(chǎn)生的解，x[i]表示第i個部件來自哪

個供應(yīng)商

i：當前考慮的部件，從0到n-1

j：循環(huán)變量

(2)函數(shù)backtrack

intn=3;

intm=3;

intcc=4;

intW[3][3]={{1}2,3},{3,2,1},{2,2,2));

intc[3][3]={{1}2,3},{3}2,1},{2,2,2));

intbestW=8;

intbestC=O;

intbestX[3]={0,0,0};

intcw=0;

intcp=0;

intx[3]={0,0,0};

intbacktrack(inti){

intj=0;

intfound=0;

if(i>n-l){/*得到問題解*/

bestW=cw;

bestC=cp;

for(j=0;j<n;j++){

(1)；//bestX[j]=x[j]

)

return1;

)

if(cpV=cc)(/*有解*/

found=1;

)

for(j=0;(2);j++){//j<m

/*第i個部件從第j個供應(yīng)商購買*/

(3);〃x[i]=j

cw=cw+w[i][j];

cp=cp+c[i][j];

if(cpV=cc&&(4)){/*深度搜尋，擴展當前結(jié)點*/

//cw<=bestW

if(backtrack(i+1)){found-1;)

/*回溯*/

cw=cw-w[i][j];

(5);//cp=cp-c[i][j]

)

returnfound;

試題四分析

本題考查算法的設(shè)計和分析技術(shù)中的回溯法。

回溯法是一種系統(tǒng)搜尋問題解的方法，在包含問題全部

解的解空間樹中，依據(jù)深度優(yōu)先的策略，從根結(jié)點動身搜尋

解空間樹。算法在到達解空間樹的任一結(jié)點時，總是先推斷

該結(jié)點是否確定不包含問題的解。若確定不包含，則跳過對

以該結(jié)點為根的子樹的系統(tǒng)搜尋，逐層向其祖先結(jié)點回溯；

否則進入該子樹，接著按深度優(yōu)先的策略進行搜尋。回溯法

在求問題的最優(yōu)解時，要回溯到根，且根結(jié)點的全部子樹都

已經(jīng)被搜尋遍才結(jié)束。

依據(jù)上述思想和題干說明，對實例：部件數(shù)n=3,廠商數(shù)

m=3,具體的重量和價格如表4-1所示。

袤4-1每個部件的重量和價格

n

123

W1C|W2ClC3

1112233

m2332211

3222222

構(gòu)造該實例的解空間樹如圖4-1所示。

圖4-1中結(jié)點編號表示生成該結(jié)點的依次。邊上的編號

表示哪個部件選擇哪個廠商，如x(2)=l,表示第2個部件來

自廠商1。結(jié)點旁邊的兩個數(shù)字表示當前解或部分解對應(yīng)的重

量和價格，如2:2表示重量為2,價格為2。從圖4T可以看

出，最優(yōu)解是結(jié)點20表示的解，即x⑴=1,x(2)=3,

x(3)=l,即第1個部件來自廠商1,第2個部件來自廠商3,

第3個部件來自廠商1,總的價格和重量分別為4和4。當

然，本實例的最優(yōu)解還可以是x(l)=l,x(2)=3,x⑶=2和

x(l)=l,x(2)=3,x(3)=3,分別對應(yīng)解空間樹上的21號和22

號結(jié)點。

代碼中的空⑴處是得到問題解之后，將搜尋過程中產(chǎn)生

的重量cw、價格cp和解x放到最終重量bestW、價格bestC

和解bestX中，因此空格⑴處填寫bestX[j]=x[j]。空⑵處

的for循環(huán)是考慮第i個部件選擇哪個廠商，因此j從。到

mT依次檢查，此處應(yīng)填j<m。對搜尋過程中產(chǎn)生的重量

cw、價格cp和解x的值進行設(shè)置，因此空⑶處應(yīng)填

x[i]=j,表示第i個部件選擇廠商j?？?4)是推斷當前結(jié)點

是否要擴展，若當前獲得的價格比目前最優(yōu)解更優(yōu)，且重量

沒有超過當前得到的最優(yōu)重量，即cpV二cc且cwVbestW,則

擴展當前結(jié)點，否則回溯。在回溯過程中，須要把原來選擇

的部件的價格和重量從搜尋過程中產(chǎn)生的重量cw和價格cp

中去掉，因此空⑸應(yīng)填cp二cp=

參考答案

(l)bestX[j]=x[j](2)j<m(3)x[i]=j

(4)cw<bestW(5)cp=cp-c[i][j]

試題五

閱讀下列說明和C++代碼，將應(yīng)填入(n)處的字句寫在答

題紙的對應(yīng)欄內(nèi)。

［說明］

某大型商場內(nèi)安裝了多個簡易的紙巾售賣機，自動出售2

元錢一包的紙巾，且每次僅售出一包紙巾。紙巾售賣機的狀

態(tài)圖如圖5-1所示。

圖5T紙巾售賣機的狀態(tài)圖

采納狀態(tài)(State)模式來實現(xiàn)該紙巾售賣機，得到如圖5-

2所示的類圖。其中類State為抽象類，定義了投幣、退幣、

出紙巾等方法接口。類SoldState、SoldOutState>

NoQuarterState和HasQuarterState分別對應(yīng)圖5-1中紙巾

售賣機的4種狀態(tài)：售出紙巾、紙巾售完、沒有投幣、有2

元錢。

State

圖5?2類圖

[C++代碼]

#include<iostream>

usingnamespacestd;

//以下為類的定義部分

classTissueMachine;〃類的提前引用

classState{

public：

virtualvoidinsertQuarter()=0;//投幣

virtualvoidejectQuarter()=0;〃退幣

virtualvoidturnCrank()=0;//按下“出紙巾"按鈕

virtualvoiddispense()=0;〃出紙巾

｝；

/*類SoldOutState、NoQuarterState>

HasQuarterState>SoldState的定義省略，每個類中均定義

了私有數(shù)據(jù)成員TissueMachine*tissueMachine;*/

classTissueMachine{

private：

⑴*soldOutState,*noQuarterState,*hasQuarterState

,*soldState,Estate;[/⑴State

intcount;〃紙巾數(shù)

public：

TissueMachine(intnumbers);

voidsetState(State*state);

State*getHasQuarterState();

State*getNoQuarterState();

State*getSoldState();

State*getSoldOutState();

intgetCount();

〃其余代碼省略

)；

〃以下為類的實現(xiàn)部分

voidNoQuarterState::insertQuarter(){

tissueMachine->setState((2));12)

tissueMachine->getHasQuarterState()

)

voidHasQuarterState::ejectQuarter(){

tissueMachine->setState((3));

(3)tissueMachine->getNoQuarterState()

)

voidSoldState::dispense(){

if(tissueMachine->getCount()>0){

tissueMachine->setState((4));

)//(4)tissueMachine->getNoQuarterState()

else{

tissueMachine->setState((5));

)//(5)tissueMachine->getSoldOutState()

)〃其余代碼省略

(1)State

(2)tissueMachine->getHasQuarterState()

(3)tissueMachine->getNoQuarterState()

(4)tissueMachine->getNoQuarterState()

(5)tissueMachine->getSoldoutState()

試題五分析

本題考查狀態(tài)(State)模式的概念及應(yīng)用。

狀態(tài)模式是一種對象的行為型模式，允許一個對象在其

內(nèi)部狀態(tài)變更時變更它的行為，對象看起來好像修改了它的

類。狀態(tài)模式的類圖如下所示：

狀態(tài)模式主要解決的是限制一個對象轉(zhuǎn)換的條件表達式

過于困難的狀況。把狀態(tài)的推斷邏輯轉(zhuǎn)移到表示不同狀態(tài)的

一系列類當中，可以把困難的推斷邏輯簡化。狀態(tài)模式的好

處是將與特定狀態(tài)相關(guān)的行為局部化，并且將不同狀態(tài)的行

為分割開來。

題目利用狀態(tài)模式來實現(xiàn)一個簡易的紙巾售賣機。售賣

機的狀態(tài)轉(zhuǎn)換圖已經(jīng)在題目中給出，類SOldState、

SoldoutState>NoQuarterState和HasQuaerState分別用來

表示售賣機的4種不同狀態(tài)，對應(yīng)于狀態(tài)模式中的

ConcreteStatel,...ConcreteStateNo題目所設(shè)置的填空，

主要集中在狀態(tài)轉(zhuǎn)換上。因此解答該題時，要求在理解狀態(tài)

模式內(nèi)涵的基礎(chǔ)上，依據(jù)紙巾售賣機的狀態(tài)轉(zhuǎn)換原則，給出

正確的狀態(tài)設(shè)置。

空(1)出現(xiàn)在類TissueMachine的數(shù)據(jù)成員定義部分。狀

態(tài)模式封裝了狀態(tài)的轉(zhuǎn)換過程，但是它須要枚舉可能的狀

態(tài)，因此須要確定狀態(tài)種類。因此在類TissueMachine中需

定義出全部可能的狀態(tài)對象。依據(jù)所給出的對象名稱及說明

中的描述，可知⑴處應(yīng)填入的類名為State。

空⑵?⑸都是與狀態(tài)轉(zhuǎn)換相關(guān)的，要求填寫類

TissueMachine中的方法setState在不同調(diào)用處的實際參

數(shù)。依據(jù)方法的名稱及調(diào)用方式，可以推斷出這個方法的功

能就是設(shè)置自動售賣機的當前狀態(tài)。要填出這些空，只要比

照圖5.1的狀態(tài)轉(zhuǎn)換圖，依據(jù)狀態(tài)轉(zhuǎn)換的條件確定出當前狀

態(tài)及下一狀態(tài)即可。

空(2)出現(xiàn)在方法insertQuaner內(nèi)，即給紙巾售賣機投

入2元錢。依據(jù)狀態(tài)圖，“投入2元錢”之后，售賣機應(yīng)轉(zhuǎn)

換到“有2元錢”的狀態(tài)?！坝?元錢”對應(yīng)的狀態(tài)的類為

^HasQuanerStatev,所以空(2)處應(yīng)填類HasQuanerState

的對象。由于hasQuanerState是類TissueMachine的私有數(shù)

據(jù)成員，不能干脆訪問，所以只能通過調(diào)用相關(guān)的get方法

來獲得該對象。由此得出(2)應(yīng)填tissueMachine->

getHasQuarterState()；

同理，空⑶表示的狀態(tài)是從“有2元錢”狀態(tài)，經(jīng)驗

“退回2元錢”事務(wù)之后的狀態(tài)，及“沒有投幣”狀態(tài)。所

以空(3)處應(yīng)填tissueMachine->getNoQuanerState()。

空(4)和(5)處分別表示賣出一包紙巾之后，售賣機應(yīng)當

轉(zhuǎn)換到的下一個狀態(tài)。這個跟售賣機中的紙巾數(shù)有關(guān)，假如

還有紙巾，則轉(zhuǎn)換到“沒有投幣”狀態(tài)，假如沒有紙巾了，

則轉(zhuǎn)換到“紙巾售完”狀態(tài)，因此，空⑷處應(yīng)填

tissueMachine->getNoQuarterState(),空(5)處應(yīng)填

tissueMachine->getSoldOutState()。

參考答案

(1)State

(2)tissueMachine->getHasQuarterState()

(3)tissueMachine->getNoQuarterState()

(4)tissueMachine->getNoQuarterState()

(5)tissueMachine->getSoldoutState()

試題六

閱讀下列說明和Java代碼，將應(yīng)填入(n)處的字句寫在

答題紙的對應(yīng)欄內(nèi)。

［說明］

某大型商場內(nèi)安裝了多個簡易的紙巾售賣機，自動出售2

元錢一包的紙巾，且每次僅售出一包紙巾。紙巾售賣機的狀

態(tài)圖如圖6-1所示。

圖6T紙巾售賣機的狀態(tài)圖

采納狀態(tài)(State)模式來實現(xiàn)該紙巾售賣機，得到如圖6-

2所示的類圖。其中類State為抽象類，定義了投幣、退幣、

出紙巾等方法接口。類SoldState、SoldOutState>

NoQuarterState和HasQuarterState分別對應(yīng)圖6-1中紙巾

售賣機的4種狀態(tài)：售出紙巾、紙巾售完、沒有投幣、有2

元錢。

State

圖6-2類圖

[Java代碼]

importjava.util.

interfaceState{

publicvoidinsertQuarter();〃投幣

publicvoidejectQuarter();〃退幣

publicvoidturnCrank();〃按下“出紙巾"按鈕

publicvoiddispense();//出紙巾

)

classTissueMachine{

(1)soldOutState,noQuarterState,hasQuarterState,soldSt

ate,state;(1)State

state=soldOutState;

intcount=0;〃紙巾數(shù)

publicTissueMachine(intnumbers){/*實現(xiàn)代碼省略*/)

publicStategetHasQuarterState(){return

hasQuarterState;}

publicStategetNoQuarterState(){return

noQuarterState;}

publicStategetSoldState(){returnsoldState;

publicStategetSoldOutState(){return

soldOutState;}

publicintgetCount(){returncount;}

〃其余代碼省略

classNoQuarterStateimplementsState{

TissueMachinetissueMachine;

publicvoidinsertQuarter(){

tissueMachine.setState((2));

}//(2)tissueMachine.getHasQuarterState()

〃構(gòu)造方法以及其余代碼省略

classHasQuarterStateimplementsState{

TissueMachinetissueMachine;

publicvoidejectQuarter(){

tissueMachine.setState((3));

}//(3)tissueMachine.getNoQuarterState()

〃構(gòu)造方法以及其余代碼省略

classSoldStateimplementsState{

TissueMachinetissueMachine;

publicvoiddispense(){

if(tissueMachine.getCount()>0){

tissueMachine.setState((4));

}//(4)tissueMachine.getNoQuarterState()

else{

tissueMachine.setState((5));

)//(5)tissueMachine.getSoldOutState()

)

試題六分析

本題考查狀態(tài)(State)模式的概念及應(yīng)用。

狀態(tài)模式