2014年上半年（下午）《軟件設(shè)計(jì)師》真題

《2014年上半年（下午）《軟件設(shè)計(jì)師》真題》由會(huì)員分享，可在線閱讀，更多相關(guān)《2014年上半年（下午）《軟件設(shè)計(jì)師》真題（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2014年上半年（下午）《軟件設(shè)計(jì)師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：6分 答題時(shí)間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：0次 問(wèn)答題 （共6題，共6分） 1.某實(shí)驗(yàn)室欲建立一個(gè)實(shí)驗(yàn)室環(huán)境監(jiān)測(cè)系統(tǒng)，能夠顯示實(shí)驗(yàn)室的溫度、濕度以及潔凈度等環(huán)境數(shù)據(jù)。當(dāng)獲取到最新的環(huán)境測(cè)量數(shù)據(jù)時(shí)，顯示的環(huán)境數(shù)據(jù)能夠更新。 現(xiàn)在采用觀察者(Observer)模式來(lái)開(kāi)發(fā)該系統(tǒng)。觀察者模式的類圖如圖5-1所示。 【C++代碼】 #include＜iostream> #include＜vector>

2、using namespace std; class Observer{ public: virtual void update(float temp,float humidity,float cleanness)=0; }; class Subject{ public: virtual void registerObserver(Observer*o)=0;//注冊(cè)對(duì)主題感興趣的觀察者 virtual void removeObserver(Observer*o)=0;//刪除觀察者 virtual void notifyObservers（　?。?0;//當(dāng)主題發(fā)生變化時(shí)

3、通知觀察者 }; class EnvironmentData:public（1）{ private: vector＜Observer*>observers; float temperature,humidity,cleanness; public: void registerObserver(Observer*o){observers.push_back(o);} void removeObserver(Observer*o){/*代碼省略*/} void notifyObservers（　?。﹞ for(vector＜Observer*>::const_iterator

4、it=observers.begin（　　）;it!=observers.end（　?。?it++) {（2）;} } Void measurementsChanged（　?。﹞（3）;} void setMeasurements(float temperature,float humidity,float cleanness){ this->temperature=temperature; this->humidity=humidity; this->cleanness=cleanness; （4）; } }; class CurrentConditionsDispla

5、y:public（5）{ private: float temperature,humidity,cleanness; Subject*envData; public: CurrentConditionsDisplay(Subject*envData){ this->envData=envData; （6）; } void update(float temperature,float humidity,float cleanness){this->temperature=temperature; this->humidity=humidity; this->cleanne

6、ss=cleanness; display（　?。? } void display（　?。﹞/*代碼省略*/} }; int main（　?。﹞ EnvironmentData*envData=new EnvironmentData（　　）; CurrentConditionsDisplay*currentDisplay=new CurrentConditionsDisplay(envData); envData->setMeasurements(80,65,30.4f); return 0; } 正確答案：

7、 本題解析： （1）Subject （2）(*it)->update(temperature,humidity,cleanness) （3）notifyObservers() （4）measurementsChanged() （5）Observer() （6）envData->registerObserver(this) EnvironmentData是環(huán)境數(shù)據(jù)，也就是我們要監(jiān)測(cè)的對(duì)象，即主題（Subject），因此（1）處為Subject。 （2）處為通知觀察者，因此遍歷觀察者容器，遍歷到一個(gè)觀察者對(duì)象，則更新該觀察者的數(shù)據(jù)，即調(diào)用觀察者的update

8、()方法。 當(dāng)環(huán)境數(shù)據(jù)變化時(shí)，需要通知觀察者，因此（4）處是調(diào)用環(huán)境變化方法measurementsChanged()，通過(guò)此方法通知觀察者更新數(shù)據(jù)，因此（3）處為notifyObservers()。 根據(jù)CurrentConditionsDisplay類中的update()方法可知：CurrentConditionsDisplay是個(gè)觀察者，因此（5）處為Observer （6）是將觀察者添加到主題中去。 2.某巴士維修連鎖公司欲開(kāi)發(fā)巴士維修系統(tǒng)，以維護(hù)與維修相關(guān)的信息。該系統(tǒng)的主要功能如下： 1）記錄巴士ID和維修問(wèn)題。巴士到車庫(kù)進(jìn)行維修，系統(tǒng)將

9、巴士基本信息和ID記錄在巴士列表文件中，將待維修機(jī)械問(wèn)題記錄在維修記錄文件中，并生成維修訂單。 2）確定所需部件。根據(jù)維修訂單確定維修所需部件，并在部件清單中進(jìn)行標(biāo)記。 3）完成維修。機(jī)械師根據(jù)維修記錄文件中的待維修機(jī)械問(wèn)題，完成對(duì)巴士的維修，登記維修情況；將機(jī)械問(wèn)題維修情況記錄在維修記錄文件中，將所用部件記錄在部件清單中，并將所用部件清單發(fā)送給庫(kù)存管理系統(tǒng)以對(duì)部件使用情況進(jìn)行監(jiān)控。巴士司機(jī)可查看已維修機(jī)械問(wèn)題。 4）記錄維修工時(shí)。將機(jī)械師提供的維修工時(shí)記錄在人事檔案中，將維修總結(jié)發(fā)送給主管進(jìn)行績(jī)效考核。 5）計(jì)算維修總成本。計(jì)算部件清單中實(shí)際所用部件、人事檔案中所用維修工時(shí)的總成本；

10、將維修工時(shí)和所用部件成本詳細(xì)信息給會(huì)計(jì)進(jìn)行計(jì)費(fèi)。 現(xiàn)采用結(jié)構(gòu)化方法對(duì)巴士維修系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。 【問(wèn)題1】（5分） 使用說(shuō)明中的詞語(yǔ)，給出圖1-1中的實(shí)體E1～E5的名稱。 【問(wèn)題2】（4分） 使用說(shuō)明中的詞語(yǔ)，給出圖1-2中的數(shù)據(jù)存儲(chǔ)D1～D4的名稱。 【問(wèn)題3】（3分） 說(shuō)明圖1-2中所存在的問(wèn)題。 【問(wèn)題4】（3分） 根據(jù)說(shuō)明和圖中術(shù)語(yǔ)，釆用補(bǔ)充數(shù)據(jù)流的方式，改正圖1-2中的問(wèn)題。要求給出所補(bǔ)充數(shù)據(jù)流的名稱、起點(diǎn)和終點(diǎn)。 正確答案：

11、 本題解析： 【問(wèn)題1】（5分） E1：巴士司機(jī) E2：機(jī)械師 E3：會(huì)計(jì) E4：主管 E5：庫(kù)存管理系統(tǒng) 【問(wèn)題2】（4分） D1：巴士列表文件 D2：維修記錄文件 D3：部件清單 D4：人事檔案 【問(wèn)題3】（3分） 處理3只有輸出數(shù)據(jù)流，沒(méi)有輸入數(shù)據(jù)流 D2、D3是黑洞，只有輸入的數(shù)據(jù)流，沒(méi)有輸入數(shù)據(jù)流 父子圖不平衡 圖1-2中沒(méi)有圖1-1中的數(shù)據(jù)流“維修情況” 【問(wèn)題4】（3分） 補(bǔ)充以下數(shù)據(jù)流： （1）名稱：待維修機(jī)械問(wèn)題；起點(diǎn)：D2；終點(diǎn)：3或完成維修。 （2）名稱：實(shí)際所用部件；起點(diǎn)：D3；終點(diǎn)：5或計(jì)算總成本。 （

12、3）名稱：維修情況；起點(diǎn)：E2；終點(diǎn)：3或完成維修 【問(wèn)題1】 根據(jù)第3)點(diǎn)：巴士司機(jī)可查看已維修機(jī)械問(wèn)題，可知E1為巴士司機(jī)；根據(jù)第3)點(diǎn)：機(jī)械師根據(jù)維修記錄文件中的待維修機(jī)械問(wèn)題，完成對(duì)巴士的維修，登記維修情況，可知E2為機(jī)械師；根據(jù)第5)點(diǎn)：將維修工時(shí)和所用部件成本詳細(xì)信息給會(huì)計(jì)進(jìn)行計(jì)費(fèi)，可知E3為會(huì)計(jì)；根據(jù)第4)點(diǎn)：將機(jī)械師提供的維修工時(shí)記錄在人事檔案中,將維修總結(jié)發(fā)送給主管進(jìn)行績(jī)效考核，可知E4為主管；根據(jù)第3)點(diǎn)：將所用部件清單發(fā)送給庫(kù)存管理系統(tǒng)以對(duì)部件使用情況進(jìn)行監(jiān)控，可知E5為庫(kù)存管理系統(tǒng)。 【問(wèn)題2】 根據(jù)第1)點(diǎn)：系統(tǒng)將巴士基本信息和ID記錄在巴士列表文件中，可知D

13、1為巴士列表文件；根據(jù)第1)點(diǎn)：將待維修機(jī)械問(wèn)題記錄在維修記錄文件中，并生成維修訂單，可知D2為維修記錄文件；根據(jù)第2)點(diǎn)：根據(jù)維修訂單確定維修所需部件，并在部件清單中進(jìn)行標(biāo)記，可知D3為部件清單；根據(jù)第4)點(diǎn)：將機(jī)械師提供的維修工時(shí)記錄在人事檔案中，可知D4為人事檔案。 【問(wèn)題3】 分析圖1-2可以發(fā)現(xiàn)： 處理3只有輸出數(shù)據(jù)流，沒(méi)有輸入數(shù)據(jù)流D2、D3是黑洞只有輸入的數(shù)據(jù)流，沒(méi)有輸出流，造成黑洞父子圖不平衡，在1-1和1-2中，1-1中從E2輸入的數(shù)據(jù)流維修工時(shí)/維修情況，在圖1-2中只有維修工時(shí)，造成父子圖不平衡 【問(wèn)題4】 3.某家電銷售電子商

14、務(wù)公司擬開(kāi)發(fā)一套信息管理系統(tǒng)，以方便對(duì)公司的員工、家電銷售、家電廠商和客戶等進(jìn)行管理。 【需求分析】 （1）系統(tǒng)需要維護(hù)電子商務(wù)公司的員工信息、客戶信息、家電信息和家電廠商信息等。員工信息主要包括：工號(hào)、姓名、性別、崗位、身份證號(hào)、電話、住址，其中崗位包括部門經(jīng)理和客服等。客戶信息主要包括：客戶ID、姓名、身份證號(hào)、電話、住址、賬戶余額。家電信息主要包括：家電條碼、家電名稱、價(jià)格、出廠日期、所屬?gòu)S商。家電廠商信息包括：廠商ID、廠商名稱、電話、法人代表信息、廠址。 （2）電子商務(wù)公司根據(jù)銷售情況，由部門經(jīng)理向家電廠商訂購(gòu)各類家電。每個(gè)家電廠商只能由一名部門經(jīng)理負(fù)責(zé)。 （3）客戶通過(guò)瀏覽

15、電子商務(wù)公司網(wǎng)站查詢家電信息，與客服溝通獲得優(yōu)惠后，在線購(gòu)買。 【概念模型設(shè)計(jì)】 根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（不完整）如圖2-1所示。 圖2-1實(shí)體聯(lián)系圖 【邏輯結(jié)構(gòu)設(shè)計(jì)】 根據(jù)概念模型設(shè)計(jì)階段完成的實(shí)體聯(lián)系圖，得出如下關(guān)系模式〔不完整）： 客戶（客戶ID、姓名、身份證號(hào)、電話、住址、賬戶余額） 員工（工號(hào)、姓名、性別、崗位、身份證號(hào)、電話、住址） 家電（家電條碼、家電名稱、價(jià)格、出廠日期、（1）） 家電廠商（廠商ID、廠商名稱、電話、法人代表信息、廠址、（2）） 購(gòu)買（訂購(gòu)單號(hào)、（3）、金額） 【問(wèn)題1】（6分） 補(bǔ)充圖2-1中的聯(lián)系和聯(lián)系的類型。

16、 【問(wèn)題2】（6分） 根據(jù)圖2-1，將邏輯結(jié)構(gòu)設(shè)計(jì)階段生成的關(guān)系模式中的空（1）～（3）補(bǔ)充完整。用下劃線指出“家電”、“家電廠商”和“購(gòu)買”關(guān)系模式的主鍵。 【問(wèn)題3】（3分） 電子商務(wù)公司的主營(yíng)業(yè)務(wù)是銷售各類家電，對(duì)賬戶有余額的客戶，還可以聯(lián)合第二方基金公司提供理財(cái)服務(wù)，為此設(shè)立客戶經(jīng)理崗位。客戶通過(guò)電子商務(wù)公司的客戶經(jīng)理和基金公司的基金經(jīng)理進(jìn)行理財(cái)。每名客戶只有一名客戶經(jīng)理和一名基金經(jīng)理負(fù)責(zé)，客戶經(jīng)理和基金經(jīng)理均可負(fù)責(zé)多名客戶。請(qǐng)根據(jù)該要求，對(duì)圖2-1進(jìn)行修改，畫出修改后的實(shí)體間聯(lián)系和聯(lián)系的類型。 正確答案：

17、 本題解析： 【問(wèn)題1】（6分） 【問(wèn)題2】（6分） （1）廠商ID （2）經(jīng)理工號(hào) （3）家電條碼，客戶ID，客服工號(hào) 家電關(guān)系的主鍵：家電條碼 家電廠商關(guān)系的主鍵：廠商ID 購(gòu)買關(guān)系的主鍵：訂購(gòu)單號(hào) 【問(wèn)題3】（3分） 根據(jù)實(shí)際生活經(jīng)驗(yàn)，不難得知家電廠商與家電之間的關(guān)系為一對(duì)多；家電與客戶之間的關(guān)系，此處的家電是指家電的類型，因此一種類型的家電可以被多個(gè)客戶購(gòu)買，一個(gè)客戶也可以購(gòu)買多種不同類型的家電，所以家電與客戶之間的關(guān)系為多對(duì)多； 根據(jù)題意：每名客戶只有一名客戶經(jīng)理和一名基金經(jīng)理負(fù)責(zé)客戶經(jīng)理和基金經(jīng)理均可負(fù)責(zé)多名客戶，可知客戶經(jīng)理與客戶

18、的關(guān)系是一對(duì)多，基金經(jīng)理與客戶的關(guān)系也是一對(duì)多。 根據(jù)題目中的需求分析，不難得出關(guān)系模式的答案。 4.某高校圖書館欲建設(shè)一個(gè)圖書館管理系統(tǒng)，目前已經(jīng)完成了需求分析階段的工作。功能需求均使用用例進(jìn)行描述，其中用例“借書（CheckOutBooks）”的詳細(xì)描述如下。 參與者：讀者（Patron）。 典型事件流： 1．輸入讀者ID； 2．確認(rèn)該讀者能夠借閱圖書，并記錄讀者ID； 3．輸入所要借閱的圖書ID； 4．根據(jù)圖書目錄中的圖書ID確認(rèn)該書可以借閱，計(jì)算歸還時(shí)間，生成借閱記錄； 5．通知讀者圖書歸還時(shí)間。 重復(fù)步驟3~5，直到讀者結(jié)束借閱圖書。

19、 備選事件流： 2a．若讀者不能借閱圖書，說(shuō)明讀者違反了圖書館的借書制度（例如，沒(méi)有支付借書費(fèi)用等） ①告知讀者不能借閱，并說(shuō)明拒絕借閱的原因； ②本用例結(jié)束。 4a．讀者要借閱的書無(wú)法外借 ①告知讀者本書無(wú)法借閱； ②回到步驟3。 說(shuō)明：圖書的歸還時(shí)間與讀者的身份有關(guān)。如果讀者是教師，圖書可以借閱一年；如果是學(xué)生，則只能借閱3個(gè)月。讀者ID中包含讀者身份信息。 現(xiàn)采用面向?qū)ο蠓椒ㄩ_(kāi)發(fā)該系統(tǒng)，得到如圖3-1所示的系統(tǒng)類模型（部分）；以及如圖3-2所示的系統(tǒng)操作“checkOut（bookID）（借書）”通信圖（或協(xié)作圖）。 【問(wèn)題1】（8分） 根據(jù)說(shuō)明中的描述，以

20、及圖3-1和圖3-2，給出圖3-1中C1-C4處所對(duì)應(yīng)的類名（類名使用圖3-1和圖3-2中給出的英文詞匯）。 【問(wèn)題2】（4分） 根據(jù)說(shuō)明中的描述，以及圖3-1和圖3-2，給出圖3-2中M1-M4處所對(duì)應(yīng)的方法名（方法名使用圖3-1和圖3-2中給出的英文詞匯）。 【問(wèn)題3】（3分） 用例“借書”的備選事件流4a中，根據(jù)借書制度來(lái)判定讀者能否借閱圖書。若圖書館的借書制度會(huì)不斷地?cái)U(kuò)充，并需要根據(jù)圖書館的實(shí)際運(yùn)行情況來(lái)調(diào)整具體使用哪些制度。為滿足這一要求，在原有類設(shè)計(jì)的基礎(chǔ)上，可以采用何種設(shè)計(jì)模式？簡(jiǎn)要說(shuō)明原因。 正確答案：

21、 本題解析： 【問(wèn)題1】（8分） C1：Patron C2：Book C3：Catalog C4：CheckoutSessionController 【問(wèn)題2】（4分） M1：getForCheckOut M2：isFaculty M3：circulates M4：recordBookLoan 【問(wèn)題3】（3分） 應(yīng)采用策略模式，策略模式定義了一系列算法，并將每個(gè)算法封裝起來(lái)，而且使它們可以相互替換。策略模式讓算法獨(dú)立于使用它們的客戶而變化。適用于需要在不同情況下使用不同的策略（算法），或者策略還可能在未來(lái)用其他方式來(lái)實(shí)現(xiàn)。 根據(jù)系統(tǒng)類模型，我們

22、可以各個(gè)類之間的關(guān)聯(lián)關(guān)系。 首先從類Accounts中的can CheckOut（patronID:string）方法，可以看出Accounts關(guān)聯(lián)Patron，因此圖中C1為Patron。 C1為Patron，則C1必會(huì)與書關(guān)聯(lián)，從C1中的recordBookLoad（b:C2），可以看出C1關(guān)聯(lián)C2。因此C2為Book。 C2為Book，根據(jù)系統(tǒng)操作check Out的通信圖，可以看出與Book關(guān)聯(lián)的是Catalog，因此C3為Catalog。 結(jié)合兩圖，則可以得出C4為CheckoutSessioncontroller。 結(jié)合典型事件流： 1.輸入讀者ID； 2.確認(rèn)該讀者

23、能夠借閱圖書，并記錄讀者ID； 以上兩步實(shí)際上就是判斷讀者是不是老師，也就是isFaculty()，因此M2為isFaculty()。 3.輸入所要借閱的圖書ID；對(duì)應(yīng)的操作就是M1：getforcheck（book ID）。 4.根據(jù)圖書目錄中的圖書ID確認(rèn)該書可以借閱，計(jì)算歸還時(shí)間，生成借閱記錄；對(duì)應(yīng)的操作就是M3：circulates()。 5.通知讀者圖書歸還時(shí)間。對(duì)應(yīng)的操作就是M4：recordBookLoan()。 5.某實(shí)驗(yàn)室欲建立一個(gè)實(shí)驗(yàn)室環(huán)境監(jiān)測(cè)系統(tǒng)，能夠顯示實(shí)驗(yàn)室的溫度、濕度以及潔凈度等環(huán)境數(shù)據(jù)。當(dāng)獲取到最新的環(huán)境測(cè)量數(shù)據(jù)時(shí)，顯示的環(huán)

24、境數(shù)據(jù)能夠更新。 現(xiàn)在采用觀察者（Observer）模式來(lái)開(kāi)發(fā)該系統(tǒng)。觀察者模式的類圖如圖6-1所示。 【Java代碼】 import java.util.*; interface Observer{ public void update(float temp,float humidity,float cleanness); } interface Subject{ public void registerObserver(Observer o);//注冊(cè)對(duì)主題感興趣的觀察者 public void removeObserver(Observer o);//刪除觀察者

25、public void notifyObservers（　　）;//當(dāng)主題發(fā)生變化時(shí)通知觀察者 } class EnvironmentData implements（1）{ private ArrayList observers; private float temperature,humidity,cleanness; public EnvironmentData（　?。﹞observers=new ArrayList（　　）;} public void registerObserver(Observer o){observers.add(o);} public void re

26、moveObserver(Observer o){/*代碼省略*/} public void notifyObservers（　?。﹞ for(int i=0;i＜o(jì)bservers.size（　　）;i++){ Observer observer=(Observer)observers.get(i); （2）; } } public void measurementsChanged（　?。﹞（3）;} public void setMeasurements(float temperature,float humidity,float cleanness){ this.tem

27、perature=temperature; this.humidity=humidity; this.cleanness=cleanness; （4）; } } class CurrentConditionsDisplay implements（5）{ private float temperature; private float humidity; private float cleanness; private Subject envData; public CurrentConditionsDisplay(Subject envData){ this.envDa

28、ta=envData; （6）; } public void update(float temperature,float humidity,float cleanness){ this.temperature=temperature; this.humidity=humidity; this.cleanness=cleanness; display（　　）; } public void display（　?。﹞/*代碼省略*/} } class EnvironmentMonitor{ public static void main(String[]args){ En

29、vironmentData envData=new EnvironmentData（　?。? CurrentConditionsDisplay currentDisplay=new CnrrentConditionsDisplay(envData); envData.setMeasurements(80,65,30.4f); } } 正確答案： 本題解析： （1）Subject （2）observer.update(temperature,humidity,cleanness) （3）not

30、ifyObservers() （4）measurementsChanged() （5）Observer （6）envData.registerObserver(this) EnvironmentData是環(huán)境數(shù)據(jù)，也就是我們要監(jiān)測(cè)的對(duì)象，即主題（Subject），因此（1）處為Subject。 （2）處為通知觀察者，因此遍歷觀察者容器，遍歷到一個(gè)觀察者對(duì)象，則更新該觀察者的數(shù)據(jù)，即調(diào)用觀察者的update()方法。 當(dāng)環(huán)境數(shù)據(jù)變化時(shí)，需要通知觀察者，因此（4）處是調(diào)用環(huán)境變化方法measurementsChanged()，通過(guò)此方法通知觀察者更新數(shù)據(jù)，因此（3）處為notifyOb

31、servers()。 根據(jù)CurrentConditionsDisplay類中的update()方法可知：CurrentConditionsDisplay是個(gè)觀察者，因此（5）處為Observer （6）是將觀察者添加到主題中去。 6.采用歸并排序?qū)個(gè)元素進(jìn)行遞增排序時(shí)，首先將n個(gè)元素的數(shù)組分成各含n/2個(gè)元素的兩個(gè)子數(shù)組，然后用歸并排序?qū)蓚€(gè)子數(shù)組進(jìn)行遞歸排序，最后合并兩個(gè)已經(jīng)排好序的子數(shù)組得到排序結(jié)果。 下面的C代碼是對(duì)上述歸并算法的實(shí)現(xiàn)，其中的常量和變量說(shuō)明如下： arr：待排序數(shù)組 p,q,r：一個(gè)子數(shù)組的位置從p到q，另一個(gè)子數(shù)組的位置

32、從q+1到r begin,end：待排序數(shù)組的起止位置 left,right：臨時(shí)存放待合并的兩個(gè)子數(shù)組 n1,n2：兩個(gè)子數(shù)組的長(zhǎng)度 i,j,k：循環(huán)變量 mid：臨時(shí)變量 【C代碼】 #inciude＜stdio.h> #inciude＜stdlib.h> #define MAX 65536 void merge(int arr[],int p,int q,int r){ int*left,*right; int n1,n2,i,j,k; n1=q-p+1; n2=r-q; if((left=(int*)malloc((n1+1)*sizeof(int)))=

33、NULL){ perror("malloc error"); exit(1); } if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL){ perror("malloc error"); exit(1); } for(i=0;i＜n1;i++){ left[i]=arr[p+i]； } left[i]=MAX； for(i=0;i＜n2;i++){ right[i]=arr[q+i+1] } right[i]=MAX; i=0;j=0; for(k=p;（1）;k++){ if(left[i]>right[j])

34、{ （2）; j++; }else{ arr[k]=left[i]； i++； } } } void mergeSort(int arr[],int begin,int end){ int mid; if(（3）){ mid=(begin+end)/2; mergeSort(arr,begin,mid); （4）; merge(arr,begin,mid,end); } } 【問(wèn)題1】（8分） 根據(jù)以上說(shuō)明和C代碼，填充1-4。 【問(wèn)題2】（5分） 根據(jù)題干說(shuō)明和以上C代碼，算法采用了（5）算法設(shè)計(jì)策略。 分析時(shí)間復(fù)雜度時(shí)，列出其遞歸式位（6），解出

35、漸進(jìn)時(shí)間復(fù)雜度為（7）（用O符號(hào)表示）?？臻g復(fù)雜度為（8）（用O符號(hào)表示）。 【問(wèn)題3】（2分） 兩個(gè)長(zhǎng)度分別為n1和n2的已經(jīng)排好序的子數(shù)組進(jìn)行歸并，根據(jù)上述C代碼，則元素之間比較次數(shù)為（9）。 正確答案： 本題解析： 【問(wèn)題1】（8分） （1）k＜=r （2）arr[k]=right[j] （3）begin＜end （4）mergeSort(arr,mid+1,end) 【問(wèn)題2】（5分） （5）分治 （6）T(n)=2T(n/2)+n （7）O(nlgn) （8）O(n)

36、【問(wèn)題3】（2分） （9）n1+n2 根據(jù)題目中的參數(shù)說(shuō)明，void merge(int arr[],int p,int q,int r)是將數(shù)組arr[p...q]和數(shù)組arr[q+1...r]進(jìn)行合并成一個(gè)排序的數(shù)組，因此合并之后數(shù)組的長(zhǎng)度為r-q+1>0，k=q，也就是k＜=r或k＜r+1；數(shù)組arr存入子數(shù)組arr[p...q]、arr[q+1...r]當(dāng)前進(jìn)行比較的最小值，因此當(dāng)left[i]>right[j]時(shí)，數(shù)組arr中存入right[i]，即arr[k]=right[j]； void mergeSort(int arr[],int begin,int end)是指將數(shù)組

37、arr遞歸進(jìn)行劃分，直到分成多個(gè)由一個(gè)元素組成的子數(shù)組時(shí)，停止劃分，此時(shí)也就是begin==end，因此（3）處為begin＜end，也就是只要begin!=end則繼續(xù)劃分。劃分的時(shí)候每次分成兩半，兩半再分別遞歸，因此mergeSort(arr,begin,mid);mergeSort(arr,mid+1,end); 很明顯歸并排序使用的分治算法，每次將數(shù)組分割成兩個(gè)小的子數(shù)組。 假設(shè)對(duì)n個(gè)元素的數(shù)組進(jìn)行歸并排序時(shí)間復(fù)雜度為T(n)，則分成兩個(gè)小的子數(shù)組后分別進(jìn)行排序所需的時(shí)間為T(n/2)，兩個(gè)子數(shù)組則時(shí)間復(fù)雜度為2T(n/2)，再加上歸并的時(shí)間n，即可得出答案歸并排序的時(shí)間復(fù)雜度為O(nlgn)，因?yàn)樵跉w并過(guò)程中，需要借助left和right兩個(gè)數(shù)組輔助，因此空間復(fù)雜度為O(n)。