2021年5月軟件設(shè)計師考試軟件設(shè)計應(yīng)用技術(shù)下午真題

2021年5月軟件設(shè)計師考試軟件設(shè)計應(yīng)用技術(shù)下午真題(總分：13.00，做題時間：180分鐘)一、問答題(總題數(shù)：13，分數(shù)：13.00)1.某停車場運營方為了降低運營成本，減員增效，提供良好的停車體驗，欲開發(fā)無人值守停車系統(tǒng)，該系統(tǒng)的主要功能是：1.信息維護。管理人員對車位（總數(shù)、空余車位數(shù)等）計費規(guī)則等基礎(chǔ)信息進行設(shè)置。2.會員注冊。車主提供手機號、車牌號等信息進行注冊，提交充值信息（等級、綁定并授權(quán)支付系統(tǒng)進行充值或交費的支付賬號）不同級別和充值額度享受不同停車折扣點。3.車牌識別。當(dāng)車輛進入停車場時，若有（空余車位數(shù)大于1），自動識別車牌號后進行道閘控制，當(dāng)車主開車離開停車場時，識別車牌號，計費成功后，請求道閘控制。4.計費。更新車輛離場時間，根據(jù)計費規(guī)則計算出停車費用，若車主是會員，提示停車費用:若儲存余額夠本次停車費用，自動扣費，更新余額，若儲值余額不足，自動使用授權(quán)繳費賬號請求支付系統(tǒng)進行支付，獲取支付狀態(tài)。若非會員臨時停車，提示停車費用，車主通過掃描費用信息中的支付碼調(diào)用支付系統(tǒng)自助交費，獲取支付狀態(tài)。5.道閘控制。根據(jù)道閘控制請求向道閘控制系統(tǒng)發(fā)送放行指令和接收道閘執(zhí)行狀態(tài)。若道閘執(zhí)行狀態(tài)為正常放行時，對入場車輛，將車牌號及其入場時間信息存入停車記錄，修改空余車位數(shù)；對出場車輛更新停車狀態(tài)，修改空余車位數(shù)。當(dāng)因道閘重置系統(tǒng)出現(xiàn)問題（斷網(wǎng)斷電或是故障為抬杠等情況），而無法在規(guī)定的時間內(nèi)接收到其返回的執(zhí)行狀態(tài)正常放行時，系統(tǒng)向管理人員發(fā)送異常告警信息，之后管理人員安排故障排查處理，確保車輛有序出入停車場。

現(xiàn)采用結(jié)構(gòu)化方法對無人值守停車系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。使用說明中的詞語，給出圖1-1中的實體E1~E5的名稱。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(E1：汽車；E2：車主；E3：支付系統(tǒng)；E4：管理人員；E5：道閘控制系統(tǒng))解析：2.某停車場運營方為了降低運營成本，減員增效，提供良好的停車體驗，欲開發(fā)無人值守停車系統(tǒng)，該系統(tǒng)的主要功能是：1.信息維護。管理人員對車位（總數(shù)、空余車位數(shù)等）計費規(guī)則等基礎(chǔ)信息進行設(shè)置。2.會員注冊。車主提供手機號、車牌號等信息進行注冊，提交充值信息（等級、綁定并授權(quán)支付系統(tǒng)進行充值或交費的支付賬號）不同級別和充值額度享受不同停車折扣點。3.車牌識別。當(dāng)車輛進入停車場時，若有（空余車位數(shù)大于1），自動識別車牌號后進行道閘控制，當(dāng)車主開車離開停車場時，識別車牌號，計費成功后，請求道閘控制。4.計費。更新車輛離場時間，根據(jù)計費規(guī)則計算出停車費用，若車主是會員，提示停車費用:若儲存余額夠本次停車費用，自動扣費，更新余額，若儲值余額不足，自動使用授權(quán)繳費賬號請求支付系統(tǒng)進行支付，獲取支付狀態(tài)。若非會員臨時停車，提示停車費用，車主通過掃描費用信息中的支付碼調(diào)用支付系統(tǒng)自助交費，獲取支付狀態(tài)。5.道閘控制。根據(jù)道閘控制請求向道閘控制系統(tǒng)發(fā)送放行指令和接收道閘執(zhí)行狀態(tài)。若道閘執(zhí)行狀態(tài)為正常放行時，對入場車輛，將車牌號及其入場時間信息存入停車記錄，修改空余車位數(shù)；對出場車輛更新停車狀態(tài)，修改空余車位數(shù)。當(dāng)因道閘重置系統(tǒng)出現(xiàn)問題（斷網(wǎng)斷電或是故障為抬杠等情況），而無法在規(guī)定的時間內(nèi)接收到其返回的執(zhí)行狀態(tài)正常放行時，系統(tǒng)向管理人員發(fā)送異常告警信息，之后管理人員安排故障排查處理，確保車輛有序出入停車場?，F(xiàn)采用結(jié)構(gòu)化方法對無人值守停車系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。使用說明中的詞語，給出圖1-2中的數(shù)據(jù)存儲D1~D3的名稱。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(D1：停車記錄表D2：會員信息表D3：基礎(chǔ)信息)解析：3.某停車場運營方為了降低運營成本，減員增效，提供良好的停車體驗，欲開發(fā)無人值守停車系統(tǒng)，該系統(tǒng)的主要功能是：1.信息維護。管理人員對車位（總數(shù)、空余車位數(shù)等）計費規(guī)則等基礎(chǔ)信息進行設(shè)置。2.會員注冊。車主提供手機號、車牌號等信息進行注冊，提交充值信息（等級、綁定并授權(quán)支付系統(tǒng)進行充值或交費的支付賬號）不同級別和充值額度享受不同停車折扣點。3.車牌識別。當(dāng)車輛進入停車場時，若有（空余車位數(shù)大于1），自動識別車牌號后進行道閘控制，當(dāng)車主開車離開停車場時，識別車牌號，計費成功后，請求道閘控制。4.計費。更新車輛離場時間，根據(jù)計費規(guī)則計算出停車費用，若車主是會員，提示停車費用:若儲存余額夠本次停車費用，自動扣費，更新余額，若儲值余額不足，自動使用授權(quán)繳費賬號請求支付系統(tǒng)進行支付，獲取支付狀態(tài)。若非會員臨時停車，提示停車費用，車主通過掃描費用信息中的支付碼調(diào)用支付系統(tǒng)自助交費，獲取支付狀態(tài)。5.道閘控制。根據(jù)道閘控制請求向道閘控制系統(tǒng)發(fā)送放行指令和接收道閘執(zhí)行狀態(tài)。若道閘執(zhí)行狀態(tài)為正常放行時，對入場車輛，將車牌號及其入場時間信息存入停車記錄，修改空余車位數(shù)；對出場車輛更新停車狀態(tài)，修改空余車位數(shù)。當(dāng)因道閘重置系統(tǒng)出現(xiàn)問題（斷網(wǎng)斷電或是故障為抬杠等情況），而無法在規(guī)定的時間內(nèi)接收到其返回的執(zhí)行狀態(tài)正常放行時，系統(tǒng)向管理人員發(fā)送異常告警信息，之后管理人員安排故障排查處理，確保車輛有序出入停車場。現(xiàn)采用結(jié)構(gòu)化方法對無人值守停車系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。根據(jù)說明和圖中術(shù)語，補充圖1-2中缺失的數(shù)據(jù)流及其起點和終點。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：()解析：4.某停車場運營方為了降低運營成本，減員增效，提供良好的停車體驗，欲開發(fā)無人值守停車系統(tǒng)，該系統(tǒng)的主要功能是：1.信息維護。管理人員對車位（總數(shù)、空余車位數(shù)等）計費規(guī)則等基礎(chǔ)信息進行設(shè)置。2.會員注冊。車主提供手機號、車牌號等信息進行注冊，提交充值信息（等級、綁定并授權(quán)支付系統(tǒng)進行充值或交費的支付賬號）不同級別和充值額度享受不同停車折扣點。3.車牌識別。當(dāng)車輛進入停車場時，若有（空余車位數(shù)大于1），自動識別車牌號后進行道閘控制，當(dāng)車主開車離開停車場時，識別車牌號，計費成功后，請求道閘控制。4.計費。更新車輛離場時間，根據(jù)計費規(guī)則計算出停車費用，若車主是會員，提示停車費用:若儲存余額夠本次停車費用，自動扣費，更新余額，若儲值余額不足，自動使用授權(quán)繳費賬號請求支付系統(tǒng)進行支付，獲取支付狀態(tài)。若非會員臨時停車，提示停車費用，車主通過掃描費用信息中的支付碼調(diào)用支付系統(tǒng)自助交費，獲取支付狀態(tài)。5.道閘控制。根據(jù)道閘控制請求向道閘控制系統(tǒng)發(fā)送放行指令和接收道閘執(zhí)行狀態(tài)。若道閘執(zhí)行狀態(tài)為正常放行時，對入場車輛，將車牌號及其入場時間信息存入停車記錄，修改空余車位數(shù)；對出場車輛更新停車狀態(tài)，修改空余車位數(shù)。當(dāng)因道閘重置系統(tǒng)出現(xiàn)問題（斷網(wǎng)斷電或是故障為抬杠等情況），而無法在規(guī)定的時間內(nèi)接收到其返回的執(zhí)行狀態(tài)正常放行時，系統(tǒng)向管理人員發(fā)送異常告警信息，之后管理人員安排故障排查處理，確保車輛有序出入停車場?，F(xiàn)采用結(jié)構(gòu)化方法對無人值守停車系統(tǒng)進行分析與設(shè)計，獲得如圖1-1所示的上下文數(shù)據(jù)流圖和圖1-2所示的0層數(shù)據(jù)流圖。根據(jù)說明，采用結(jié)構(gòu)化語言對“道閘控制”的加工邏輯進行描述。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：("道閘控制"加工過程IF(道閘執(zhí)行狀態(tài)正常)IF(車輛入場)THEN將車牌號及其入場時間信息存入停車記錄,修改空余車位數(shù)ELSEIF(車輛出場)THEN更新停車狀態(tài)，修改空余車位數(shù)ENDIFELSESIF(未在規(guī)定的時間內(nèi)接收到其返回的執(zhí)行狀態(tài)正常放行)THEN向管理人員發(fā)送異常告警信息ENDIF)解析：5.某社區(qū)蔬菜團購網(wǎng)站，為規(guī)范商品收發(fā)流程，便于查詢客戶訂單情況，需要開發(fā)一個信息系統(tǒng)。請根據(jù)下述需求描述完成該系統(tǒng)的數(shù)據(jù)庫設(shè)計。[需求描述](1)記錄蔬菜供應(yīng)商的信息，包括供應(yīng)商編號、地址和一個電話。(2)記錄社區(qū)團購點的信息，包括團購點編號、地址和一個電話。(3)記錄客戶信息，包括客戶姓名和一個電話?？蛻艨梢栽诓煌纳鐓^(qū)團購點下訂單，不直接與蔬菜供應(yīng)商發(fā)生聯(lián)系。(4)記錄客戶訂單信息，包括訂單編號、團購點編號、客戶電話、訂單內(nèi)容和日期。[概念模型設(shè)計]根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖(不完整)如圖1-1所示。[邏輯結(jié)構(gòu)設(shè)計]根據(jù)概念模型設(shè)計階段完成的實體聯(lián)系圖，得出如下關(guān)系模式(不完整):蔬菜供貨商(供貨商編號，地址，電話)社區(qū)團購點(團購點編號，地址,電話)供貨(供貨商編號，(a))客戶(姓名，客戶電話)訂單(訂單編號，團購點編號，訂單內(nèi)容，日期，(b))根據(jù)問題描述，補充1-1的實體聯(lián)系圖

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：()解析：6.某社區(qū)蔬菜團購網(wǎng)站，為規(guī)范商品收發(fā)流程，便于查詢客戶訂單情況，需要開發(fā)一個信息系統(tǒng)。請根據(jù)下述需求描述完成該系統(tǒng)的數(shù)據(jù)庫設(shè)計。[需求描述](1)記錄蔬菜供應(yīng)商的信息，包括供應(yīng)商編號、地址和一個電話。(2)記錄社區(qū)團購點的信息，包括團購點編號、地址和一個電話。(3)記錄客戶信息，包括客戶姓名和一個電話?？蛻艨梢栽诓煌纳鐓^(qū)團購點下訂單，不直接與蔬菜供應(yīng)商發(fā)生聯(lián)系。(4)記錄客戶訂單信息，包括訂單編號、團購點編號、客戶電話、訂單內(nèi)容和日期。[概念模型設(shè)計]根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖(不完整)如圖1-1所示。[邏輯結(jié)構(gòu)設(shè)計]根據(jù)概念模型設(shè)計階段完成的實體聯(lián)系圖，得出如下關(guān)系模式(不完整):蔬菜供貨商(供貨商編號，地址，電話)社區(qū)團購點(團購點編號，地址,電話)供貨(供貨商編號，(a))客戶(姓名，客戶電話)訂單(訂單編號，團購點編號，訂單內(nèi)容，日期，(b))補充邏輯結(jié)構(gòu)設(shè)計結(jié)構(gòu)中的（a）（b）兩處空缺及完整性的約束關(guān)系

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(a：團購點編號

b：客戶電話供貨關(guān)系主鍵：（團購點編號、供貨商編號）；外鍵：團購點編號、供貨商編號訂單關(guān)系主鍵：訂單編號；外鍵：團購點編號、客戶電話)解析：7.某社區(qū)蔬菜團購網(wǎng)站，為規(guī)范商品收發(fā)流程，便于查詢客戶訂單情況，需要開發(fā)一個信息系統(tǒng)。請根據(jù)下述需求描述完成該系統(tǒng)的數(shù)據(jù)庫設(shè)計。[需求描述](1)記錄蔬菜供應(yīng)商的信息，包括供應(yīng)商編號、地址和一個電話。(2)記錄社區(qū)團購點的信息，包括團購點編號、地址和一個電話。(3)記錄客戶信息，包括客戶姓名和一個電話?？蛻艨梢栽诓煌纳鐓^(qū)團購點下訂單，不直接與蔬菜供應(yīng)商發(fā)生聯(lián)系。(4)記錄客戶訂單信息，包括訂單編號、團購點編號、客戶電話、訂單內(nèi)容和日期。[概念模型設(shè)計]根據(jù)需求階段收集的信息，設(shè)計的實體聯(lián)系圖(不完整)如圖1-1所示。[邏輯結(jié)構(gòu)設(shè)計]根據(jù)概念模型設(shè)計階段完成的實體聯(lián)系圖，得出如下關(guān)系模式(不完整):蔬菜供貨商(供貨商編號，地址，電話)社區(qū)團購點(團購點編號，地址,電話)供貨(供貨商編號，(a))客戶(姓名，客戶電話)訂單(訂單編號，團購點編號，訂單內(nèi)容，日期，(b))若社區(qū)蔬菜團購網(wǎng)站還將有代收快遞的業(yè)務(wù)，請增加新的“快遞”實體，并給出客戶實體和快遞實體之間的“收取”聯(lián)系，對圖1-1進行補充，“快遞”關(guān)系模式包括快遞編號、客戶電話和日期。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：()解析：8.某中醫(yī)醫(yī)院擬開發(fā)一套線上抓藥APP，允許患者憑借該醫(yī)院醫(yī)生開具的處方線上抓藥，并提供免費送藥上門服務(wù)。該系統(tǒng)的主要功能描述如下:(1)注冊?；颊邟呙栳t(yī)院提供的二維碼進行注冊，注冊過程中，患者需提供其病歷號，系統(tǒng)根據(jù)病歷號自動獲取患者基本信息。(2)登錄。已注冊的患者可以登錄系統(tǒng)進行線上抓藥，未注冊的患者系統(tǒng)拒絕其登錄。(3)確認處方?；颊叩卿浐?，可以查看醫(yī)生開具的所有處方?；颊哌x擇需要抓藥的處方和數(shù)量（需要抓幾副藥)，同時說明是否需要煎制。選擇取藥方式:自行到店取藥或者送藥上門，若選擇送藥上門,患者需要提供提供收貨人姓名、聯(lián)系方式和收貨地址。系統(tǒng)自動計算本次抓藥的費用,患者可以使用微信或支付寶等支付方式支付費用。支付成功之后，處方被發(fā)送給藥師進行藥品配制。(4)處理處方。藥師根據(jù)處方配置好藥品。若患者要求煎制,藥師對配置好的藥品進行煎制。煎制完成，藥師將該處方設(shè)置為已完成。若患者選擇的是自行取藥，取藥后確認已取藥。(5)藥品派送。處方完成后,對于選擇送藥上門的患者,系統(tǒng)將給快遞人員發(fā)送藥品配送信息，等待快遞人員取藥；并給患者發(fā)送收貨驗證碼。(6)送藥上門?？爝f人員將配制好的藥品送到患者指定的收貨地址?；颊呤肇洉r，向快遞人員出示收貨驗證碼,快遞人員使用該驗證碼確認藥品已送到?，F(xiàn)采用面向?qū)ο蠓治雠c設(shè)計方法開發(fā)上述系統(tǒng)，得到如圖3-1所示的用例圖以及圖3-2所示的類圖。根據(jù)說明中的描述，給出圖3-1中A1~A3所對應(yīng)的參與者名稱和U1~U4處所對應(yīng)的用例名稱。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(A1：患者；A2：快遞員；A3：藥師U1：確認處方；U2：支付；U3：微信支付；U4：支付寶支付)解析：9.某中醫(yī)醫(yī)院擬開發(fā)一套線上抓藥APP，允許患者憑借該醫(yī)院醫(yī)生開具的處方線上抓藥，并提供免費送藥上門服務(wù)。該系統(tǒng)的主要功能描述如下:(1)注冊?；颊邟呙栳t(yī)院提供的二維碼進行注冊，注冊過程中，患者需提供其病歷號，系統(tǒng)根據(jù)病歷號自動獲取患者基本信息。(2)登錄。已注冊的患者可以登錄系統(tǒng)進行線上抓藥，未注冊的患者系統(tǒng)拒絕其登錄。(3)確認處方?；颊叩卿浐螅梢圆榭瘁t(yī)生開具的所有處方?；颊哌x擇需要抓藥的處方和數(shù)量（需要抓幾副藥)，同時說明是否需要煎制。選擇取藥方式:自行到店取藥或者送藥上門，若選擇送藥上門,患者需要提供提供收貨人姓名、聯(lián)系方式和收貨地址。系統(tǒng)自動計算本次抓藥的費用,患者可以使用微信或支付寶等支付方式支付費用。支付成功之后，處方被發(fā)送給藥師進行藥品配制。(4)處理處方。藥師根據(jù)處方配置好藥品。若患者要求煎制,藥師對配置好的藥品進行煎制。煎制完成，藥師將該處方設(shè)置為已完成。若患者選擇的是自行取藥，取藥后確認已取藥。(5)藥品派送。處方完成后,對于選擇送藥上門的患者,系統(tǒng)將給快遞人員發(fā)送藥品配送信息，等待快遞人員取藥；并給患者發(fā)送收貨驗證碼。(6)送藥上門?？爝f人員將配制好的藥品送到患者指定的收貨地址?；颊呤肇洉r，向快遞人員出示收貨驗證碼,快遞人員使用該驗證碼確認藥品已送到?，F(xiàn)采用面向?qū)ο蠓治雠c設(shè)計方法開發(fā)上述系統(tǒng)，得到如圖3-1所示的用例圖以及圖3-2所示的類圖。根據(jù)說明中的描述，給出圖3-2中C1~C5所對應(yīng)的類名。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(C1：支付方式C2：微信支付C3：支付寶支付C4：處方C5：藥品)解析：10.某中醫(yī)醫(yī)院擬開發(fā)一套線上抓藥APP，允許患者憑借該醫(yī)院醫(yī)生開具的處方線上抓藥，并提供免費送藥上門服務(wù)。該系統(tǒng)的主要功能描述如下:(1)注冊?；颊邟呙栳t(yī)院提供的二維碼進行注冊，注冊過程中，患者需提供其病歷號，系統(tǒng)根據(jù)病歷號自動獲取患者基本信息。(2)登錄。已注冊的患者可以登錄系統(tǒng)進行線上抓藥，未注冊的患者系統(tǒng)拒絕其登錄。(3)確認處方?；颊叩卿浐?，可以查看醫(yī)生開具的所有處方?；颊哌x擇需要抓藥的處方和數(shù)量（需要抓幾副藥)，同時說明是否需要煎制。選擇取藥方式:自行到店取藥或者送藥上門，若選擇送藥上門,患者需要提供提供收貨人姓名、聯(lián)系方式和收貨地址。系統(tǒng)自動計算本次抓藥的費用,患者可以使用微信或支付寶等支付方式支付費用。支付成功之后，處方被發(fā)送給藥師進行藥品配制。(4)處理處方。藥師根據(jù)處方配置好藥品。若患者要求煎制,藥師對配置好的藥品進行煎制。煎制完成，藥師將該處方設(shè)置為已完成。若患者選擇的是自行取藥，取藥后確認已取藥。(5)藥品派送。處方完成后,對于選擇送藥上門的患者,系統(tǒng)將給快遞人員發(fā)送藥品配送信息，等待快遞人員取藥；并給患者發(fā)送收貨驗證碼。(6)送藥上門。快遞人員將配制好的藥品送到患者指定的收貨地址?；颊呤肇洉r，向快遞人員出示收貨驗證碼,快遞人員使用該驗證碼確認藥品已送到?，F(xiàn)采用面向?qū)ο蠓治雠c設(shè)計方法開發(fā)上述系統(tǒng)，得到如圖3-1所示的用例圖以及圖3-2所示的類圖。簡要解釋用例之間的include，extend和generalie關(guān)系的內(nèi)涵。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(包含(include)：include為包含關(guān)系，當(dāng)兩個或多個用例中共用一組相同的動作，這時可以將這組相同的動作抽出來作為一個獨立的子用例，供多個基用例所共享。因為子用例被抽出，基用例并非一個完整的用例，所以include關(guān)系中的基用例必須和子用例一起使用才夠完整，子用例也必然被執(zhí)行。include關(guān)系在用例圖中使用帶箭頭的虛線表示(在線上標(biāo)注include>>)，箭頭從基用例指向子用例。擴展(extend)：extend關(guān)系是對基用例的擴展，基用例是一個完整的用例，即使沒有子用例的參與，也可以完成一個完整的功能。extend的基用例中將存在一個擴展點，只有當(dāng)擴展點被激活時，子用例才會被執(zhí)行。extend關(guān)系在用例圖中使用帶箭頭的虛線表示(在線上標(biāo)注extend>>)，箭頭從子用例指向基用例。泛化(generalization)：泛化關(guān)系是一種繼承關(guān)系，子用例將繼承基用例的所有行為，關(guān)系和通信關(guān)系，也就是說在任何使用基用例的地方都可以用子用例來代替。泛化關(guān)系在用例圖中使用空心的箭頭表示，箭頭方向從子用例指向基用例。)解析：11.凸多邊形是指多邊形的任意兩點的連線均落在多邊形的邊界或者內(nèi)部。相鄰的點連線落在多邊形邊上，稱為邊，不相鄰的點連線落在多邊形內(nèi)部，稱為弦。假設(shè)任意兩點連線上均有權(quán)重，凸多邊形最優(yōu)三角剖分問題定義為:求將凸多邊形劃分為不相交的三角形集合，且各三角形權(quán)重之和最小的剖分方案。每個三角形的權(quán)重為三條邊權(quán)重之和。假設(shè)N個點的凸多邊形，點編號為V1,V2,..Vn，若在Vk處將原凸多邊形劃分為一個三角形V1VkVn，兩個子凸多邊形V1,V2,...,Vk和Vk,Vk+1,.....Vn。到一個最優(yōu)的剖分方案，則該最優(yōu)剖分方案應(yīng)該包含這兩個子凸多邊形的最優(yōu)剖分方案。用m[i][j]表示點Vi-1,Vi….Vj構(gòu)成的凸多邊形的最優(yōu)剖分方案的權(quán)重，s[i][j]記錄剖分該凸多邊形的k值。則:其中，W(Vi-1,VkVj)=Wi-1,k+Wk,j+Wj,i-1為三角形Vi-1VkVj的權(quán)重，Wi-1,Wk,j,Wj,i-1分別為該三角形三條邊的權(quán)重。求解凸多邊形的最優(yōu)剖分方案，即求解最小剖分的權(quán)重及對應(yīng)的三角形集。C代碼#includestdio.h>#defineN6//凸多邊形規(guī)模intm[N+1][N+1];//m[i][j]表示多邊形Vi-1到Vj最優(yōu)三角剖分的權(quán)值ints[N+1][N+1];//s[i][j]記錄多邊形Vi-1到Vj最優(yōu)三角剖分的k值intw[N+1][N+1];//凸多邊形的權(quán)重矩陣，在main函數(shù)中輸入/*三角形的權(quán)重a,b,c，三角形的頂點下標(biāo)*/intget_triangle_weight(inta,intb,intc){

returnW[a][b]+W[b][c]+W[c][a];}/*求解最優(yōu)值*/voidtriangle_partition(){

inti,r,k,j;

inttemp;

/*初始化*/

for(i=1;i=N;i++){

m[i][j]=0;}/*自底向上計算m,S*/for(r=2;(1);r++){/*r為子問題規(guī)模*/

for(i=1;K=N-r+1;i++){

(2)

m[i][j]=m[i][j]+m[i+1][j]+get_triangle_weight(i-1,i,j);

/*k=j*/

S[i][j]=i;

for(k=i+1;kj;k++){/*計算m[i][j]的最小代價*/

temp=m[i][k]+m[k+1][j]+get_triangle_weight(i-1,k,j);

if((3)){

/*判斷是否是最小值*/}

m[i][j]=temp;

S[i][j]=k;

}

}}/*輸出剖分的三角形i,j;凸多邊形的起始點下標(biāo)*/voidprint_triangle(inti,intj){

if(i==j)return;

print_triangle(i,S[i][j]);

print_triangle((4));

printf("V%d--V%d--V%d\n",i-1,S[i][j],j);}根據(jù)說明和C代碼，填充C代碼中的空（1）~（4）。

（分數(shù)：1.00）__________________________________________________________________________________________

正確答案：(（1）r=N（2）j=i+r-1;（3）tempm[i][j]（4）s[i][j]+1,j)解析：12.凸多邊形是指多邊形的任意兩點的連線均落在多邊形的邊界或者內(nèi)部。相鄰的點連線落在多邊形邊上，稱為邊，不相鄰的點連線落在多邊形內(nèi)部，稱為弦。假設(shè)任意兩點連線上均有權(quán)重，凸多邊形最優(yōu)三角剖分問題定義為:求將凸多邊形劃分為不相交的三角形集合，且各三角形權(quán)重之和最小的剖分方案。每個三角形的權(quán)重為三條邊權(quán)重之和。假設(shè)N個點的凸多邊形，點編號為V1,V2,..Vn，若在Vk處將原凸多邊形劃分為一個三角形V1VkVn，兩個子凸多邊形V1,V2,...,Vk和Vk,Vk+1,.....Vn。到一個最優(yōu)的剖分方案，則該最優(yōu)剖分方案應(yīng)該包含這兩個子凸多邊形的最優(yōu)剖分方案。用m[i][j]表示點Vi-1,Vi….Vj構(gòu)成的凸多邊形的最優(yōu)剖分方案的權(quán)重，s[i][j]記錄剖分該凸多邊形的k值。則:其中，W(Vi-1,VkVj)=Wi-1,k+Wk,j+Wj,i-1為三角形Vi-1VkVj的權(quán)重，Wi-1,Wk,j,Wj,i-1分別為該三角形三條邊的權(quán)重。求解凸多邊形的最優(yōu)剖分方案，即求解最小剖分的權(quán)重及對應(yīng)的三角形集。C代碼#includestdio.h>#defineN6//凸多邊形規(guī)模intm[N+1][N+1];//m[i][j]表示多邊形Vi-1到Vj最優(yōu)三角剖分的權(quán)值ints[N+1][N+1];//s[i][j]記錄多邊形Vi-1到Vj最優(yōu)三角剖分的k值intw[N+1][N+1];//凸多邊形的權(quán)重矩陣，在main函數(shù)中輸入/*三角形的權(quán)重a,b,c，三角形的頂點下標(biāo)*/intget_triangle_weight(inta,intb,intc){

returnW[a][b]+W[b][c]+W[c][a];}/*求解最優(yōu)值*/voidtriangle_partition(){

inti,r,k,j;

inttemp;

/*初始化*/

for(i=1;i=N;i++){

m[i][j]=0;}/*自底向上計算m,S*/for(r=2;(1);r++){/*r為子問題規(guī)模*/