省考軟件設(shè)計(jì)師考試模擬題及答案資格證從業(yè)考試題卷(9)

1、 軟件設(shè)計(jì)師考試模擬題及答案-試題一某大學(xué)欲開(kāi)發(fā)一個(gè)基于Web的課程注冊(cè)系統(tǒng)，該系統(tǒng)的主要功能如下：1. 驗(yàn)證輸入信息(1) 檢查學(xué)生信息：檢查學(xué)生輸入的所有注冊(cè)所需信息。如果信息不合法，返回學(xué)生信息不合法提示；如果合法，輸出合法學(xué)生信息。(2) 檢查學(xué)位考試結(jié)果：檢查學(xué)生提供的學(xué)位考試結(jié)果。如果不合法，返回學(xué)位考試結(jié)果不合法提示；如果合法，檢査該學(xué)生注冊(cè)資格。(3) 檢查學(xué)生注冊(cè)資格：根據(jù)合法學(xué)生信息和合法學(xué)位考試結(jié)果，檢查該學(xué)生對(duì)欲選課程的注冊(cè)資格。如果無(wú)資格，返回?zé)o注冊(cè)資格提示；如果有注冊(cè)資格，則輸出注冊(cè)學(xué)生信息（包含選課學(xué)生標(biāo)識(shí)）和欲注冊(cè)課程信息。2. 處理注冊(cè)申請(qǐng)(1) 存儲(chǔ)注冊(cè)信息

2、：將注冊(cè)學(xué)生信息記錄在學(xué)生庫(kù)。(2) 存儲(chǔ)所注冊(cè)課程：將選課學(xué)生標(biāo)識(shí)與欲注冊(cè)課程進(jìn)行關(guān)聯(lián)，然后存入課程庫(kù)。(3) 發(fā)送注冊(cè)通知：從學(xué)生庫(kù)中讀取注冊(cè)學(xué)生信息，從課程庫(kù)中讀取所注冊(cè)課程信息，給學(xué)生發(fā)送接受提示；給教務(wù)人員發(fā)送所注冊(cè)課程信息和已注冊(cè)學(xué)生信息?，F(xiàn)采用結(jié)構(gòu)化方法對(duì)課程注冊(cè)系統(tǒng)進(jìn)行分析與設(shè)計(jì)，獲得如圖1-1所示的0層數(shù)據(jù)流圖和圖1-2所示的1層數(shù)據(jù)流圖?！締?wèn)題1】使用說(shuō)明中的詞語(yǔ)，給出圖1-1中的實(shí)體E1和E2的名稱。E1：學(xué)生 E2：教務(wù)人員本問(wèn)題考查0層DFD，要求確定外部實(shí)體。不難看出，在0層DFD中，系統(tǒng)主要功能“驗(yàn)證輸入信息”和“處理注冊(cè)申請(qǐng)”，涉及與系統(tǒng)交互的外部實(shí)體有“學(xué)生”

3、提供輸入信息，發(fā)送注冊(cè)通知功能給“教務(wù)人員”發(fā)送所注冊(cè)的課程信息和已注冊(cè)的學(xué)生信息，從而即可確定E1為“學(xué)生”實(shí)體，E2為“教務(wù)人員”實(shí)體?！締?wèn)題2】使用說(shuō)明中的詞語(yǔ)，給出圖1-2中的數(shù)據(jù)存儲(chǔ)D1和D2的名稱。D1：學(xué)生庫(kù) D2：課程庫(kù)本問(wèn)題要求確定1層數(shù)據(jù)流圖中的數(shù)據(jù)存儲(chǔ)。分析說(shuō)明中和數(shù)據(jù)存儲(chǔ)有關(guān)的描述，不難發(fā)現(xiàn)，說(shuō)明2.(1)存儲(chǔ)注冊(cè)信息明確說(shuō)明“將注冊(cè)學(xué)生信息記錄在學(xué)生庫(kù)”，可知D1為學(xué)生庫(kù)；說(shuō)明2.(2)存儲(chǔ)所注冊(cè)課程中明確說(shuō)明“然后存入課程庫(kù)”，可知D2為課程庫(kù)?！締?wèn)題3】根據(jù)說(shuō)明和圖中術(shù)語(yǔ)，補(bǔ)充圖1-2中缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)。 本問(wèn)題要求補(bǔ)充缺失的數(shù)據(jù)流及其起點(diǎn)和終點(diǎn)。細(xì)心的

4、考生可能會(huì)發(fā)現(xiàn)，對(duì)照?qǐng)D1-1和圖1-2的輸入數(shù)據(jù)流，數(shù)量和名稱均相同，所以缺失的數(shù)據(jù)流是輸出數(shù)據(jù)流或者處理之間的數(shù)據(jù)流?？疾閳D1-1中輸出至E1的數(shù)據(jù)流，有“接受提示”和“不合法提示”，而圖1-2中沒(méi)有這兩條數(shù)據(jù)流，可以確定缺失的數(shù)據(jù)流包括這兩條或者其分解的數(shù)據(jù)流?？疾檎f(shuō)明1中的3個(gè)子功能，1.(1)檢查學(xué)生信息完成檢查學(xué)生輸入的所有注冊(cè)所需信息。如果信息不合法，返回學(xué)生信息不合法提示。1.(2)檢查學(xué)位考試結(jié)果完成檢查學(xué)生提供的學(xué)位考試結(jié)果。如果不合法，返回學(xué)位考試結(jié)果不合法提示。1.(3)檢查學(xué)生注冊(cè)資格完成根據(jù)合法學(xué)生信息和合法學(xué)位考試結(jié)果，檢查該學(xué)生對(duì)欲選課程的注冊(cè)資格。如果無(wú)資格，返

5、回?zé)o注冊(cè)資格提示。對(duì)應(yīng)圖1-1中的處理1驗(yàn)證輸入信息的輸出數(shù)據(jù)流“不合法提示”，不難發(fā)現(xiàn)，在圖1-2中，處理1.1缺少了到實(shí)體學(xué)生的輸出數(shù)據(jù)流“學(xué)生信息不合法提示”；處理1.2缺少了到實(shí)體學(xué)生的輸出數(shù)據(jù)流“無(wú)注冊(cè)資格提示”；處理1.3缺少了到實(shí)體學(xué)生的輸出數(shù)據(jù)流“學(xué)位考試結(jié)果不合法提示”。再考查圖1-1中處理2,其輸出數(shù)據(jù)流有三條，而圖1-2中對(duì)圖1-1中處理2的分解中，只包含了“所注冊(cè)課程信息”和“已注冊(cè)學(xué)生信息”兩條數(shù)據(jù)流，缺失了“接受提示”。說(shuō)明2.(3)中發(fā)送注冊(cè)通知功能完成從學(xué)生庫(kù)中讀取注冊(cè)學(xué)生信息，從課程庫(kù)中讀取所注冊(cè)課程信息，給學(xué)生發(fā)送接受提示；給教務(wù)人員發(fā)送所注冊(cè)課程信息和己注

6、冊(cè)學(xué)生信息。所以，缺失的“接受提示”的起點(diǎn)是處理2.3發(fā)送注冊(cè)通知，終點(diǎn)是E1學(xué)生?！締?wèn)題4】根據(jù)補(bǔ)充完整的圖1-1和圖1-2,說(shuō)明上層的哪些數(shù)據(jù)流是由下層的哪些數(shù)據(jù)流組合而成。圖1-1中不合法提示分解為圖1-2中的三條數(shù)據(jù)流的組合：學(xué)生信息不合法提示、無(wú)注冊(cè)資格提示、學(xué)位考試結(jié)果不合法提示。圖1-1中注冊(cè)學(xué)生信息對(duì)應(yīng)圖1-2中注冊(cè)學(xué)生信息和選課學(xué)生標(biāo)識(shí)。本問(wèn)題考查數(shù)據(jù)流的分解與組合。仔細(xì)分析【說(shuō)明】中的文字并與圖1-1的對(duì)照，可以發(fā)現(xiàn)在圖1-1中不合法提示在圖1-2中沒(méi)有出現(xiàn)。事實(shí)上，從前述【問(wèn)題3】缺失數(shù)據(jù)流的分析中，己經(jīng)發(fā)現(xiàn)，圖1-2中對(duì)于說(shuō)明中的功能出現(xiàn)了“學(xué)生信息不合法提示”、“無(wú)注

7、冊(cè)資格提示”和“學(xué)位考試結(jié)果不合法提示”三條數(shù)據(jù)流，說(shuō)明圖1-1中的數(shù)據(jù)流“不合法提示”是由這三條數(shù)據(jù)流組合而成。同樣，2.(2)存儲(chǔ)所注冊(cè)課程將選課學(xué)生標(biāo)識(shí)與欲注冊(cè)課程進(jìn)行關(guān)聯(lián)，然后存入課程庫(kù)，圖1-1中注冊(cè)學(xué)生信息在圖1-2中進(jìn)一步分出注冊(cè)學(xué)生信息和選課學(xué)生標(biāo)識(shí)，即圖1-1中注冊(cè)學(xué)生信息是注冊(cè)學(xué)生信息和選課學(xué)生標(biāo)識(shí)的并集。試題二某快遞公司為了方便管理公司物品運(yùn)送的各項(xiàng)業(yè)務(wù)活動(dòng)，需要構(gòu)建一個(gè)物品運(yùn)送信息管理系統(tǒng)?！拘枨蠓治鼋Y(jié)果】(1) 快遞公司有多個(gè)分公司，分公司信息包括分公司編號(hào)、名稱、經(jīng)理、辦公電話和地址。每個(gè)分公司可以有多名員工處理分公司的日常業(yè)務(wù)，每名員工只能在一個(gè)分公司工作。每個(gè)分

8、公司由一名經(jīng)理負(fù)責(zé)管理分公司的業(yè)務(wù)和員工，系統(tǒng)需要記錄每個(gè)經(jīng)理的任職時(shí)間。(2) 員工信息包括員工號(hào)、姓名、崗位、薪資、手機(jī)號(hào)和家庭地址。其中，員工號(hào)唯一標(biāo)識(shí)員工信息的每一個(gè)元組。崗位包括經(jīng)理、調(diào)度員、業(yè)務(wù)員等。業(yè)務(wù)員根據(jù)客戶提交的快件申請(qǐng)單進(jìn)行快件受理事宜，一個(gè)業(yè)務(wù)員可以受理多個(gè)客戶的快件申請(qǐng)，一個(gè)快件申請(qǐng)只能由一個(gè)業(yè)務(wù)員受理。調(diào)度員根據(jù)已受理的申請(qǐng)單安排快件的承運(yùn)事宜，例如：執(zhí)行承運(yùn)的業(yè)務(wù)員、運(yùn)達(dá)時(shí)間等。一個(gè)業(yè)務(wù)員可以執(zhí)行調(diào)度員安排的多個(gè)快件的承運(yùn)業(yè)務(wù)。(3)客戶信息包括客戶號(hào)、單位名稱、通信地址、所屬省份、聯(lián)系人、聯(lián)系電話、銀行賬號(hào)。其中，客戶號(hào)唯一標(biāo)識(shí)客戶信息的每一個(gè)元組。當(dāng)客戶要寄快

9、件時(shí)，先要提交快件申請(qǐng)單，申請(qǐng)?zhí)栍上到y(tǒng)自動(dòng)生成?？旒暾?qǐng)信息包括申請(qǐng)?zhí)枴⒖蛻籼?hào)、發(fā)件人、發(fā)件人電話、快件名稱、運(yùn)費(fèi)、發(fā)出地、收件人、收件人電話、收件地址。其中，一個(gè)申請(qǐng)?zhí)枌?duì)應(yīng)唯一的一個(gè)快件申請(qǐng)，一個(gè)客戶可以提交多個(gè)快件申請(qǐng)，但一個(gè)快件申請(qǐng)由唯一的一個(gè)客戶提交?！靖拍钅Ｐ驮O(shè)計(jì)】根據(jù)需求階段收集的信息，設(shè)計(jì)的實(shí)體聯(lián)系圖（圖2-1)和關(guān)系模式（不完整）如下：【關(guān)系模式設(shè)計(jì)】分公司（分公司編號(hào)，名稱，經(jīng)理，辦公電話，地址）員工（員工號(hào)，姓名，(a),崗位，薪資，手機(jī)號(hào)，家庭地址）客戶（客戶號(hào)，單位名稱，通信地址，所屬省份，聯(lián)系人，聯(lián)系電話，銀行賬號(hào)）申請(qǐng)單( (b) ,發(fā)件人，發(fā)件人電話，發(fā)件人地址，

10、快件名稱，運(yùn)費(fèi)，收件人，收件人電話，收件地址，受理標(biāo)志，業(yè)務(wù)員）安排承運(yùn)( （c） ，實(shí)際完成時(shí)間，調(diào)度員）【問(wèn)題1】根據(jù)問(wèn)題描述，補(bǔ)充五個(gè)聯(lián)系，完善圖2-1的實(shí)體聯(lián)系圖。聯(lián)系名可用聯(lián)系1、聯(lián)系2、聯(lián)系3、聯(lián)系4和聯(lián)系5代替，聯(lián)系的類型分為1:1、1:n和m:n(或1:1、1：*和*:*)。圖中的*可表示為m或n，對(duì)聯(lián)系名稱可不做要求，但不能出現(xiàn)重名。由“每個(gè)分公司有一位經(jīng)理”可知分公司與經(jīng)理之間的管理聯(lián)系類型為1:);由“每個(gè)分公司有多名員工處理日常事務(wù)，每個(gè)員工屬于一個(gè)分公司”可知分公司與員工間的所屬聯(lián)系類型為1:*;并且員工是經(jīng)理的超類型，經(jīng)理是員工的子類型。由“一個(gè)客戶可以有多個(gè)快件申

11、請(qǐng)，但一個(gè)快件申請(qǐng)對(duì)應(yīng)唯一的一個(gè)客戶”可知，客戶與申請(qǐng)單之間的提交聯(lián)系類型為1:*。由“業(yè)務(wù)員根據(jù)客戶提交的快件申請(qǐng)單進(jìn)行快件受理事宜，一個(gè)業(yè)務(wù)員可以受理多個(gè)客戶的快件申請(qǐng)，一個(gè)快件申請(qǐng)只能由一個(gè)業(yè)務(wù)員受理”可知業(yè)務(wù)員與申請(qǐng)單之間的受理聯(lián)系類型為1:*。由“調(diào)度根據(jù)已受理的申請(qǐng)單安排快件的承運(yùn)事宜，例如：執(zhí)行承運(yùn)的業(yè)務(wù)員、運(yùn)達(dá)時(shí)間等；一個(gè)業(yè)務(wù)員可以執(zhí)行調(diào)度安排的多個(gè)快件的承運(yùn)業(yè)務(wù)?！笨芍?，調(diào)度、業(yè)務(wù)員和申請(qǐng)單之間的承運(yùn)聯(lián)系類型為1:*:*?！締?wèn)題2】(1) 根據(jù)實(shí)體聯(lián)系圖，將關(guān)系模式中的空(a)（c)補(bǔ)充完整。(2) 給出員工、申請(qǐng)單和安排承運(yùn)關(guān)系模式的主鍵和外鍵。(1) (a)分公司編號(hào)(b

12、) 申請(qǐng)?zhí)?，客戶?hào)(c) 申請(qǐng)?zhí)?，業(yè)務(wù)員(1)完整的關(guān)系模式如下：分公司（分公司編號(hào)，名稱，辦公電話，地址）員工(員工號(hào)，姓名，分公_司_編_號(hào)，崗位，薪資，手機(jī)號(hào)，家庭地址）客戶(客戶號(hào)，單位名稱，通信地址，所屬省份，聯(lián)系人，聯(lián)系電話，銀行賬號(hào))申請(qǐng)單(申請(qǐng)?zhí)?，客方?hào)，發(fā)件人，發(fā)件人電話，發(fā)件人地址，快件名稱，運(yùn)費(fèi)，收件人，收件人電話，收件地址，受理標(biāo)志，業(yè)務(wù)員）安排承運(yùn)(申請(qǐng)?zhí)枺瑏唲?wù)炅，實(shí)際完成時(shí)間，調(diào)度員）(2)員工、申請(qǐng)單和安排承運(yùn)關(guān)系模式的主鍵和外鍵的分析如下：在申請(qǐng)單信息中，申請(qǐng)?zhí)栍上到y(tǒng)自動(dòng)生成，不會(huì)重復(fù)，可作為申請(qǐng)單的主鍵屬性，外鍵為客戶號(hào)，業(yè)務(wù)員；在員工信息中，員工號(hào)唯一標(biāo)識(shí)員

13、工信息的每一個(gè)元組，故為員工關(guān)系的主鍵屬性，外鍵為分公司編號(hào)；安排承運(yùn)關(guān)系模式的主鍵為申請(qǐng)?zhí)枺怄I為業(yè)務(wù)員和調(diào)度員。【問(wèn)題3】(1)客戶關(guān)系的通信地址可以進(jìn)一步分為郵編、省、市、街道，那么該屬性是否屬于簡(jiǎn)單屬性，為什么？請(qǐng)用100字以內(nèi)的文字說(shuō)明。(2)假設(shè)分公司需要增設(shè)一位經(jīng)理的職位，那么分公司與經(jīng)理之間的聯(lián)系類型應(yīng)修改為（d) ，分公司的主鍵應(yīng)修改為 （e) 。(1)該屬性不屬于簡(jiǎn)單屬性。因?yàn)楹?jiǎn)單屬性是原子的、不可再分的，復(fù)合屬性是可以細(xì)分為更小的部分（即劃分為別的屬性），本題客戶關(guān)系的通信地址可以進(jìn)一步分為郵編、省、市、街道，所以屬于復(fù)合屬性。(2) (d)1:n (e)分公司編號(hào)，經(jīng)理

14、(1) 客戶的通信地址屬性不屬于簡(jiǎn)單屬性。因?yàn)楦鶕?jù)題意，客戶關(guān)系的通信地址可以進(jìn)一步分為郵編、省、市、街道，而簡(jiǎn)單屬性是原子的、不可再分的，復(fù)合屬性可以細(xì)分為更小的部分（即劃分為別的屬性)。由于客戶的通信地址可以進(jìn)一步分為郵編、省、市、街道，故屬于復(fù)合屬性。(2) 根據(jù)題意，分公司需要增設(shè)一位經(jīng)理的職位，那么分公司與經(jīng)理之間的聯(lián)系類型應(yīng)修改為l:n，分公司的主鍵應(yīng)修改為分公司編號(hào)，經(jīng)理。試題三某航空公司會(huì)員積分系統(tǒng)（CFequentFlyer)的主要功能描述如下：乘客只要辦理該航空公司的會(huì)員卡，即可成為普卡會(huì)員（CBasic)。隨著飛行里程數(shù)的積累，可以從普卡會(huì)員升級(jí)到銀卡會(huì)員（CSilver

15、)或金卡會(huì)員（CGold)。非會(huì)員(CNonMember)不能累積里程數(shù).每年年末，系統(tǒng)根據(jù)會(huì)員在本年度累積的里程數(shù)對(duì)下一年會(huì)員等級(jí)進(jìn)行調(diào)整。普卡會(huì)員在一年內(nèi)累積的里程數(shù)若滿25,000英里但不足50,000英里，則自動(dòng)升級(jí)為銀卡會(huì)員；若累積的里程數(shù)在50,000英里以上，則自動(dòng)升級(jí)為金卡會(huì)員。銀卡會(huì)員在一年內(nèi)累積的里程數(shù)若在50,000英里以上，則自動(dòng)升級(jí)為金卡會(huì)員。若一年內(nèi)沒(méi)有達(dá)到對(duì)應(yīng)級(jí)別要求的里程數(shù)，則自動(dòng)降低會(huì)員等級(jí)。金卡會(huì)員一年內(nèi)累積的里程數(shù)若不足25,000英里，則自動(dòng)降級(jí)為普卡會(huì)員；若累積的里程數(shù)達(dá)到25,000英里，但是不足50,000英里，則自動(dòng)降級(jí)為銀卡會(huì)員。銀卡會(huì)員一年內(nèi)

16、累積的里程數(shù)若不足25,000英里，則自動(dòng)降級(jí)為普卡會(huì)員。采用面向?qū)ο蠓椒▽?duì)會(huì)員積分系統(tǒng)進(jìn)行分析與設(shè)計(jì)，得到如圖3-1所示的狀態(tài)圖和圖3-2所示的類圖?！締?wèn)題1】根據(jù)說(shuō)明中的描述，給出圖3-1中S1S3處所對(duì)應(yīng)的狀態(tài)以及T1T3處所對(duì)應(yīng)的遷移的名稱。S1：普卡、普卡會(huì)員S2：銀卡、銀卡會(huì)員S3：金卡、金卡會(huì)員T1:25000=里程數(shù)=50000 T3:里程數(shù)=50000UML中的狀態(tài)圖主要用于描述一個(gè)對(duì)象在其生存期間的動(dòng)態(tài)行為，表現(xiàn)一個(gè)對(duì)象所經(jīng)歷的裝填序列，引起狀態(tài)轉(zhuǎn)移的事件以及因狀態(tài)轉(zhuǎn)移而伴隨的動(dòng)作。圖中給出的是會(huì)員的狀態(tài)圖。圖中要求填充SI、S2、S3這三個(gè)狀態(tài)以及它們之間的變遷關(guān)系。本題

17、中會(huì)員有三種狀態(tài)：普卡、金卡和銀卡。根據(jù)說(shuō)明，辦理會(huì)員卡之后即可成為普卡會(huì)員，所以S1可以判定為普卡會(huì)員。當(dāng)“里程數(shù)滿25,000英里但不足50,000英里，則自動(dòng)升級(jí)為銀卡會(huì)員”，所以S2應(yīng)為銀卡會(huì)員，那么S3就應(yīng)該是金卡會(huì)員。T1、T2就是S2和S3之間的轉(zhuǎn)換原則。T3是S1-S2的轉(zhuǎn)換原則。由說(shuō)明可知，S2-S3(T2)：里程數(shù)在50,000英里以上;S3-S3(T1)：里程數(shù)達(dá)到25,000英里，但是不足50,000英里；S1-S3(T3)：累積的里程數(shù)在50,000英里以上?！締?wèn)題2】根據(jù)說(shuō)明中的描述，給出圖3-2中C1C4所對(duì)應(yīng)的類名（類名使用說(shuō)明中給出的英文詞匯）。Cl：CNon

18、MemberC2：CBasicC3：CSilverC4：CGold(C1C4的次序可以互換）由圖3-2可知，需要補(bǔ)充的是繼承結(jié)構(gòu)中的子類。根據(jù)題目說(shuō)明，能夠具有一般/特殊關(guān)系的只有不同級(jí)別的會(huì)員。所以C1C4依次應(yīng)該是：CNonMember、CBasic,CSilver,CGold。【問(wèn)題3】圖3-2所示的類圖中使用了哪種設(shè)計(jì)模式？在這種設(shè)計(jì)模式下，類CFrecuentFlyer必須具有的屬性是什么？C1C4中的travel方法應(yīng)具有什么功能？使用了State模式（狀態(tài)模式)。類CFrequentFlyer必須具有的屬性：CLevel的對(duì)象。travel方法的功能：計(jì)算飛行里程數(shù)，根據(jù)里程數(shù)判

19、斷是否需要調(diào)整會(huì)員級(jí)別（跳轉(zhuǎn)到不同的狀態(tài))。本題在設(shè)計(jì)類時(shí)使用到了狀態(tài)模式。狀態(tài)模式允許對(duì)象在內(nèi)部狀態(tài)變化時(shí)，變更其行為，并且修改其類。狀態(tài)模式的類圖如下所示。其中：環(huán)境類（Context):定義客戶感興趣的接口。維護(hù)一個(gè)ConcreteState子類的實(shí)例，這個(gè)實(shí)例定義當(dāng)前狀態(tài)。抽象狀態(tài)類（State):定義一個(gè)接口以封裝與Context的一個(gè)特定狀態(tài)相關(guān)的行為。具體狀態(tài)類（ConcreteState):每一子類實(shí)現(xiàn)一與Context的一個(gè)狀態(tài)相關(guān)的行為。圖3-2中的類CFrequentFlyer對(duì)應(yīng)上圖中的環(huán)境類，因此類CFrequentFlyer應(yīng)該有一個(gè)CLevel類的對(duì)象。trave

20、l方法的功能：計(jì)算飛行里程數(shù)，根據(jù)里程數(shù)判斷是否需要調(diào)整會(huì)員級(jí)別（跳轉(zhuǎn)到不同的狀態(tài))。試題四某工程計(jì)算中要完成多個(gè)矩陣相乘（鏈乘）的計(jì)算任務(wù)。兩個(gè)矩陣相乘要求第一個(gè)矩陣的列數(shù)等于第二個(gè)矩陣的行數(shù)，計(jì)算量主要由進(jìn)行乘法運(yùn)算的次數(shù)決定。采用標(biāo)準(zhǔn)的矩陣相乘算法，計(jì)算Amn*Bnp，需要m*n*p次乘法運(yùn)算。矩陣相乘滿足結(jié)合律，多個(gè)矩陣相乘，不同的計(jì)算順序會(huì)產(chǎn)生不同的計(jì)算量。以矩陣A110100，A2100 x5,A35x50三個(gè)矩陣相乘為例，若按（A1*A2)*A3計(jì)算，則需要進(jìn)行10*100*5+10*5*50=7500次乘法運(yùn)算；若按Al*(A2*A3)計(jì)算，則需要進(jìn)行100*5*50+10*1

21、00*50=75000次乘法運(yùn)算?？梢?jiàn)不同的計(jì)算順序?qū)τ?jì)算量有很大的影響。矩陣鏈乘問(wèn)題可描述為：給定n個(gè)矩陣，矩陣Ai的維數(shù)為pMXPi，其中i=1，2,，n。確定一種乘法順序，使得這n個(gè)矩陣相乘時(shí)進(jìn)行乘法的運(yùn)算次數(shù)最少。由于可能的計(jì)算順序數(shù)量非常龐大，對(duì)較大的n，用蠻力法確定計(jì)算順序是不實(shí)際的。經(jīng)過(guò)對(duì)問(wèn)題進(jìn)行分析，發(fā)現(xiàn)矩陣鏈乘問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即若A1*A2*An的一個(gè)最優(yōu)計(jì)算順序從第k個(gè)矩陣處斷開(kāi)，即分為Al*A2*“，*Ak和Ak+1*Ak-2*“，*An兩個(gè)子問(wèn)題，則該最優(yōu)解應(yīng)該包含Al*A2*-，*Ak的一個(gè)最優(yōu)計(jì)算順序和Ak+PAk+St-*An的一個(gè)最優(yōu)計(jì)算順序。據(jù)此構(gòu)造遞歸式

22、，其中，costij表示Ai+1*Ai+2*Aj+l的最優(yōu)計(jì)算的計(jì)算代價(jià)。最終需要求解cost0n-1?！綜代碼】算法實(shí)現(xiàn)采用自底向上的計(jì)算過(guò)程。首先計(jì)算兩個(gè)矩陣相乘的計(jì)算量，然后依次計(jì)算3個(gè)矩陣、4個(gè)矩陣n個(gè)矩陣相乘的最小計(jì)算量及最優(yōu)計(jì)算順序。下面是該算法的C語(yǔ)言實(shí)現(xiàn)。(1)主要變量說(shuō)明n：矩陣數(shù)seq：矩陣維數(shù)序列cost：二維數(shù)組，長(zhǎng)度為n*n,其中元素costiU表示Ai+1*Ai+2* *Aj+1的最優(yōu)計(jì)算的計(jì)算代價(jià)trace：二維數(shù)組，長(zhǎng)度為n*n,其中元素traceij表示Ai+1*Ai+2*，*Aj+1的最優(yōu)計(jì)算對(duì)應(yīng)的劃分位置，即k(2)函數(shù)cmm【問(wèn)題1】根據(jù)以上說(shuō)明和C代碼

23、，填充C代碼中的空（1)（4)。 (1) in-p(2) j=i+p(3) costik+costk+lj+seqi*seqk+1*seqj+1(4) tempTrace=k本問(wèn)題考查算法的實(shí)現(xiàn)。C程序中主要部分是三重循環(huán)，循環(huán)變量p定義了求解問(wèn)題的規(guī)模，因?yàn)槭亲缘紫蛏?，因此，p的值應(yīng)該是從1到n-1，即從規(guī)模為1的問(wèn)題一直到規(guī)模為n-1的問(wèn)題。循環(huán)變量i是要求解的子問(wèn)題的起始，從0開(kāi)始，最大為n-p-1，故（1)處應(yīng)填n-p。確定了i和p之后，下來(lái)就要確定j了，顯然，空（2)處為j=i+p。循環(huán)變量k是問(wèn)題Ai*Ai+1*_，*Aj的劃分位置，對(duì)每一個(gè)k，都要計(jì)算需要的計(jì)算成本，可以根據(jù)遞歸式來(lái)填寫(xiě)，空（3)處為costik+cos