《2013年上半年（下午）《軟件設計師》真題》由會員分享，可在線閱讀，更多相關《2013年上半年（下午）《軟件設計師》真題（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2013年上半年（下午）《軟件設計師》真題 注意：圖片可根據(jù)實際需要調整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習次數(shù)：0次 問答題 （共6題，共6分） 1.某城市擬開發(fā)一個基于Web城市黃頁，公開發(fā)布該城市重要的組織或機構（以下統(tǒng)稱為客戶）的基本信息，方便城市生活。該系統(tǒng)的主要功能描述如下： （1）搜索信息：任何使用Internert的網(wǎng)絡用戶都可以搜索發(fā)布在城市黃頁中的信息，例如客戶的名稱、地址、聯(lián)系電話等。 （2）認證：客戶若想在城市黃頁上發(fā)布信息，需通過系統(tǒng)的認證。認證成

2、功后，該客戶成為系統(tǒng)授權用戶。 （3）更新信息：授權用戶登錄系統(tǒng)后，可以更改自己在城市黃頁中的相關信息，例如變更聯(lián)系電話等。 （4）刪除客戶：對于拒絕繼續(xù)在城市黃頁上發(fā)布信息的客戶，有系統(tǒng)管理員刪除該客戶的相關信息。 系統(tǒng)采用面向對象方法進行開發(fā)，在開發(fā)過程中認定出如表3-1所示的類。系統(tǒng)的用例圖和類圖分別如圖3-1和圖3-2所示。 表3-1類列表 【問題1】（5分） 根據(jù)說明中的描述，給出圖3-1中A1和A2處所對應的參與者，UC1和UC2所對應的用例以及（1）處的關系。 【問題2】（7分） 根據(jù)說明中的描述，給出圖3-2中C1~C5所對應的類名（表3-1中給出的

3、類名）和（2）~（5）處所對應的多重度。 【問題3】（3分） 認定類是面向對象分析中非常關鍵的一個步驟。一般首先從問題域中得到候選類集合，在根據(jù)相應的原則從該集合中刪除不作為類的，剩余的就是從問題域中認定出來的類。簡要說明選擇候選類的原則，以及對候選類集合進行刪除的原則。 正確答案： 本題解析： 【問題1】 A1網(wǎng)絡用戶；A2授權用戶；UC1更新信息；UC2認證； （1）＜＜include>> 【問題2】 C1：InternetClient；C2：CustomerList；C3：Admini

4、strator；C4：RegisteredClient C5：Customer； （2）1；（3）0…*；（4）0..1；（5）0..1 【問題3】 候選類的選擇運用了良性依賴原則“不會在實際中造成危害的依賴關系，都是良性依賴”和接口隔離原則（ISP）。 本題考查面向對象分析中的類圖、用例圖。 【問題1】 用例圖中，A1可以搜索信息，A2由A1派生且A2參與了兩個用例，根據(jù)題中的說明（1）和（2），可知A1為網(wǎng)絡用戶，A2為授權用戶；由用例UC1和登錄用例之間存在關系，可知UC1為更新信息，因為更新信息前必須登錄，所以更新信息用例包含登錄用例，它們之間的關系為include。

5、【問題2】 本問題查考類圖?？疾轭悎D的層次結構和多重度。 首先根據(jù)C2和C5之間存在聚合關系，滿足要求的類應該是客戶與客戶集，又因為其中C2為整體，C5為部分，所以C2為客戶集，C5為客戶信息。 又因為圖中更有兩個非常明顯的繼承結構，即C3和C4繼承與C1，且C1與C2是多對一的關系，根據(jù)C2為客戶集，又因為說明（1）中任何網(wǎng)絡用戶都可以搜索客戶信息，即C1為網(wǎng)絡用戶，由此很明顯得出C3和C4在授權用戶和系統(tǒng)管理員中選取。再由C4和C5之間的關聯(lián)關系，且C5為客戶信息，通過題意可以了解到客戶信息是由其成為授權用戶之后，自己發(fā)布與管理的，而管理員在此并未進行職責描述（管理員對客戶的刪除，可

6、以通過其父類對客戶集進行操作），可以不管他。用戶C4顯然就是授權用戶，由此得出C3為管理員。由此（2）~（5）的多重度就顯而易見，（2）為1，（3）為0…*，（4）為1，（5）為1。 【問題3】 候選類的選擇運用了良性依賴原則“不會在實際中造成危害的依賴關系，都是良性依賴”和接口隔離原則（ISP）。ISP：使用多個專門的接口比使用單一的總接口要好。一個類對另外一個類的依賴性應當是建立在最小的接口上的。一個接口代表一個角色，不應當將不同的角色都交給一個接口。沒有關系的接口合并在一起，形成一個臃腫的大接口，這是對角色和接口的污染。“不應該強迫客戶依賴于它們不用的方法。接口屬于客戶，不屬于它所在

7、的類層次結構?！边@個說得很明白了，再通俗點說，不要強迫客戶使用它們不用的方法，如果強迫用戶使用它們不使用的方法，那么這些客戶就會面臨由于這些不使用的方法的改變所帶來的改變。 2.現(xiàn)要求實現(xiàn)一個能夠自動生成求職簡歷的程序，簡歷的基本內容包括求職者的姓名、性別、年齡及工作經(jīng)歷。希望每份簡歷中的工作經(jīng)歷有所不同，并盡量減少程序中的重復代碼。 現(xiàn)采用原型模式（Prototype）來實現(xiàn)上述要求，得到如圖5-1所示的類圖。 圖5-1類圖 【C++代碼】 #include＜string> using namespace std; class?Cloneabl

8、e{ public: (1); }; class?workExperience:public?Cloneable{//工作經(jīng)歷 private: string?workData; string?company; public: Cloneable*clone（　　）{ (2); Obj->workDate=this->workDate; Obj->company=this->company; return Obj; } //其余代碼省略 }; class?Resume:public?Cloneable{//簡歷 private: string name;

9、 string sex; string age; WorkExperience*work; Resume(WorkExperience*work){ this->work=(3); } public: Resume(string name){/*實現(xiàn)省略*/} void SetPersonInfo(string sex,string age){/*實現(xiàn)省略*/} void SetWorkExperience(string workDate,string company){/*實現(xiàn)省略*/} Cloneable*Clone（　　）{ (4); Obj->name=this

10、->name; Obj->sex=this->sex; Obj->age=this->age; return Obj; } }; int?main（　　）{ Resume*a=new Resume(“張三”); a->SetPersonInfo(“男”,“29”)； a->SetWorkExperience(“1998-2000”,“XXX公司”); Resume*b=(5); b->SetWorkExperience(“2001-2006”,“YYY公司”); return 0; } 正確答案：

11、 本題解析： （1）virtual Cloneable*Clone()=0 （2）WorkExperience*obj=new WorkExperience() （3）(WorkExperience*)work->Clone() （4）Resume*obj=new Resume(this->work) （6）(Resume*)a->Clone() 本題考查原型模型的概念及應用。 原型模型的主要思想：先借用已有系統(tǒng)作為原型模型，通過“樣品”不斷改進，使得最后的產品就是用戶所需要的。原型模型通過向用戶提供原型獲取用戶的反饋，使開發(fā)出的軟件能夠真正反映用戶的需求。同時

12、，原型模型采用逐步求精的方法完善原型，使得原型能夠“快速”開發(fā)，避免了像瀑布模型一樣在冗長的開發(fā)過程中難以對用戶的反饋作出快速的響應。相對瀑布模型而言，原型模型更符合人們開發(fā)軟件的習慣，使目前較流行的一種實用軟件生存期模型。 Prototype模式其實就是常說的“虛擬構造函數(shù)”一個實現(xiàn)，C++的實現(xiàn)機制中并沒有支持這個特性，但是通過不同派生類實現(xiàn)的Clone接口函數(shù)可以完成與“虛擬構造函數(shù)”同樣的效果。 題中聲明一個虛擬基類，所有的原型都是從這個基類繼承，（1）所代表的就是這個基類中的純虛函數(shù)，需要供繼承者自行實現(xiàn)，即為virtual Cloneable*Clone()=0，（1）聲明一個

13、抽象基類，并定義clone()函數(shù)為純虛函數(shù)。然后根據(jù)基類實例化各個子類，并且實現(xiàn)賦復制構造函數(shù)，并實現(xiàn)clone()函數(shù)，由此可知（2）處為WorkExperience*Obj，（3）處為Work，（4）處為Resume*Obj。在main函數(shù)中實現(xiàn)Resume*b對*a的復制，故根據(jù)C++語法（5）中為a->Clone()。 注：解析部分只是給出思路，沒有遵循相關語法。 3.某慈善機構欲開發(fā)一個募捐系統(tǒng)，已跟蹤記錄為事業(yè)或項目向目標群體進行募捐而組織的集體性活動。該系統(tǒng)的主要功能如下所述。 （1）管理志愿者。根據(jù)募捐任務給志愿者發(fā)送加入邀請、邀請跟進、工

14、作任務；管理志愿者提供的邀請響應、志愿者信息、工作時長、工作結果等。 （2）確定募捐需求和收集所募捐贈（資金及物品）。根據(jù)需求提出募捐任務、活動請求和捐贈請求，獲取所募集的資金和物品。 （3）組織募捐活動。根據(jù)活動請求，確定活動時間范圍。根據(jù)活動時間，搜索場館，即：向場館發(fā)送場館可用性請求，獲得場館可用性。然后根據(jù)活動時間和地點推廣募捐活動，根據(jù)相應的活動信息舉辦活動，從募捐機構獲取資金并向其發(fā)放贈品。獲取和處理捐贈，根據(jù)捐贈請求，提供所募集的捐贈；處理與捐贈人之間的交互，即： 錄入捐贈人信息，處理后存入捐贈人信息表；從捐贈人信息表中查詢捐贈人信息，向捐贈人發(fā)送捐贈請求，并將已聯(lián)系的捐贈

15、人存入已聯(lián)系的捐贈人表。根據(jù)捐贈請求進行募集，募得捐贈后，將捐贈記錄存入捐贈表；對捐贈記錄進行記錄后，存入已處理捐贈表，向捐贈人發(fā)送致謝函，根據(jù)已聯(lián)系的捐贈人和捐贈記錄進行跟蹤，并將捐贈跟進情況發(fā)送給捐贈人。 先采用結構化方法對募捐系統(tǒng)進行分析和設計，獲得如圖1-1、圖1-2和圖1-3所示分層數(shù)據(jù)流圖。 【問題1】（4分） 使用說明中的詞語，給出圖1-1中的實體E1~E4的名稱。 【問題2】（7分） 在建模DFD時，需要對有些復雜加工（處理）進行進一步精化，圖1-2為圖1-1中處理3的進一步細化的1層數(shù)據(jù)流圖，圖1-3為圖1-2中3.1進一步細化的2層數(shù)據(jù)流圖。補全1-2

16、中加工P1、P2和P3的名稱和圖1-2與圖1-3中缺少的數(shù)據(jù)流。 【問題3】（4分） 使用說明中的詞語，給出圖1-3中的數(shù)據(jù)存儲D1~D4的名稱。 正確答案： 本題解析： 【問題1】 E1：志愿者E2：捐贈人E3：募捐機構E4：場館 【問題2】 P1：確定活動時間范圍P2：搜索場館P3：推廣募捐活動 圖1-2缺少的數(shù)據(jù)流： 名稱：活動請求起點：2確定募款需求收集所募捐款終點：P1 名稱：所募集資金起點：3.5舉辦活動并募集資金終點：2確定募捐需求收集所募捐款 圖1-3缺失的數(shù)據(jù)流：

17、名稱：捐贈請求起點：2確定募款需求收集所募捐款終點：3.1.3募集 名稱：所募集資金起點：3.1.3募集終點：2確定募款需求收集所募捐款 名稱：所募集物品起點：3.1.3募集終點：2確定募款需求收集所募捐款 或后兩條數(shù)據(jù)流合并為： 名稱：所募集捐贈起點：3.1.3募集終點：2確定募款需求收集所募捐款 【問題3】 D1：捐贈人信息表D2：已聯(lián)系的捐贈人信息表D3：捐贈表D4：已經(jīng)處理的捐贈表。 解答這類題目有兩個原則： 1.第一個原則是緊扣試題系統(tǒng)說明部分，數(shù)據(jù)流圖與系統(tǒng)說明有著嚴格的對應關系，系統(tǒng)說明部分的每一句話都能對應到圖中來，解題時一句一句的對照圖來分析。 2.第二個原

18、則即數(shù)據(jù)平衡原則，這一點在解題過程中也是至關重要的。數(shù)據(jù)平衡原則有兩方面的含義，一方面是分層數(shù)據(jù)流圖父子圖之間的數(shù)據(jù)流平衡原則，另一方面是每張數(shù)據(jù)流圖中輸入與輸出數(shù)據(jù)流的平衡原則。 【問題1】 根據(jù)0層數(shù)據(jù)流管理志愿者中的募捐任務給志愿者發(fā)送加入邀請，邀請跟進，工作任務和管理志愿者提供的邀請響應可知E1為志愿者；從錄入捐款人信息，向捐贈人發(fā)送募捐請求，；向捐贈人發(fā)送致謝函等可知E2為捐贈人；從根據(jù)說明中從募捐機構獲取資金并向其發(fā)放贈品可知E3為募捐機構；根據(jù)向場館發(fā)送可用性請求和獲得場所可用性可知E4為場館。 【問題2】 根據(jù)1層數(shù)據(jù)流圖中P1的輸出流活動時間再結合說明可知P1為確定活

19、動時間范圍；從加工P2的輸入流活動時間和輸出流場館可用性請求和活動時間和地點可知P2為搜索場館；說明中根據(jù)活動時間和地點推廣募捐活動，根據(jù)相應的活動信息舉辦活動，再結合P3的輸入輸出流可知P3為推廣募捐活動。 比較0層和1層中的數(shù)據(jù)流可知，P1加工只有輸出流，故缺少輸出流，根據(jù)說明可知需要根據(jù)活動請求才能確定P1，故該數(shù)據(jù)流為活動請求，在0層數(shù)據(jù)流中活動請求的起始加工為確定募款需求收集所募捐贈，故可知答案。又因為對于加工3.5只有輸入數(shù)據(jù)流資金，沒有輸出數(shù)據(jù)流，因此缺失數(shù)據(jù)流所募集資金，起點為加工3.5，又因為加工2為確定募捐請求和收集所募捐贈，所以該數(shù)據(jù)流終點為加工2。 比較1層圖和2層

20、圖的數(shù)據(jù)流可知，2層圖是1層圖中加工3.1的分解，而對于加工3.1與加工2之間，在父圖中存在3條數(shù)據(jù)流，而子圖中沒有給出，因此子圖缺失數(shù)據(jù)流：捐贈請求，起點為2，終點為3.1.3；所募集物品，起點為3.1.3，終點為2；所募集資金，起點為3.1.3，終點為2。或者將后面兩條數(shù)據(jù)流合并為所募集捐贈。 【問題3】 根據(jù)最后的說明和2層數(shù)據(jù)流可知D1為捐贈人信息表，D2為已聯(lián)系的捐贈人信息表，D3為捐贈表，D4為已經(jīng)處理的捐贈表。 4.某電視臺擬開發(fā)一套信息管理系統(tǒng)，以方便對全臺的員工、欄目、廣告和演播室等進行管理。 【需求分析】 （1）系統(tǒng)需要維護全臺員工的

21、詳細信息、欄目信息、廣告信息和演播廳信息等。員工的信息主要包括：工號、姓名、性別、出生日期、電話、住址等。欄目信息主要包括：欄目名稱、播出時間、時長等。廣告信息主要包括：廣告編號、價格等。演播廳信息包括：房間號、房間面積等。 （2）電視臺分局調度單來協(xié)調各檔欄目、演播廳和場務。一銷售檔欄目只會占用一個演播廳，但會使用多名場務來進行演出協(xié)調。演播廳和場務可以被多個欄目循環(huán)使用。 （3）電視臺根據(jù)欄目來插播廣告。每檔欄目可以插播多條廣告，每條廣告也可以在多的欄目插播。 （4）一檔欄目可以有多個主持人，但一名主持人只能支持一檔欄目。 （5）一名編輯人員可以編輯多條廣告，一條廣告只能由一名編輯

22、人員編輯。 【概念模型設計】 根據(jù)需求階段收集的信息設計的實體聯(lián)系圖（不完整）如圖2-1所示。 【邏輯結構設計】 根據(jù)概念模式設計階段完成的實體聯(lián)系圖，得出如下關系模型（不完整）： 演播廳（房間號，房間面積） 欄目（欄目名稱，播出時間，時長） 廣告（廣告編號，銷售價格，（1）） 員工（工號，姓名，性別，出生日期，電話，住址） 主持人（主持人工號，（2）） 插播單（（3），播出時間） 調度單（（4）） 【問題1】（7分） 補充圖2-1中的聯(lián)系和聯(lián)系類型。 【問題2】（5分） 根據(jù)圖2-1，將邏輯結構設計階段生產的關系模型的空(1)~(4)補充完整，并用下劃線指出

23、（1）~（4）所在關系模型的主鍵。 【問題3】（3分） 現(xiàn)需要記錄廣告商信息，增加廣告商實體。一個廣告商可以提供多條廣告，一條廣告只由一個廣告商提供。請根據(jù)該要求，對圖2-1進行修改，畫出修改后的實體間聯(lián)系和聯(lián)系的類型。 正確答案： 本題解析： 【問題1】 【問題2】 （1）編輯人員工號主鍵：廣告編號 （2）欄目名稱主鍵：主持人工號 （3）欄目名稱、廣告編號主鍵：欄目名稱、廣告編號 （4）欄目名稱、房間號、場務工號主鍵：欄目名稱、房間號、場務工號 【問題3】 本題考查數(shù)據(jù)庫設計

24、，設計考點有：數(shù)據(jù)庫的概念結構設計和邏輯結構設計。 【問題1】 由說明每檔欄目可以插播多條廣告，每條廣告可以在多檔欄目中插播，可知廣告和欄目之間是插播關系且為多比多；一個主持人可以主持一個欄目，一個欄目可以有多個主持人，故主持人和欄目之間是多比一的關系；一銷售檔欄目只會占用一個演播廳，但會使用多名場務來進行演出協(xié)調，故三者之間存在三元聯(lián)系，其中場務為多du。補充關系如圖1所示。 【問題2】 邏輯結構設計中，廣告實體中缺少編輯人員工號，主鍵為廣告編號；主持人實體與欄目實體為多對一的關系，故將欄目中主鍵欄目名稱加入到主持人實體中，主鍵為主持人工號；插播單為欄目實體和廣告實體這種多對多的關系

25、所派生出的實體，其中記錄了欄目和廣告的主鍵信息，故插播單中缺少欄目名稱和廣告編號信息，又因為題干說明電視臺根據(jù)欄目來插播廣告，因此主鍵為欄目名稱和廣告編號；調度單為場務、欄目和演播廳實體這種多對多的關系所派生的實體，故其記錄了欄目名稱，房間號，場務工號，主鍵為欄目名稱、房間號和場務工號。 【問題3】 因為一個廣告商可以提供多條廣告，一條廣告只能由一個廣告商提供，故廣告商和廣告之間的關系為一對多，其關系如圖所示。 5.現(xiàn)要求實現(xiàn)一個能夠自動生成求職簡歷的程序，簡歷的基本內容包括求職者的姓名、性別、年齡及工作經(jīng)歷。希望每份簡歷中的工作經(jīng)歷有所不同，并盡量減少程序

26、中的重復代碼。 現(xiàn)采用原型模式（Prototype）來實現(xiàn)上述要求，得到如圖6-1所示的類圖。 圖6-1類圖 【Java代碼】 public class WorkExperience(1)Cloneable{//工作經(jīng)歷 private String workDate; private String company; public Object clone（　?。﹞ (2); Obj.workDate=this.workDate; Opany=pany; return Obj; } //其余代碼省略 } public class Resume(3)Clonea

27、ble{//簡歷 private String name; private String sex; private String age; private WorkExperience work; public Resume(string name){ this.name=name; work=new WorkExperience（　　）; } private Resume(WorkExperience work){ this.work=(4); } public void?SetPersonInfo(string sex,string age){/*實現(xiàn)省略*/}

28、public void?SetWorkExperience(string workDate,string company){/*實現(xiàn)省略*/} public Object clone（　　）{ Resume Obj=(5); return Obj; } } Class WorkResume{ public static void?main（　?。﹞ Resume?a=new Resume(“張三”); a.SetPersonInfo(“男”,“29”)； a.SetWorkExperience(“1998-2000”,“XXX公司”); Resume?b=(6); b.

29、SetWorkExperience(“2001-2006”,“YYY公司”); } } 正確答案： 本題解析： （1）implements （2）WorkExperience obj=new Workexperience() （3）implements （4）(WorkExperience)work.Clone() （5）new Resume(this.work) （6）(Resume)a.Clone() 本題考查原型模型的概念及應用。 原型模型的主要思想：先借用已有系統(tǒng)作為原型模型，

30、通過“樣品”不斷改進，使得最后的產品就是用戶所需要的。原型模型通過向用戶提供原型獲取用戶的反饋，使開發(fā)出的軟件能夠真正反映用戶的需求。同時，原型模型采用逐步求精的方法完善原型，使得原型能夠“快速”開發(fā)，避免了像瀑布模型一樣在冗長的開發(fā)過程中難以對用戶的反饋作出快速的響應。相對瀑布模型而言，原型模型更符合人們開發(fā)軟件的習慣，使目前較流行的一種實用軟件生存期模型。 所有java類都繼承自java.lang.Object，而object類提供一個clone()方法，可以將一個java對象復制一份。因此在java中可以直接使用Object提供的clone()方法來實現(xiàn)對象的克隆。能夠實現(xiàn)克隆的jav

31、a類必須實現(xiàn)一個標識接口Cloneable，表示這個java支持復制。 題中WorkExperience類和Resume類需要實現(xiàn)Cloneable接口，故（1）和（3）為implements，WorkExperience中需要實現(xiàn)Clone()方法，并將自身復制一份，有下面代碼可知（2）為WorkExperience obj=new WorkExperience()。Resume類中的私有構造方法實現(xiàn)WorkExperience深復制，故（4）中為（WorkExperience）work.clone()，而Resume類中Clone方法實現(xiàn)自身的復制，故（5）中為new Resume(th

32、is.work)。 在main中實現(xiàn)Resume b對a的復制，故（6）中為(Resume)a.Clone()。 6.設有m臺完全相同的機器運行n個獨立的任務，運行任務i所需的時間為ti，要求確定一個調度方案，使得完成所有任務所需要的時間最短。 假設任務已經(jīng)按照其運行時間從大到小排序，算法基于最長運行時間作業(yè)優(yōu)先的策略，按順序先把每個任務分配到一臺機器上，然后將剩余的任務依次放入最先空閑的機器。 【C代碼】 下面是算法的C語言實現(xiàn)。 1.常量和變量說明 m：機器數(shù) n：任務數(shù) t[]：輸入數(shù)組，長度為n，下標從0開始，其中每個元素表示任務的運行時

33、間，下標從0開始。 s[][]：二維數(shù)組，長度為m*n，下標從0開始，其中元素s[i][j]表示機器i運行的任務j的編號。 d[]：數(shù)組，長度為m其中元素d[i]表示機器i的運行時間，下標從0開始。 count[]：數(shù)組，長度為m，下標從0開始，其中元素count[i]表示機器i運行的任務數(shù)。 i：循環(huán)變量。 j：循環(huán)變量。 k：臨時變量。 max：完成所有任務的時間。 min：臨時變量。 2.函數(shù)schedule void schedule（　　）{ int i,j,k,max=0; for(i=0;i＜m;i++){ d[i]=0; for(j=0;j＜n;j+

34、+){ s[i][j]=0; } } for(i=0;i＜m;i++){//分配前m個任務 s[i][0]=i; (1); count[i]=1; } for((2);i＜n;i++){//分配后n-m個任務 int min=d[0]; k=0; for(j=1;j＜m;j++){//確定空閑時間 if(min>d[j]){ min=d[j]; k=j;//機器k空閑 } } (3); count[k]=count[k]+1; d[k]=d[k]+t[i]; } for(i=0;i＜m;i++){//確定完成所有任務所需要的時間 if((4)){

35、 max=d[i]; } } } 【問題1】（8分） 根據(jù)說明和C代碼，填充C代碼中的空（1）~（4）。 【問題2】（2分） 根據(jù)說明和C代碼，該問題采用了（5）算法設計策略，時間復雜度（6）（用O符號表示） 【問題3】（5分） 考慮實例m=3（編號0~2），n=7（編號0~6），各任務的運行時間為{16，14，6，5，4，3，2}。則在機器0、1和2上運行的任務分別為（7）、（8）和（9）（給出任務編號）。從任務開始運行到完成所需的時間為（10）。 正確答案： 本題解析： 【問題1】

36、 （1）d[i]=t[i]（2）i=m（3）s[k][count[k]]=i（4）max＜d[i] 【問題2】 （5）貪心（6）O(mn) 【問題3】 （7）0（8）1、5（9）2、3、4、6（10）17 本題考查算法的設計和分析技術中的貪心算法。 貪婪算法（Greedy algorithm）是一種對某些求最優(yōu)解問題的更簡單、更迅速的設計技術。用貪婪法設計算法的特點是一步一步地進行，常以當前情況為基礎根據(jù)某個優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間，它采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求

37、問題簡化為一個規(guī)模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產生的全局解有時不一定是最優(yōu)的，所以貪婪法不要回溯。 【問題1】 根據(jù)上述思想和題中的說明，首先將s[][]和d[]數(shù)組初始化為0，然后要做的就是按要求“算法基于最長運行時間作業(yè)優(yōu)先的策略，按順序先把每個任務分配到一臺機器上”，可以推斷（1）處為d[i]=t[i]，此后需將剩下的n-m個任務按順序分配給空閑的機器，故（2）處將i初始化為以m為起始的任務，即i=m，（3）處所在的位置是分配后n-m個任務，在這個過程中，必須要對s矩陣的內容進行修改，但目前已經(jīng)出的代碼沒有這個

38、內容，所以此處必然是對s的修改。從對s矩陣的注釋可以了解到，s[i][j]表示機器i運行的任務j的編號，此時涉及任務的機器號為k，而待分配的任務i是機器的第count[k]個任務，即s[k][count[k]]=i，（4）處已經(jīng)完成了任務的運行，此處需要統(tǒng)計所有機器所運行任務的最長時間，對于每個機器i的運行時間為d[i]，存在d[i]大于當前的最大時間Max，就將當前機器的運行時間d[i]賦給Max，即Max＜d[i]。 【問題2】 根據(jù)以上分析，（5）處采用了貪心算法的策略，而時間復雜度由算法中的兩個嵌套for循環(huán)和兩個非嵌套for循環(huán)確定，即為O(mn)。 【問題3】 根據(jù)題中算法的思想將任務的前三個任務分給三個機器，再將接下來的任務分給最先空閑的機器，故可知機器0運行任務0，機器1運行任務1、5，機器3運行任務2、3、4、6；且運行的最長時間為17。