2013 年上半年軟件設(shè)計(jì)師下午試卷第 1 題某慈善機(jī)構(gòu)欲開發(fā)一個(gè)募捐系統(tǒng)，以跟蹤記錄為事業(yè)或項(xiàng)目向目標(biāo)群體進(jìn)行募捐而組織的集體性活動(dòng)，該系統(tǒng)的主要功能如下所述。（1）管理志愿者。根據(jù)募捐任務(wù)給志愿者發(fā)送加入邀請、邀請跟進(jìn)、工作任務(wù)；管理志愿者提供的邀請響應(yīng)、支援站信息、工作時(shí)長、工作結(jié)果等。（2）確定募捐需求和收集所募捐贈(zèng)（資金及物品） 。根據(jù)需求提出的募捐任務(wù)、活動(dòng)請求和募捐請求，獲取所募集的資金和物品。（3）組織募捐活動(dòng)。根據(jù)活動(dòng)請求，確定活動(dòng)時(shí)間范圍。根據(jù)活動(dòng)時(shí)間，搜索場館，即向場館發(fā)送場館可用性請求，獲得場館可用性。然后根據(jù)活動(dòng)時(shí)間和地點(diǎn)推廣募捐活動(dòng)，根據(jù)相應(yīng)的活動(dòng)信息舉辦活動(dòng)，從募款機(jī)構(gòu)獲取資金并向其發(fā)放贈(zèng)品。獲取和處理捐贈(zèng)，根據(jù)捐贈(zèng)要求，提供所募集的捐贈(zèng)；處理與處理人之間的交互。即：錄入捐贈(zèng)人信息，處理后存入捐贈(zèng)人信息表；從捐贈(zèng)人信息表中查詢捐贈(zèng)人信息，向捐贈(zèng)人發(fā)送捐贈(zèng)請求，并將已聯(lián)系的捐贈(zèng)人存入已聯(lián)系的捐贈(zèng)人表。根據(jù)捐贈(zèng)請求進(jìn)行募集，募得捐贈(zèng)后，將捐贈(zèng)記錄存入捐贈(zèng)表；對捐贈(zèng)記錄進(jìn)行處理后，存入已處理捐贈(zèng)表，向捐贈(zèng)人發(fā)送致謝函。根據(jù)已聯(lián)系的捐贈(zèng)人和捐贈(zèng)記錄進(jìn)行跟進(jìn)，將捐贈(zèng)跟進(jìn)情況發(fā)送給捐贈(zèng)人。現(xiàn)采用機(jī)構(gòu)化方法對募捐系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖 1-1、1-2 和 1-3 所示分層數(shù)據(jù)流圖。圖 1-1 所示分層數(shù)據(jù)流圖圖 1-2 所示分層數(shù)據(jù)流圖圖 1-3 所示分層數(shù)據(jù)流圖問題：1.1 使用說明中的詞語，給出圖 1-1 中的實(shí)體 E1E4 的名稱。問題：1.2 在建模 DFD 時(shí)，需要對有些復(fù)雜加工（處理）進(jìn)行進(jìn)一步精化，圖1-2 為圖 1-1 中處理 3 的進(jìn)一步細(xì)化的 1 層數(shù)據(jù)圖，圖 1-3 為圖 1-2 中 3.1 進(jìn)一步細(xì)化的 2 層數(shù)據(jù)流圖。補(bǔ)全圖 1-2 中加工 P1、P2 和 P3 的名稱和圖 1-2 與圖1-3 中缺少的數(shù)據(jù)流。問題：1.3 使用說明中的詞語，給出圖 1-3 中的數(shù)據(jù)存儲(chǔ) D1D4 的名稱。答案解析問題 1：E1 志愿者 E2 捐贈(zèng)人 E3 募捐機(jī)構(gòu) E4 場館本題采用結(jié)構(gòu)化方法進(jìn)行系統(tǒng)分析與設(shè)計(jì)，主要考查數(shù)據(jù)流圖（DFD)的應(yīng)用，是比較傳統(tǒng)的題目，要求考生細(xì)心分析題目中所描述的內(nèi)容。DFD 是一種便于用戶理解、分析系統(tǒng)數(shù)據(jù)流程的圖形化建模工具，是系統(tǒng)邏輯模型的重要組成部分。頂層 DFD般用來確定系統(tǒng)邊界，將待開發(fā)系統(tǒng)看作一個(gè)大的加工(處理)，然后根據(jù)系統(tǒng)從哪些外部實(shí)體接收數(shù)據(jù)流，以及系統(tǒng)將數(shù)據(jù)流發(fā)送到哪些外部實(shí)體，建模出的頂層圖中只有唯一的一個(gè)加工和一些外部實(shí)體，以及這兩者之間的輸入輸出數(shù)據(jù)流。0 層 DFD 在頂層確定的系統(tǒng)外部實(shí)體以及與外部實(shí)體的輸入輸出數(shù)據(jù)流的基礎(chǔ)上，將頂層 DFD 中的加工分解成多個(gè)加工，識(shí)別這些加工的輸入輸出數(shù)據(jù)流，使得所有頂層 DFD 中的輸入數(shù)據(jù)流，經(jīng)過這些加工之后變換成頂層 DFD 的輸出數(shù)據(jù)流。根據(jù) 0 層 DFD 中的加工的復(fù)雜程度進(jìn)一步建模加工的內(nèi)容。在建分層 DFD 時(shí)，根據(jù)需求情況可以將數(shù)據(jù)存儲(chǔ)建模在不同層次的 DFD 中，注意在繪制下層數(shù)據(jù)流圖時(shí)要保持父圖與子圖平衡。父圖中某加工的輸入輸出數(shù)據(jù)流必須與它的子圖的輸入輸出數(shù)據(jù)流在數(shù)量和名稱上相同，或者父圖中的一個(gè)輸入（或輸出）數(shù)據(jù)流對應(yīng)于子圖中幾個(gè)輸入（或輸出）數(shù)據(jù)流，而子圖中組成這些數(shù)據(jù)流的數(shù)據(jù)項(xiàng)全體正好是父圖中的這一個(gè)數(shù)據(jù)流。本問題給出 0 層 DFD，要求根據(jù)描述確定圖中的外部實(shí)體。分析題目中描述，并結(jié)合己在圖中給出的數(shù)據(jù)流進(jìn)行分析。從題目的說明中可以看出，與系統(tǒng)交互實(shí)體包括志愿者、捐贈(zèng)人、募款機(jī)構(gòu)和場館，這四個(gè)作為外部實(shí)體。問題 2 答案解析：P1：確定活動(dòng)時(shí)間范圍 P2：搜索場館 P3：推廣募捐活動(dòng)本題考查分層 DFD 的加工分解，以及父圖與子圖的平衡。圖 1-2 中對圖 1-1 的加工 3 進(jìn)行進(jìn)一步分解，根據(jù)說明（3)中對加工 3 的描述對圖 1-2 進(jìn)行分析。首先需要確定活動(dòng)時(shí)間范圍，其輸入數(shù)據(jù)流是活動(dòng)請求，輸出流為活動(dòng)時(shí)間。然后是搜索場館，其輸入流為活動(dòng)時(shí)間，輸出活動(dòng)時(shí)間和地點(diǎn)，同時(shí)向場館發(fā)送的場館可用性請求和獲得的場館可用性分別作為輸入和輸出數(shù)據(jù)流。在確定活動(dòng)時(shí)間和地點(diǎn)的基礎(chǔ)上推廣募捐活動(dòng)， 活動(dòng)時(shí)間和地點(diǎn)是其輸入流，活動(dòng)信息作為其輸出流，流向舉辦活動(dòng)并募集資金，從募款機(jī)構(gòu)獲取資金并向其發(fā)放贈(zèng)品，加工 2 收集募得的資金和物品，因此 3.5 還需要將所募集資金作為輸出流。獲取和處理捐贈(zèng)（資金和物品）時(shí)以捐贈(zèng)請求作為其輸入流，輸出流為所募集的捐贈(zèng)，因?yàn)榧扔匈Y金又有物品，而從募款機(jī)構(gòu)募得的只有資金，將圖 1-1中加工 3 流向加工 2 的數(shù)據(jù)流，分為所募集資金和所募集物品，而 3.5 的輸出流中只有所募集資金。因此，P1 為確定活動(dòng)時(shí)間范圍，P2 為搜索場館，P3 為推廣募捐活動(dòng)。圖 1-2 中缺失了從 2 到 3.3 的活動(dòng)時(shí)間和從 3.5 到 2 的所募集資金這兩條數(shù)據(jù)流。題目給出處理和捐贈(zèng)人之間的交互進(jìn)一步描述，對 3.1 進(jìn)一步建模下層數(shù)據(jù)流圖（圖 1-3)。分解加工 3.1，確定相關(guān)數(shù)據(jù)流。其中根據(jù)加工 2 的捐贈(zèng)請求進(jìn)行募集，所募捐贈(zèng)需要返回給加工 2。根據(jù)父圖與子圖的平衡原則，圖 1-3 中此處也缺失了捐贈(zèng)請求和所募集資金和所募集物品。問題 3 答案解析：D1：捐贈(zèng)人信息表 D2:已聯(lián)系的捐贈(zèng)人表；D3：捐贈(zèng)表 D4:已處理捐贈(zèng)表本問題考查 2 層 DFD 中數(shù)據(jù)存儲(chǔ)的確定。本案例中，數(shù)據(jù)存儲(chǔ)的描述都是在這一部分描述給出，所以數(shù)據(jù)存儲(chǔ)建模在此層體現(xiàn)第 2 題【說明】某電視臺(tái)擬開發(fā)一套信息管理系統(tǒng)，以方便對全臺(tái)的員工、欄目、廣告和演播廳等進(jìn)行管理。【需求分析】（1）系統(tǒng)需要維護(hù)全臺(tái)員工的詳細(xì)信息、欄目信息、廣告信息和演播廳信息等。員工的信息包括：工號、姓名、性別、出生日期、電話、住址等。欄目信息主要包括：欄目名稱、播出時(shí)間、時(shí)長等。廣告信息主要包括：廣告編號、價(jià)格等。演播廳信息包括：房間號、房間面積等。（2）電視臺(tái)根據(jù)調(diào)度單來協(xié)調(diào)各個(gè)欄目、演播廳和場務(wù)。一銷售檔欄目只會(huì)占用一個(gè)演播廳，但會(huì)使用多名場務(wù)來進(jìn)行演出協(xié)調(diào)。演播廳和場務(wù)可以被多個(gè)欄目循環(huán)使用。（3）電視臺(tái)根據(jù)欄目來插播廣告。每檔欄目可以插播多條廣告，每條廣告也可以在多檔欄目插播。（4）一檔欄目可以有多個(gè)主持人，但一名主持人只能主持一檔欄目。（5）一名編輯人員可以編輯多條廣告，一條廣告只能由一名編輯人員編輯。【概念模型設(shè)計(jì)】根據(jù)需求階段收集的信息設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖 2-1 所示。【邏輯結(jié)構(gòu)設(shè)計(jì)】根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式（不完整） ；演播廳（房間號，房間面積）欄目（欄目名稱，播出時(shí)間，時(shí)長）廣告（廣告編號，銷售價(jià)格， （1） ）員工（工號，姓名，性別，出生日期，電話，住址）主持人（主持人工號， （2） ）插播單（ （3） ，播出時(shí)間）調(diào)度單（4） ）問題：2.1 補(bǔ)充圖 2-1 中的聯(lián)系和聯(lián)系的類型。問題：2.2 根據(jù)圖 2-1，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空（1）（4）補(bǔ)充完整，并用下劃線指出空（1） （4）所在關(guān)系模式的主鍵。問題：2.3 現(xiàn)需要記錄廣告商信息，增加廣告商實(shí)體。一個(gè)廣告商可以提供多條廣告，一條廣告只由一個(gè)廣告商提供。請根據(jù)該要求，對圖 2-1 進(jìn)行修改，畫出修改后的實(shí)體間聯(lián)系和聯(lián)系的類型。答案解析問題 1 答案解析：本題考查數(shù)據(jù)庫設(shè)計(jì)，屬于比較傳統(tǒng)的題目，考查點(diǎn)也與往年類似。本問題考查數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計(jì)，題目要求補(bǔ)充完整實(shí)體聯(lián)系圖中的聯(lián)系和聯(lián)系的類型。根據(jù)題目的需求描述可知，一個(gè)欄目可以插播多條廣告，而多條廣告也可以在多個(gè)欄目中播放，因此欄目和廣告之間存在“插播” 聯(lián)系，聯(lián)系的類型為多對多（*:*，或 m:n)。根據(jù)題目的需求描述可知，一個(gè)欄目可以有多個(gè)主持人，而一個(gè)主持人只能主持一檔欄目，因此欄目和主持人之間存在“主持” 聯(lián)系，聯(lián)系的類型為一對多（1:*，或 l:n)。根據(jù)題目的需求描述可知，一個(gè)欄目需要使用多名場務(wù)來進(jìn)行演出協(xié)調(diào)，場務(wù)可以被多個(gè)欄目循環(huán)使用，因此演播廳、欄目和場務(wù)之間存在“ 調(diào)度”聯(lián)系，聯(lián)系的類型為 1 對多對多（ 1:*:*，或 l:m:n)。問題 2 答案解析：本問題考查數(shù)據(jù)庫的邏輯結(jié)構(gòu)設(shè)計(jì)，題目要求補(bǔ)充完整各關(guān)系模式，并給出各系模式的主鍵。根據(jù)實(shí)體聯(lián)系圖和需求描述，廣告記錄廣告編號、銷售價(jià)格和編輯人員工號。所以， 對于“廣告” 關(guān)系模式，需補(bǔ)充屬性“廣告編號”。廣告編號為廣告的主鍵。根據(jù)實(shí)體聯(lián)系圖和需求描述，主持人記錄主持人工號和所屬的欄目名稱。所以，對于“主持人” 關(guān)系模式，需補(bǔ)充屬性 “主持人工號”。主持人工號為主持人的主鍵。根據(jù)實(shí)體聯(lián)系圖和需求描述，插播單需要記錄欄目名稱、廣告編號和播出的時(shí)間。 所以，對于“ 插播單”關(guān)系模式，需補(bǔ)充屬性“欄目名稱”和“廣告編號”。欄目名稱和廣告編號聯(lián)合作為插播單的主鍵。根據(jù)實(shí)體聯(lián)系圖和需求描述，調(diào)度單需要記錄欄目名稱、房間號和參與的場務(wù)工號。 所以，對于“調(diào)度單 ”關(guān)系模式，需補(bǔ)充屬性 “欄目名稱”、 “房間號”和“ 場務(wù)工號”。 欄目名稱、房間號和場務(wù)工號聯(lián)合作為插播單的主鍵。問題 3 答案解析：本問題考查數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計(jì)，根據(jù)新增的需求增加實(shí)體聯(lián)系圖中的實(shí)體的聯(lián)系和聯(lián)系的類型。根據(jù)問題描述，一個(gè)廣告商可以提供多條廣告，一條廣告只由一個(gè)廣告商提供。則須在廣告商實(shí)體和廣告實(shí)體之間存在“提供” 聯(lián)系，聯(lián)系的類型為 1 對多（1:*，或 l:n)第 3 題【說明】某城市擬開發(fā)一個(gè)基于 Web 的城市黃頁，公開發(fā)布該城市重要的組織或機(jī)構(gòu)（以下統(tǒng)稱為客戶）的基本信息，方便城市生活。該系統(tǒng)的主要功能描述如下：（1）搜索信息：任何使用 Internet 的網(wǎng)絡(luò)用戶都可以搜索發(fā)布在城市黃頁中的信息，例如客戶的名稱、地址、聯(lián)系電話等。（2）認(rèn)證：客戶若想在城市黃頁上發(fā)布信息，需要通過系統(tǒng)的認(rèn)證。認(rèn)證成功后，該客戶成為系統(tǒng)授權(quán)用戶。（3）更新信息：授權(quán)用戶登錄系統(tǒng)之后，可以更改自己的在城市黃頁中的相關(guān)信息，例如變更聯(lián)系電話等。 （4）刪除客戶：對于拒絕繼續(xù)在城市黃頁上發(fā)布信息的客戶，由系統(tǒng)管理員刪除該客戶的相關(guān)信息。系統(tǒng)采用面向?qū)ο蠓椒ㄟM(jìn)行開發(fā)，在開發(fā)過程中認(rèn)定出如表 3-1 所示的類。系統(tǒng)的用例圖和類圖分別如圖 3-1 和 3-2 所示。問題：3.1 根據(jù)說明中的描述，給出圖 3-1 中的 A1 和 A2 處所對應(yīng)的參與者、UC1 和 UC2 處所對應(yīng)的用例以及（1）處的關(guān)系。問題：3.2 根據(jù)說明中的描述，給出圖 3-2 中的 C1C5 所對應(yīng)的類名（表 3-1 中給出的類名）和（2）（5）處所對應(yīng)的多重度。問題：3.3 認(rèn)定類是面向?qū)ο蠓治鲋蟹浅ｊP(guān)鍵的一個(gè)步驟。一般首先從問題域中得到候選類集合，再根據(jù)相應(yīng)的原則從該集合中刪除不作為類的，剩余的就是從問題域中認(rèn)定出來的類。簡要說明選擇題選類的原則，以及對候選類集合進(jìn)行刪除的原則。答案解析問題 1 答案解析：A1 ：網(wǎng)絡(luò)用戶或 IntemetClient A2：授權(quán)用戶或 RegisteredClientUC1：更新信息 UC2:認(rèn)證(1): include本題屬于經(jīng)典的考題，主要考查面向?qū)ο蠓治龇椒ㄒ约?UML 的用例圖和類圖的相關(guān)應(yīng)用。本問題要求將圖 3-1 所給出的用例圖補(bǔ)充完整。用例圖的構(gòu)成要素有：參與者(Actor)、用例 (Usecase)以及用例之間的關(guān)系。本題背景描述簡單，再結(jié)合圖 3-1 中給出的兩個(gè)用例“搜索信息” 和“刪除客戶”，很容易確定出“ 認(rèn)證” 、 “更新信息”就是需要補(bǔ)充的用例。下面只需要確定參與者A1、A2 以及這兩個(gè)用例與 A1、A2 之間的關(guān)系即可將圖補(bǔ)充完整。在說明中出現(xiàn)了兩類角色: 客戶和系統(tǒng)管理員。系統(tǒng)管理員已經(jīng)作為參與者明確標(biāo)識(shí)在3-1 中了。那么 A1 和 A2 只能從“客戶” 這個(gè)角色中產(chǎn)生。明顯地， “客戶”在說明中被細(xì)分成了兩類：網(wǎng)絡(luò)用戶和授權(quán)用戶，而認(rèn)證用戶是一種特殊的網(wǎng)絡(luò)用戶。因此，A1 應(yīng)該對應(yīng)“ 網(wǎng)絡(luò)用戶” ，A2 應(yīng)該對應(yīng)“授權(quán)客戶”。要成為授權(quán)用戶，必須首先經(jīng)過認(rèn)證。成為授權(quán)用戶之后，不僅可以搜索信息，還具有更新信息的權(quán)限。更新信息時(shí)要求首先登錄系統(tǒng)，因此“登錄” 是“更新信息”操作中所包含的一個(gè)必須步驟。由此可以確定 UC1 對應(yīng)“更新信息”， UC2 對應(yīng)“認(rèn)證”，而（1) 處的關(guān)系應(yīng)該是include 問題 2 解析：Cl： IntemetClient C2：CustomerList C3：RegisteredClientC4:AdministratorC5：Customer(2)1 (3)0.* (4) 0.1 (5) 0.1本問題考查類建模。表 3-1 已經(jīng)給出了類列表，這樣對照圖 3-2 尋找對應(yīng)關(guān)系即可。圖 3-2 中有兩個(gè)明顯的結(jié)構(gòu)：繼承（Cl、C3 和 C4 之間）和聚集（C2 和C5 之間） 。先確定聚集關(guān)系相關(guān)的類。由表 3-1 可以找出兩個(gè)明顯具有部分整體概念的類：CustomerList 和 Customer,由類的說明可以看出，CustomerList 表示整體概念，Customer 表示部分概念。由此可以確定 C2 對應(yīng) CustomerList, C5 對應(yīng)Customer。同時(shí)可以確定出這兩個(gè)類之間的多重度，即（2)處應(yīng)為 1，(3)處為0.*。下面來確定繼承關(guān)系相關(guān)的類。圖 3-1 中已經(jīng)出現(xiàn)了一個(gè)繼承關(guān)系(A1 和 A2 之間） ， 這就給出了一個(gè)明顯的提示：圖 3-2 中的繼承關(guān)系與這兩類角色相關(guān)。回到表 3-1 中，發(fā)現(xiàn)了 3 個(gè)與角色相關(guān)的類：IntemetClient (網(wǎng)絡(luò)用戶） 、RegisteredClient (授權(quán)用戶）和 Administrator (系統(tǒng)管理員） 。由于己經(jīng)確定了C5 是 Customer,而能夠?qū)?Customer 進(jìn)行操作的只有系統(tǒng)管理員。因此具有繼承關(guān)系的這 3 個(gè)類應(yīng)分別是：C1-網(wǎng)絡(luò)用戶，C3-授權(quán)用戶，C4-系統(tǒng)管理員。 （4)、(5)處的多重度也可以確定下來，均為 0.1。問題 3 答案解析：選擇候選類時(shí)通常考慮的是問題域中自然存在的名詞。具有下列特征的候選類需要?jiǎng)h除：含義相近（冗余） 、含義不明確的對象、暗示實(shí) 現(xiàn)方式的、表示屬性或特征、有動(dòng)詞含義的名詞（表示行為和方法)。本問題考查面向?qū)ο蠓治鲞^程中認(rèn)定類/對象的過程。通常分為兩個(gè)步驟進(jìn)行，首先將問題域（需求分析）中所有自然存在的名詞都選出來，構(gòu)成候選類集合。然后針對這個(gè)候選類集合，將滿足以下原則的名詞從候選類集合中刪除：含義相近（冗余)、含義不明確的對象、暗示實(shí)現(xiàn)方式的、表示屬性或特征、有動(dòng)詞含義的名詞（表示行為和方法)。 最后剩余的就是所認(rèn)定的類/ 對象。第 4 題閱讀下列說明和 C 代碼，回答問題 1 至問題 3,將解答寫在答題紙的對應(yīng)欄內(nèi)。【說明】設(shè)有 m 臺(tái)完全相同的機(jī)器運(yùn)行 n 個(gè)獨(dú)立的任務(wù)，運(yùn)行任務(wù) i 所需要的時(shí)間為 ti，要求確定一個(gè)調(diào)度方案，使得完成所有任務(wù)所需要的時(shí)間最短。假設(shè)任務(wù)已經(jīng)按照其運(yùn)行時(shí)間從大到小順序。算法基于最長運(yùn)行時(shí)間作業(yè)優(yōu)先的策略；按順序先把每個(gè)任務(wù)分配到一臺(tái)機(jī)器上，然后將剩余的任務(wù)依次放入空閑的機(jī)器。【C 代碼 】下面是算法的 C 語言實(shí)現(xiàn)。（1）常量和變量說明m:機(jī)器數(shù)n:任務(wù)數(shù)t:輸入數(shù)組，長度為 n，其中每個(gè)元素表示任務(wù)的運(yùn)行時(shí)間，下標(biāo)從 0 開始s:二維數(shù)組，長度為 m*n，下標(biāo)從 0 開始，其中元素 sij表示機(jī)器 i 運(yùn)行的任務(wù) j 的編號d:數(shù)組，長度為 m，其中元素 di表示機(jī)器 i 的運(yùn)行時(shí)間，下標(biāo)從 0 開始count:數(shù)組，長度為 m，下標(biāo)從 0 開始，其中元素 counti表示機(jī)器 i 的運(yùn)行任務(wù)數(shù)i:循環(huán)變量j:循環(huán)變量k:臨時(shí)變量max:完成所有任務(wù)的時(shí)間min:臨時(shí)變量（2）函數(shù) schedulevoid schedule()int i,j,k,max=0for(i=0;idj) min=dj;k=j; / 機(jī)器 K 空閑（3） ；countk=countk+1;dk=dk+ti;for(i=0;im;i+) /確定完成所有任務(wù)需要的時(shí)間if( (4)max=di;問題：4.1 根據(jù)說明和 c 代碼，填充 C 代碼中的空（ 1）（4） 。問題：4.2 根據(jù)說明和 C 代碼，該問題采用了 （ 5） 算法設(shè)計(jì)策略，時(shí)間復(fù)雜度為 （6） （用 O 符號表示） 。問題：4.3 考慮實(shí)例 m=3（編號 02） ，n=7（編號 06） ，各任務(wù)的運(yùn)行時(shí)間為16,14,6,5,4,3,2。則在機(jī)器 0、1 和 2 上運(yùn)行的任務(wù)分別為（7） 、 （8）和（9） （給出任務(wù)編號） 。從任務(wù)開始運(yùn)行到完成所需要的時(shí)間為 （10） 。問題 1 答案解析：(1) di = ti(2) i=m (3) skcountk =i (4) maxdi本題考查算法設(shè)計(jì)與分析技術(shù)以及算法的 C 語言實(shí)現(xiàn)，是比較傳統(tǒng)的題目，要求考生細(xì)心分析題目中所描述的內(nèi)容。根據(jù)題中說明和代碼注釋，算法首先初始化數(shù)組 d 和 s 中的元素；然后將 m 個(gè)任務(wù)分配到 m 臺(tái)機(jī)器上，此時(shí)將任務(wù) 0，1，.，m-1 分別分配到機(jī)器0，1，m-1 上，同時(shí)設(shè)置 d、s 和 count 數(shù)組中的相關(guān)元素的值，故空格（1)填寫 di = ti;接下來將剩下的 n-m 個(gè)任務(wù)分配到 m 臺(tái)機(jī)器上，從任務(wù) m 開始，因此空格（2)填寫 i=m，確定首先空閑的機(jī)器 k，將當(dāng)前尚未分配的第一個(gè)任務(wù)分配到機(jī)器 k 上，并設(shè)置 d、s 和 count 數(shù)組中的相關(guān)元素的值，故空格（ 3)填寫 skc0untk = i;最后確定從任務(wù)開始到結(jié)束所需要的時(shí)間，從所有機(jī)器的運(yùn)行時(shí)間中選擇運(yùn)行時(shí)間最長的機(jī)器的運(yùn)行時(shí)間，即最大的 di， 因此空格（4)填寫 maxdi。問題 2 答案解析：(5) 貪心 （6) O(mn)根據(jù)上述 C 代碼，算法有兩處兩重循環(huán)，時(shí)間復(fù)雜度為 O(mn)，有兩處一重循環(huán)，時(shí)間復(fù)雜度為 0(m)，因此整個(gè)算法的時(shí)間復(fù)雜度為 O(mn)。問題 3 答案解析：(7) 0 (8) 1,5 (9) 2,3,4,6 (10) 17根據(jù)說明中的算法思想和 C 代碼，首先將任務(wù) 0、1 和 2 分配到機(jī)器 0、1 和 2上運(yùn)行，運(yùn)行時(shí)間分別為 16、14 和 6。由于任務(wù) 2 的時(shí)間最短，故任務(wù) 3 在機(jī)器 2 上運(yùn)行，機(jī)器 2 上的運(yùn)行時(shí)間為 6+5=11，仍然是時(shí)間最短，任務(wù) 4 繼續(xù)在機(jī)器 2 上運(yùn)行，機(jī)器 2 上的運(yùn)行時(shí)間為 11+4=15。此時(shí)機(jī)器 1 上的運(yùn)行時(shí)間最短，任務(wù) 5 在機(jī)器 1 上運(yùn)行，機(jī)器 1 上的運(yùn)行時(shí)間為 14+3=17。此時(shí)機(jī)器 2 上的運(yùn)行時(shí)間最短，任務(wù) 6 在機(jī)器 2 上運(yùn)行， 機(jī)器 2 上的運(yùn)行時(shí)間為 15+2=17。所以任務(wù)分配完成。根據(jù)此分配，在機(jī)器 0 上運(yùn)行任務(wù) 0,運(yùn)行時(shí)間為 16;機(jī)器 1上運(yùn)行任務(wù) 1 和 5,運(yùn)行時(shí)間為 17;在機(jī)器 2 上運(yùn)行任務(wù) 2, 3, 4 和 6,運(yùn)行時(shí)間為17。因此從任務(wù)開始到結(jié)束的時(shí)間為 17。第 6 題【說明】現(xiàn)要求實(shí)現(xiàn)一個(gè)能夠自動(dòng)生成求職簡歷的程序。簡歷的基本內(nèi)容包括求職者的姓名、性別、年齡及工作經(jīng)歷等。希望每份簡歷中的工作經(jīng)歷有所不同，并盡量減少程序中的重復(fù)代碼。現(xiàn)采用原型（Prototype）模式來實(shí)現(xiàn)上述要求，得到如圖 6-1 所示的類圖。【Java 代碼】class WorkExperience(1) Closeable /工作經(jīng)歷private string workDate;private string company;public Object Clone()(2) ；obj.workDate=this.workDate;pany=pany;return obj;class Resume(3)Closeable /簡歷private string name; private string sex; private string age; private WorkExperience work;public Resume(string name)this name=name; work=new SetWorkExperience();private Resume(WorkExperience work)this work= (4);public void SetPersonallnfo(string sex, string age;) /* 代碼略 */ public void SetWorkExperience(string workDate, string company) /* 代碼略 */ public Object Clone()Resume obj= (5) ;/ 其余代碼省略return obj;class WorkResume public static void main(stringarg)Resume a=new Resume(“張三”)； a.SetPersonallnfo(“男”,“29”)；a.SetWorkExperience(“19982000”,“XXX 公司”) ；Resume b= (6) ;b.SetWorkExperience(“20012006”,“YYY 公司”)；問題：6.1 閱讀下列說明和 Java 代碼，將應(yīng)填入（ n）處的字句寫在答題紙的對應(yīng)欄內(nèi)。答案解析：(1) implements(2) WorkExperience obj = new WorkExperience()(3) implements(4) (WorkExperience)work.Clone()(5) new Resume(this.work)(6) (Resume)a.Clone()本題考査原型（Prototype)模式的概念及應(yīng)用。Prototype 模式是一種對象創(chuàng)建型模式。Prototype 模式通過給出一個(gè)原型對象來指明所要?jiǎng)?chuàng)建的對象的類型，然后通過復(fù)制這個(gè)原型對象的方法，創(chuàng)建出更多同類型的對象。 原型模式又可以分為兩種：淺克隆和深克隆。淺克隆僅僅復(fù)制所考慮的對象，而不復(fù)制它所引用的對象，也就是其中的成員對象并不復(fù)