2011(下半年)試題及答案(下午).doc

第8章 軟件設(shè)計(jì)師下午試題分析與解答試題一閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題4，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某公司欲開發(fā)招聘系統(tǒng)以提高招聘效率，其主要功能如下：(1)接受申請(qǐng)驗(yàn)證應(yīng)聘者所提供的自身信息是否完整，是否說(shuō)明了應(yīng)聘職位，受理驗(yàn)證合格的申請(qǐng)，給應(yīng)聘者發(fā)送致謝信息。(2)評(píng)估應(yīng)聘者根據(jù)部門經(jīng)理設(shè)置的職位要求，審查已經(jīng)受理的申請(qǐng)；對(duì)未被錄用的應(yīng)聘者進(jìn)行謝絕處理，將未被錄用的應(yīng)聘者信息存入未錄用的應(yīng)聘者表，并給其發(fā)送謝絕決策；對(duì)錄用的應(yīng)聘者進(jìn)行職位安排評(píng)價(jià)，將評(píng)價(jià)結(jié)果存入評(píng)價(jià)結(jié)果表，并給其發(fā)送錄用決策，發(fā)送錄用職位和錄用者信息給工資系統(tǒng)。現(xiàn)采用結(jié)構(gòu)化方法對(duì)招聘系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的頂層數(shù)據(jù)流圖、圖1-2所示0層數(shù)據(jù)流圖和圖1-3所示1層數(shù)據(jù)流圖。問(wèn)題1使用說(shuō)明中的術(shù)語(yǔ)，給出圖中E1E3所對(duì)應(yīng)的實(shí)體名稱。答：E1:應(yīng)聘者 E2: 部門經(jīng)理 E3: 工資系統(tǒng)問(wèn)題2 使用說(shuō)明中的術(shù)語(yǔ)，給出圖中D1D2所對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)答：D1: 未錄用的應(yīng)聘者表 D2: 評(píng)價(jià)結(jié)果表問(wèn)題3使用說(shuō)明和圖中的術(shù)語(yǔ)，給出圖1-3中加工P1P3的名稱。答：P1:驗(yàn)證申請(qǐng) P2: 審查申請(qǐng) P3: 職位安排評(píng)價(jià)問(wèn)題4解釋說(shuō)明圖1-2和圖1-3是否保持平衡，若不平衡請(qǐng)按如下格式補(bǔ)充圖1-3中數(shù)據(jù)流的名稱以及數(shù)據(jù)流的起點(diǎn)或終點(diǎn)，使其平衡(使用說(shuō)明中的術(shù)語(yǔ)或圖中符號(hào))。 答：數(shù)據(jù)流名稱起 點(diǎn)錄用職位P3 或 2.3職位安排評(píng)價(jià)已受理的申請(qǐng)1.2受理申請(qǐng)謝絕決策2.2謝絕應(yīng)聘者試題二閱讀下列說(shuō)明，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某物流公司為了整合上游供應(yīng)商與下游客戶，縮短物流過(guò)程，降低產(chǎn)品庫(kù)存，需要構(gòu)建一個(gè)信息系統(tǒng)以方便管理其業(yè)務(wù)運(yùn)作活動(dòng)。需求分析結(jié)果(1)物流公司包含若干部門，部門信息包括部門號(hào)、部門名稱、經(jīng)理、電話和郵箱。一個(gè)部門可以有多名員工處理部門的日常事務(wù)，每名員工只能在一個(gè)部門工作。每個(gè)部門有一名經(jīng)理，只需負(fù)責(zé)管理本部門的事務(wù)和人員。(2)員工信息包括員工號(hào)、姓名、職位、電話號(hào)碼和工資；其中，職位包括：經(jīng)理、業(yè)務(wù)員等。業(yè)務(wù)員根據(jù)托運(yùn)申請(qǐng)負(fù)責(zé)安排承運(yùn)貨物事宜，例如：裝貨時(shí)間、到達(dá)時(shí)間等。一個(gè)業(yè)務(wù)員可以安排多個(gè)托運(yùn)申請(qǐng)，但一個(gè)托運(yùn)申請(qǐng)只由一個(gè)業(yè)務(wù)員處理。(3)客戶信息包括客戶號(hào)、單位名稱、通信地址、所屬省份、聯(lián)系人、聯(lián)系電話、銀行賬號(hào)，其中，客戶號(hào)唯一標(biāo)識(shí)客戶信息的每一個(gè)元組。每當(dāng)客戶要進(jìn)行貨物托運(yùn)時(shí)，先要提出貨物托運(yùn)申請(qǐng)。托運(yùn)申請(qǐng)信息包括申請(qǐng)?zhí)枴⒖蛻籼?hào)、貨物名稱、數(shù)量、運(yùn)費(fèi)、出發(fā)地、目的地。其中，一個(gè)申請(qǐng)?zhí)枌?duì)應(yīng)唯一的一個(gè)托運(yùn)申請(qǐng)；一個(gè)客戶可以有多個(gè)貨物托運(yùn)申請(qǐng)，但一個(gè)托運(yùn)申請(qǐng)對(duì)應(yīng)唯一的一個(gè)客戶號(hào)。概念模型設(shè)計(jì)根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式(不完整)如圖2-1所示。關(guān)系模式設(shè)計(jì)部門(部門號(hào)，部門名稱，經(jīng)理，電話，郵箱)員工(員工號(hào)，姓名，職位，電話號(hào)碼，工資， (a) 部門號(hào) )客戶( (b) ，單位名稱，通信地址，所屬省份，聯(lián)系人，聯(lián)系電話，銀行賬號(hào))托運(yùn)申請(qǐng)( (c) ，貨物名稱，數(shù)量，運(yùn)費(fèi)，出發(fā)地，目的地) 申請(qǐng)?zhí)枴⒖蛻籼?hào)、貨物名稱、數(shù)量、運(yùn)費(fèi)、出發(fā)地、目的地安排承運(yùn)( (d) ，裝貨時(shí)間，到達(dá)時(shí)間，業(yè)務(wù)員)問(wèn)題1根據(jù)問(wèn)題描述，補(bǔ)充四個(gè)聯(lián)系、聯(lián)系的類型，以及實(shí)體與子實(shí)體的聯(lián)系，完善圖2-1所示的實(shí)體聯(lián)系圖。答：托運(yùn)申請(qǐng)客戶員工部門處理申請(qǐng)安排管理業(yè)務(wù)員經(jīng)理nn11n111問(wèn)題2根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空(a)(d)補(bǔ)充完整。分別指出部門、員工和安排承運(yùn)關(guān)系模式的主鍵和外鍵。答：（1）a: 部門號(hào) b: 客戶號(hào)c: 申請(qǐng)?zhí)?、客戶?hào) d: 申請(qǐng)?zhí)枺?）部門： 主鍵：部門號(hào) 外鍵：無(wú)員工： 主鍵：?jiǎn)T工號(hào) 外鍵：部門號(hào)安排承運(yùn)：主鍵：申請(qǐng)?zhí)?外鍵：無(wú)問(wèn)題3若系統(tǒng)新增需求描述如下：為了數(shù)據(jù)庫(kù)信息的安全性，公司要求對(duì)數(shù)據(jù)庫(kù)操作設(shè)置權(quán)限管理功能，當(dāng)員工登錄系統(tǒng)時(shí)，系統(tǒng)需要檢查員工的權(quán)限。權(quán)限的設(shè)置人是部門經(jīng)理。為滿足上述需要，應(yīng)如何修改(或補(bǔ)充)圖2-1所示的實(shí)體聯(lián)系圖，請(qǐng)給出修改后的實(shí)體聯(lián)系圖和關(guān)系模式。權(quán)限客戶員工部門處理申請(qǐng)安排管理業(yè)務(wù)員經(jīng)理設(shè)置托運(yùn)申請(qǐng)答：1nnn11111n試題二分析本題考查數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)體聯(lián)系模型(E-R模型)和關(guān)系模式設(shè)計(jì)方面的應(yīng)用知識(shí)。問(wèn)題1兩個(gè)實(shí)體集之間的聯(lián)系類型分為三類：一對(duì)一(1:1)聯(lián)系、一對(duì)多(1:n)聯(lián)系和多對(duì)多(m:n)聯(lián)系。根據(jù)題意，每名員工只能在一個(gè)部門工作，所以部門和員工之間有一個(gè)1:n的“所屬”聯(lián)系；由于每個(gè)部門有一名經(jīng)理，只需負(fù)責(zé)管理本部門的事務(wù)和人員，因此部門和經(jīng)理之間有一個(gè)1:1的“管理”聯(lián)系；由于一個(gè)業(yè)務(wù)員可以安排多個(gè)托運(yùn)申請(qǐng)，但一個(gè)托運(yùn)申請(qǐng)只由一個(gè)業(yè)務(wù)員處理，故業(yè)務(wù)員和托運(yùn)申請(qǐng)之間有一個(gè)1:n的“托運(yùn)”聯(lián)系；又由于一個(gè)客戶可以有多個(gè)貨物托運(yùn)申請(qǐng)，但一個(gè)托運(yùn)申請(qǐng)對(duì)應(yīng)唯一的一個(gè)客戶號(hào)，故客戶和托運(yùn)申請(qǐng)之間有一個(gè)1:n的“申請(qǐng)”聯(lián)系。根據(jù)上述分析，完善圖2-1所示的實(shí)體聯(lián)系圖可參見(jiàn)參考答案。問(wèn)題2根據(jù)題意，部門和員工之間有一個(gè)1:n的“所屬”聯(lián)系需要將一端的碼并入多端，故員工關(guān)系模式中的空(a)應(yīng)填寫部門號(hào)；在客戶關(guān)系模式中，客戶號(hào)為主鍵，故空(b)應(yīng)填寫客戶號(hào)；在托運(yùn)申請(qǐng)關(guān)系模式中，申請(qǐng)?zhí)?、客戶?hào)為主鍵，故空(c)應(yīng)填寫申請(qǐng)?zhí)?、客戶?hào)；又由于一個(gè)業(yè)務(wù)員可以安排多個(gè)托運(yùn)申請(qǐng)，但一個(gè)托運(yùn)申請(qǐng)只由一個(gè)業(yè)務(wù)員處理，因此在安排承運(yùn)關(guān)系模式中，申請(qǐng)?zhí)枮橹麈I，故空(d)應(yīng)填寫申請(qǐng)?zhí)?。部門關(guān)系模式中的部門號(hào)為主鍵，經(jīng)理為外鍵；因?yàn)榻?jīng)理來(lái)自員工關(guān)系。員工關(guān)系模式中的員工號(hào)為主鍵，部門號(hào)為外鍵，因?yàn)椴块T號(hào)來(lái)自部門關(guān)系。安排承運(yùn)關(guān)系模式中的申請(qǐng)?zhí)枮橹麈I，業(yè)務(wù)員為外鍵，因?yàn)闃I(yè)務(wù)員來(lái)自員工關(guān)系。問(wèn)題3根據(jù)題意，權(quán)限的設(shè)置人是部門經(jīng)理，因此，需要建立一個(gè)權(quán)限關(guān)系模式，以及經(jīng)理到權(quán)限之間的1:n的“設(shè)置”聯(lián)系。修改后的實(shí)體聯(lián)系圖和關(guān)系模式參見(jiàn)參考答案。參考答案問(wèn)題1問(wèn)題2(a)部門號(hào)(b)客戶號(hào)(c)申請(qǐng)?zhí)?，客戶?hào)(d)申請(qǐng)?zhí)柌块T主鍵：部門號(hào)外鍵：經(jīng)理員工主鍵：?jiǎn)T工號(hào)外鍵：部門號(hào)安排承運(yùn)主鍵：申請(qǐng)?zhí)柾怄I：業(yè)務(wù)員問(wèn)題3關(guān)系模式：權(quán)限(員工號(hào)，權(quán)限，設(shè)置人)或權(quán)限(員工號(hào)，權(quán)限，部門經(jīng)理)試題三閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明Pay&Drive系統(tǒng)(開多少付多少)能夠根據(jù)駕駛里程自動(dòng)計(jì)算應(yīng)付的費(fèi)用。系統(tǒng)中存儲(chǔ)了特定區(qū)域的道路交通網(wǎng)的信息。道路交通網(wǎng)由若干個(gè)路段(RoadSegment)構(gòu)成，每個(gè)路段由兩個(gè)地理坐標(biāo)點(diǎn)(Node)標(biāo)定，其里程數(shù)(Distance)是已知的。在某些地理坐標(biāo)點(diǎn)上安裝了訪問(wèn)控制(Access Control)設(shè)備，可以自動(dòng)掃描行駛卡(Card)。行程(Trajectory)由一組連續(xù)的路段構(gòu)成。行程的起點(diǎn)(Entry)和終點(diǎn)(Exit)都裝有訪問(wèn)控制設(shè)備。系統(tǒng)提供了3種行駛卡。常規(guī)卡(Regular Card)有效期(Valid Period)為一年，可以在整個(gè)道路交通網(wǎng)內(nèi)使用。季卡(Season Card)有效期為三個(gè)月，可以在整個(gè)道路交通網(wǎng)內(nèi)使用。單次卡(Minitrip Card)在指定的行程內(nèi)使用，且只能使用一次。其中，季卡和單次卡都是預(yù)付卡(Prepaid Card)，需要客戶(Customer)預(yù)存一定的費(fèi)用。系統(tǒng)的主要功能有：客戶注冊(cè)、申請(qǐng)行駛卡、使用行駛卡行駛等。使用常規(guī)卡行駛，在進(jìn)入行程起點(diǎn)時(shí)，系統(tǒng)記錄行程起點(diǎn)、進(jìn)入時(shí)間(Date Of Entry)等信息。在到達(dá)行程終點(diǎn)時(shí)，系統(tǒng)根據(jù)行駛的里程數(shù)和所持卡的里程單價(jià)(Unit Price)計(jì)算應(yīng)付費(fèi)用，并打印費(fèi)用單(Invoice)。季卡的使用流程與常規(guī)卡類似，但是不需要打印費(fèi)用單，系統(tǒng)自動(dòng)從卡中扣除應(yīng)付費(fèi)用。單次卡的使用流程與季卡類似，但還需要在行程的起點(diǎn)和終點(diǎn)上檢查行駛路線是否符合該卡所規(guī)定的行駛路線?，F(xiàn)采用面向?qū)ο蠓椒ㄩ_發(fā)該系統(tǒng)，使用UML進(jìn)行建模。構(gòu)建出的用例圖和類圖分別如圖3-1和圖3-2所示。問(wèn)題1根據(jù)說(shuō)明中的描述，給出圖3-1中U1和U2所對(duì)應(yīng)的用例，以及(1)所對(duì)應(yīng)的關(guān)系。答：U1:使用常規(guī)卡行駛 U2：使用單次卡行駛（1）：?jiǎn)栴}2根據(jù)說(shuō)明中的描述，給出圖3-2中缺少的C1C6所對(duì)應(yīng)的類名以及(2)(3)處所對(duì)應(yīng)的多重度(類名使用說(shuō)明中給出的英文詞匯)。答：C1: RoadSegment C2: TrajectoryC3: Card C4: Regular CardC5: Prepaid Card C6: Minitrip Card(2):1(3):13問(wèn)題3根據(jù)說(shuō)明中的描述，給出Road Segment、Trajectory和Card所對(duì)應(yīng)的類的關(guān)鍵屬性(屬性名使用說(shuō)明中給出的英文詞匯)。答：RoadSegment的屬性：DistanceTrajectory的屬性：Entry、Exit、DateOfEntryCard的屬性：UnitPrice、ValidPeriod試題三分析本題屬于經(jīng)典的考題，主要考查面向?qū)ο蠓治龇椒ㄒ约癠ML的用例圖和類圖的相關(guān)知識(shí)。問(wèn)題1本問(wèn)題要求將圖3-1所給出的用例圖補(bǔ)充完整。用例圖的構(gòu)成要素有：參與者、用例以及用例之間的關(guān)系。圖中缺少了兩個(gè)用例，以及一個(gè)用例關(guān)系。解答此題時(shí)，首先應(yīng)從說(shuō)明中找到所有的用例。用例表示系統(tǒng)的一個(gè)單一業(yè)務(wù)功能。從題目的描述中可以看出，系統(tǒng)的主要功能就是申請(qǐng)行駛卡，以及使用行駛卡行駛。由于行駛卡分為三種，所以在說(shuō)明中詳細(xì)描述了三種行駛卡的使用方法。再結(jié)合用例圖來(lái)看，缺少的兩個(gè)用例與用例“使用季卡行駛”有關(guān)聯(lián)關(guān)系，由此可以推斷出，需要補(bǔ)充的這兩個(gè)用例必定與另外兩種行駛卡相關(guān)，分別為“使用常規(guī)卡行駛”和“使用單次卡行駛”。下面需要解決的問(wèn)題是這兩個(gè)用例與U1和U2的對(duì)應(yīng)關(guān)系。這就需要仔細(xì)考查一下用例圖所給出的用例關(guān)系。由圖3-1可知，U1和“使用季卡行駛”之間是泛化(generalization)關(guān)系。當(dāng)多個(gè)用例共同擁有一種類似的結(jié)構(gòu)和行為時(shí)，可以將它們的共性抽象為父用例，其他的用例作為泛化關(guān)系中的子用例。在用例的泛化關(guān)系中，子用例是父用例的一種特殊形式，子用例繼承了父用例所有的結(jié)構(gòu)、行為和關(guān)系。根據(jù)說(shuō)明中的“季卡的使用流程與常規(guī)卡類似，但是不需要打印費(fèi)用單，系統(tǒng)自動(dòng)從卡中扣除應(yīng)付費(fèi)用”可知，U1應(yīng)該對(duì)應(yīng)著用例“使用常規(guī)卡行駛”。由此不難得出U2對(duì)應(yīng)著用例“用單次卡行駛”。現(xiàn)在圖中只剩下(1)處的用例關(guān)系沒(méi)有確定。用例之間的關(guān)系在用例圖上只有三種：包含(include)、擴(kuò)展(extend)和泛化(generalization)。包含關(guān)系是指當(dāng)多個(gè)用例中存在相同事件流時(shí)，可以把這些公共事件流抽象成為公共用例，這個(gè)公共用例稱為抽象用例，而原始用例稱為基礎(chǔ)用例?；A(chǔ)用例和抽象用例之間是包含關(guān)系。如果一個(gè)用例明顯地混合了兩種或兩種以上的不同場(chǎng)景，則可以將這個(gè)用例分為一個(gè)基本用例和多個(gè)擴(kuò)展用例。擴(kuò)展關(guān)系用“extend”表示，箭頭指向基本用例。包含關(guān)系和擴(kuò)展關(guān)系的區(qū)別在于，抽象用例中的事件流一定要插入到基本用例中去，并且插入點(diǎn)只有一個(gè)，通常抽象用例不能脫離基本用例而獨(dú)立存在。擴(kuò)展用例的事件流往往可以抽象為基本用例的備選事件流，在擴(kuò)展關(guān)系中，可以根據(jù)一定的條件來(lái)決定是否將擴(kuò)展用例的事件流插入到基本用例的事件流中，并且插入點(diǎn)可以有多個(gè)。根據(jù)以上分析可知，(1)處的用例關(guān)系選擇“extend”最為合適。問(wèn)題2本問(wèn)題考查的是類圖建模。解題的重點(diǎn)在于根據(jù)類圖中提供的類及類之間的關(guān)聯(lián)關(guān)系，推斷出剩余的類?？梢韵扔^察一下類圖?？梢钥吹剑枰a(bǔ)充的類基本上集中在兩個(gè)結(jié)構(gòu)上：聚集結(jié)構(gòu)(類C1和C2)以及繼承結(jié)構(gòu)(類C3C6)。繼承結(jié)構(gòu)是比較容易辨識(shí)的類之間的關(guān)聯(lián)關(guān)系，圖上給出了其中的一個(gè)子類SeasonCard。以這個(gè)類為線索，回到說(shuō)明中尋找與類SeasonCard相關(guān)的其他類。從說(shuō)明中可知，“系統(tǒng)提供了3種卡”，常規(guī)卡、季卡、單次卡，而“季卡和單次卡都是預(yù)付卡”。這些描述暗示，“季卡”、“單次卡”與“預(yù)付卡”之間存在著特殊/一般關(guān)系，即“is-a”關(guān)系，這是繼承結(jié)構(gòu)的典型標(biāo)志。由此可以得出類C5和C6應(yīng)該分別對(duì)應(yīng)PrepaidCard(預(yù)付卡)和MinitripCard(單次卡)。根據(jù)C5和C6所對(duì)應(yīng)的類，可以推斷出，C4和C3必定也是與行駛卡相關(guān)的類。三種卡中，已經(jīng)有兩種卡有了對(duì)應(yīng)的類，還剩下一種卡即“常規(guī)卡”。而“常規(guī)卡”只能是與“預(yù)付卡”同層次的概念，所以只能對(duì)應(yīng)于C4，C3表示的是能代表所有這幾種卡的公共概念。所以C3和C4應(yīng)分別對(duì)應(yīng)于Card和RegularCard。確定了C3之后，就可以識(shí)別出(2)和(3)處的多重度。Customer和Card之間是持有和被持有的關(guān)系，由于系統(tǒng)中只有3種卡，所以一個(gè)客戶最多只能有3種卡，所以(3)處應(yīng)填1.3。而對(duì)于任何一張卡來(lái)說(shuō)，只能有唯一地一個(gè)所屬人，因此(2)處應(yīng)填1。現(xiàn)在還剩下類C1和C2沒(méi)有確定。由于這兩個(gè)類之間是聚集關(guān)系，所以需要在說(shuō)明中尋找具有“部分一整體”關(guān)系的概念。由說(shuō)明中的“行程(Trajectory)由一組連續(xù)的路段構(gòu)成”可知，C1和C2應(yīng)分別對(duì)應(yīng)于RoadSegment和Trajectory。問(wèn)題3本問(wèn)題考查類的關(guān)鍵屬性的識(shí)別。由說(shuō)明中給出的描述可知，類RoadSegment的屬性至少應(yīng)包括Distance；類Trajectory的屬性至少應(yīng)包括Entry、Exit和DateOfEntry;類Card的屬性至少應(yīng)包括UnitPrice、ValidPeriod。參考答案問(wèn)題1U1：使用常規(guī)卡行駛 U2：使用單次卡行駛 (1)：extend問(wèn)題2C1：RoadSegment C2：Trajectory C3：CardC4：RegularCard C5：PrepaidCard C6：MinitripCard(2)1 (3)1.3問(wèn)題3RoadSegment的屬性：DistanceTrajectory的屬性：Entry、Exit、DateOfEntryCard的屬性：UnitPrice、ValidPeriod試題四閱讀下列說(shuō)明和C代碼，將應(yīng)填入 (n) 處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明設(shè)某一機(jī)器由n個(gè)部件組成，每一個(gè)部件都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。供應(yīng)商j供應(yīng)的部件i具有重量wij和價(jià)格cij。設(shè)計(jì)一個(gè)算法，求解總價(jià)格不超過(guò)上限cc的最小重量的機(jī)器組成。采用回溯法來(lái)求解該問(wèn)題：首先定義解空間。解空間由長(zhǎng)度為n的向量組成，其中每個(gè)分量取值來(lái)自集合1，2，m)，將解空間用樹形結(jié)構(gòu)表示。接著從根結(jié)點(diǎn)開始，以深度優(yōu)先的方式搜索整個(gè)解空間。從根結(jié)點(diǎn)開始，根結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。向縱深方向考慮第一個(gè)部件從第一個(gè)供應(yīng)商處購(gòu)買，得到一個(gè)新結(jié)點(diǎn)。判斷當(dāng)前的機(jī)器價(jià)格(c11)是否超過(guò)上限(cc)，重量(w11)是否比當(dāng)前已知的解(最小重量)大，若是，應(yīng)回溯至最近的一個(gè)活結(jié)點(diǎn)；若否，則該新結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)，根結(jié)點(diǎn)不再是擴(kuò)展結(jié)點(diǎn)。繼續(xù)向縱深方向考慮第二個(gè)部件從第一個(gè)供應(yīng)商處購(gòu)買，得到一個(gè)新結(jié)點(diǎn)。同樣判斷當(dāng)前的機(jī)器價(jià)格(c11+c21)是否超過(guò)上限(cc)，重量(w11+w21)是否比當(dāng)前已知的解(最小重量)大。若是，應(yīng)回溯至最近的一個(gè)活結(jié)點(diǎn)；若否，則該新結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)，原來(lái)的結(jié)點(diǎn)不再是擴(kuò)展結(jié)點(diǎn)。以這種方式遞歸地在解空間中搜索，直到找到所要求的解或者解空間中已無(wú)活結(jié)點(diǎn)為止。C代碼下面是該算法的C語(yǔ)言實(shí)現(xiàn)。(1)變量說(shuō)明n：機(jī)器的部件數(shù)m：供應(yīng)商數(shù)cc：價(jià)格上限w：二維數(shù)組，wij表示第j個(gè)供應(yīng)商供應(yīng)的第i個(gè)部件的重量c：二維數(shù)組，cij表示第j個(gè)供應(yīng)商供應(yīng)的第i個(gè)部件的價(jià)格bestW：滿足價(jià)格上限約束條件的最小機(jī)器重量bestC：最小重量機(jī)器的價(jià)格bestX：最優(yōu)解，一維數(shù)組，bestXi表示第i個(gè)部件來(lái)自哪個(gè)供應(yīng)商cw：搜索過(guò)程中機(jī)器的重量cp：搜索過(guò)程中機(jī)器的價(jià)格x：搜索過(guò)程中產(chǎn)生的解，xi表示第i個(gè)部件來(lái)自哪個(gè)供應(yīng)商i：當(dāng)前考慮的部件，從0到n-1j：循環(huán)變量(2)函數(shù)backtrackint n=3;int m=3;int cc=4;int w33=1,2,3,3,2,1,2,2,2;int c33=1,2,3,3,2,1,2,2,2;int bestW=8;int bestC=0;int bestX3=0，0，0;int cw=0;int cp=0;int x3=0，0，0;int backtrack (int i)int j=0;int found=0;if(in-1) /*得到問(wèn)題解*/bestW=cw;bestC=cp;for(j=0; jn; j+)(1) ; /bestXj=xjreturn 1;if (cp=cc)(/*有解*/found=1;for(j=0; (2) ; j+) /jm/*第i個(gè)部件從第j個(gè)供應(yīng)商購(gòu)買*/(3) ; /xi=jcw=cw+wi j;cp=cp+ci j;if (cp=cc& (4) )/*深度搜索，擴(kuò)展當(dāng)前結(jié)點(diǎn)*/cw0投入2元錢有2元錢沒(méi)有投幣售出紙巾紙巾售完按下取紙巾按鈕紙巾數(shù)0 圖5-1 紙巾售賣機(jī)的狀態(tài)圖采用狀態(tài)(State)模式來(lái)實(shí)現(xiàn)該紙巾售賣機(jī)，得到如圖5-2所示的類圖。其中類State為抽象類，定義了投幣、退幣、出紙巾等方法接口。類SoldState、SoldOutState、NoQuarterState和HasQuarterState分別對(duì)應(yīng)圖5-1中紙巾售賣機(jī)的4種狀態(tài)：售出紙巾、紙巾售完、沒(méi)有投幣、有2元錢。C+代碼#include iostreamusing namespace std;/以下為類的定義部分 class TissueMachine; /類的提前引用 class State public： virtual void insertQuarter()=0; /投幣 virtual void ejectQuarter()=0; /退幣 virtual void turnCrank()=0; /按下“出紙巾”按鈕 virtual void dispense()=0; /出紙巾 ; /*類SoldOutState、NoQuarterState、HasQuarterState、SoldState的定義省略，每個(gè)類中均定義了私有數(shù)據(jù)成員TissueMachine*tissueMachine;*/ class TissueMachine private： (1)*soldOutState,*noQuarterState,*hasQuarterState,*soldState，*state; /(1) Stateint count; /紙巾數(shù) public： TissueMachine(int numbers); void setState(State* state); State* getHasQuarterState(); State* getNoQuarterState(); State* getSoldState(); State* getSoldOutState(); int getCount(); /其余代碼省略; /以下為類的實(shí)現(xiàn)部分 void NoQuarterState :insertQuarter() tissueMachine-setState( (2) ); /(2) tissueMachine-getHasQuarterState() void HasQuarterState :ejectQuarter()tissueMachine-setState( (3) ); / (3)tissueMachine-getNoQuarterState() void SoldState :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)模式是一種對(duì)象的行為型模式，允許一個(gè)對(duì)象在其內(nèi)部狀態(tài)改變時(shí)改變它的行為，對(duì)象看起來(lái)似乎修改了它的類。狀態(tài)模式的類圖如下所示：狀態(tài)模式主要解決的是控制一個(gè)對(duì)象轉(zhuǎn)換的條件表達(dá)式過(guò)于復(fù)雜的情況。把狀態(tài)的判斷邏輯轉(zhuǎn)移到表示不同狀態(tài)的一系列類當(dāng)中，可以把復(fù)雜的判斷邏輯簡(jiǎn)化。狀態(tài)模式的好處是將與特定狀態(tài)相關(guān)的行為局部化，并且將不同狀態(tài)的行為分割開來(lái)。題目利用狀態(tài)模式來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)易的紙巾售賣機(jī)。售賣機(jī)的狀態(tài)轉(zhuǎn)換圖已經(jīng)在題目中給出，類S01dState、SoldoutState、NoQuarterState和HasQuaerState分別用來(lái)表示售賣機(jī)的4種不同狀態(tài)，對(duì)應(yīng)于狀態(tài)模式中的ConcreteState1，.ConcreteStateN。題目所設(shè)置的填空，主要集中在狀態(tài)轉(zhuǎn)換上。因此解答該題時(shí)，要求在理解狀態(tài)模式內(nèi)涵的基礎(chǔ)上，依據(jù)紙巾售賣機(jī)的狀態(tài)轉(zhuǎn)換原則，給出正確的狀態(tài)設(shè)置?？?1)出現(xiàn)在類TissueMachine的數(shù)據(jù)成員定義部分。狀態(tài)模式封裝了狀態(tài)的轉(zhuǎn)換過(guò)程，但是它需要枚舉可能的狀態(tài)，因此需要確定狀態(tài)種類。因此在類TissueMachine中需定義出所有可能的狀態(tài)對(duì)象。根據(jù)所給出的對(duì)象名稱及說(shuō)明中的描述，可知(1)處應(yīng)填入的類名為State?？?2)(5)都是與狀態(tài)轉(zhuǎn)換相關(guān)的，要求填寫類TissueMachine中的方法setState在不同調(diào)用處的實(shí)際參數(shù)。根據(jù)方法的名稱及調(diào)用方式，可以推斷出這個(gè)方法的功能就是設(shè)置自動(dòng)售賣機(jī)的當(dāng)前狀態(tài)。要填出這些空，只要對(duì)照?qǐng)D5.1的狀態(tài)轉(zhuǎn)換圖，根據(jù)狀態(tài)轉(zhuǎn)換的條件確定出當(dāng)前狀態(tài)及下一狀態(tài)即可?？?2)出現(xiàn)在方法insertQuaner內(nèi)，即給紙巾售賣機(jī)投入2元錢。根據(jù)狀態(tài)圖，“投入2元錢”之后，售賣機(jī)應(yīng)轉(zhuǎn)換到“有2元錢”的狀態(tài)?！坝?元錢”對(duì)應(yīng)的狀態(tài)的類為“HasQuanerState”，所以空(2)處應(yīng)填類HasQuanerState的對(duì)象。由于hasQuanerState是類TissueMachine的私有數(shù)據(jù)成員，不能直接訪問(wèn)，所以只能通過(guò)調(diào)用相關(guān)的get方法來(lái)獲取該對(duì)象。由此得出(2)應(yīng)填tissueMachine-getHasQuarterState()；同理，空(3)表示的狀態(tài)是從“有2元錢”狀態(tài)，經(jīng)歷“退回2元錢”事件之后的狀態(tài)，及“沒(méi)有投幣”狀態(tài)。所以空(3)處應(yīng)填tissueMachine-getNoQuanerState()?？?4)和(5)處分別表示賣出一包紙巾之后，售賣機(jī)應(yīng)該轉(zhuǎn)換到的下一個(gè)狀態(tài)。這個(gè)跟售賣機(jī)中的紙巾數(shù)有關(guān)，如果還有紙巾，則轉(zhuǎn)換到“沒(méi)有投幣”狀態(tài)，如果沒(méi)有紙巾了，則轉(zhuǎn)換到“紙巾售完”狀態(tài)，因此，空(4)處應(yīng)填tissueMachine-getNoQuarterState()，空(5)處應(yīng)填tissueMachine-getSoldOutState()。參考答案(1) State(2) tissueMachine-getHasQuarterState()(3) tissueMachine-getNoQuarterState()(4) tissueMachine-getNoQuarterState()(5) tissueMachine-getSoldoutState()試題六閱讀下列說(shuō)明和Java代碼，將應(yīng)填入(n)處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某大型商場(chǎng)內(nèi)安裝了多個(gè)簡(jiǎn)易的紙巾售賣機(jī)，自動(dòng)出售2元錢一包的紙巾，且每次僅售出一包紙巾。紙巾售賣機(jī)的狀態(tài)圖如圖6-1所示。圖6-1退回2元錢紙巾數(shù)0投入2元錢有2元錢沒(méi)有投幣售出紙巾紙巾售完按下取紙巾按鈕紙巾數(shù)0 紙巾售賣機(jī)的狀態(tài)圖采用狀態(tài)(State)模式來(lái)實(shí)現(xiàn)該紙巾售賣機(jī)，得到如圖6-2所示的類圖。其中類State為抽象類，定義了投幣、退幣、出紙巾等方法接口。類SoldState、SoldOutState、NoQuarterState和HasQuarterState分別對(duì)應(yīng)圖6-1中紙巾售賣機(jī)的4種狀態(tài)：售出紙巾、紙巾售完、沒(méi)有投幣、有2元錢。Java代碼import java.util.*;interface Statepublic void insertQuarter(); /投幣public void ejectQuarter(); /退幣public void turnCrank(); /按下“出紙巾”按鈕public void dispense(); /出紙巾class TissueMachine(1)soldOutState,noQuarterState,hasQuarterState,soldState,state;/ (1) Statestate=soldOutState;int count=0; /紙巾數(shù)public TissueMachine(int numbers) /*實(shí)現(xiàn)代碼省略*/)public State getHasQuarterState() return hasQuarterState;public State getNoQuarterState() return noQuarterState; public State getSoldState() return soldState; public State getSoldOutState() return soldOutState; public int getCount() retum count; /其余代碼省略class NoQuarterState implements StateTissueMachine tissueMachine;public void insertQuarter()tissueMachine.setState( (2) );/(2) tissueMachine. getHasQuarterState()/構(gòu)造方法以及其余代碼省略class HasQuarterState implements StateTissueMachine tissueMachine;public void ejectQuarter()tissueMachine.setState( (3) ); /(3)tissueMachine.getNoQuarterState()/構(gòu)造方法以及其余代碼省略class SoldState implements StateTissueMachine tissueMachine;public void dispense()if(tissueMachine.getCount()0)tissueMachine.setState( (4) ); / (4)tissueMachine.getNoQuarterState()elsetissueMachine.setState( (5) );/ (5)tissueMachine.getSoldOutState()試題六分析本題考查狀態(tài)(State)模式的概念及應(yīng)用。狀態(tài)模式是一種對(duì)象的行為型模式，允許一個(gè)對(duì)象在其內(nèi)部狀態(tài)改變時(shí)改變它的行為，對(duì)象看起來(lái)似乎修改了它的類。狀態(tài)模式的類圖如下所示：狀態(tài)模式主要解決的是控制一個(gè)對(duì)象轉(zhuǎn)換的條件表達(dá)式過(guò)于復(fù)雜的情況。把狀態(tài)的判斷邏輯轉(zhuǎn)移到表示不同狀態(tài)的一系列類當(dāng)中，可以把復(fù)雜的判斷邏輯簡(jiǎn)化。狀態(tài)模式的好處是將與特定狀態(tài)相關(guān)的行為局部化，并且將不同狀態(tài)的行為分割開來(lái)。題目利用狀態(tài)模式來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)易的紙巾售賣機(jī)。售賣機(jī)的狀態(tài)轉(zhuǎn)換圖已經(jīng)在題目中給出，類SoldState、SoldOutState、NoQuarterState和HasQuarterState分別用來(lái)表示售賣機(jī)的4種不同狀態(tài)，對(duì)應(yīng)于狀態(tài)模式中的ConcreteStatel，.ConcreteStateN。題目所設(shè)置的填空，主要集中在狀態(tài)轉(zhuǎn)換上。因此解答該題時(shí)，要求在理解狀態(tài)模式內(nèi)涵的基礎(chǔ)上，依據(jù)紙巾售賣機(jī)的狀態(tài)轉(zhuǎn)換原則，給出正確的狀態(tài)設(shè)置?？?1)出現(xiàn)在類Tissu