2018年上半年（下午）《軟件設計師》真題

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

1、2018年上半年（下午）《軟件設計師》真題 注意：圖片可根據(jù)實際需要調整大小 卷面總分：6分 答題時間：240分鐘 試卷題量：6題 練習次數(shù)：0次 問答題 （共6題，共6分） 1.某ETC（ElectronicTollCollection，不停車收費）系統(tǒng)在高速公路沿線的特定位置上設置一個橫跨道路上空的龍門架（Tollgantry），龍門架下包括6條車道（Trafficlanes），每條車道上安裝有雷達傳感器（Radarsensor）、無線傳輸器（Radiotransceiver）和數(shù)碼相機（Digita

2、lCamera）等用于不停車收費的設備，以完成正常行駛速度下的收費工作。該系統(tǒng)的基本工作過程如下： （1）每輛汽車上安裝有車載器，駕駛員（Driver）將一張具有唯一識別碼的磁卡插入車載器中。磁卡中還包含有駕駛員賬戶的當前信用記錄。 （2）當汽車通過某條車道時，不停車收費設備識別車載器內的特有編碼，判斷車型，將收集到的相關信息發(fā)送到該路段所屬的區(qū)域系統(tǒng)（Regionalcenter）中，計算通行費用，創(chuàng)建收費交易（Transaction），從駕駛員的專用賬戶中扣除通行費用。如果駕駛員賬戶透支，則記錄透支賬戶交易信息。區(qū)域系統(tǒng)再將交易后的賬戶信息發(fā)送到維護駕駛員賬戶信息的中心系統(tǒng)（Centr

3、alsystem）。 （3）車載器中的磁卡可以使用郵局的付款機進行充值。充值信息會傳送至中心系統(tǒng)，以更新駕駛員賬戶的余額。 （4）當沒有安裝車載器或者車載器發(fā)生故障的車輛通過車道時，車道上的數(shù)碼相機將對車輛進行拍照，并將車輛照片及拍攝時間發(fā)送到區(qū)域系統(tǒng)，記錄失敗的交易信息；并將該交易信息發(fā)送到中心系統(tǒng)。 （5）區(qū)域系統(tǒng)會獲取不停車收費設備所記錄的交通事件（Trafficevents）；交通廣播電臺（Trafficadvicecenter）根據(jù)這些交通事件進行路況分析并播報路況。 現(xiàn)采用面向對象方法對上述系統(tǒng)進行分析與設計，得到如表3-1所示的用例列表以及如圖3-1所示的用例圖和圖3-2

4、所示的分析類圖。 【問題1】（4分） 根據(jù)說明中的描述，給出圖3－1中A1～A4所對應的參與者名稱。 【問題2】（5分） 根據(jù)說明中的描述及表3－1，給出圖3－1中U1～U5所對應的用例名稱。 【問題3】（6分） 根據(jù)說明中的描述，給出圖3－2中C1~C6所對應的類名。 正確答案： 本題解析： 【問題1】 A1：Central system或中心系統(tǒng) A2：Driver或駕駛員 A3：Regional center或區(qū)域系統(tǒng) A4：Traffic advice cen

5、ter或交通廣播電臺 其中A1、A2或以互換；A3、A4可以互換。 【問題2】 U1：Underpaid transaction U2：Record Illegal use U3：Create transaction U4：Record traffic event U5：Charge card 其中U1、U2可以互換，用例名稱必須為英文，因為表中的漢字是對用例的說明。 【問題3】 C1：Central system C2：Toll gantry C3：Traffic lanes C4：Radar sensor C5：Radio transceiver C6：Dig

6、ital Camera 其中C4、C5、C6可以互換。 本題是對UML用例圖和類圖的結合考查。 根據(jù)題目給出的用例表格，用例名一定要用英文進行填寫，一般圖示中建議統(tǒng)一用中文后者英文，用例名用英文填寫，那么參與者建議也用英文表示。類圖中已出現(xiàn)的類名已經用英文，填空時也盡量用英文填空。 在本題中由于用例圖的缺失，【問題1】和【問題2】需要結合思考。 首先根據(jù)提示可以看到，A1、A2使用都是用例U3、U5；A3、A4使用的都是用例U4，因此A1、A2可互換，A3、A4可互換，并且參與者要根據(jù)用例才能確定。 首先分析給出的用例表格，其中與交易相關的有用例Create transaction

7、記錄交易信息（寫作創(chuàng)建交易信息更明確一些）、Underpaid transaction記錄透支賬戶交易信息、Record Illegal use記錄失敗交易信息，另外兩個用例，Charge card磁卡充值與交易有一定的關聯(lián)，而Record traffic event記錄交通事件是完全獨立的用例。 從記錄交通事件進行分析，根據(jù)提干描述“區(qū)域系統(tǒng)會獲取不停車收費設備所記錄的交通事件（Traffic events）；交通廣播電臺（Traffic advice center）根據(jù)這些交通事件進行路況分析并播報路況?！迸c獨立用例記錄交通事件相關的，有來年改革相關參與者，分別是區(qū)域系統(tǒng)和交通廣播電臺，

8、根據(jù)用例圖圖示，U4是完全獨立的用例，即為U4，與之相關的參與者A3、A4即為Regional center區(qū)域系統(tǒng)與Traffic advice center交通廣播電臺，A3和A4位置可互換。 U1、U2、U3是一組相關用例，其中U3有兩個擴展用例，分別是U1、U2，根據(jù)題目查找擴展關系。擴展關系：在基礎用例中，出現(xiàn)某些特殊條件才執(zhí)行的，屬于擴展用例，一般有“若”“如果”等類似描述。根據(jù)表格給定的用例名和題干說明“當汽車通過某條車道時，…，計算通行費用，創(chuàng)建收費交易（Transaction），…。如果駕駛員賬戶透支，則記錄透支賬戶交易信息。區(qū)域系統(tǒng)再將交易后的賬戶信息發(fā)送到維護駕駛員賬戶

9、信息的中心系統(tǒng)（Central system）”、“當沒有安裝車載器或者車載器發(fā)生故障的車輛通過車道時，車道上的數(shù)碼相機將對車輛進行拍照，并將車輛照片及拍攝時間發(fā)送到區(qū)域系統(tǒng)，記錄失敗的交易信息；并將該交易信息發(fā)送到中心系統(tǒng)。”，只有記錄透支賬戶交易信息和記錄失敗交易信息是某種情況下的描述，即二者是記錄收費交易的擴展，因此U3是Create transaction記錄收費交易（創(chuàng)建收費交易作為說明更恰當），U1和U2分別是Underpaid transaction記錄透支賬戶交易信息、Record Illegal use記錄失敗交易信息，U1和U2可互換。剩下U5即為Charge card磁卡

10、充值。 根據(jù)提干描述“車載器中的磁卡可以使用郵局的付款機進行充值。充值信息會傳送至中心系統(tǒng)，以更新駕駛員賬戶的余額”與充值相關的信息最終會傳送至Central system中心系統(tǒng)，另外這里雖然沒有明確給出，但磁卡的擁有者是駕駛員，使用充值功能的一定是駕駛員進行充值，因此A1和A2分別是Central system中心系統(tǒng)和Driver駕駛員，二者位置可互換。 【問題3】 類名填空需要結合類圖中的關系進行分析。 先從C4、C5、C6與C3的一個多組合關系。題干中只有龍門架由三個部分組成。 C1與Regional Center對應關系是1個對象對應多個對象，C1只可能為中心系統(tǒng)。 然

11、后題干（5）中獲取龍門架的所有記錄叫交通事件。且一個Regional Center有多個C2對象與之對應。 2.生成器（Builder）模式的意圖是將一個復雜對象的構建與它的表示分離，使得同樣的構建過程可以創(chuàng)建不同的表示。圖5-1所示為其類圖。 【C++代碼】 #include＜iostream> #include＜string> using namespace std; class Product{ private: string partA,partB; public: Product（　?。﹞} void setPartA(cons

12、t string&s){PartA=s;} void setPartB(const string&s){PartB=s;} //其余代碼省略 }; class Builder{ public: （1）; virtual void buildPartB（　?。?0; （2）; }; class ConcreteBuilder1:public Builder{ private: Product*product; public: ConcreteBuilder1（　　）{product=new Product（　?。?} void buildPartA（　　）{（3）(

13、"Component A");} void buildPartB（　　）{（4）("Component B");} Product*getResult（　　）{return product;} //其余代碼省略 }; class ConcreteBuilder2:public Builder{ /*代碼省略*/ }; class Director{ private: Builder*builder; public: Director(Builder*pBuilder){builder=pBuilder;} void construct（　?。﹞ （5）; //其余

14、代碼省略 } //其余代碼省略 }; int main（　?。﹞ Director*director1=new Director(new ConcreteBuilder1（　　）); director1->construct（　?。? delete director1; return 0; } 正確答案： 本題解析： （1）virtual void buildPartA()=0 （2）virtual Product*getResult()=0 （3）product->setPart

15、A （4）product->setPartB （5）builder->buildPartA(); 或builder->buildPartB(); 本題考查的是面向對象程序設計，是JAVA語言與設計模式的結合考查。本題涉及的設計模式是構建器模式，將復雜類的構造過程推遲到子類實現(xiàn)。 對于第一空、第二空，根據(jù)實現(xiàn)接口的類，補充其接口缺失的方法，因此，空（1）和空（2）分別填寫：virtual void buildPartA()=0和virtual Product*getResult()=0，二者可以互換； 對于第三空、第四空，是根據(jù)product類方法進行的補充，與具體產品的實現(xiàn)保持一致

16、，因此，分別填寫：product->setPartA，product->setPartB； 對于第五空，由于在填空后面跟隨的是代碼省略，因此題目并不嚴謹，缺失的語句可以有builder->buildPartA();builder->buildPartB()。 3.某醫(yī)療護理機構為老年人或有護理需求者提供專業(yè)護理，現(xiàn)欲開發(fā)一基于Web的醫(yī)療管理系統(tǒng)，以改善醫(yī)療護理效率。該系統(tǒng)的主要功能如下： （1）通用信息查詢?？蛻籼峤煌ㄓ眯畔⒉樵冋埱螅樵兺ㄓ眯畔⒈?，返回查詢結果。 （2）醫(yī)生聘用。醫(yī)生提出應聘／辭職申請，交由主管進行聘用/解聘審批，更新醫(yī)生表，并給醫(yī)生反

17、饋聘用/解聘結果；刪除解聘醫(yī)生的出診安排。 （3）預約處理。醫(yī)生安排出診時間，存入醫(yī)生出診時間表；根據(jù)客戶提交的預約查詢請求，查詢在職醫(yī)生及其出診時間等預約所需數(shù)據(jù)并返回；創(chuàng)建預約，提交預約請求，在預約表中新增預約記錄，更新所約醫(yī)生出診時間并給醫(yī)生發(fā)送預約通知；給客戶反饋預約結果。 （4）藥品管理。醫(yī)生提交處方，根據(jù)藥品名稱從藥品數(shù)據(jù)中查詢相關藥品庫存信息，開出藥品，更新對應藥品的庫存以及預約表中的治療信息；給醫(yī)生發(fā)送“藥品已開出”反饋。 （5）報表創(chuàng)建。根據(jù)主管提交的報表查詢請求（報表類型和時間段），從預約數(shù)據(jù)、通用信息、藥品庫存數(shù)據(jù)、醫(yī)生以及醫(yī)生出診時間中進行查詢，生成報表返回給主管

18、。 現(xiàn)采用結構化方法對醫(yī)療管理系統(tǒng)進行分析與設計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。 【問題1】（3分） 使用說明中的詞語，給出圖1-1中的實體E1～E3的名稱。 【問題2】（5分） 使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1～D5的名稱。 【問題3）（4分） 使用說明和圖中術語，補充圖1-2中缺失的數(shù)據(jù)流及其起點和終點。 【問題4】（3分） 使用說明中的詞語，說明“預約處理”可以分解為哪些子加工，并說明建模圖1-1和圖1-2是如何保持數(shù)據(jù)流圖平衡。 正確答案：

19、 本題解析： 【問題1】 E1：客戶E2:醫(yī)生E3：主管 【問題2】 D1：通用信息表 D2：預約表 D3：醫(yī)生表 D4：出診時間表 D5：藥品庫存表 【問題3】 數(shù)據(jù)流：更新的出診時間起點：P3終點：D4 數(shù)據(jù)流：刪除的醫(yī)生出診安排起點：P2終點：D4 數(shù)據(jù)流：藥品庫存信息起點：D5終點：P4 數(shù)據(jù)流：治療信息起點：P4終點：D2 【問題4】 預約處理分解為：安排出診、預約查詢、創(chuàng)建預約、預約反饋。 即保持父圖與子圖之間的平衡：父圖中某個加工的輸入輸出數(shù)據(jù)流必須與其子圖的輸入輸出數(shù)據(jù)流在數(shù)量上和名字上相同。父圖的一個輸入（或輸出）數(shù)據(jù)流對應于子

20、圖中幾個輸入（或輸出）數(shù)據(jù)流，而子圖中組成的這些數(shù)據(jù)流的數(shù)據(jù)項全體正好是父圖中的這一個數(shù)據(jù)流。 本題是對數(shù)據(jù)流圖的考查，題型是傳統(tǒng)的考題，主要參考題干說明找到答案。 【問題1】 本題要求找到對應的實體名稱。 根據(jù)題干敘述，“客戶提交通用信息查詢請求，查詢通用信息表，返回查詢結果”，綜合圖示，提交通用信息查詢請求的是實體E1，即客戶。 根據(jù)題干敘述，“醫(yī)生提出應聘／辭職申請，交由主管進行聘用/解聘審批”，綜合圖示，提出辭職/應聘申請的是E2，即醫(yī)生，進行審批的是E3，即主管。 【問題2】 本題要求找到對應的存儲名稱。 根據(jù)題干描述，“客戶提交通用信息查詢請求，查詢通用信息表，返回

21、查詢結果”，綜合圖示，接收查詢請求，返還查詢結果的是通用信息表，即D1； 根據(jù)題干描述，“醫(yī)生提出應聘／辭職申請，交由主管進行聘用/解聘審批，更新醫(yī)生表”，綜合圖示，醫(yī)生聘用加工，會更新醫(yī)生表，即D3為醫(yī)生表； 根據(jù)題干描述，“安排出診時間，存入醫(yī)生出診時間表；根據(jù)客戶提交的預約查詢請求，查詢在職醫(yī)生及其出診時間等預約所需數(shù)據(jù)并返回；創(chuàng)建預約，提交預約請求，在預約表中新增預約記錄”，綜合圖示，與出診時間相關的是D4，即出診時間表，與新預約相關的是D2，即預約表； 根據(jù)題干描述，“醫(yī)生提交處方，根據(jù)藥品名稱從藥品數(shù)據(jù)中查詢相關藥品庫存信息”，綜合圖示，與藥品管理相關的是D5即藥品庫存表。

22、 【問題3】 本題考查補充數(shù)據(jù)流，可以根據(jù)父圖和子圖的平衡，再根據(jù)題干說明，查找缺失數(shù)據(jù)流。 本題檢查父圖數(shù)據(jù)流，都已出現(xiàn)在子圖中，詳細查看說明： “醫(yī)生聘用。醫(yī)生提出應聘／辭職申請，交由主管進行聘用/解聘審批，更新醫(yī)生表，并給醫(yī)生反饋聘用/解聘結果；刪除解聘醫(yī)生的出診安排。”此處缺少數(shù)據(jù)流刪除解聘醫(yī)生的出診安排，數(shù)據(jù)名稱更新出診安排，起點P2，終點是D4。 “創(chuàng)建預約，提交預約請求，在預約表中新增預約記錄，更新所約醫(yī)生出診時間并給醫(yī)生發(fā)送預約通知；”，此處缺少數(shù)據(jù)流更新出診時間，起點是P3，終點是D4。 “醫(yī)生提交處方，根據(jù)藥品名稱從藥品數(shù)據(jù)中查詢相關藥品庫存信息”，此處缺少查詢相

23、關藥品庫存信息數(shù)據(jù)流，起點是D5，終點是P4； “開出藥品，更新對應藥品的庫存以及預約表中的治療信息”，缺少更新預約表中的治療信息，數(shù)據(jù)名稱更新治療信息，起點P4，終點是預約表D2。 【問題4】 預約處理。醫(yī)生安排出診時間，存入醫(yī)生出診時間表；根據(jù)客戶提交的預約查詢請求，查詢在職醫(yī)生及其出診時間等預約所需數(shù)據(jù)并返回；創(chuàng)建預約，提交預約請求，在預約表中新增預約記錄，更新所約醫(yī)生出診時間并給醫(yī)生發(fā)送預約通知；給客戶反饋預約結果。 預約處理分解為：安排出診、預約查詢、創(chuàng)建預約、預約反饋（更新出診時間、發(fā)送預約通知）。 即保持父圖與子圖之間的平衡：父圖中某個加工的輸入輸出數(shù)據(jù)流必須與其子圖的

24、輸入輸出數(shù)據(jù)流在數(shù)量上和名字上相同。父圖的一個輸入（或輸出）數(shù)據(jù)流對應于子圖中幾個輸入（或輸出）數(shù)據(jù)流，而子圖中組成的這些數(shù)據(jù)流的數(shù)據(jù)項全體正好是父圖中的這一個數(shù)據(jù)流。 4.某海外代購公司為擴展公司業(yè)務，需要開發(fā)一個信息化管理系統(tǒng)。請根據(jù)公司現(xiàn)有業(yè)務及需求完成該系統(tǒng)的數(shù)據(jù)庫設計。 【需求描述】 （1）記錄公司員工信息。員工信息包括工號、身份證號、姓名、性別和一個手機號，工號唯一標識每位員工，員工分為代購員和配送員。 （2）記錄采購的商品信息。商品信息包括商品名稱、所在超市名稱、采購價格、銷售價格和商品介紹，系統(tǒng)內部用商品條碼唯一標識每種商品。一種商品只在一

25、家超市代購。 （3）記錄顧客信息。顧客信息包括顧客真實姓名、身份證號（清關繳稅用）、一個手機號和一個收貨地址，系統(tǒng)自動生成唯一的顧客編號。 （4）記錄托運公司信息。托運公司信息包括托運公司名稱、電話和地址，系統(tǒng)自動生成唯一的托運公司編號。 （5）顧客登錄系統(tǒng)之后，可以下訂單購買商品。訂單支付成功后，系統(tǒng)記錄唯一的支付憑證編號，顧客需要在訂單里指定運送方式：空運或海運。 （6）代購員根據(jù)顧客的訂單在超市采購對應商品，一份訂單所含的多個商品可能由多名代購員從不同超市采購。 （7）采購完的商品交由配送員根據(jù)顧客訂單組合裝箱，然后交給托運公司運送。托運公司按顧客訂單核對商品名稱和數(shù)量，然后按

26、顧客的地址進行運送。 【概念模型設計】 根據(jù)需求階段收集的信息，設計的實體聯(lián)系圖（不完整）如圖2－1所示。 【邏輯結構設計】 根據(jù)概念模型設計階段完成的實體聯(lián)系圖，得出如下關系模式（不完整）： 員工（工號，身份證號，姓名，性別，手機號） 商品（條碼，商品名稱，所在超市名稱，采購價格，銷售價格，商品介紹） 顧客（編號，姓名，身份證號，手機號，收貨地址） 托運公司（托運公司編號，托運公司名稱，電話，地址） 訂單（訂單ID，（a），商品數(shù)量，運送方式，支付憑證編號） 代購（代購ID，代購員工號，（b）） 運送（運送ID，配送員工號，托運公司編號，訂單ID，發(fā)運時間） 【問

27、題1】（3分） 根據(jù)問題描述，補充圖2-1的實體聯(lián)系圖。 【問題2】（6分） 補充邏輯結構設計結果中的（a）、（b）兩處空缺。 【問題3】（6分） 為方便顧客，允許顧客在系統(tǒng)中保存多組收貨地址。請根據(jù)此需求，增加“顧客地址”弱實體，對圖2-1進行補充，并修改“運送”關系模式。 正確答案： 本題解析： 【問題1】 【問題2】 （a）商品條碼，顧客編號 （b）訂單ID，商品條碼 【問題3】 新增一個弱實體顧客地址，新增一個聯(lián)系客戶收貨地址，聯(lián)連接顧客實體和顧客地址類型為1:*；弱

28、實體用雙矩型 運送關系模式增加屬性：顧客地址 運送（運送ID，配送員工號，托運公司編號，訂單ID，顧客地址，發(fā)運時間） 【問題1】 根據(jù)題干描述，“采購完的商品交由配送員根據(jù)顧客訂單組合裝箱，然后交給托運公司運送。”其中配送員，托運公司，和代購訂單商品，存在多對多的三元聯(lián)系。 【問題2】 訂單是商品與客戶之間多對多的聯(lián)系轉換而來，因此a空需要補充二者的主鍵，商品條碼和客戶編號。代購是代購員與代購訂單之間多對多的聯(lián)系轉換而來，因此，b空應補充訂單的主鍵訂單ID，又因為“一份訂單所含的多個商品可能由多名代購員從不同超市采購”，所以還需要補充商品條碼。 【問題3】 新增一個弱實體顧客

29、地址，新增一個聯(lián)系客戶收貨地址，聯(lián)連接顧客實體和顧客地址類型為1:*；弱實體用雙矩型。 運送關系模式增加屬性：顧客地址 運送（運送ID，配送員工號，托運公司編號，訂單ID，顧客地址，發(fā)運時間） 5.生成器（Builder）模式的意圖是將一個復雜對象的構建與它的表示分離，使得同樣的構建過程可以創(chuàng)建不同的表示。圖6-1所示為其類圖。 【Java代碼】 import java.util.*; class Product{ private String partA; private String partB; public Product（　?。﹞}

30、 public void setPartA(String s){partA=s;} public void setPartB(String s){partB=s;} } interface Builder{ public（1）; public void buildPartB（　?。? public（2）; } class ConcreteBuilder1 implements Builder{ private Product product; public ConcreteBuilder1（　　）{product=new Product（　?。?} public voi

31、d buildPartA（　?。﹞（3）("Component A");} public void buildPartB（　　）{（4）("Component B");} public Product getResult（　?。﹞return product;} } class ConcreteBuilder2 implements Builder{ //代碼省略 } class Director{ private Builder builder; public Director(Builder builder){this.builder=builder;} public

32、void construct（　?。﹞ （5）; //代碼省略 } } class Test{ public static void main(String[]args){ Director director1=new Director(new ConcreteBuilder1（　　）); director1.construct（　?。? } } 正確答案： 本題解析： （1）void buildPartA() （2）Product getResult() （3）product.

33、setPartA （4）product.setPartB （5）builder.buildPartA(); 或builder.buildPartB() 本題考查的是面向對象程序設計，是JAVA語言與設計模式的結合考查。本題涉及的設計模式是構建器模式，將復雜類的構造過程推遲到子類實現(xiàn)。 對于第一空、第二空，根據(jù)實現(xiàn)接口的類，補充其接口缺失的方法，因此，空（1）和空（2）分別填寫void buildPartA()和Product getResult()，二者可以互換； 對于第三空、第四空，是根據(jù)product類方法進行的補充，與具體產品的實現(xiàn)保持一致，因此，分別填寫，product.s

34、etPartA，product.setPartB； 對于第五空，由于在填空后面跟隨的是代碼省略，因此題目并不嚴謹，缺失的語句可以有builder.buildPartA();builder.buildPartB()。 6.某公司購買長鋼條，將其切割后進行出售。切割鋼條的成本可以忽略不計，鋼條的長度為整英寸。已知價格表p，其中pi（i＝1，2，…，m）表示長度為i英寸的鋼條的價格。現(xiàn)要求解使銷售收益最大的切割方案。 求解此切割方案的算法基本思想如下： 假設長鋼條的長度為n英寸，最佳切割方案的最左邊切割段長度為i英寸，則繼續(xù)求解剩余長度為n－i英寸鋼條的最佳切割

35、方案。考慮所有可能的i，得到的最大收益rn對應的切割方案即為最佳切割方案。rn的遞歸定義如下： rn=max1≤i≤n(pi+rn-i) 對此遞歸式，給出自頂向下和自底向上兩種實現(xiàn)方式。 【C代碼】 /*常量和變量說明 n：長鋼條的長度 p[]：價格數(shù)組 */ #define LEN 100 int Top_Down_Cut_Rod(int p[],int n){/*自頂向下*/ int r=0; int i; if(n==0){ return 0; } for(i=1;（1）;i++){ int tmp=p[i]+Top_Down_Cut_Rod(p,n-i)

36、; r=(r>=tmp）r：tmp; } return r; } int Bottom_Up_Cut_Rod(int p[],int n){/*自底向上*/ int r[LEN]={0}; int temp=0; int i,j; for(j=1;j＜=n;j++){ temp=0; for(i=1;（2）;i++){ temp=（3）; } （4）; } return r[n]; } 【問題1】（8分） 根據(jù)說明，填充C代碼中的空（1）～（4）。 【問題2】（7分） 根據(jù)說明和C代碼，算法采用的設計策略為（5）。 求解rn時，自頂向下方法的時間復雜

37、度為（6）；自底向上方法的時間復雜度為（7）（用O表示）。 正確答案： 本題解析： 【問題1】 （1）：i＜=n （2）：i＜=j （3）：(temp>=p[i]+r[j-i])?temp:(p[i]+r[j-i]) （4）：r[j]=temp 或 （3）：(temp>=r[i]+r[j-i])?temp:(r[i]+r[j-i]) （4）：r[j]=(temp>p[j])?temp:p[j]; 【問題2】 （5）動態(tài)規(guī)劃法 （6）O(2n) （7）O(n2) 【問題1】 在自

38、頂向下實現(xiàn)過程中，n-i表示規(guī)模從大到小即n-1~0，即對應i的初始值為1，結束值為n，第一空填寫i＜=n，遞歸式也有范圍提示可以參照。 在自底向上實現(xiàn)過程中，采用雙重嵌套循環(huán)，內層循環(huán)從1~j，第二空填寫i＜=j。 第三空和第四空比較復雜，是具體的實現(xiàn)過程，是本題的難點。 根據(jù)題干內容，本題考查的是鋼條切割問題最優(yōu)化問題，求解的思路即先考慮最左側的切割考慮，再依次向右擴展，中間的最優(yōu)解結果記錄在數(shù)組r[]中，并用temp中間變量傳遞最大值。 根據(jù)遞歸式rn=max1≤i≤n(pi+rn-i)，即r[]最終結果是該過程的最大值，（3）空給temp賦值，那么（4）空應該是將這個中間值傳給

39、最終的rn，也就是代碼中的r[j]，即第四空填寫r[j]=temp，那么此時第三空對應最大值的求取，也就是本算法的核心，這里的最大值是在1~j的規(guī)模范圍循環(huán)比較，用temp放置本輪結果，再與下一輪結果進行比較，第三空temp=(temp>=p[i]+r[j-i])?(temp:(p[i]+r[j-i])。 【問題2】 題干中提到說考慮所有可能的i，得到最大收益的方式，而自底向上算法實現(xiàn)時，使用到數(shù)組把其中最優(yōu)的解記錄，并用r[]記錄中間解，因此本題算法策略是動態(tài)規(guī)劃法。 動態(tài)規(guī)劃法自頂向下時需要對規(guī)模n進行求取，此時需要遞歸至規(guī)模1并最終返回結果規(guī)模n的解并記錄，規(guī)模n-1同樣如此，時間復雜度較大，可以達到O(2n)； 動態(tài)規(guī)劃法自底向上時先求取規(guī)模1的解并記錄，然后查詢規(guī)模1的解從而求解規(guī)模2的解，以此類推，直至求取至規(guī)模n，有查詢和循環(huán)求解2層嵌套循環(huán)，時間復雜度為O(n2)。