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

1、2014年下半年（下午）《軟件設(shè)計(jì)師》真題 注意：圖片可根據(jù)實(shí)際需要調(diào)整大小 卷面總分：6分 答題時(shí)間：240分鐘 試卷題量：6題 練習(xí)次數(shù)：0次 問答題 （共6題，共6分） 1.某燈具廠商欲生產(chǎn)一個燈具遙控器，該遙控器具有7個可編程的插槽，每個插槽都有開關(guān)按鈕，對應(yīng)著一個不同的燈。利用該遙控器能夠統(tǒng)一控制房間中該廠商所有品牌燈具的開關(guān)，現(xiàn)采用Command（命令）模式實(shí)現(xiàn)該遙控器的軟件部分。Command模式的類圖如圖5-1所示。 【C++代碼】 class Light{ public: L

2、ight(string name){/*代碼省略*/} void on（　?。﹞/*代碼省略*/}//開燈 void off（　　）{/*代碼省略*/}//關(guān)燈 }; class Command{ public: （1）; }； class LightOnCommand:public Command{//開燈命令 private: Light*light; public: LightOnCommand(Light*light){this->light=light;} void execute（　?。﹞（2）;} }; class LightOffCommand:p

3、ublic Command{//關(guān)燈命令 private: Light*light; public: LightOffCommand(Light*light){this->light=light;} void execute（　?。﹞（3）;} }; class RemoteControl{//遙控器 private: Command*onCommands[7]; Command*offCommands[7]; public: RemoteControl（　?。﹞/*代碼省略*/} void setCommand(int slot,Command*onCommand,

4、Command*offCommand){ （4）=onCommand; （5）=offCommand; } void onButtonWasPushed(int slot){（6）;} void offButtonWasPushed(int slot){（7）;} }; int main（　?。﹞ RemoteControl*remoteControl=new RemoteControl（　　）; Light*livingRoomLight=new Light("Living Room"); Light*kitchenLight=new Light("kitchen");

5、 LightOnCommand*livingRoomLightOn=new LightOnCommand(livingRoomLight); LightOffCommand*livingRoomLightOff=newLightOffCommand(livingRoomLight); LightOnCommand*kitchenLightOn=new LightOnCommand(kitchenLight); LightOffCommand*kitchenLightOff=new LightOffCommand(kitchenLight); remoteControl->setComm

6、and(0,livingRoomLightOn,livingRoomLightOff); remoteControl->setCommand(1,kitchenLightOn,kitchenLightOff); remoteControl->onButtonWasPushed(0); remoteControl->offButtonWasPushed(0); remoteControl->onButtonWasPushed(1); remoteControl->offButtonWasPushed(1); /*其余代碼省略*/ return 0; }

7、 正確答案： 本題解析： （1）virtual void execute()=0 （2）light->on() （3）light->off() （4）onCommands[slot] （5）offCommands[slot] （6）onCommands[slot]->execute() （7）offCommands[slot]->execute() 本題考查設(shè)計(jì)模式的實(shí)現(xiàn)，難度較小。根據(jù)類圖和已有代碼可寫出空缺的代碼，書寫方式注意java和C++的區(qū)別即可。 Command類為所有的命令聲明了一個接口，因此需要一個

8、純虛函數(shù)，這個函數(shù)根據(jù)下面的子類可以看到，應(yīng)該為execute()，因此第一空填寫virtual void execute()=0； （2）和（3）定義了開燈、關(guān)燈action，因此，分別填寫（2）light->on()（3）light->off()； （4）（5）分別設(shè)置“開燈”命令對象、“關(guān)燈”命令對象，因此分別填寫（4）onCommands[slot]（5）offCommands[slot]； （6）（7）分別完成對開燈、關(guān)燈命令對象的execute方法的調(diào)用，因此分別填寫（6）onCommands[slot]->execute() （7）offCommands[slot]->e

9、xecute()。 2.某大型披薩加工和銷售商為了有效管理生產(chǎn)和銷售情況，欲開發(fā)一披薩信息系統(tǒng)，其主要功能如下： （1）銷售。處理客戶的訂單信息，生成銷售訂單，并將其記錄在銷售訂單表中。銷售訂單記錄了訂購者、所訂購的披薩、期望的交付日期等信息。 （2）生產(chǎn)控制。根據(jù)銷售訂單以及庫存的披薩數(shù)量，制定披薩生產(chǎn)計(jì)劃（包括生產(chǎn)哪些披薩、生產(chǎn)順序和生產(chǎn)量等），并將其保存在生產(chǎn)計(jì)劃表中。 （3）生產(chǎn)。根據(jù)生產(chǎn)計(jì)劃和配方表中的披薩配方，向庫存發(fā)出原材料申領(lǐng)單，將制作好的披薩的信息存入庫存表中，以便及時(shí)進(jìn)行交付。 （4）采購。根據(jù)所需原材料及庫存量，確定采購數(shù)量，向供應(yīng)

10、商發(fā)送采購訂單，并將其記錄在采購訂單表中；得到供應(yīng)商的供應(yīng)量，將原材料數(shù)量記錄在庫存表中，在采購訂單表中標(biāo)記已完成采購的訂單。 （5）運(yùn)送。根據(jù)銷售訂單將披薩交付給客戶，并記錄在交付記錄表中。 （6）財(cái)務(wù)管理。在披薩交付后，為客戶開具費(fèi)用清單，收款并出具收據(jù)；依據(jù)完成的采購訂單給供應(yīng)商支付原材料費(fèi)用并出具支付細(xì)節(jié)；將收款和支付記錄存入收支記錄表中。 （7）存儲。檢查庫存的原材料、拔薩和未完成訂單，確定所需原材料。 現(xiàn)采用結(jié)構(gòu)化方法對披薩信息系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。 圖1-1上下文數(shù)據(jù)流圖 圖1-2 0層數(shù)據(jù)流圖

11、【問題1】（4分） 根據(jù)說明中的詞語，給出圖1-1中的實(shí)體E1～E2的名稱。 【問題2】（5分） 根據(jù)說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1～D5的名稱。 【問題3】（6分） 根據(jù)說明和圖中詞語，補(bǔ)充圖1-2中缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)。 正確答案： 本題解析： 【問題1】 E1：客戶；E2：供應(yīng)商 【問題2】 D1：銷售訂單表；D2：庫存表；D3：生產(chǎn)計(jì)劃表；D4：配方表；D5：采購訂單表 【問題3】 本題考查數(shù)據(jù)流圖（DFD）應(yīng)用于采用結(jié)構(gòu)化方法進(jìn)行系統(tǒng)分析與設(shè)計(jì)，是比較

12、傳統(tǒng)的題目，要求考生細(xì)心分析題目中所描述的內(nèi)容。 DFD是一種便于用戶理解、分析系統(tǒng)數(shù)據(jù)流程的圖形化建模工具，是系統(tǒng)邏輯模型的重要組成部分。 【問題1】 本問題考查上下文數(shù)據(jù)流圖。上下文數(shù)據(jù)流圖一般用來建立初始的項(xiàng)目范圍的，將待開發(fā)系統(tǒng)看作一個加工，因此圖中只有唯一的一個處理和一些外部實(shí)體，以及這兩者之間的輸入輸出數(shù)據(jù)流。題目要求根據(jù)描述來確定圖中的外部實(shí)體。分析題目中的描述，并結(jié)合已經(jīng)在上下文數(shù)據(jù)流圖中給出的數(shù)據(jù)流進(jìn)行分析。從中可以看出，與系統(tǒng)的交互者包括客戶和供應(yīng)商。其中，客戶下訂單，將訂單信息交付給系統(tǒng)，系統(tǒng)向供應(yīng)商發(fā)送采購訂單，可知E1為客戶，E2為供應(yīng)商。 【問題2】 本問

13、題考查0層DFD中數(shù)據(jù)存儲的確定。根據(jù)說明中描述和圖中數(shù)據(jù)流內(nèi)容： （1）銷售。處理客戶的訂單信息，生成銷售訂單，并將其記錄在銷售訂單表中。銷售訂單記錄了訂購者、所訂購的披薩、期望的交付日期等信息，因此D1是銷售訂單表； （2）生產(chǎn)控制。根據(jù)銷售訂單以及庫存的披薩數(shù)量，制定披薩生產(chǎn)計(jì)劃（包括生產(chǎn)哪些披薩、生產(chǎn)順序和生產(chǎn)量等），并將其保存在生產(chǎn)計(jì)劃表中，因此D3為生產(chǎn)計(jì)劃表； （3）生產(chǎn)。根據(jù)生產(chǎn)計(jì)劃和配方表中的披薩配方，向庫存發(fā)出原材料申領(lǐng)單，將制作好的披薩的信息存入庫存表中，以便及時(shí)進(jìn)行交付，因此D2為庫存表，D4為配方表； （4）采購。根據(jù)所需原材料及庫存量，確定采購數(shù)量，向供應(yīng)商

14、發(fā)送采購訂單，并將其記錄在采購訂單表中；得到供應(yīng)商的供應(yīng)量，將原材料數(shù)量記錄在庫存表中，在采購訂單表中標(biāo)記已完成采購的訂單，因此D5為采購訂單表。 【問題3】 本問題考查0層DFD中缺失的處理和數(shù)據(jù)流。從說明中的描述和圖1-2可知，財(cái)務(wù)管理需依據(jù)完成的采購訂單給供應(yīng)商支付原材料費(fèi)用并出具支付細(xì)節(jié)；運(yùn)送的主要作用為根據(jù)銷售訂單將披薩交付給客戶，并記錄在交付記錄表中；生產(chǎn)計(jì)劃按生產(chǎn)計(jì)劃表進(jìn)行生產(chǎn)；庫存表傳輸庫存量進(jìn)行采購；采購?fù)陚鬏斣牧蠑?shù)量給庫存表；銷售訂單表存儲未完成訂單。 3.某集團(tuán)公司在全國不同城市擁有多個大型超市，為了有效管理各個超市的業(yè)務(wù)工作，需要構(gòu)

15、建一個超市信息管理系統(tǒng)。 【需求分析結(jié)果】 （1）超市信息包括：超市名稱、地址、經(jīng)理和電話，其中超市名稱唯一確定超市關(guān)系的每一個元組。每個超市只有一名經(jīng)理。 （2）超市設(shè)有計(jì)劃部、財(cái)務(wù)部、銷售部等多個部門，每個部門只有一名部門經(jīng)理，有多名員工，每個員工只屬于一個部門。部門信息包括：超市名稱、部門名稱、部門經(jīng)理和聯(lián)系電話。超市名稱、部門名稱唯一確定部門關(guān)系的每一個元組。 （3）員工信息包括：員工號、姓名、超市名稱、部門名稱、職位、聯(lián)系方式和工資。其中，職位信息包括：經(jīng)理、部門經(jīng)理、業(yè)務(wù)員等。員工號唯一確定員工關(guān)系的每一個元組。 （4）商品信息包括：商品號、商品名稱、型號、單價(jià)和數(shù)量。商

16、品號唯一確定商品關(guān)系的每一個元組。一名業(yè)務(wù)員可以負(fù)責(zé)超市內(nèi)多種商品的配給，一種商品可以由多名業(yè)務(wù)員配給。 【概念模型設(shè)計(jì)】 根據(jù)需求分析階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖和關(guān)系模式（不完整）如下： 圖2-1實(shí)體聯(lián)系圖 【關(guān)系模式設(shè)計(jì)】 超市（超市名稱，經(jīng)理，地址，電話） 部門（（a），部門經(jīng)理，聯(lián)系電話） 員工（（b），姓名，聯(lián)系方式，職位，工資） 商品（商品號，商品名稱，型號，單價(jià)，數(shù)量） 配給（（c），配給時(shí)間，配給數(shù)量，業(yè)務(wù)員） 【問題1】（4分） 根據(jù)問題描述，補(bǔ)充四個聯(lián)系，完善圖1-1的實(shí)體聯(lián)系圖。聯(lián)系名可用聯(lián)系1、聯(lián)系2、聯(lián)系3和聯(lián)系4代替，聯(lián)系的類型分為1

17、:1、1:n和m:n（或1:1、1:*和*:*）。 【問題2】（7分） （1）根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空（a）～（c）補(bǔ)充完整； （2）給出部門和配給關(guān)系模式的主鍵和外鍵。 【問題3】（4分） （1）超市關(guān)系的地址可以進(jìn)一步分為郵編、省、市、街道，那么該屬性是屬于簡單屬性還是復(fù)合屬性？請用100字以內(nèi)文字說明。 （2）假設(shè)超市需要增設(shè)一個經(jīng)理的職位，那么超市與經(jīng)理之間的聯(lián)系類型應(yīng)修改為（d），超市關(guān)系應(yīng)修改為（e）。 正確答案： 本題解析： 【問題1】 【問題2】 （a）超市名

18、稱，部門名稱主鍵：（超市名稱，部門名稱）外鍵：超市名稱，部門經(jīng)理 （b）員工號，超市名稱，部門名稱 （c）商品號主鍵：（商品號，業(yè)務(wù)員，配給時(shí)間）外鍵：業(yè)務(wù)員，商品號 【問題3】 （1）超市關(guān)系中的地址屬于復(fù)合屬性。所謂復(fù)合屬性就是指屬性中含有多種信息，可以進(jìn)一步拆分的屬性，地址可以拆分成多個簡單屬性，符合這一特征。 （2）（d）1:n（e）超市名稱，經(jīng)理，電話 注：本題問題（e）并不嚴(yán)謹(jǐn)，針對（1）地址屬于復(fù)合屬性，超市關(guān)系應(yīng)修改為（超市名稱，經(jīng)理，電話），其中超市名稱和經(jīng)理作為組合主鍵，另外新增地址關(guān)系模式。 針對（2）假設(shè)超市與經(jīng)理1:m的聯(lián)系，也可以將聯(lián)系歸并到經(jīng)理端，即

19、超市關(guān)系修改為（超市名稱，地址，電話），另外新增經(jīng)理關(guān)系模式。 本題考查數(shù)據(jù)庫設(shè)計(jì)，屬于比較傳統(tǒng)的題目，考查點(diǎn)也與往年類似。 【問題1】 本問題考查數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計(jì)，題目要求補(bǔ)充完整實(shí)體聯(lián)系圖中的聯(lián)系和聯(lián)系的類型。配給有商品號的屬性，其主鍵可為商品號，業(yè)務(wù)員，配給時(shí)間，外鍵有業(yè)務(wù)員，商品號。 根據(jù)題目的需求描述可知，每個超市只有一名經(jīng)理；超市設(shè)有計(jì)劃部、財(cái)務(wù)部、銷售部等多個部門，每個部門只有一名部門經(jīng)理，有多名員工，每個員工只屬于一個部門。一名業(yè)務(wù)員可以負(fù)責(zé)超市內(nèi)多種商品的配給，一種商品可以由多名業(yè)務(wù)員配給。故答案如上所示。 【問題2】 本問題考查數(shù)據(jù)庫的邏輯結(jié)構(gòu)設(shè)計(jì)，題目要求

20、補(bǔ)充完整各關(guān)系模式，并給出部門和配給關(guān)系模式的主鍵和外鍵。 根據(jù)實(shí)體聯(lián)系圖和需求描述，部門有超市名稱和部門名稱的屬性，而超市名稱和部門名稱均唯一可作為主鍵。超市名稱和部門經(jīng)理可作為外鍵。員工還有員工號、超市名稱和部門名稱等屬性；配給關(guān)系中也需要商品號這一屬性且為主鍵，主鍵包括了商品號、業(yè)務(wù)員和配給時(shí)間，外鍵有業(yè)務(wù)員和商品號。 【問題3】 本問題考查的是數(shù)據(jù)庫的概念結(jié)構(gòu)設(shè)計(jì)，根據(jù)新增的需求增加實(shí)體聯(lián)系圖中的實(shí)體的聯(lián)系和聯(lián)系的類型。 根據(jù)問題描述，超市關(guān)系的地址可以進(jìn)一步分為郵編、省、市、街道，那么該屬性是屬于復(fù)合屬性，所謂復(fù)合屬性就是指屬性中含有多種信息，可以進(jìn)一步拆分的屬性，地址可以拆

21、分成多個簡單屬性，符合這一特征。超市增設(shè)一個經(jīng)理的職位，則超市和經(jīng)理的聯(lián)系類型變?yōu)?對多，即1:n。 本題問題（e）并不嚴(yán)謹(jǐn)，針對（1）地址屬于復(fù)合屬性，超市關(guān)系應(yīng)修改為（超市名稱，經(jīng)理，電話），其中超市名稱和經(jīng)理作為組合主鍵，另外新增地址關(guān)系模式。 針對（2）假設(shè)超市與經(jīng)理1:m的聯(lián)系，也可以將聯(lián)系歸并到經(jīng)理端，即超市關(guān)系修改為（超市名稱，地址，電話），另外新增經(jīng)理關(guān)系模式。 4.某公司欲開發(fā)一個管理選民信息的軟件系統(tǒng)。系統(tǒng)的基本需求描述如下： （1）每個人（Person）可以是一個合法選民（Eligible）或者無效的選民(Ineligible)。

22、（2）每個合法選民必須通過該系統(tǒng)對其投票所在區(qū)域（即選區(qū)，Riding）進(jìn)行注冊（Registration）。每個合法選民僅能注冊一個選區(qū)。 （3）選民所屬選區(qū)由其居住地址（Address）決定。假設(shè)每個人只有一個地址，地址可以是鎮(zhèn)（Town）或者城市（City）。 （4）某些選區(qū)可能包含多個鎮(zhèn)；而某些較大的城市也可能包含多個選區(qū)。 現(xiàn)采用面向?qū)ο蠓椒▽υ撓到y(tǒng)進(jìn)行分析與設(shè)計(jì)，得到如圖1-1所示的初始類圖。 【問題1】（8分） 根據(jù)說明中的描述，給出圖1-1中C1～C4所對應(yīng)的類名（類名使用說明中給出的英文詞匯）。 【問題2】（3分） 根據(jù)說明中的描述，給出圖1-1中M1～M6

23、處的多重度。 【問題3】（4分） 現(xiàn)對該系統(tǒng)提出了以下新需求： （1）某些人擁有在多個選區(qū)投票的權(quán)利，因此需要注冊多個選區(qū)； （2）對于滿足（1）的選民，需要劃定其“主要居住地”，以確定他們應(yīng)該在哪個選區(qū)進(jìn)行投票。 為了滿足上述需求，需要對圖1-1所示的類圖進(jìn)行哪些修改？請用100字以內(nèi)文字說明。 正確答案： 本題解析： 【問題1】 C1：Address?C2：Riding?C3：Ineligible?C4：Eligible 【問題2】 M1：1，M2：*，M3：*，M4：1，M5：*，

24、M6：1。 【問題3】 （1）將M1修改為1..*，在Registration類中增加address屬性，指明注冊時(shí)使用的是哪個地址。 （2）增加一個類“主要居住地”，作為類Address的子類；類Person與類"主要居住地"之間具有關(guān)系聯(lián)系，且每個人只有一個主要居住地。 本題考查在面向?qū)ο蠓治雠c設(shè)計(jì)過程中，如何利用類圖描述系統(tǒng)需求模型及設(shè)計(jì)模型。考試需要理解面向?qū)ο蠓椒ǖ南嚓P(guān)概念和思想，并熟悉UML的語法及應(yīng)用。類圖及用例圖是考試題中最多出現(xiàn)的兩種UML模型。 （1）由需求1可知，Person下面只有Ineligible和Eligible，C3為孤立點(diǎn)，C4還與其他類有關(guān)系，故C

25、3為Ineligible，C4為Eligible。Person與C1的關(guān)系是lives at，故C1應(yīng)為Address，C2為Riding。 （2）Address與Person應(yīng)為1對多，故M1為1，M2為*。Eligible與Riding的關(guān)系應(yīng)為多對1，則M3應(yīng)為*，M4應(yīng)為1。一個選區(qū)包含多個鎮(zhèn)，每個鎮(zhèn)多個地址，故Address與Riding的關(guān)系為多對1。 5.某燈具廠商欲生產(chǎn)一個燈具遙控器，該遙控器具有7個可編程的插槽，每個插槽都有開關(guān)燈具的開關(guān)，現(xiàn)采用Command（命令）模式實(shí)現(xiàn)該遙控器的軟件部分。Command模式的類圖如圖6-1所示。

26、【Java代碼】 class Light{ public Light（　　）{} public Light(String name){/*代碼省略*/} public void on（　?。﹞/*代碼省略*/}//開燈 public void off（　?。﹞/*代碼省略*/}//關(guān)燈 //其余代碼省略 } （1）{ public void execute（　　）; } class LightOnCommand implements Command{//開燈命令 Light light; public LightOnCommand(Light light){this.

27、light=light;} public void execute（　　）{（2）;} } class LightOffCommand implements Command{//關(guān)燈命令 Light light; public LightOffCommand(Light light){this.light=light;} public void execute（　?。﹞（3）;} } class RemoteControl{//遙控器 Command[]onCommands=new Command[7]; Command[]offCommands=new Command[7

28、]; public RemoteControl（　?。﹞/*代碼省略*/} public void setCommand(int slot,Command onCommand,Command offCommand){ （4）=onCommand; （5）=offCommand; } public void onButtonWasPushed(int slot){ （6）; } public void offlButtonWasPushed(int slot){ （7）; } } class RemoteLoader{ public static void main(

29、String[]args){ RemoteControl remoteControl=new RemoteControl（　?。? Light livingRoomLight=new Light("Living Room"); Light kitchenLight=new Light("kitchen"); LightOnCommand livingRoomLightOn=new LightOnCommand(livingRoomLight); LightOffCommand livingRoomLightOff=new LightOffCommand(livingRoomLight

30、); LightOnCommand kitchenLightOn=new LightOnCommand(kitchenLight); LightOffCommand kitchenLightOff=new LightOffCommand(kitchenLight); remoteControl.setCommand(0,livingRoomLightOn,livingRoomLightOff); remoteControl.setCommand(1,kitchenLightOn,kitchenLightOff); remoteControl.onButtonWasPushed(0);

31、 remoteControl.offButtonWasPushed(0); remoteControl.onButtonWasPushed(1); remoteControl.offButtonWasPushed(1); } } 正確答案： 本題解析： （1）interface Command （2）light.on() （3）light.off() （4）onCommands[slot] （5）offCommands[slot] （6）onCommands[slot].execut

32、e() （7）offCommands[slot].execute() 本題考察設(shè)計(jì)模式的實(shí)現(xiàn)，難度較小。根據(jù)類圖和已有代碼可寫出空缺的代碼. （1）是Command接口的實(shí)現(xiàn)，應(yīng)該填寫interface Command； （2）和（3）定義了開燈、關(guān)燈action，因此，分別填寫（2）light->on()（3）light->off()； （4）（5）分別設(shè)置“開燈”命令對象、“關(guān)燈”命令對象，因此分別填寫（4）onCommands[slot]（5）offCommands[slot]； （6）（7）分別完成對開燈、關(guān)燈命令對象的execute方法的調(diào)用，因此分別填寫（6）onCom

33、mands[slot].execute() （7）offCommands[slot].execute()。 6.計(jì)算一個整數(shù)數(shù)組a的最長遞增子序列長度的方法描述如下： 假設(shè)數(shù)組a的長度為n，用數(shù)組b的元素b[i]記錄以a[i](0≤i＜n)為結(jié)尾元素的最長遞增予序列的長度，則數(shù)組a的最長遞增子序列的長度為；其中b[i]滿足最優(yōu)子結(jié)構(gòu)，可遞歸定義為： 【C代碼】 下面是算法的C語言實(shí)現(xiàn)。 （1）常量和變量說明 a：長度為n的整數(shù)數(shù)組，待求其最長遞增子序列 b：長度為n的數(shù)組，b[i]記錄以a[i](0≤i＜n)為結(jié)尾元素的最長遞增子序列的長 度

34、，其中0≤i＜n len：最長遞增子序列的長度 i,j：循環(huán)變量 temp：臨時(shí)變量 （2）C程序 #include＜stdio.h> int maxL(int*b,int n){ int i,temp=0; for(i=0;i＜n;i++){ if(b[i]>temp) temp=b[i]; } return temp; } int main（　　）{ int n,a[100],b[100],i,j,len; scanf("%d",&n); for(i=0;i＜n;i++){ scanf("%d",&a[i]); } (1); for(i=1;i＜n

35、;i++){ for(j=0,len=0;(2);j++){ if((3)&&len＜b[j]) len=b[j]; } (4); } Printf("len:%d\n",maxL(b,n)); printf("\n"); } 【問題1】（8分） 根據(jù)說明和C代碼，填充C代碼中的空（1）～（4）。 【問題2】（4分） 根據(jù)說明和C代碼，算法采用了（5）設(shè)計(jì)策略，時(shí)間復(fù)雜度為（6）（用O符號表示）。 【問題3】（3分） 已知數(shù)組a={3,10,5,15,6,8}，根據(jù)說明和C代碼，給出數(shù)組b的元素值。 正確答案：

36、 本題解析： 【問題1】 （1）b[0]=1 （2）j＜i （3）a[j]＜=a[i] （4）b[i]=len+1 【問題2】 （5）動態(tài)規(guī)劃法 （6）O(n2) 【問題3】 b={1,2,2,3,3,4} 本題考查算法設(shè)計(jì)與分析技術(shù)以及算法的C語言實(shí)現(xiàn)，是比較傳統(tǒng)的題目，要求考生細(xì)心分析題目中所描述的內(nèi)容。 （1）根據(jù)題中說明，b數(shù)組記錄最長遞增子序列的長，故應(yīng)初始化b[0]=1，這是第一問的答案。兩重for循環(huán)中，第一重是從a數(shù)組的第二個元素開始，考慮每個子數(shù)組a[0...i]的最長遞增子序列的長度，第二重是具體的計(jì)算過程?？紤]子

37、數(shù)組a[0..i]，其最長遞增子序列的長度應(yīng)該等于子數(shù)組a[0..i-1]中的比元素a[i]小的元素的最長遞增子序列的長度加1，當(dāng)然，可能存在多個元素比元素a[i]小，那么存在多個最長遞增子序列的長度，此時(shí)，取最大者。因此，空（2）填寫“j＜i”，即考慮子數(shù)組a[0..i-1]第三問為a[j]＜=a[i]，第四問為b[i]=len+1。 （2）算法將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。使用的是動態(tài)規(guī)劃的思想。時(shí)間復(fù)雜度計(jì)算最壞情況下的運(yùn)算次數(shù)，最壞情況時(shí)i和j都從1跑到n,故運(yùn)算n的平方次。算法的時(shí)間復(fù)雜度為O(n2)。 （3）初始b[0]=1，a[0]=3，a[1]=10進(jìn)入時(shí)b[1]=2，a[2]=5進(jìn)入時(shí)有3、5的序列故b[2]=2，a[3]=15進(jìn)入時(shí)有3、10、15，故子序列為3，a[4]=6時(shí)有子序列3、5、6，故為3，當(dāng)最后一個元素8進(jìn)入時(shí)有3、5、6、8，故b[5]=4。所以b=[1,2,2,3,3,4]。