中級(jí)軟件設(shè)計(jì)師2007下半年下午試題

中級(jí)軟件設(shè)計(jì)師2007下半年下午試題試題一閱讀以下說(shuō)明和圖，回答問(wèn)題1至問(wèn)題4，將解答填入對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

某高校欲開(kāi)發(fā)一個(gè)成績(jī)管理系統(tǒng)，記錄并管理所有選修課程的學(xué)生的平時(shí)成績(jī)和考試成績(jī)，其主要功能描述如下；

1．每門(mén)課程都有3到6個(gè)單元構(gòu)成，每個(gè)單元結(jié)束后會(huì)進(jìn)行一次測(cè)試，其成績(jī)作為這門(mén)課程的千時(shí)成績(jī)。課程結(jié)束后進(jìn)行期末考試，其成績(jī)作為這門(mén)課程的考試成績(jī)。

2．學(xué)生的平時(shí)成績(jī)和考試成績(jī)均由每門(mén)課程的主講教師上傳給成績(jī)管理系統(tǒng)。

3．在記錄學(xué)生成績(jī)之前，系統(tǒng)需要驗(yàn)證這些成績(jī)是否有效。首先，根據(jù)學(xué)生信息文件來(lái)確認(rèn)該學(xué)生是否選修這門(mén)課程，若沒(méi)有，那么這些成績(jī)是無(wú)效的：如果他的確選修了這門(mén)課程，再根據(jù)課程信息文件和課程單元信息文件來(lái)驗(yàn)證平時(shí)成績(jī)是否與這門(mén)課程所包含的單元相對(duì)應(yīng)，如果是，那么這些成績(jī)足有效的，否則無(wú)效。

4．對(duì)于有效成績(jī)，系統(tǒng)將其保存在課程成績(jī)文件中。對(duì)于無(wú)效成績(jī)，系統(tǒng)會(huì)單獨(dú)將其保存在無(wú)效成績(jī)文件中，并將詳細(xì)情況提交給教務(wù)處。在教務(wù)處沒(méi)有給出具體處理意見(jiàn)之前，系統(tǒng)不會(huì)處理這些成績(jī)。

5．若一門(mén)課程的所有有效的平時(shí)成績(jī)和考試成績(jī)都已經(jīng)被系統(tǒng)記錄，系統(tǒng)會(huì)發(fā)送課程完成通知給教務(wù)處，告知該門(mén)課程的成績(jī)已經(jīng)齊全。教務(wù)處根據(jù)需要，請(qǐng)求系統(tǒng)生成相應(yīng)的成績(jī)列表，用來(lái)提交考試委員會(huì)審查。

6．在生成成績(jī)列表之前，系統(tǒng)會(huì)生成一份成績(jī)報(bào)告給主講教師，以便核對(duì)是否存在錯(cuò)誤。主講教師須將核對(duì)之后的成績(jī)報(bào)告返還系統(tǒng)。

7．根據(jù)主講教師核對(duì)后的成績(jī)報(bào)告，系統(tǒng)生成相應(yīng)的成績(jī)列表，遞交考試委員會(huì)進(jìn)行審查?？荚囄瘑T會(huì)在審查之后，上交一份成績(jī)審查結(jié)果給系統(tǒng)。對(duì)于所有通過(guò)審查的成績(jī)，系統(tǒng)將會(huì)生成最終的成績(jī)單，并通知每個(gè)選課學(xué)生。

現(xiàn)采用結(jié)構(gòu)化方法對(duì)這個(gè)系統(tǒng)進(jìn)行分析與設(shè)計(jì)，得到如圖1-1所示的頂層數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。1.【問(wèn)題1】

使用說(shuō)明中的詞語(yǔ)，給山圖l-1中的外部實(shí)體E1～E4的名稱(chēng)。這道題您沒(méi)有回答答案:E1：考試委員會(huì)；E2：主講教師；E3：學(xué)生或選課學(xué)生：E4：教務(wù)處11.【問(wèn)題2】

使用說(shuō)明中的詞語(yǔ)，給出圖1-2中的數(shù)據(jù)存儲(chǔ)D1～D5的名稱(chēng)。

這道題您沒(méi)有回答答案:D1：學(xué)生信息文件；D2：課程單元信息文件：D3：課程信息文件；D4：課程成績(jī)文件；

D5：無(wú)效成績(jī)文件。

注：D2和D3的答案可以互換。12.【問(wèn)題3】

數(shù)據(jù)流圖1-2缺少了三條數(shù)據(jù)流，根據(jù)說(shuō)明及數(shù)據(jù)流圖1-1提供的信息，分別指出這三條數(shù)據(jù)流的起點(diǎn)和終點(diǎn)。起點(diǎn)終點(diǎn)這道題您沒(méi)有回答

【邏輯結(jié)構(gòu)設(shè)計(jì)】

客戶(hù)((5)，折扣率，聯(lián)系人，聯(lián)系電話(huà))

車(chē)輛(車(chē)牌號(hào)，客戶(hù)編號(hào)，車(chē)型，顏色，車(chē)輛類(lèi)別)

委托書(shū)((6)，維修類(lèi)型，作業(yè)分類(lèi)，結(jié)算方式，進(jìn)廠時(shí)間，

預(yù)計(jì)完工時(shí)間，登記日期，故障描述，總費(fèi)用)

維修項(xiàng)目(維修項(xiàng)目編號(hào)，維修項(xiàng)目，單價(jià))

派工單((7)，工時(shí))

員工((8)，工種，員工類(lèi)型，級(jí)別)2.【問(wèn)題1】

根據(jù)問(wèn)題描述，填寫(xiě)圖2-1中(1)～(4)處聯(lián)系的類(lèi)型。聯(lián)系類(lèi)型分為一對(duì)一、一對(duì)多和多對(duì)多三種，分別使用1:1，1:n或1:*，m:n或*:*表示。這道題您沒(méi)有回答答案:*(或n或m)(2)1

(3)*(或n或m)(4)*(或n或m)10.【問(wèn)題2】

補(bǔ)充圖2-1中的聯(lián)系并指明其聯(lián)系類(lèi)型。聯(lián)系名可為：聯(lián)系1，聯(lián)系2，…這道題您沒(méi)有回答答案:13.【問(wèn)題3】

根據(jù)圖2-1和說(shuō)明，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空(5)～(8)補(bǔ)充完整。這道題您沒(méi)有回答答案:客戶(hù)編號(hào)，客戶(hù)名稱(chēng)，客戶(hù)性質(zhì)

(6)委托書(shū)編號(hào)，客戶(hù)編號(hào)，車(chē)牌號(hào)，業(yè)務(wù)員編號(hào)

或：委托書(shū)編號(hào)，車(chē)牌號(hào)，業(yè)務(wù)員編號(hào)

(7)委托書(shū)編號(hào)，維修工編號(hào)，維修項(xiàng)目編號(hào)

(8)員工編號(hào)，員工姓名17.【問(wèn)題4】

根據(jù)問(wèn)題描述，寫(xiě)出客戶(hù)、委托書(shū)和派工單這三個(gè)關(guān)系的主鍵。這道題您沒(méi)有回答答案:客戶(hù)：客戶(hù)編號(hào)

委托：委委托書(shū)編號(hào)

派工單：委托書(shū)編號(hào)，維修項(xiàng)目編號(hào)，維修工編號(hào)[分析]

本題考查數(shù)據(jù)庫(kù)設(shè)計(jì)，屬于比較傳統(tǒng)的題目，考查點(diǎn)也與往年類(lèi)似。

問(wèn)題1、問(wèn)題2考查的是數(shù)據(jù)庫(kù)的概念結(jié)構(gòu)設(shè)計(jì)，題目要求補(bǔ)充完整實(shí)體聯(lián)系圖中的聯(lián)系和聯(lián)系的類(lèi)型。

根據(jù)題目的需求描述和表2-1中的數(shù)據(jù)可知，一個(gè)客戶(hù)至少擁有一臺(tái)車(chē)，每臺(tái)車(chē)輛有一個(gè)對(duì)應(yīng)的客戶(hù)。所以，客戶(hù)實(shí)體和車(chē)輛實(shí)體之間存在“擁有”聯(lián)系，聯(lián)系的類(lèi)型為一對(duì)多(1:*)。

根據(jù)題目的需求描述和表2-2中的數(shù)據(jù)可知，一份委托書(shū)由一個(gè)業(yè)務(wù)員負(fù)責(zé)接受委托，一個(gè)業(yè)務(wù)員可以負(fù)責(zé)多份委托書(shū)。所以，業(yè)務(wù)員實(shí)體和委托書(shū)實(shí)體之間存在“委托”聯(lián)系，聯(lián)系的類(lèi)型為一對(duì)多(1:*)。

根據(jù)題目的需求描述和表2-3中的數(shù)據(jù)可知，一份委托書(shū)可以對(duì)應(yīng)多個(gè)維修項(xiàng)目和維修員工，一個(gè)維修項(xiàng)目可能涉及多個(gè)維修工，一個(gè)維修工可以參與多個(gè)維修項(xiàng)目。因此，維修派工單的信息涉及三個(gè)實(shí)體，是由三個(gè)實(shí)體相互聯(lián)系而形成的。所以，委托書(shū)實(shí)體和維修工實(shí)體之間存在“派工”聯(lián)系，聯(lián)系的類(lèi)型為一對(duì)多(1:*)，維修項(xiàng)目實(shí)體和維修工實(shí)體之間存在聯(lián)系“派工”，聯(lián)系的類(lèi)型為多對(duì)多(*:*)。

問(wèn)題3考查的是數(shù)據(jù)庫(kù)的邏輯結(jié)構(gòu)設(shè)計(jì)，題目要求補(bǔ)充完整各關(guān)系模式，并給出各關(guān)系模式的主鍵。

根據(jù)實(shí)體聯(lián)系圖和表2-1中的數(shù)據(jù)，對(duì)于“客戶(hù)”關(guān)系模式需補(bǔ)充屬性：客戶(hù)編號(hào)，客戶(hù)名稱(chēng)和客戶(hù)性質(zhì)。

根據(jù)實(shí)體聯(lián)系圖和表2-1中的數(shù)據(jù)，對(duì)于“車(chē)輛”關(guān)系模式，由于車(chē)輛實(shí)體與客戶(hù)實(shí)體有聯(lián)系，需記錄對(duì)應(yīng)的客戶(hù)信息，并且車(chē)輛有自己的屬性——車(chē)牌號(hào)，因此，“車(chē)輛”關(guān)系模式需補(bǔ)充屬性：車(chē)牌號(hào)，客戶(hù)編號(hào)。

根據(jù)實(shí)體聯(lián)系圖和表2-2中的數(shù)據(jù)，對(duì)于“委托書(shū)”關(guān)系模式，由于車(chē)輛實(shí)體與委托書(shū)實(shí)體和業(yè)務(wù)員實(shí)體都有聯(lián)系，需記錄對(duì)應(yīng)的車(chē)輛和業(yè)務(wù)員信息，并且委托書(shū)有自己的屬性——委托書(shū)編號(hào)，因此，“委托書(shū)”關(guān)系模式需補(bǔ)充屬性；委托書(shū)編號(hào)，車(chē)牌號(hào)和業(yè)務(wù)員編號(hào)。

根據(jù)實(shí)體聯(lián)系圖和表2-3中的數(shù)據(jù)，“派工單”關(guān)系模式記錄的是委托書(shū)、維修項(xiàng)目和維修工三個(gè)實(shí)體之間的聯(lián)系，因此，“派工單”關(guān)系模式需補(bǔ)充屬性：委托書(shū)編號(hào)，維修項(xiàng)目編號(hào)和維修員編號(hào)。

根據(jù)實(shí)體聯(lián)系圖和表2-1中的數(shù)據(jù)，對(duì)于“員工”關(guān)系模式需補(bǔ)充屬性：?jiǎn)T工編號(hào)，員工姓名。

問(wèn)題4指定給定關(guān)系模式的主鍵，顯然，管理客戶(hù)數(shù)據(jù)時(shí)，應(yīng)為每位客戶(hù)設(shè)置唯一的編碼，因此客戶(hù)關(guān)系模式的主鍵為“客戶(hù)編號(hào)”。類(lèi)似的，委托書(shū)關(guān)系模式的主鍵為“委托書(shū)編號(hào)”。根據(jù)E-R圖中派工聯(lián)系與相關(guān)實(shí)體的關(guān)系，派工單關(guān)系模式的主鍵為“委托書(shū)編號(hào)，維修項(xiàng)目編號(hào)和維修員編號(hào)”。試題三閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題4，將解答填入對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

已知某唱片播放器不僅可以播放唱片，而且可以連接電腦并把電腦中的歌曲刻錄到唱片上(同步歌曲)。連接電腦的過(guò)程中還可自動(dòng)完成充電。

關(guān)于唱片，還有以下描述信息：

1．每首歌曲的描述信息包括：歌曲的名字、譜寫(xiě)這首歌曲的藝術(shù)家以及演奏這首歌曲的藝術(shù)家。只有兩首歌曲的這三部分信息完全相同時(shí)，才認(rèn)為它們是同一首歌曲。藝術(shù)家可能是一名歌手或一支由2名或2名以上的歌手所組成的樂(lè)隊(duì)。一名歌手可以不屬于任何樂(lè)隊(duì)，也可以屬于一個(gè)或多個(gè)樂(lè)隊(duì)。

2．每張唱片由多條音軌構(gòu)成；一條音軌中只包含一首歌曲或?yàn)榭?，一首歌曲可分布在多條音軌上；同一首歌曲在一張唱片中最多只能出現(xiàn)一次。

3．每條音軌都有一個(gè)開(kāi)始位置和持續(xù)時(shí)間。一張唱片上音軌的次序是非常重要的，因此對(duì)于任意一條音軌，播放器需要準(zhǔn)確地知道，它的下一條音軌和上——條音軌是什么(如果存在的話(huà))。

根據(jù)上述描述，采用面向?qū)ο蠓椒▽?duì)其進(jìn)行分析與設(shè)計(jì)，得到了如表3-1所示的類(lèi)列表、如圖3-1所示的初始類(lèi)圖以及如圖3-2所示的描述播放器行為的UML狀態(tài)圖。

表3-1類(lèi)列表類(lèi)名說(shuō)明Artist藝術(shù)家Song歌曲Band樂(lè)隊(duì)Musician歌手Track音軌Album唱片3.【問(wèn)題1】

根據(jù)說(shuō)明中的描述，使用表3-1給出的類(lèi)的名稱(chēng)，給出圖3-1中的A～F所對(duì)應(yīng)的類(lèi)。這道題您沒(méi)有回答答案:A：ArtistB：SongC：BandD：MusicianE：TrackF：Album9.【問(wèn)題2】

根據(jù)說(shuō)明中的描述，給山圖3-1中(1)～(6)處的多重度。這道題您沒(méi)有回答答案:0..*(2)2..*：(3)0..1(4)1..*(5)1..*(6)114.【問(wèn)題3】

圖3-1中缺少了一條關(guān)聯(lián)，請(qǐng)指出這條關(guān)聯(lián)兩端所對(duì)應(yīng)的類(lèi)以及每一端的多重度。類(lèi)多重度這道題您沒(méi)有回答答案:類(lèi)多重度Track或E(1分)0..11分)Track或E(1分)0..1(1分)16.【問(wèn)題4】

根據(jù)圖3-2所示的播放器行為UML狀態(tài)圖，給出從“關(guān)閉”狀態(tài)到“播放”狀態(tài)所經(jīng)過(guò)的最短事件序列(假設(shè)電池一開(kāi)始就是有電的)。這道題您沒(méi)有回答答案:按任意鍵，選擇歌曲[分析]

本題考查的是面向?qū)ο蟮姆治雠c設(shè)計(jì)。前三個(gè)問(wèn)題的考點(diǎn)比較傳統(tǒng)，考查的是類(lèi)圖的設(shè)計(jì)要素。今年增加了一個(gè)關(guān)于狀態(tài)圖的考點(diǎn)：如何理解給定的狀態(tài)圖。

問(wèn)題1屬于傳統(tǒng)的考法，要求考生根據(jù)說(shuō)明將類(lèi)圖填充完整。實(shí)際上就是把表3-1中的類(lèi)和圖中的A-E對(duì)號(hào)入座。針對(duì)這道題目的類(lèi)圖而言，完成這個(gè)問(wèn)題是比較簡(jiǎn)單的，因?yàn)轭?lèi)圖中出現(xiàn)了三個(gè)典型的類(lèi)/對(duì)象關(guān)系結(jié)構(gòu)：繼承(類(lèi)A、C、D)、聚集(類(lèi)B、e)和組裝(類(lèi)E、F)。從說(shuō)明可以明顯地看出，可能具有繼承關(guān)系的只能是Artist、Band和Musician。這樣類(lèi)A、C、D就確定了，下面來(lái)看B。B和A之間兩條關(guān)聯(lián)的名字，已經(jīng)很明確地告訴了我們，能夠被Artist編寫(xiě)、演奏的只能是歌曲(Song)。這樣B也確定下來(lái)了，剩下的E和F就顯而易見(jiàn)了。音軌(Track)中包含的是歌曲，而唱片是由音軌構(gòu)成的。所以E應(yīng)該是Track，F(xiàn)應(yīng)該是Album。

第二步是要確定關(guān)鍵類(lèi)之間的多重度。這在說(shuō)明中已經(jīng)有了明確的描述。(1)和(2)處的多重度描述的是類(lèi)Band和Musician的實(shí)例之間的關(guān)系。由“藝術(shù)家可能是——名歌手或一支由2名或2名以上的歌手所組成的樂(lè)隊(duì)”可知，組成樂(lè)隊(duì)的最少人數(shù)應(yīng)該是2，所以(2)應(yīng)該是2..*。由“一名歌手可以不屬于任何樂(lè)隊(duì)，也可以屬于一個(gè)或多個(gè)樂(lè)隊(duì)”可知，(1)應(yīng)該是0..*。

(3)～(4)處的多重度描述的是類(lèi)Song和Track的實(shí)例之間的關(guān)系。由“一條音軌中只包含一首歌曲或?yàn)榭铡笨芍?3)應(yīng)該為0..1。由“一首歌曲可分布在多條音軌上”可知，(4)應(yīng)該為1..*。同理可以得到，(5)應(yīng)該是1..*(一張唱片上有多條音軌)；(6)應(yīng)該為1。

問(wèn)題3考查的是類(lèi)對(duì)象關(guān)聯(lián)中的一種特殊關(guān)聯(lián)：遞歸關(guān)聯(lián)，它描述的是同一個(gè)類(lèi)的不同實(shí)例之間的關(guān)系。而類(lèi)Track的不同實(shí)例之間恰好具有這種關(guān)系(因此對(duì)于任意一條音軌，播放器需要準(zhǔn)確地知道，它的下一條音軌和上一條音軌是什么)。所以缺少的那條聯(lián)系的兩端都是類(lèi)Track，其多重度都為0..1。下限為0，是對(duì)應(yīng)不存在上一條或下一條音軌的情況。

狀態(tài)圖是描述系統(tǒng)動(dòng)態(tài)行為的一種模型。這里狀態(tài)圖的考查僅限于能夠理解它所描述的行為。狀態(tài)圖由狀態(tài)及狀態(tài)之間的遷移構(gòu)成，遷移可以由相關(guān)的事件觸發(fā)。問(wèn)題4給定了兩個(gè)狀態(tài)“關(guān)閉”和“播放”，要求找出從“關(guān)閉”到“播放”的最短事件序列。這就要求我們能夠在狀態(tài)圖上找到連接這兩個(gè)狀態(tài)的最短遷移，然后將遷移上的事件記錄下來(lái)就可以了。

從“關(guān)閉”狀態(tài)到“播放”狀態(tài)可以選擇經(jīng)過(guò)遷移“連接電腦”、到達(dá)“聯(lián)機(jī)”狀態(tài)，再經(jīng)過(guò)遷移“斷開(kāi)連接”到達(dá)狀態(tài)“打開(kāi)”，再?gòu)摹按蜷_(kāi)”狀態(tài)的初始狀態(tài)“歌曲待選”，經(jīng)過(guò)遷移“選擇歌曲”到達(dá)“播放狀態(tài)”。這樣經(jīng)過(guò)的事件序列為；連接電腦——電量飽和/完成復(fù)制——斷開(kāi)連接——選擇歌曲。顯然這樣的事件序列遠(yuǎn)比從“關(guān)閉”經(jīng)過(guò)“按任意鍵”直接到達(dá)“打開(kāi)”狀態(tài)要長(zhǎng)得多。所以從“關(guān)閉”到“播放”的最短事件序列是：按任意鍵，選擇歌曲。試題四閱讀下列說(shuō)明和圖，回答問(wèn)題1至問(wèn)題3，將解答填入對(duì)應(yīng)欄內(nèi)。

【說(shuō)明】

某機(jī)器上需要處理n個(gè)作業(yè)．job1，job2，…，jobn，其中：

(1)每個(gè)作jobi(1≤i≤n)的編號(hào)為i，jobi有一個(gè)收益值p[i]和最后期限值d[i]小

(2)機(jī)器在一個(gè)時(shí)刻只能處理一個(gè)作業(yè)，而且每個(gè)作業(yè)需要一個(gè)單位時(shí)間進(jìn)行處理，一旦作業(yè)開(kāi)始就不可中斷，每個(gè)作業(yè)的最后期限值為單位時(shí)間的正整數(shù)倍；

(3)job1～jobn的收益值呈非遞增順序排列，即p[1)≥P[2]≥…[n)：

(4)如果作業(yè)jobi在其期限之內(nèi)完成，則獲得收益9[i]；如果在其期限之后完成，則沒(méi)有收益。

為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖4*1是基于貪心策略求解該問(wèn)題的流程圖。

(1)整型數(shù)組J[]有n個(gè)存儲(chǔ)單元，變量k眾表示在期限之內(nèi)完成的作業(yè)J[1..k]存儲(chǔ)所有能夠在期限內(nèi)完成的作業(yè)編號(hào)，數(shù)組J[1..k]里的作業(yè)按其最后期限非遞減排序，即d[J[1]]≤…≤d[J[k]]。

(2)為了便于在數(shù)組J中加入作業(yè)，增加一個(gè)虛擬作業(yè)Job0，并令d[0]=0，j[0]=0。

(3)算法大致思想：先將作業(yè)．job1的編號(hào)1放入J[1]，然后，依次對(duì)每個(gè)作業(yè)．jobi(2≤i≤n)進(jìn)行判定，看其能否插入到數(shù)組J中。若能，則將其編號(hào)插入到數(shù)組J的適當(dāng)位置，并保證J中作業(yè)按其最后期限非遞減排列；否則不插入。

jobi能插入數(shù)組J的充要條件是：jobi和數(shù)組J中已有作業(yè)均能在其期限之內(nèi)完成。

(4)流程圖中的主要變量院明如下。

i：循環(huán)控制變量，表示作業(yè)的編號(hào)；

k：表示在期限內(nèi)完成的作業(yè)數(shù)：

r：若．jobi能插入數(shù)組J，則其在數(shù)組了中的位置為r+1：

q：循環(huán)控制變量，用于移動(dòng)數(shù)組J中的元素。4.【問(wèn)題1】

請(qǐng)?zhí)畛鋱D4-1中的空缺(1)、(2)和(3)處。這道題您沒(méi)有回答答案:i<=n

(2)d[J[r]]>d[i]

(3)J[r+1]=i，或J[q+1]=i8.【問(wèn)題2】

假設(shè)有6個(gè)作業(yè)job1，job2，…，job6；

完成作業(yè)的收益數(shù)組p=(p[1]，p[2]，p[3]，p[4]，p[5]，p[6])=(90,80,50,30,20,10)：

每個(gè)作業(yè)的處理期限數(shù)組d=(d[1]，d[2]，d[3]，d[4]，d[5]，d[6])=(1,2,1,3,4,3)。

請(qǐng)應(yīng)用試題中描述的貪心策略算法，給出在期限之內(nèi)處理的作業(yè)編號(hào)序列(4)(按作業(yè)處理的順序給出)，得到的總收益為(5)。這道題您沒(méi)有回答答案:1,2,4,5或job1、job2、job4、job5及其等價(jià)描述形式

(5)22015.【問(wèn)題3】

對(duì)于本題的作業(yè)處理問(wèn)題，用圖4-1的貪心算法策略，能否求得最高收益?(6)。用貪心算法求解任意給定問(wèn)題時(shí)，是否一定能得到最優(yōu)解?(7)。

這道題您沒(méi)有回答答案:能，或可以、行及其他含義相同的詞語(yǔ)

(7)不能，或不可以、不行及其他含義相同的詞語(yǔ)[分析]

本題考查的是算法的設(shè)計(jì)和分析技術(shù)。

問(wèn)題1考查的是貪心算法的流程圖。第(1)空表示第2個(gè)作業(yè)到第n個(gè)作業(yè)的主循環(huán)，i是循環(huán)控制變量，故第(1)空填入i<=n。

應(yīng)注意到數(shù)組／中的作業(yè)J[i](1≤i≤k)是在其期限之前完成的作業(yè)，且d[J[i]]≤d[J[i+1]](1≤id[i]。另一方面，J[D[R]]與r的關(guān)系只有兩種：J[d[r]]>r，表示還可能在J[1]與J[r]之間插入作業(yè)i；J[d[r]]=r，表示不可能在J[1]～J[r]之間插入作業(yè)i。J[d[r]]

問(wèn)題2是本題算法的一個(gè)實(shí)例。6個(gè)作業(yè)的收益已經(jīng)按降序排好序。根據(jù)流程圖，將作業(yè)1，2，4和5放入數(shù)組J中，并得到總收益為220，具體過(guò)程如表4-1所示。

表4-1算法執(zhí)行過(guò)程J數(shù)組收益考慮的作業(yè)期限操作Ф0job11放入J中190job22放入J中1,2170job31不放入J中1,2170job43放入J中1,2,4200job54放入J中1,2,4,5220job63不放入J中1,2,4,5220

問(wèn)題3考查算法策略。對(duì)于該題，貪心策略可以求得最優(yōu)解。但不是所有的問(wèn)題都能通過(guò)貪心策略來(lái)求得最優(yōu)解，一個(gè)典型的例子是0-1背包問(wèn)題。舉例如下，有三件物品，背包可容納50磅重的東西，每件物品的詳細(xì)信息如表4-2所示，問(wèn)如何裝包使得其價(jià)值最大?表4-2物品信息物品編號(hào)重量?jī)r(jià)值單位價(jià)值11060622010053301204

如果按貪心策略求解該問(wèn)題，優(yōu)先選擇單位價(jià)值最大的物品，則先選擇物品1，然后選擇物品2。由于此時(shí)背包容量還剩下50-10-20=20，不足以容納物品3，故總價(jià)值為60+100=160美元。但若選擇物品2和物品3，容量總和為20+30，小于等于總?cè)萘?0，得到總價(jià)值為100+120=220，會(huì)得到更優(yōu)解。此時(shí)用貪心策略不能得到最優(yōu)解。試題五閱讀以下說(shuō)明和C代碼，將應(yīng)填入(n)處的字句寫(xiě)在的對(duì)應(yīng)欄內(nèi)。5.【說(shuō)明】

在一個(gè)簡(jiǎn)化的繪圖程序中，支持的圖形種類(lèi)有點(diǎn)(point)和圓(circle)，在設(shè)計(jì)過(guò)程中采用面向?qū)ο笏枷耄J(rèn)為所有的點(diǎn)和圓都是一種圖形(shape)，并定義了類(lèi)型shapet、pointt和circlet分別表示基本圖形、點(diǎn)和圓，并且點(diǎn)和圓具有基本圖形的所有特征。

【C代碼】

typedefenum{point,circle}shapetype;/*程序中的兩種圖形：點(diǎn)和圓*/

typedefstruct{/*基本的圖形類(lèi)型*/

shape_typetype;/*圖形中類(lèi)標(biāo)識(shí)：點(diǎn)或者圓*/

void(*destroy)();/*銷(xiāo)毀圖形操作的函數(shù)指針*/

void(*draw)();/*繪制圖形操作的函數(shù)指針*/

}shape_t;

typedefstruct{shape_tcommon;intx;ihty;}point_t;/*定義點(diǎn)類(lèi)

型,x,y為點(diǎn)坐標(biāo)*/

voiddestroyPoint(point_t*this){free(this);printf("Pointdestoryed!

\n");})/*銷(xiāo)毀點(diǎn)對(duì)象*/

voiddrawPoint(point_t*this){printf("P(%d,%d)",this->x,this->y);}

/*繪制點(diǎn)對(duì)象*/

shape_t*createPoint(va_list*ap)(/*創(chuàng)建點(diǎn)對(duì)象，并設(shè)置其屬性*/

point_t*p_point;

if((p_point=(point_t*)malloc(sizeof(point_t)))==NULL)returnNULL;

p_point-＞common,type=point;p_point->common,destroy=destroyPoint;

p_point-＞common.draw=drawPoint;

p_point-＞x=va_arg(*ap,int);/*設(shè)置點(diǎn)的橫坐標(biāo)*/

p_point-＞y=va_arg(*ap,int);/*設(shè)置點(diǎn)的縱坐標(biāo)*/

return(shape_t*)p_ooint;/*返回點(diǎn)對(duì)象指針*/

}

typedefstruct{/*定義圓類(lèi)型*/

shape_tcommon;

point_t4center;/*圓心點(diǎn)*/

intradius;/*圓半徑*/

}circle_t;

voiddestroyCircle(circle_t*this){

free((1));free(this);printf("Circledestoryed!\n");

}

voiddrawCircle(circle_t*this){

printf("C(");

(2).draw(this-＞center);/*繪制圓心*/

printf(",%d)",this-＞radius);

}

shape_t*createCircle(va_list4ap){/*創(chuàng)建一個(gè)圓，并設(shè)置其屬性*/

circle_t4pcircle;

if((p_circle=(circle_t4)malloc(sizeof(circle_t)))==NULL)returnNULL;

p_circle-＞common.type=circle;p_circle-＞common.destroy=destroy

Circle;

p_circle-＞common.draw=drawCircle;

(3)=createPoint(ap);/*設(shè)置圓心*/

p_circle-＞radius=va_arg(*ap,int);/*設(shè)置圓半徑*/

returnp_circle;

}

shape_t*createShape(shape_typest,"'){/*創(chuàng)建某一種具體的圖形*/

va_listap;/*可變參數(shù)列表*/

shape_t4p_shape=NULL;

(4)(ap,st);

if(st==point)pshape=createPoint(&ap);/*創(chuàng)建點(diǎn)對(duì)象*/

if(st==circle)pshape=createCircle(&ap);/*創(chuàng)建圓對(duì)象*/

va_end(ap);

returnp_shape;

}

intmain(){

inti;/*循環(huán)控制變量，用于循環(huán)計(jì)數(shù)*/

shape_t*shapes[2];/*圖形指針數(shù)組，存儲(chǔ)圖形的地址*/

shapes[0]=createShape(point,2,3);/*橫坐標(biāo)為2，比值坐標(biāo)為3*/

shapes[ii=createShape(circle,20,40,10);/*圓心坐標(biāo)(20,40),

半徑為10*/

for(i=0i＜2;i++){shapes[i]-＞draw(shapes[i]);printf("\n");}/*

縱制數(shù)組中圖形*/

for(i=1;i＞=0;i--)shapes[i]-＞destroy(shapes[i]);/*銷(xiāo)毀

數(shù)組中圖形*/

return0;

}

【運(yùn)行結(jié)果】

P(2,3)

(5)

Circledestoryed!

Pointdestoryed!這道題您沒(méi)有回答答案:this-＞center(2)this-＞center-＞common

(3)p_circle-＞center(4)vastart

(5)C(P(20,40)，10)本題考查C語(yǔ)言中指針機(jī)制、可變數(shù)目參數(shù)機(jī)制及結(jié)構(gòu)體存儲(chǔ)映像。本題中涉及的三個(gè)數(shù)據(jù)結(jié)構(gòu)shape_t、circle_t和point_t的關(guān)系如下圖所示。

通過(guò)閱讀給出的程序代碼可以看出，point_t和circle_t兩種結(jié)構(gòu)通過(guò)其成員shape_tcommon表示了上圖中的繼承關(guān)系：circlet中的數(shù)據(jù)成員point_t*center表示了與pornt_t之間的引用關(guān)系。

函數(shù)destroyCircle(circle_t*this)完成一個(gè)circlet對(duì)象的內(nèi)存釋放工作。在結(jié)構(gòu)circlet定義中，由于數(shù)據(jù)成員center是一個(gè)指針，所以必須釋放對(duì)應(yīng)內(nèi)存，即free(this-＞center)。

函數(shù)drawCircle(circlet*this)完成圓形的顯示工作。其中需要顯示其圓心的信息，而此信息由circle_mon.draw()函數(shù)完成，即this-＞center-＞common.draw(this.center)。point_t類(lèi)型的顯示工作由函數(shù)drawPoint完成，其在屏幕上顯示的信息格式為P(x,y)，其中x表示點(diǎn)的橫坐標(biāo)，y表示點(diǎn)的縱坐標(biāo)。圓形的顯示函數(shù)drawCirele在屏幕卜顯示的信息格式為C(P(x,y)，r)，其中x表示圓心的橫坐標(biāo)，y表示圓心的縱坐標(biāo)，r表示半徑。

函數(shù)ereateCircle(va_list*叩)完成創(chuàng)建一個(gè)圓形工作，其中需要?jiǎng)?chuàng)建其圓心對(duì)象，a圓心對(duì)象的地址保存在circlet.center數(shù)據(jù)成員中。該函數(shù)的參數(shù)采用了C語(yǔ)言提供的標(biāo)準(zhǔn)類(lèi)型valist，以處理可變數(shù)目的函數(shù)實(shí)參。對(duì)于可變數(shù)目的參數(shù)列表的一般處理方式如下：

#include＜stdarg．h＞

voidfoo(char*fmt，…)/*表示fmt后面的參數(shù)個(gè)數(shù)可變*/

{

valistap；/*保存可變數(shù)目的參數(shù)列表*/

vastart(ap，fmt)；/*初始化ap，保存參數(shù)fmt后面的實(shí)參列表*/

//…

vaarg(ap，TYPE)；/*獲取下一個(gè)實(shí)參，其中TYPE指明該參數(shù)的類(lèi)型*/

//…

vaend(ap)；/*釋放ap占用的資源*/

}試題六閱讀下列說(shuō)明和C++代碼，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。6.【說(shuō)明】

已知某企業(yè)的采購(gòu)審批是分級(jí)進(jìn)行的，即根據(jù)采購(gòu)金額的不同由不同層次的主管人員來(lái)審批，主任可以審批5萬(wàn)元以下(不包括5萬(wàn)元)的采購(gòu)單，副董事長(zhǎng)可以審批5萬(wàn)元至10萬(wàn)元(不包括10萬(wàn)元)的采購(gòu)單，董事長(zhǎng)可以審批10萬(wàn)元至50萬(wàn)元(不包括50萬(wàn)元)的采購(gòu)單，50萬(wàn)元及以上的采購(gòu)單就需要開(kāi)會(huì)討論決定。

采用責(zé)任鏈設(shè)計(jì)模式(ChainofResponsibility)對(duì)上述過(guò)程進(jìn)行設(shè)計(jì)后得到的類(lèi)圖如圖6-1所示。

【C++代碼】

#include＜string＞

#include＜iostream＞

usingnamespacestd;

classPurchaseRequest{

public:

doubleAmount;/*一個(gè)采購(gòu)的金額*/

intNumber;/*采購(gòu)單編號(hào)*/

stringPurpose;/*采購(gòu)目的*/

};

classApprover{/*審批者類(lèi)*/

public:

Approver(){successor=NULL;}

virtualvoidProcessRequest(PurchaseRequestaRequest){

if(successor!=NULL){successor-＞(1);}

}

voidSetSuccessor(Approver*aSuccesssor){successor=aSuccesssor;}private:

(2)successor;};

classCongress:publicApprover{

public:

voidProcessRequest(PurchaseRequestaRequest){

if(aRequest.Amount＞=500000){/*決定是否審批的代碼少略*/}

else(3)ProcessRequest(aRequest);

}

classDirector:publicApprover{

public:

voidProcessRequest(PurchaseRequestaRequest){/*此處代碼省略*/

}

};

classPresident:publicApprover{

public:

voidProcessRequest(PurchaseRequestaRequest)/*此處代碼省略*/}

};

classVicePresident:publicApprover{

public:

voidProcessRequest(PurchaseRequestaRequest)/*此處代碼省略*/}

};

voidmain(){

CongressMeeting;VicePresidentSam;DirectorLarry;President

Tammy;

Meeting.SetSuccessor(NULL);Sam.SetSuccessor((4));

Tammy.SetSuccessor((5));Larry.SetSuccessor((6));

PurchaseRequestaRequest;/*構(gòu)造一采購(gòu)審批請(qǐng)求*/

cin＞＞aRequest.Amount;/*輸入采購(gòu)請(qǐng)求的金額*/

(7).ProcessRequest(aRequest);/*開(kāi)始審批*/

return;

}這道題您沒(méi)有回答答案:(1)ProcessRequest(aRequest)(2)Approver*(3)Approver::

(4)&Tammy(5)&Meeting(6)&Sam

(7)Larry[分析]

本題考查的是設(shè)計(jì)模式的應(yīng)用，屬于比較傳統(tǒng)的題目。責(zé)任鏈設(shè)計(jì)模式屬于常用的23種沒(méi)計(jì)模式之一，其目的是為了將一個(gè)請(qǐng)求發(fā)送給一個(gè)對(duì)象集合，對(duì)象被組織成一條鏈，而負(fù)責(zé)處理該請(qǐng)求的對(duì)象將獲取請(qǐng)求消息并加以處理，其余對(duì)象則僅僅負(fù)責(zé)將該請(qǐng)求消息按照責(zé)任鏈的順序傳遞到下一個(gè)對(duì)象。因此責(zé)任人鏈模式的關(guān)鍵在于組織不同的對(duì)象成為一條鏈并傳遞消息。

代碼中空(1)處位于條件判斷if(successor!=NULL)內(nèi)，因此其含義是判斷當(dāng)前對(duì)象是否存在后繼對(duì)象，如果存在，按照責(zé)任鏈設(shè)計(jì)模式，可以把請(qǐng)求消息進(jìn)行傳遞，也就是調(diào)用后繼對(duì)象的ProcessRequest方法。空(2)處要求填寫(xiě)successor的類(lèi)型，因?yàn)樨?zé)任鏈模式中的每一個(gè)對(duì)象都繼承自同一個(gè)父類(lèi)，在本題中，就是Approver類(lèi)型?？?3)處位于Congress類(lèi)中的ProcessRequest方法中，該方法表示處理外界的請(qǐng)求，else塊的含義表明Congress對(duì)象不處理審批金額大于50萬(wàn)元的請(qǐng)求，因此，Congress對(duì)象應(yīng)該將該請(qǐng)求轉(zhuǎn)發(fā)到下一個(gè)對(duì)象進(jìn)行處理，可以直接調(diào)用父類(lèi)的ProcessRequest方法?？?4)、(5)、(6)則主要用來(lái)將各種對(duì)象串接成一個(gè)鏈，根據(jù)題目的要求，對(duì)象在責(zé)任鏈中的順序應(yīng)該為DirectorLarry：VicePresidentSam；PresidentTammy：CongressMeeting，而審批的請(qǐng)求應(yīng)該從Larry開(kāi)始。試題七閱讀下列說(shuō)明和Java代碼，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。7.【說(shuō)明】

已知某企業(yè)的采購(gòu)審批是分級(jí)進(jìn)行的，即根據(jù)采購(gòu)金額的不同由不同層次的主管人員來(lái)審批，主任可以審批5萬(wàn)元以下(不包括5萬(wàn)元)的采購(gòu)單，副董事長(zhǎng)可以審批5萬(wàn)元至10萬(wàn)元(不包括10萬(wàn)元)的采購(gòu)單，董事長(zhǎng)可以審批10萬(wàn)元至50萬(wàn)元(不包括50萬(wàn)元)的采購(gòu)單，50萬(wàn)元及以上的采購(gòu)單就需要開(kāi)會(huì)討論決定。

采用責(zé)任鏈設(shè)計(jì)模式(ChainofResponsibility)對(duì)上述過(guò)程進(jìn)行設(shè)計(jì)后得到的類(lèi)圖如圖7-1所示。

【Java代碼】

classPurchaseRequest{

publicdoubleAmount;//一個(gè)采購(gòu)的金額

publicintNumber;//采購(gòu)單編號(hào)

publicStringPurpose;//采購(gòu)目的

};

classApprover{//審批者類(lèi)

publicApprover(){successor=null;}

publicvoidProcessRequest(PurchaseRequestaRequest){

if(successor!=null){successor.(1);}

}

publicvoidSetSuccesser(ApproveraSuccesssor){successor=aSuccesssor;}

private(2)successor;

};

classCongressextendsApprover{

publicvoidProcessRequest(PurchaseRequestaRequest){

if(aRequest,Amount＞=500000){//決定是否審批的代碼省略}

else(3).ProcessRequest(aRequest);

}

};

classDirectorextendsApprover{

publicvoidProcessRequest(PurchaseRequestaRequest){//此處代碼省略}

};

classPres