2009年上半年軟件設計師上午試卷?海明校驗碼是在n個數據位之外增設k個校驗位，從而形成一個k+n位的新的碼字，使新的碼字的碼距比較均勻地拉大。n與k的關系是(1)。(1)A.2k-1N(1)A.2k-1NnkB.2n-1WnkC.nkD.n1-Wk?假設某硬盤由5個盤片構成(共有8個記錄面)，盤面有效記錄區域的外直徑為30cm，內直徑為10cm，記錄位密度為(2)A.C.250位度為(2)A.C.250位/mm，磁道密度為16道/mm，每磁道分16個扇區，每扇區512字節，則該硬盤的格式化容量約為(2)MB。8*(30—10)*10*250*168*1024*10248*(30—10)*10*250*16*168*1024*10248*(30—10)*10*2500*16*16*512B.2*1024*10248*(30—10)*10*250*16*512°2*1024*1024?―)是指按內容訪問的存儲器。C,高速緩存(Cache)D.隨機訪問存儲器(3)A.虛擬存儲器B.相聯存儲器C,高速緩存(Cache)D.隨機訪問存儲器(4)A.數據總線、地址總線、控制總線B.并行總線、串行總線、邏輯總線C.單工總線、雙工總線、外部總線D.邏輯總線、物理總線、內部總線計算機中常采用原碼、反碼、補碼和移碼表示數據，其中，±0編碼相同的是一(5)。5)A.原碼和補碼B.反碼和補碼C.補碼和移碼D.原碼和移碼某指令流水線由5段組成，第1、3、5段所需時間為At，第2、4段所需時間分別為3At、2At，如下圖所示，那么連續輸入n條指令時的吞吐率(單位時間內執行的指令個數)TP為(6)2AtAt2AtAtB.〔3B.〔3+3+2)山+33—1)金C.彩(3+2)也+下面關于漏洞掃描系統的敘述，錯誤的是。A.漏洞掃描系統是一種自動檢測目標主機安全弱點的程序黑客利用漏洞掃描系統可以發現目標主機的安全漏洞漏洞掃描系統可以用于發現網絡入侵者漏洞掃描系統的實現依賴于系統漏洞庫的完善網絡安全包含了網絡信息的可用性、保密性、完整性和網絡通信對象的真實性。其中，數字簽名是對的保護。A.可用性B.保密性C.連通性D.真實性計算機感染特洛伊木馬后的典型現象是一⑵。A.程序異常退出B.有未知程序試圖建立網絡連接C.郵箱被垃圾郵件填滿D.Windows系統黑屏?關于軟件著作權產生的時間，下面表述正確的是。A.自作品首次公開發表時B.自作者有創作意圖時C.自作品得到國家著作權行政管理部門認可時D.自作品完成創作之日?程序員甲與同事乙在乙家探討甲近期編寫的程序，甲表示對該程序極不滿意，說要棄之重寫，并將程序手稿扔到乙家垃圾筒。后來乙將甲這一程序稍加修改，并署乙名發表。以下說法正確的是(11)。A.乙的行為侵犯了甲的軟件著作權乙的行為沒有侵犯甲的軟件著作權，因為甲巳將程序手稿丟棄乙的行為沒有侵犯甲的著作權，因為乙巳將程序修改甲沒有發表該程序并棄之，而乙將程序修改后發表，故乙應享有著作權?PC機處理的音頻信號主要是人耳能聽得到的音頻信號，它的頻率范圍是_(12)。(12)A.300Hz?3400HzB.20Hz?20KHzC.10Hz?20KHzD.20Hz?44KHz?多媒體計算機圖像文件格式分為靜態圖像文件格式和動態圖像文件格式，二13)屬于靜態圖像文件格式。(13)A.MPGB.AVSC.JPGD.AVI?計算機獲取模擬視頻信息的過程中首先要進行(W—。(14)A.A/D變換B.數據壓縮C.D/A變換D,數據存儲?在采用面向對象技術構建軟件系統時，很多敏捷方法都建議的一種重要的設計活動是，它是一種重新組織的技術，可以簡化構件的設計而無需改變其功能或行為。(15)A.精化B.設計類C.重構D.抽象一個軟件開發過程描述了“誰做”、“做什么”、“怎么做”和“什么時候做”，RUP用(16)來表述“誰做”。(16)A.角色B.活動C.制品D.工作流某項目主要由A?I任務構成，其計劃圖(如下圖所示)展示了各任務之間的前后關系以及每個任務的工期(單位：天)，該項目的關鍵路徑是(17)。在不延誤項目總工期的情況下，任務A最多可以推遲開始的時間是一天。打崟：時問A.A—G—IB.A—D—F—H—IC.B—E—G—ID.C—F—H—IA.0B.2C.5D.7?軟件風險一般包含(19)兩個特性。A.救火和危機管理B.巳知風險和未知風險C.不確定性和損失D.員工和預算?函數調用時，基本的參數傳遞方式有傳值與傳地址兩種，。A.在傳值方式下，形參將值傳給實參在傳值方式下，實參不能是數組元素在傳地址方式下，形參和實參間可以實現數據的雙向傳遞在傳地址方式下，實參可以是任意的變量和表達式巳知某高級語言源程序A經編譯后得到機器C上的目標程序B，貝(21)。A.對B進行反編譯，不能還原出源程序A對B進行反匯編，不能得到與源程序A等價的匯編程序代碼對B進行反編譯，得到的是源程序A的變量聲明和算法流程對A和B進行交叉編譯，可以產生在機器C上運行的動態鏈接庫下面關于程序語言的敘述，錯誤的是(22)。A.腳本語言屬于動態語言，其程序結構可以在運行中改變腳本語言一般通過腳本引擎解釋執行，不產生獨立保存的目標程序php、JavaScript屬于靜態語言，其所有成分可在編譯時確定C語言屬于靜態語言，其所有成分可在編譯時確定在WindowsXP操作系統中，用戶利用“磁盤管理”程序可以對磁盤進行初始化、創建卷,—。通常將“C:\Windows\myprogram.exe”文件設置成只讀和隱藏屬性，以便控制用戶對該文件的訪問，這一級安全管理稱之為(24)安全管理。A.但只能使用FAT文件系統格式化卷但只能使用FAT32文件系統格式化卷但只能使用NTFS文件系統格式化卷D,可以選擇使用FAT、FAT32或NTFS文件系統格式化卷A.文件級B.目錄級C,用戶級D.系統級在移臂調度算法中，一算法可能會隨時改變移動臂的運動方向。A.電梯調度和先來先服務B.先來先服務和最短尋找時間優先單向掃描和先來先服務D.電梯調度和最短尋找時間優先設系統中有R類資源m個，現有n個進程互斥使用。若每個進程對R資源的最大需求為w，那么當m、n、w取下表的值時，對于下表中的a?e五種情況，(26)兩種情況可能會發生死鎖。對于這兩種情況，若將——,則不會發生死鎖。a<1111222441112：耳3全12：3A.a和bB.b和cC.c和dD.c和eA.n加1或w加B.m加1或w減11C.m減1或w加1D.m減1或w減1某文件系統采用鏈式存儲管理方案，磁盤塊的大小為1024字節。文件Myfile.doc由5個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊的大小相等，并依次存放在121、75、86、65和114號磁盤塊上。若需要存取文件的第5120邏輯字節處的信息，應該訪問號磁盤塊。A.75B.85C.65D.114軟件能力成熟度模型(CMM)將軟件能力成熟度自低到高依次劃分為5級。目前，達到CMM第3級(巳定義級)是許多組織努力的目標，該級的核心是_(29)。A.建立基本的項目管理和實踐來跟蹤項目費用、進度和功能特性使用標準開發過程(或方法論)構建(或集成)系統管理層尋求更主動地應對系統的開發問題連續地監督和改進標準化的系統開發過程RUP在每個階段都有主要目標，并在結束時產生一些制品。在結束時產生“在適當的平臺上集成的軟件產品”。(30)A.初期階段B.精化階段C.構建階段D.移交階段根據ISO/IEC9126軟件質量度量模型定義，一個軟件的時間和資源質量子特性屬于質量特性。(31)A.功能性B.效率C.可靠性D.易使用性McCabe度量法是通過定義環路復雜度，建立程序復雜性的度量，它基于一個程序模塊的程序圖中環路的個數。計算有向圖G的環路復雜性的公式為：V(G)=m-n+2,其中V(G)是有向圖G中的環路個數，m是G中的有向弧數，n是G中的節點數。下圖所示程序圖的程序復雜度是(32)。(32)A.2B.3C.4D.5在開發信息系統時，用于系統開發人員與項目管理人員溝通的主要文檔是二33)。(33)A.系統開發合同B.系統設計說明書C.系統開發計劃D.系統測試報告軟件工程每一個階段結束前，應該著重對可維護性進行復審。在系統設計階段的復審期間，應該從一(34)出發，評價軟件的結構和過程。(34)A.指出可移植性問題以及可能影響軟件維護的系統界面容易修改、模塊化和功能獨立的目的強調編碼風格和內部說明文檔可測試性?當用分支覆蓋法對以下流程圖進行測試時，至少需要設計（35）個測試用例。(?當用分支覆蓋法對以下流程圖進行測試時，至少需要設計（35）個測試用例。(35)A.4B.5C.6D.8?某銀行為了使其網上銀行系統能夠支持信用卡多幣種付款功能而進行擴充升級，這需要對數據類型稍微進行一些改變，這一狀況需要對網上銀行系統進行（36）維護。（36）A.正確性B.適應性C.完善性D.預防性?下面關于面向對象分析與面向對象設計的說法中，不正確的是一。（37）A.面向對象分析側重于理解問題B.面向對象設計側重于理解解決方案C.面向對象分析描述軟件要做什么D.面向對象設計一般不關注技術和實現層面的細節?在面向對象分析與設計中，（38）是應用領域中的核心類，一般用于保存系統中的信息以及提供針對這些信息的相關處理行為；是系統內對象和系統外參與者的聯系媒介；。40^主要是協調上述兩種類對象之間的交互。（38）A.控制類B.邊界類C.實體類D.軟件類（39）A.控制類B.邊界類C.實體類D.軟件類（40）A.控制類B.邊界類C.實體類D.軟件類?若類A僅在其方法Methodi中定義并使用了類B的一個對象，類A其它部分的代碼都不涉及類B，那么類A與類B的關系應為一（41）；若類A的某個屬性是類B的一個對象，并且類A對象消失時，類B對象也隨之消失，則類A與類B的關系應為（42）。（41）A.關聯B.依賴C.聚合D.組合（42）A.關聯B.依賴C.聚合D.組合?當不適合采用生成子類的方法對巳有的類進行擴充時，可以采用工3）設計模式動態地給一個對象添加一些額外的職責；當應用程序由于使用大量的對象，造成很大的存儲開銷時，可以采用（44）設計模式運用共享技術來有效地支持大量細粒度的對象；當想使用一個巳經存在的類，但其接口不符合需求時，可以采用（5）設計模式將該類的接口轉換成我們希望的接口。（43）A.命令（Command）（44）A.命令（Command）（45）A.命令（Command）B.適配器（Adapter）B.適配器（Adapter（43）A.命令（Command）（44）A.命令（Command）（45）A.命令（Command）B.適配器（Adapter）B.適配器（Adapter）B.適配器（Adapter）C.裝飾（Decorate）C.裝飾（Decorate）C.裝飾（Decorate）D.享元(Flyweight)D.享元(Flyweight)D.享元(Flyweight)?下圖屬于UML中的（46），其中，AccountManagement需要（47）調用CreditCardServices實現的IdentityVerifier接口實現IdentityVerifier接口并被Logger調用調用Logger實現的IdentityVerifier接口?下圖所示有限自動機的特點是一(48)一。(48)A.識別的0、1串是以0開頭且以1結尾B.識別的0、1串中1的數目為偶數C.識別的0、1串中0后面必須是1D.識別的0、1串中1不能連續出現?由a、b構造且僅包含偶數個a的串的集合用正規式表示為一。(49)A.(a*a)*b*B.(b*(ab*a)*)*C.(a*(ba*)*b)*D.(alb)*(aa)*?設某語言的語法規則用上下文無關文法G=(N,T,P,S表示，其中N是非終結符號的集合，T是終結符號的集合，P是產生式集合，S是開始符號，令V=NUT,那么符合該語言的句子是(50)。A.從S出發推導的、僅包含T中符號的符號串從N中符號出發推導的、僅包含T中符號的符號串從S出發推導的、包含V中符號的符號串從N中符號出發推導的、包含V中符號的符號串采用二維表格結構表達實體類型及實體間聯系的數據模型是*1^。A.層次模型B.網狀模型C.關系模型D.面向對象模型假設員工關系EMP(員工號，姓名，部門，部門電話，部門負責人，家庭住址，家庭成員，成員關系)如下表所示。如果一個部門可以有多名員工，一個員工可以有多個家庭成員，那么關系EMP屬于(52)，且—心問題；為了解決這一問題，應該將員工關系EMP分解為皿。以!完姓#部門部門電M<y關瘵0O1Ig部0012北京海*ii區1'J-張大軍00118083560012北京海蒲H1心001!盅澆劇80E3560012北京洵淀區1??此!堤麗妹妹0012808300121.阮：！由別瑋15號0012尤祁808^560012枷.i㈣■15落荏心帝0021幣場部EDS3580021叫?廠推皓七&爭國慶父親0021畢H市場部SDS35S0021四?廈他」尊4S.隼明母米0022卜'.學強Pi場割0021四?..1.父親0031財80S360四究科技籍以?號A.1NFB.2NFC.3NFD.BCNFA.無冗余、無插入異常和刪除異常B.無冗余，但存在插入異常和刪除異常C.存在冗余，但不存在修改操作的不一致D.存在冗余、修改操作的不一致，以及插入異常和刪除異常A.EMP1(員工號，姓名，家庭住址)EMP2(部門，部門電話，部門負責人)EMP3(員工號，家庭成員，成員關系)EMP1(員工號，姓名，部門，家庭住址)EMP2(部門，部門電話，部門負責人)EMP3(員工號，家庭成員，成員關系)EMP1(員工號，姓名，家庭住址)EMP2(部門，部門電話，部門負責人，家庭成員，成員關系)

EMP1(員工號，姓名，部門，部門電話，部門負責人，家庭住址)EMP2(員工號，家庭住址，家庭成員，成員關系)S))=(55)，對關系R、S進行自然連接后的屬性?關系R、S如下圖所示，關系代數表達式S))=(55)，對關系R、S進行自然連接后的屬性d124345d124345斗55-<56Au543631Qs3G-1B.<55JA.ABc152343Ac-593S33ABC53494AC-12445D.6A.3和0B.3和2C.6和0下面關于查找運算及查找表的敘述，錯誤的是。D.6A,哈希表可以動態創建二叉排序樹屬于動態查找表二分查找要求查找表采用順序存儲結構或循環鏈表結構順序查找方法既適用于順序存儲結構，也適用于鏈表結構下面關于圖(網)的敘述，正確的是。A.連通無向網的最小生成樹中，頂點數恰好比邊數多1若有向圖是強連通的，則其邊數至少是頂點數的2倍可以采用AOV網估算工程的工期關鍵路徑是AOE網中源點至匯點的最短路徑下面關于二叉排序樹的敘述，錯誤的是(59)。A.對二叉排序樹進行中序遍歷，必定得到結點關鍵字的有序序列B.依據關鍵字無序的序列建立二叉排序樹，也可能構造出單支樹若構造二叉排序樹時進行平衡化處理，則根結點的左子樹結點數與右子樹結點數的差值一定不超過1若構造二叉排序樹時進行平衡化處理，則根結點的左子樹高度與右子樹高度的差值一定不超過1下面關于棧和隊列的敘述，錯誤的是一。A.棧和隊列都是操作受限的線性表隊列采用單循環鏈表存儲時，只需設置隊尾指針就可使入隊和出隊操作的時間復雜度都為O(1)若隊列的數據規模n可以確定，則采用順序存儲結構比鏈式存儲結構效率更高利用兩個棧可以模擬一個隊列的操作，反之亦可下面關于二叉樹的敘述，正確的是一。A.完全二叉樹的高度h與其結點數n之間存在確定的關系在二叉樹的順序存儲和鏈式存儲結構中，完全二叉樹更適合采用鏈式存儲結構完全二叉樹中一定不存在度為1的結點完全二叉樹中必定有偶數個葉子結點?設L為廣義表，將head(L)定義為取非空廣義表的第一個元素，tail(L)定義為取非空廣義表除第一個元素外剩余元素構成的廣義表。若廣義表L=((x,y,z),a,(u,t,w))，則從L中取出原子項y的運算是—(62)——。A.head(tail(tail(L)))B.tail(head(head(L)))C.head(tail(head(L)))D.tail(tail(head(L)))現有16枚外形相同的硬幣，其中有一枚比真幣的重量輕的假幣，若采用分治法找出這枚假幣，至少比較-(63)——次才能夠找出該假幣。

TOC\o"1-5"\h\z（63）A.3B.4C.5D.6以下的算法設計方法中，以獲取問題最優解為目標。（64）A.回溯方法B.分治法C.動態規劃D.遞推歸并排序采用的算法設計方法屬于一d。（65）A.歸納法B,分治法C.貪心法D,回溯方法一個B類網絡的子網掩碼為，則這個網絡被劃分成了個子網。（66）A.2B.4C.6D.8?在Windows系統中設置默認路由的作用是—（67）（67）A.當主機接收到一個訪問請求時首先選擇的路由B.當沒有其它路由可選時最后選擇的路由訪問本地主機的路由必須選擇的路由?HTML＜body＞元素中，二68）屬性用于定義超鏈接被鼠標點擊后所顯示的顏色。（68）（68）A.alinkB.backgroundC.bgcolorHTML中＜tr＞標記用于定義表格的怎9）。（69）A.行B.列C.單元格以下不符合XML文檔語法規范的是一。（70）A.文檔的第一行必須是XML文檔聲明C.每個開始標記必須和結束標記配對使用Fornearlytenyears,theUnifiedModelingD.標題B.文檔必須包含根元素標記之間可以交叉嵌套Language(UML)hasbeentheindustrystandardforvisualizing,specifying,constructing,anddocumentingthe(71)ofaoftware-intensivesystem.Asthe(72)standardmodelinglanguage,theUMLfacilitatesommunicationandreducesconfusionamongproject(73)TherecentstandardizationofUML2.0hasfurtherextendedthelanguage'sscopeandviability.Itsinherentexpressivenessallowsusersto(74)everythingfromenterpriseinformationsystemsanddistributedWeb-basedapplicationstoreal-timeembeddedsystems.TheUMLisnotlimitedtomodelingsoftware.Infact,itisexpressiveenoughtomodel—(75)systems,suchasworkflowinthelegalsystem,thestructureandbehaviorofapatienthealthcaresystem,softwareengineeringinaircraftcombatsystems,andthedesignofhardware.TounderstandtheUML,youneedtoformaconceptualmodelofthelanguage,andthisrequireslearningthreemajorelements:theUML'sbasicbuildingblocks,therulesthatdictatehowthosebuildingblocksmaybeputtogether,andsomecommonmechanismsthatapplythroughouttheUML.(71)A.classesB.componentsC.sequencesD.artifacts(72)A.realB.legalC.defactoD.illegal(73)A.investorsB.developersC.designersD.stakeholders(74)A.modelB.codeC.testD.modify(75)A.non-hardwareB.non-softwareC.hardwareD.software2009年上半年軟件設計師下午試卷試題一（共15分）閱讀下列說明，回答問題1和問題2,將解答填入答題紙的對應欄內。【說明】假設某大型商業企業由商品配送中心和連鎖超市組成，其中商品配送中心包括采購、財務、配送等部門。為實現高效管理，設計了商品配送中心信息管理系統，其主要功能描述如下：系統接收由連鎖超市提出的供貨請求，并將其記錄到供貨請求記錄文件。在接到供貨請求后，從商品庫存記錄文件中進行商品庫存信息查詢。如果庫存滿足供貨請求，則給配送處理發送配送通知；否則，向采購部門發出缺貨通知。配送處理接到配送通知后，查詢供貨請求記錄文件，更新商品庫存記錄文件，并向配送部門發送配送單，在配送貨品的同時記錄配送信息至商品配送記錄文件。采購部門接到缺貨通知后，與供貨商洽談，進行商品采購處理，合格商品入庫，并記錄采購清單至采購清單記錄文

件、向配送處理發出配送通知，同時通知財務部門給供貨商支付貨款。該系統采用結構化方法進行開發，得到待修改的數據流圖（如圖1-1所示）。【問題1】（8分）JH1■110JH1■110、—E2E31度］1I?敖十同濟曰竺IH-4IF」1LJ,，->F謎E片qiIf.j.【問題1】（8分使用【說明】中的詞語，給出圖1-1中外部實體E1至E4的名稱和數據存儲D1至D4的名稱。【問題2】（7分）圖1-1中存在四處錯誤數據流，請指出各自的起點和終點；若將上述四條錯誤數據流刪除，為保證數據流圖的正確性，應補充三條數據流，請給出所補充數據流的起點和終點。（起點和終點請采用數據流圖1-1中的符號或名稱）試題二（共15分）閱讀下列說明，回答問題1至問題3,將解答填入答題紙的對應欄內。【說明】某集團公司擁有多個大型連鎖商場，公司需要構建一個數據庫系統以方便管理其業務運作活動。【需求分析結果】1.商場需要記錄的信息包括商場編號（編號唯一），商場名稱，地址和聯系電話。某商場信息如表2-1所示。表2-]商場信息表商場編號商場名稱地址聯系電話PS2101淮海商場淮海中路918號PS2902西大街商場西大街時代盛典大廈PS2903東大街商場碑林區東大街239號PS2901長安商場雁塔區長安中路38號2.每個商場包含有不同的部門，部門需要記錄的信息包括部門編號（集團公司分配），部門名稱，位置分布和聯系電話。某商場的部門信息如表2-2所示。表2-2部門信息表部門編號部門名稱位置分布聯系電話DT002財務部商場大樓六層82504342DT007后勤部商場地下副一層82504347DT021安保部商場地下副一層82504358DT005人事部商場大樓六層82504446DT001管理部商場裙樓三層825046683,每個部門雇用多名員工處理日常事務，每名員工只能隸屬于一個部門（新進員工在培訓期不隸屬于任何部門）。員工需要記錄的信息包括員工編號（集團公司分配），姓名，崗位，電話號碼和工資。員工信息如表2-3所示。表2-3員工信息表員工編號姓名uud崗位電話號碼工資XA3310周超理貨員1500.00SH1075劉飛防損員1500.00XA0048江雪花廣播員1428.00BJ3123張正華部門主管1876.004,每個部門的員工中有一名是經理，每個經理只能管理一個部門，系統需要記錄每個經理的任職時間。【概念模型設計】根據需求階段收集的信息，設計的實體聯系圖和關系模式（（不完整）如下:商場部門I經理———員工——圖2-1實體聯系圖【關系模式設計】商場（商場編號，商場名稱，地址，聯系電話）部門（部門編號，部門名稱，位置分布，聯系電話，）員工（員工編號，員工姓名，崗位，電話號碼，工資，上））經理（g，任職時間）【問題1】（6分）根據問題描述，補充四個聯系，完善圖2-1的實體聯系圖。聯系名可用聯系1、聯系2、聯系3和聯系4代替，聯系的類型分為1:1、1:n和m:n。【問題2】（6分）根據實體聯系圖，將關系模式中的空（a）?（c）補充完整，并分別給出部門、員工和經理關系模式的主鍵和外鍵。【問題3】（3分）為了使商場有緊急事務時能聯系到輪休的員工，要求每位員工必須且只能登記一位緊急聯系人的姓名和聯系電話，不同的員工可以登記相同的緊急聯系人。則在圖2-1中還需添加的實體是（1），該實體和圖2-1中的員工存在⑵聯系（填寫聯系類型九給出該實體的關系模式。試題三（共15分）閱讀下列說明和圖，回答問題1至問題3,將解答填入答題紙的對應欄內。【說明】某銀行計劃開發一個自動存提款機模擬系統（ATMSystem）o系統通過讀卡器CardReader）讀取ATM卡；系統與客戶（Customer）的交互由客戶控制臺（CustomerConsole）實現；銀行操作員（Operator）可控制系統的啟動（SystemStartup）和停止（SystemShutdown）；系統通過網絡和銀行系統（Bank）實現通信。當讀卡器判斷用戶巳將ATM卡插入后，創建會話（Session）。會話開始后，讀卡器進行讀卡，并要求客戶輸入個人驗證碼（PIN）。系統將卡號和個人驗證碼信息送到銀行系統進行驗證。驗證通過后，客戶可從菜單選擇如下事務（Transaction）：1,從ATM卡賬戶取款（Withdraw）；向ATM卡賬戶存款（Deposit）；進行轉賬（Transfer）；查詢（Inquire）ATM卡賬戶信息。一次會話可以包含多個事務，每個事務處理也會將卡號和個人驗證碼信息送到銀行系統進行驗證。若個人驗證碼錯誤，則轉個人驗證碼錯誤處理（InvalidPINProcess）。每個事務完成后，客戶可選擇繼續上述事務或退卡。選擇退卡時，系統彈出ATM卡，會話結束。系統采用面向對象方法開發，使用UML進行建模。系統的頂層用例圖如圖3-1所示，一次會話的序列圖（不考慮驗證）如圖3-2所示。消息名稱參見表3-1。表3-1可能的消息名稱列表名稱說明名稱說明cardInserted()ATM卡巳插入performTransaction()執行事務performSession()執行會話readCard()讀卡readPIN()讀取個人驗證碼PIN個人驗證碼信息creat(atm,this,card,pin)為當前會話創建事務create(this)為當前ATM創建話cardATM卡信息doAgain執行下一個事務ejectCard()彈出ATM卡【問題1】（7分）根據【說明】中的描述，給出圖3-1中A1和A2所對應的參與者，U1至U3所對應的用例，以及該圖中空（1）所對應的關系。（U1至U3的可選用例包括：Session、Transaction、InsertCard、InvalidPINProcess和Transfer）【問題2】（6分）根據【說明】中的描述，使用表3-1中的英文名稱，給出圖3-2中6?9對應的消息。【問題3】（2分）解釋圖3-1中用例U3和用例Withdraw、Deposit等四個用例之間的關系及其內涵。ATW1Sw■st&m圖3-1ATM系統頂層用例圖圖3-2一次會話的序列圖（無驗證消息）試題四（共15分）閱讀下列說明，回答問題1和問題2,將解答填入答題紙的對應欄內。【說明】現需在某城市中選擇一個社區建一個大型超市，使該城市的其它社區到該超市的距離總和最小。用圖模型表示該城市的地圖，其中頂點表示社區，邊表示社區間的路線，邊上的權重表示該路線的長度。現設計一個算法來找到該大型超市的最佳位置：即在給定圖中選擇一個頂點，使該頂點到其它各頂點的最短路徑之和最小。算法首先需要求出每個頂點到其它任一頂點的最短路徑，即需要計算任意兩個頂點之間的最短路徑；然后對每個頂點，計算其它各頂點到該頂點的最短路徑之和；最后，選擇最短路徑之和最小的頂點作為建大型超市的最佳位置。【問題1】（12分）本題采用Floyd-Warshall算法求解任意兩個頂點之間的最短路徑。巳知圖G的頂點集合為V=｛1,2,...,｝，w=｛wy為權重矩陣。設d俄）為從頂點i到頂點j的一條最短路徑的權重。當k=0時，不存在中間頂點，因此d（0）11Jjj=wij；當k>0時，該最短路徑上所有的中間頂點均屬于集合｛1,2,...,｝。若中間頂點包括頂點k，則d；）=d（：T）+d（i；若中間頂點不包括頂點k，則d（k）=d俄T）。于是得到如下遞歸式。kjijijI1Wijk=0d（k）_Jjn（d（k-i）），d（k-i）+d（k-i）k>olijikkj因為對于任意路徑，所有的中間頂點都在集合｛1,2,...,｝內，因此矩陣D（n）=｛dS）｝n*n給出了任意兩個頂點之間的最短路徑，即對所有i，jEV，dj）表示頂點i到頂點j的最短路徑。下面是求解該問題的偽代碼，請填充其中空缺的（1）至（6）處。偽代碼中的主要變量說明如下：W：權重矩陣n：圖的頂點個數SP：最短路徑權重之和數組，SP[i]表示頂點i到其它各頂點的最短路徑權重之和，i從1到nmin_SP：最小的最短路徑權重之和min_v：具有最小的最短路徑權重之和的頂點i：循環控制變量j：循環控制變量k：循環控制變量LOCATE-SHOPPINGMALL（W,n）

1D(0)=W2for(1)3fori=1ton4forj=1ton5ifd(k-1)^d(k-1)+d(k-1)ijikkj6(2)7else8(3)—9fori=1ton10SP[i]=011forj=1ton12(4)13min_SP=SP[1]14(5)15fori=2ton16ifmin_SP>SP[i]17min_SP=SP[i]18min_v=i19return(6)【問題2】（3分）【問題1】中偽代碼的時間復雜度為（用0符號表示）。從下列的3道試題（試題五至試題七）中任選1道解答。如果解答的試題數超過1道，則題號小的1道解答有效。試題五（共15分）閱讀下列說明和C函數代碼，將應填入（n）處的字句寫在答題紙的對應欄內。【說明】對二叉樹進行遍歷是二叉樹的一個基本運算。遍歷是指按某種策略訪問二叉樹的每個結點，且每個結點僅訪問一次的過程。函數InOrder（）借助棧實現二叉樹的非遞歸中序遍歷運算。設二叉樹采用二叉鏈表存儲，結點類型定義如下：typedefstructBtNode（ElemTypedata;/*結點的數據域，ElemType的具體定義省略*/structBtNode*lchild,*rchild;/*結點的左、右孩子指針域*/}BtNode,*BTree;在函數InOrder（）中，用棧暫存二叉樹中各個結點的指針，并將棧表示為不含頭結點的單向鏈表（簡稱鏈棧），其結點類型定義如下：typedefstructStNode（BTreeelem;/*鏈棧的結點類型*/structStNode*link;/*棧中的元素是指向二叉鏈表結點的指針*/}StNode;假設從棧頂到棧底的元素為en、en-1、…、e1，則不含頭結點的鏈棧示意圖如圖5-1所示。H（acklL1p————*————?*--e-b4ULL圖5-1鏈棧示意圖【C函數】

intInOrder（BTreeroot）/*實現二叉樹的非遞歸中序遍歷*/{BTreeptr;/*ptr用于指向二叉樹中的結點*/StNode*q;/*q暫存鏈棧中新創建或待刪除的結點指針*/StNode*stacktop=NULL;/*初始化空棧的棧頂指針stacktop*/ptr=root;/*ptr指向二叉樹的根結點*/while((1)||stacktop!=NULL){while(ptr!=NULL){q=(StNode*)malloc(sizeof(StNode));if(q==NULL)if(q==NULL)return-1;q->elem=ptr;——(2);stacktop=q;ptr=(3)}q=stacktop;(4);visit(q);ptr=(5);free(q);}return0;}/*InOrder*/試題六(共15分)閱讀下列說明和C++代碼，將應填入/*stacktop指向新的棧頂*//*進入左子樹*//*棧頂元素出棧*//*visit是訪問結點的函數，其具體定義省略*//*進入右子樹*//*釋放原棧頂元素的結點空間*/（n）處的字句寫在答題紙的對應欄內。【說明】現欲實現一個圖像瀏覽系統，要求該系統能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統上運行。系統首先將BMP、Linux兩種操作系統上運行。系統首先將BMP、JPEG和GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統需具有較好的擴展性以支持新的文件格式和操作系統。為滿足上述需求并減少所需生成的子類數目，采用橋接（Bridge）設計模式進行設計所得類圖如圖6-1所示。圖6-1類圖采用該設計模式的原因在于：系統解析BMP、GIF與JPEG文件的代碼僅與文件格式相關，而在屏幕上顯示像素矩陣的代碼則僅與操作系統相關。【C++代碼】classMatrix{〃各種格式的文件最終都被轉化為像素矩陣〃此處代碼省略};classImageImp{public:virtualvoiddoPaint(Matrixm)=0;〃顯示像素矩陣m}；classWinImp:publicImageImp(public:voiddoPaint(Matrixm)(/*調用windows系統的繪制函數繪制像素矩陣*/}};classLinuxImp:publicImageImp(public:voiddoPaint(Matrixm)(/*調用Linux系統的繪制函數繪制像素矩陣*/}};classImage{public:voidsetImp(ImageImp*imp){L1)=imp;}virtualvoidparseFile(stringfileName)=0;protected:(2)*imp;};classBMP:publicImage{public:voidparseFile(stringfileName){〃此處解析BMP文件并獲得一個像素矩陣對象m(3);//顯示像素矩陣m}};classGIF:publicImage{〃此處代碼省略};classJPEG:publicImage{//此處代碼省略};voidmain(){//在windows操作系統上查看demo.bmp圖像文件Image*image1=(4);ImageImp*imageImp1=(5);(6)image1->parseFile("demo.bmp");}現假設該系統需要支持10種格式的圖像文件和5種操作系統，不考慮類Matrix，若采用橋接設計模式則至少需要設計個類。試題七(共15分)閱讀下列說明和Java代碼，將應填入(n)處的字句寫在答題紙的對應欄內。【說明】現欲實現一個圖像瀏覽系統，要求該系統能夠顯示BMP、JPEG和GIF三種格式的文件，并且能夠在Windows和Linux兩種操作系統上運行。系統首先將BMP、JPEG和GIF三種格式的文件解析為像素矩陣，然后將像素矩陣顯示在屏幕上。系統需具有較好的擴展性以支持新的文件格式和操作系統。為滿足上述需求并減少所需生成的子類數目，采用橋接(Bridge)設計模式進行設計所得類圖如圖7-1所示。圖7-1類圖采用該設計模式的原因在于：系統解析BMP、GIF與JPEG文件的代碼僅與文件格式相關，而在屏幕上顯示像素矩陣的代碼則僅與操作系統相關。【Java代碼】classMatrix(〃各種格式的文件最終都被轉化為像素矩陣〃此處代碼省略}；abstractclassImageImp(publicabstractvoiddoPaint(Matrixm);〃顯示像素矩陣m};classWinImpextendsImageImp(publicvoiddoPaint(Matrixm)(/*調用windows系統的繪制函數繪制像素矩陣*/}};classLinuxImpextendsImageImp(publicvoiddoPaint(Matrixm)(/*調用Linux系統的繪制函數繪制像素矩陣*/}};abstractclassImage{publicvoidsetImp(ImageImpimp){};(1)=imp;}publicabstractvoidparseFile(StringfileName);protected(2)imp;classBMPextendsImage{publicvoidparseFile(StringfileName){//此處解析BMP文件并獲得一個像素矩陣對象m(3);//顯示像素矩陣m}};classGIFextendsImage{//此處代碼省略};classJPEGextendsImage{//此處代碼省略};publicclassjav