2008上半年軟件設(shè)計師上午試題●在計算機體系結(jié)構(gòu)中,CPU內(nèi)部包括程序計數(shù)器PC、存儲器數(shù)據(jù)寄存器MDR、指令寄存器IR和存儲器地址寄存器MAR等。若CPU要執(zhí)行的指令為:MOVR0,#100(即將數(shù)值100傳送到寄存器R0中),則CPU首先要完成的操作是(1)。(1)A.100→R0B.100→MDRC.PC→MARD.PC→IR●現(xiàn)有四級指令流水線,分別完成取指、取數(shù)、運算、傳送結(jié)果四步操作。若完成上述操作的時間依次為9ns、10ns、6ns、8ns,則流水線的操作周期應(yīng)設(shè)計為(2)ns。(2)A.6B.8C.9D.10●內(nèi)存按字節(jié)編址,地址從90000H到CFFFFH,若用存儲容量為16K×8bit的存儲器芯片構(gòu)成該內(nèi)存,至少需要(3)片。(3)A.2B.4C.8D.16●CPU中的數(shù)據(jù)總線寬度會影響(4)。(4)A.內(nèi)存容量的大小B.系統(tǒng)的運算速度C.指令系統(tǒng)的指令數(shù)量D.寄存器的寬度●利用高速通信網(wǎng)絡(luò)將多臺高性能工作站或微型機互連構(gòu)成機群系統(tǒng),其系統(tǒng)結(jié)構(gòu)形式屬于(5)計算機。(5)A.單指令流單數(shù)據(jù)流(SISD)B.多指令流單數(shù)據(jù)流(MISD)C.單指令流多數(shù)據(jù)流(SIMD)D.多指令流多數(shù)據(jù)流(MIMD)●內(nèi)存采用段式存儲管理有許多優(yōu)點,但“(6)”不是其優(yōu)點。(6)A.分段是信息的邏輯單位,用戶不可見B.各段程序的修改互不影響C.地址變換速度快、內(nèi)存碎片少D.便于多道程序共享主存的某些段●如果希望別的計算機不能通過ping命令測試服務(wù)器的連通情況,可以(7)。如果希望通過默認(rèn)的Telnet端口連接服務(wù)器,則下面對防火墻配置正確的是(8)。(7)A.刪除服務(wù)器中的ping.exe文件B.刪除服務(wù)器中的cmd.exe文件C.關(guān)閉服務(wù)器中ICMP端口D.關(guān)閉服務(wù)器中的NetLogon服務(wù)(8)A.B.C.D.●某銀行為用戶提供網(wǎng)上服務(wù),允許用戶通過瀏覽器管理自己的銀行賬戶信息。為保障通信的安全性,該Web服務(wù)器可選的協(xié)議是(9)。(9)A.POPB.SNMPC.HTTPD.HTTPS●關(guān)于軟件著作權(quán)產(chǎn)生的時間,表述正確的是(10)。(10)A.自軟件首次公開發(fā)表時B.自開發(fā)者有開發(fā)意圖時C.自軟件得到國家著作權(quán)行政管理部門認(rèn)可時D.自軟件完成創(chuàng)作之日起●李某大學(xué)畢業(yè)后在學(xué)賽網(wǎng)銷售部門工作,后由于該公司軟件開發(fā)部門人手較緊,李某被暫調(diào)到該公司軟件開發(fā)部開發(fā)新產(chǎn)品,2周后,李某開發(fā)出一種新軟件。該軟件著作權(quán)應(yīng)歸(11)所有。(11)A.李某B.學(xué)賽網(wǎng)C.李某和學(xué)賽網(wǎng)D.軟件開發(fā)部●一幅灰度圖像,若每個像素有8位像素深度,則最大灰度數(shù)目為(12)。(12)A.128B.256C.512D.1024●當(dāng)圖像分辨率為800×600,屏幕分辨率為640×480時,(13)。(13)A.屏幕上顯示一幅圖像的64%左右B.圖像正好占滿屏幕C.屏幕上顯示一幅完整的圖像D.圖像只占屏幕的一部分●若視頻圖像每幀的數(shù)據(jù)量為6.4MB,幀速率為30幀/秒,則顯示10秒的視頻信息,其原始數(shù)據(jù)量為(14)MB。(14)A.64B.192C.640D.1920●(15)是一種面向數(shù)據(jù)流的開發(fā)方法,其基本思想是軟件功能的分解和抽象。(15)A.結(jié)構(gòu)化開發(fā)方法B.Jackson系統(tǒng)開發(fā)方法C.Booch方法D.UML(統(tǒng)一建模語言)●采用UML進(jìn)行軟件設(shè)計時,可用(16)關(guān)系表示兩類事物之間存在的特殊/一般關(guān)系,用聚集關(guān)系表示事物之間存在的整體/部分關(guān)系。(16)A.依賴B.聚集C.泛化D.實現(xiàn)●某項目制定的開發(fā)計劃中定義了三個任務(wù),其中任務(wù)A首先開始,且需要3周完成,任務(wù)B必須在任務(wù)A啟動1周后開始,且需要2周完成,任務(wù)C必須在任務(wù)A完成后才能開始,且需要2周完成。該項目的進(jìn)度安排可用下面的甘特圖(17)來描述。●風(fēng)險分析在軟件項目開發(fā)中具有重要作用,包括風(fēng)險識別、風(fēng)險預(yù)測、風(fēng)險評估和風(fēng)險控制等?！敖L(fēng)險條目檢查表”是(18)時的活動,“描述風(fēng)險的結(jié)果”是(19)時的活動。(18)(19)A.風(fēng)險識別B.風(fēng)險預(yù)測C.風(fēng)險評估D.風(fēng)險控制●編譯器對高級語言源程序的處理過程可以劃分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等幾個階段,其中,(20)并不是每種編譯器都必需的。(20)A.詞法分析和語法分析B.語義分析和中間代碼生成C.中間代碼生成和代碼優(yōu)化D.代碼優(yōu)化和目標(biāo)代碼生成●已知某文法G[S]:S→0S0S→1,從S推導(dǎo)出的符號串可用(21)(n≥0)描述。(21)A.(010)nB.0n10nC.1nD.01n0●下列敘述中錯誤的是(22)。(22)A.面向?qū)ο蟪绦蛟O(shè)計語言可支持過程化的程序設(shè)計B.給定算法的時間復(fù)雜性與實現(xiàn)該算法所采用的程序設(shè)計語言無關(guān)C.與匯編語言相比,采用腳本語言編程可獲得更高的運行效率D.面向?qū)ο蟪绦蛟O(shè)計語言不支持對一個對象的成員變量進(jìn)行直接訪問●某火車票銷售系統(tǒng)有n個售票點,該系統(tǒng)為每個售票點創(chuàng)建一個進(jìn)程Pi(i=1,2,Λ,n)。假設(shè)Hj(j=1,2,Λ,m)單元存放某日某車次的剩余票數(shù),Temp為Pi進(jìn)程的臨時工作單元,x為某用戶的訂票張數(shù)。初始化時系統(tǒng)應(yīng)將信號量S賦值為(23)。Pi進(jìn)程的工作流程如下,若用P操作和V操作實現(xiàn)進(jìn)程間的同步與互斥,則圖中a、b和c應(yīng)分別填入(24)。(23)A.0B.1C.2D.3(24)A.P(S)、V(S)和V(S)B.P(S)、P(S)和V(S)C.V(S)、P(S)和P(S)D.V(S)、V(S)和P(S)●在下圖所示的樹型文件系統(tǒng)中,方框表示目錄,圓圈表示文件,“/”表示路徑中的分隔符,“/”在路徑之首時表示根目錄。圖中,(25)。假設(shè)當(dāng)前目錄是A2,若進(jìn)程A以如下兩種方式打開文件f2:方式①fd1=open(″(26)/f2″,o_RDONLY);方式②fd1=open(″/A2/C3/f2″,o_RDONLY);那么,采用方式①的工作效率比方式②的工作效率高。(25)A.根目錄中文件f1與子目錄C1、C2和C3中文件f1一定相同B.子目錄C1中文件f2與子目錄C3中文件f2一定相同C.子目錄C1中文件f2與子目錄C3中文件f2一定不同D.子目錄C1中文件f2與子目錄C3中文件f2是可能相同也可能不相同(26)A./A2/C3B.A2/C3C.C3D.f2●在某計算機中,假設(shè)某程序的6個頁面如下圖所示,其中某指令“COPYATOB”跨兩個頁面,且源地址A和目標(biāo)地址B所涉及的區(qū)域也跨兩個頁面。若地址為A和B的操作數(shù)均不在內(nèi)存,計算機執(zhí)行該COPY指令時,系統(tǒng)將產(chǎn)生(27)次缺頁中斷;若系統(tǒng)產(chǎn)生三次缺頁中斷,那么該程序應(yīng)有(28)個頁面在內(nèi)存。(27)A.2B.3C.4D.5(28)A.2B.3C.4D.5●極限編程(eXtremeProgramming)是一種輕量級軟件開發(fā)方法,(29)不是它強調(diào)的準(zhǔn)則。(29)A.持續(xù)的交流和溝通B.用最簡單的設(shè)計實現(xiàn)用戶需求C.用測試驅(qū)動開發(fā)D.關(guān)注用戶反饋●學(xué)賽網(wǎng)采用的軟件開發(fā)過程通過了CMM2認(rèn)證,表明該公司(30)。(30)A.開發(fā)項目成效不穩(wěn)定,管理混亂B.對軟件過程和產(chǎn)品質(zhì)量建立了定量的質(zhì)量目標(biāo)C.建立了基本的項目級管理制度和規(guī)程,可對項目的成本、進(jìn)度進(jìn)行跟蹤和控制D.可集中精力采用新技術(shù)新方法,優(yōu)化軟件過程●某數(shù)據(jù)處理軟件包括2個完全相同的數(shù)據(jù)處理部件和1個數(shù)據(jù)存儲部件,且采用下圖給出的容錯方案。當(dāng)數(shù)據(jù)處理部件的可靠性為0.6時,為使整個軟件系統(tǒng)的可靠性不小于0.66,則數(shù)據(jù)存儲部件的可靠性至少應(yīng)為(31)。(31)A.0.6B.0.66C.0.79D.1.0●在軟件設(shè)計和編碼過程中,采取“(32)”的做法將使軟件更加容易理解和維護(hù)。(32)A.良好的程序結(jié)構(gòu),有無文檔均可B.使用標(biāo)準(zhǔn)或規(guī)定之外的語句C.編寫詳細(xì)正確的文檔,采用良好的程序結(jié)構(gòu)D.盡量減少程序中的注釋●軟件維護(hù)成本在軟件成本中占較大比重。為降低維護(hù)的難度,可采取的措施有(33)。(33)A.設(shè)計并實現(xiàn)沒有錯誤的軟件B.限制可修改的范圍C.增加維護(hù)人員數(shù)量D.在開發(fā)過程中就采取有利于維護(hù)的措施,并加強維護(hù)管理●軟件文檔按照其產(chǎn)生和使用的范圍可分為開發(fā)文檔、管理文檔和用戶文檔。其中開發(fā)文檔不包括(34)。(34)A.軟件需求說明B.可行性研究報告C.維護(hù)修改建議D.項目開發(fā)計劃●軟件測試是軟件開發(fā)中不可缺少的活動,通常(35)在代碼編寫階段進(jìn)行。檢查軟件的功能是否與用戶要求一致是(36)的任務(wù)。(35)(36)A.驗收測試B.系統(tǒng)測試C.單元測試D.集成測試●(37)是指把數(shù)據(jù)以及操作數(shù)據(jù)的相關(guān)方法組合在同一個單元中,使我們可以把類作為軟件中的基本復(fù)用單元,提高其內(nèi)聚度,降低其耦合度。面向?qū)ο笾械?38)機制是對現(xiàn)實世界中遺傳現(xiàn)象的模擬,通過該機制,基類的屬性和方法被遺傳給派生類。(37)(38)A.封裝B.多態(tài)C.繼承D.變異●(39)以靜態(tài)或動態(tài)的連接方式,為應(yīng)用程序提供一組可使用的類。(40)除了提供可被應(yīng)用程序調(diào)用的類以外,還基本實現(xiàn)了一個可執(zhí)行的架構(gòu)。(39)(40)A.函數(shù)庫B.類庫C.框架D.類屬●已知某子系統(tǒng)為外界提供功能服務(wù),但該子系統(tǒng)中存在很多粒度十分小的類,不便被外界系統(tǒng)直接使用,采用(41)設(shè)計模式可以定義一個高層接口,這個接口使得這一子系統(tǒng)更加容易使用;當(dāng)不能采用生成子類的方法進(jìn)行擴充時,可采用(42)設(shè)計模式動態(tài)地給一個對象添加一些額外的職責(zé)。(41)(42)A.Facade(外觀)B.Singleton(單件)C.Participant(參與者)D.Decorator(裝飾)●(43)設(shè)計模式將抽象部分與它的實現(xiàn)部分相分離,使它們都可以獨立地變化。下圖為該設(shè)計模式的類圖,其中,(44)用于定義實現(xiàn)部分的接口。(43)A.Singleton(單件)B.Bridge(橋接)C.Composite(組合)D.Facade(外觀)(44)A.AbstractionB.ConcreteImplementorAC.ConcreteImplementorBD.Implementor●在UML類圖中,類與類之間存在依賴(Dependency)、關(guān)聯(lián)(Association)、聚合(Aggregation)、組合(Composition)和繼承(Inheritance)五種關(guān)系,其中,(45)關(guān)系表明類之間的相互聯(lián)系最弱,(46)關(guān)系表明類之間的相互聯(lián)系最強,聚合(Aggregation)的標(biāo)準(zhǔn)UML圖形表示是(47)。(45)(46)A.依賴B.聚合C.組合D.繼承●有限自動機(FA)可用于識別高級語言源程序中的記號(單詞),FA可分為確定的有限自動機(DFA)和不確定的有限自動機(NFA)。若某DFAD與某NFAM等價,則(48)。(48)A.DFAD與NFAM的狀態(tài)數(shù)一定相等B.DFAD與NFAM可識別的記號相同C.NFAM能識別的正規(guī)集是DFAD所識別正規(guī)集的真子集D.DFAD能識別的正規(guī)集是NFAM所識別正規(guī)集的真子集●某確定性有限自動機(DFA)的狀態(tài)轉(zhuǎn)換圖如下圖所示,令d=0|1|2|...|9,則以下字符串中,能被該DFA接受的是(49)。(49)A.3857B.1.2E+5C.-123.67D.0.576E10●若有數(shù)組聲明a[0..3,0..2,1..4],設(shè)編譯時為a分配的存儲空間首地址為base_a,且每個數(shù)組元素占據(jù)一個存儲單元。當(dāng)元素以行為序存放(即按a[0,0,1],a[0,0,2],a[0,0,3],a[0,0,4],a[0,1,1],a[0,1,2],…,a[3,2,4]順序存儲),則數(shù)組元素a[2,2,2]在其存儲空間中相對base_a的偏移量是(50)。(50)A.8B.12C.33D.48●從數(shù)據(jù)庫管理系統(tǒng)的角度看,數(shù)據(jù)庫系統(tǒng)一般采用如下圖所示的三級模式結(jié)構(gòu)。圖中①②處應(yīng)填寫(51),③處應(yīng)填寫(52)。(51)(52)A.外模式/概念模式B.概念模式/內(nèi)模式C.外模式/概念模式映象D.概念模式/內(nèi)模式映象●設(shè)有職工EMP(職工號,姓名,性別,部門號,職務(wù),進(jìn)單位時間,電話),職務(wù)JOB(職務(wù),月薪)和部門DEPT(部門號,部門名稱,部門電話,負(fù)責(zé)人)實體集。一個職務(wù)可以由多個職工擔(dān)任,但一個職工只能擔(dān)任一個職務(wù),并屬于一個部門,部門負(fù)責(zé)人是一個職工。下圖所示的a、b處的實體名分別為(53);圖中a、b之間為(54)聯(lián)系。(53)A.DEPT、EMPB.EMP、DEPTC.JOB、EMPD.EMP、JOB(54)A.11B.*1C.1*D.**●若關(guān)系R、S如下圖所示,則R與S自然連接后的屬性列數(shù)和元組個數(shù)分別為(55);1,4(3=6(RXS))=(56)。(55)A.4和3B.4和6C.6和3D.6和6●已知一個線性表(16,25,35,43,51,62,87,93),采用散列函數(shù)H(Key)=Keymod7將元素散列到表長為9的散列表中。若采用線性探測的開放定址法解決沖突(順序地探查可用存儲單元),則構(gòu)造的哈希表為(57),在該散列表上進(jìn)行等概率成功查找的平均查找長度為(58)(為確定記錄在查找表中的位置,需和給定關(guān)鍵字值進(jìn)行比較的次數(shù)的期望值稱為查找算法在查找成功時的平均查找長度)。(57)A.0123456783543165125628793B.0123456783543169325516287C.0123456783543165125876293D.0123456783543165125876293(58)A.(5*1+2+3+6)/8B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/9●若將某有序樹T轉(zhuǎn)換為二叉樹T1,則T中結(jié)點的后(根)序序列就是T1中結(jié)點的(59)遍歷序列。例如,下圖(a)所示的有序樹轉(zhuǎn)化為二叉樹后如圖(b)所示。(59)A.先序B.中序C.后序D.層序●設(shè)一個包含N個頂點、E條邊的簡單有向圖采用鄰接矩陣存儲結(jié)構(gòu)(矩陣元素A[i][j]等于1/0分別表示頂點i與頂點j之間有/無弧),則該矩陣的元素數(shù)目為(60),其中非零元素數(shù)目為(61)。(60)A.E2B.N2C.N2-E2D.N2+E2(61)A.NB.N+EC.ED.N–E●一個算法是對某類給定問題求解過程的精確描述,算法中描述的操作都可以通過將已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn),這句話說明算法具有(62)特性。(62)A.有窮性B.可行性C.確定性D.健壯性●斐波那契(Fibonacci)數(shù)列可以遞歸地定義為:用遞歸算法求解F(5)時需要執(zhí)行(63)次“+”運算,該方法采用的算法策略是(64)。(63)A.5B.6C.7D.8(64)A.動態(tài)規(guī)劃B.分治C.回溯D.分支限界●若總是以待排序列的第一個元素作為基準(zhǔn)元素進(jìn)行快速排序,那么最好情況下的時間復(fù)雜度為(65)?！襁\行Web瀏覽器的計算機與網(wǎng)頁所在的計算機要建立(66)連接,采用(67)協(xié)議傳輸網(wǎng)頁文件。(66)A.UDPB.TCPC.IPD.RIP(67)A.HTTPB.HTMLC.ASPD.RPC●(68)不屬于電子郵件協(xié)議。(68)A.POP3B.SMTPC.IMAPD.MPLS●某客戶端在采用ping命令檢測網(wǎng)絡(luò)連接故障時,發(fā)現(xiàn)可以ping通及本機的IP地址,但無法ping通同一網(wǎng)段內(nèi)其他工作正常的計算機的IP地址,說明該客戶端的故障是(69)。(69)A.TCP/IP協(xié)議不能正常工作B.本機網(wǎng)卡不能正常工作C.本機網(wǎng)絡(luò)接口故障D.本機DNS服務(wù)器地址設(shè)置錯誤●用戶可以通過和訪問在同一臺服務(wù)器上(70)不同的兩個Web站點。(70)A.IP地址B.端口號C.協(xié)議D.虛擬目錄●Object-orientedanalysis(OOA)isasemiformalspecificationtechniquefortheobject-orientedparadigm.Object-orientedanalysisconsistsofthreesteps.Thefirststepis(71).Itdetermineshowthevariousresultsarecomputedbytheproductandpresentsthisinformationintheformofa(72)andassociatedscenarios.Thesecondis(73),whichdeterminestheclassesandtheirattributes,thendeterminestheinterrelationshipsandinteractionamongtheclasses.Thelaststepis(74),whichdeterminestheactionsperformedbyortoeachclassorsubclassandpresentsthisinformationintheformof(75).(71)A.use-casemodelingB.classmodelingC.dynamicmodelingD.behavioralmodeling(72)A.collaborationdiagramB.sequencediagramC.use-casediagramD.activitydiagram(73)A.use-casemodelingB.classmodelingC.dynamicmodelingD.behavioralmodeling(74)A.use-casemodelingB.classmodelingC.dynamicmodelingD.behavioralmodeling(75)A.activitydiagramB.componentdiagramC.sequencediagramD.statediagram2008上半年軟件設(shè)計師下午試題試題一(共15分)閱讀以下說明和圖,回答問題1至問題4,將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某音像制品出租商店欲開發(fā)一個音像管理信息系統(tǒng),管理音像制品的租借業(yè)務(wù)。需求如下:1.系統(tǒng)中的客戶信息文件保存了該商店的所有客戶的用戶名、密碼等信息。對于首次來租借的客戶,系統(tǒng)會為其生成用戶名和初始密碼。2.系統(tǒng)中音像制品信息文件記錄了商店中所有音像制品的詳細(xì)信息及其庫存數(shù)量。3.根據(jù)客戶所租借的音像制品的品種,會按天收取相應(yīng)的費用。音像制品的最長租借周期為一周,每位客戶每次最多只能租借6件音像制品。4.客戶租借某種音像制品的具體流程為:(1)根據(jù)客戶提供的用戶名和密碼,驗證客戶身份。(2)若該客戶是合法客戶,查詢音像制品信息文件,查看商店中是否還有這種音像制品。(3)若還有該音像制品,且客戶所要租借的音像制品數(shù)小于等于6個,就可以將該音像制品租借給客戶。這時,系統(tǒng)給出相應(yīng)的租借確認(rèn)信息,生成一條新的租借記錄并將其保存在租借記錄文件中。(4)系統(tǒng)計算租借費用,將費用信息保存在租借記錄文件中并告知客戶。(5)客戶付清租借費用之后,系統(tǒng)接收客戶付款信息,將音像制品租借給該客戶。5.當(dāng)庫存中某音像制品數(shù)量不能滿足客戶的租借請求數(shù)量時,系統(tǒng)可以接受客戶網(wǎng)上預(yù)約租借某種音像制品。系統(tǒng)接收到預(yù)約請求后,檢查庫存信息,驗證用戶身份,創(chuàng)建相應(yīng)的預(yù)約記錄,生成預(yù)約流水號給該客戶,并將信息保存在預(yù)約記錄文件中。6.客戶歸還到期的音像制品,系統(tǒng)修改租借記錄文件,并查詢預(yù)約記錄文件和客戶信息文件,判定是否有客戶預(yù)約了這些音像制品。若有,則生成預(yù)約提示信息,通知系統(tǒng)履行預(yù)約服務(wù),系統(tǒng)查詢客戶信息文件和預(yù)約記錄文件,通知相關(guān)客戶前來租借音像制品。圖1-1頂層數(shù)據(jù)流圖【問題1】(1分)圖1-1中只有一個外部實體E1。使用【說明】中的詞語,給出E1的名稱?！締栴}2】(6分)使用【說明】中的詞語,給出圖1-2中的數(shù)據(jù)存儲D1~D4的名稱?！締栴}3】(6分)數(shù)據(jù)流圖1-2缺少了三條數(shù)據(jù)流,根據(jù)說明及數(shù)據(jù)流圖1-1提供的信息,分別指出這三條數(shù)據(jù)流的起點和終點。起點終點【問題4】(2分)在進(jìn)行系統(tǒng)分析與設(shè)計時,面向數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法(如Jackson方法)也被廣泛應(yīng)用。簡要說明面向數(shù)據(jù)結(jié)構(gòu)設(shè)計方法的基本思想及其適用場合。試題二(共15分)閱讀下列說明,回答問題1至問題3,將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某地區(qū)舉行籃球比賽,需要開發(fā)一個比賽信息管理系統(tǒng)來記錄比賽的相關(guān)信息。【需求分析結(jié)果】1.登記參賽球隊的信息。記錄球隊的名稱、代表地區(qū)、成立時間等信息。系統(tǒng)記錄球隊每個隊員的姓名、年齡、身高、體重等信息。每個球隊有一個教練負(fù)責(zé)管理球隊,一個教練僅負(fù)責(zé)一個球隊。系統(tǒng)記錄教練的姓名、年齡等信息。2.安排球隊的訓(xùn)練信息。比賽組織者為球隊提供了若干個場地,供球隊進(jìn)行適應(yīng)性訓(xùn)練。系統(tǒng)記錄現(xiàn)有的場地信息,包括:場地名稱、場地規(guī)模、位置等信息。系統(tǒng)可為每個球隊安排不同的訓(xùn)練場地,如表2-1所示。系統(tǒng)記錄訓(xùn)練場地安排的信息。表2-1訓(xùn)練安排表球隊名稱場地名稱訓(xùn)練時間解放軍一號球場2008-06-0914:00－18:00解放軍一號球場2008-06-1209:00－12:00解放軍二號球場2008-06-1114:00－18:00山西一號球場2008-06-1009:00－12:003.安排比賽。該賽事聘請專職裁判,每場比賽只安排一個裁判。系統(tǒng)記錄裁判的姓名、年齡、級別等信息。系統(tǒng)按照一定的規(guī)則,首先分組,然后根據(jù)球隊、場地和裁判情況,安排比賽(每場比賽的對陣雙方分別稱為甲隊和乙隊)。記錄參賽球隊名稱、比賽時間、比分、比賽場地等信息,如表2-2所示。4.所有球員、教練和裁判可能出現(xiàn)重名情況。表2-2比賽安排表A組:甲隊——乙隊場地名稱比賽時間裁判比分解放軍——北京一號球場2008-06-1715:00李大明天津——山西一號球場2008-06-1719:00胡學(xué)梅B組:甲隊——乙隊場地名稱比賽時間裁判比分上海----安徽二號球場2008-06-1715:00丁鴻平山東----遼寧二號球場2008-06-1719:00郭愛琪【概念模型設(shè)計】根據(jù)需求階段收集的信息,設(shè)計的實體聯(lián)系圖和關(guān)系模式(不完整)如下:1.實體聯(lián)系圖2.關(guān)系模式教練(教練編號,姓名,年齡)隊員(隊員編號,姓名,年齡,身高,體重,(a))球隊(球隊名稱,代表地區(qū),成立時間,(b))場地(場地名稱,場地規(guī)模,位置)訓(xùn)練記錄((c))裁判(裁判編號,姓名,年齡,級別)比賽記錄((d))【問題1】(4分)根據(jù)問題描述,補充聯(lián)系及其類型,完善實體聯(lián)系圖2-1。(聯(lián)系及其類型的書寫格式參照教練與球隊之間的聯(lián)系描述,聯(lián)系名稱也可使用聯(lián)系1、聯(lián)系2、…)【問題2】(8分)根據(jù)實體聯(lián)系圖2-1,填充關(guān)系模式中的(a)、(b)、(c)和(d),并給出訓(xùn)練記錄和比賽記錄關(guān)系模式的主鍵和外鍵?！締栴}3】(3分)如果考慮記錄一些特別資深的熱心球迷的情況,每個熱心球迷可能支持多個球隊。熱心球迷包括:姓名、住址和喜歡的俱樂部等基本信息。根據(jù)這一要求修改圖2-1的實體聯(lián)系圖,給出修改后的關(guān)系模式。(僅給出增加的關(guān)系模式描述)試題三(共15分)閱讀下列說明和圖,回答問題1至問題4,將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】某汽車停車場欲建立一個信息系統(tǒng),已經(jīng)調(diào)查到的需求如下:1.在停車場的入口和出口分別安裝一個自動欄桿、一臺停車卡打印機、一臺讀卡器和一個車輛通過傳感器,示意圖如下:2.當(dāng)汽車到達(dá)入口時,駕駛員按下停車卡打印機的按鈕獲取停車卡。當(dāng)駕駛員拿走停車卡后,系統(tǒng)命令欄桿自動抬起;汽車通過入口后,入口處的傳感器通知系統(tǒng)發(fā)出命令,欄桿自動放下。3.在停車場內(nèi)分布著若干個付款機器。駕駛員將在入口處獲取的停車卡插入付款機器,并繳納停車費。付清停車費之后,將獲得一張出場卡,用于離開停車場。4.當(dāng)汽車到達(dá)出口時,駕駛員將出場卡插入出口處的讀卡器。如果這張卡是有效的,系統(tǒng)命令欄桿自動抬起;汽車通過出口后,出口傳感器通知系統(tǒng)發(fā)出命令,欄桿自動放下。若這張卡是無效的,系統(tǒng)不發(fā)出欄桿抬起命令而發(fā)出告警信號。5.系統(tǒng)自動記錄停車場內(nèi)空閑的停車位的數(shù)量。若停車場當(dāng)前沒有車位,系統(tǒng)將在入口處顯示“車位已滿”信息。這時,停車卡打印機將不再出卡,只允許場內(nèi)汽車出場。根據(jù)上述描述,采用面向?qū)ο蠓椒▽ζ溥M(jìn)行分析與設(shè)計,得到了表3-1所示的類/用例/狀態(tài)列表、圖3-1所示的用例圖、圖3-2所示的初始類圖以及圖3-3所示的描述入口自動欄桿行為的UML狀態(tài)圖?！締栴}1】(3分)根據(jù)說明中的描述,使用表3-1給出的用例名稱,給出圖3-1中U1、U2和U3所對應(yīng)的用例?！締栴}2】(5分)根據(jù)說明中的描述,使用表3-1給出的類的名稱,給出圖3-2中的A~D所對應(yīng)的類。【問題3】(4分)根據(jù)說明中的描述,使用表3-1給出的狀態(tài)名稱,給出圖3-3中S1~S4所對應(yīng)的狀態(tài)?！締栴}4】(3分)簡要解釋圖3-1中用例U1和U3之間的extend關(guān)系的內(nèi)涵。試題四(共15分)閱讀下列說明,回答問題1至問題3,將解答填入答題紙的對應(yīng)欄內(nèi)?！菊f明】快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組A[p..r]排序的三個步驟如下:分解:選擇一個樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組A[p..r]劃分為兩個子數(shù)組(可能為空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每個元素,小于A[q+1..r]中的每個元素。q的值在劃分過程中計算。遞歸求解:通過遞歸的調(diào)用快速排序,對子數(shù)組A[p..q-1]和A[q+1..r]分別排序。合并:快速排序在原地排序,故不需合并操作?！締栴}1】(6分)下面是快速排序的偽代碼,請?zhí)钛a其中的空缺。偽代碼中的主要變量說明如下:A:待排序數(shù)組p,r:數(shù)組元素下標(biāo),從p到rq:劃分的位置x:樞軸元素i:整型變量,用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值j:循環(huán)控制變量,表示數(shù)組元素下標(biāo)QUICKSORT(A,p,r){if(p<r){q=PARTITION(A,p,r);QUICKSORT(A,p,q-1);QUICKSORT(A,q+1,r);}}

PARTITION(A,p,r){x=A[r];i=p–1;for(j=p;j≤r–1;j++){if(A[j]≤x){i=i+1;交換A[i]和A[j]}}交換(1)和(2)//注:空(1)和空(2)答案可互換,但兩空全部答對方可得分return(3)}【問題2】(5分)(1)假設(shè)要排序包含n個元素的數(shù)組,請給出在各種不同的劃分情況下,快速排序的時間復(fù)雜度,用O記號。最佳情況為(4),平均情況為(5),最壞情況為(6)。(2)假設(shè)要排序的n個元素都具有相同值時,快速排序的運行時間復(fù)雜度屬于哪種情況?(7)。(最佳、平均、最壞)【問題3】(4分)(1)待排序數(shù)組是否能被較均勻地劃分對快速排序的性能有重要影響,因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機地取出一個元素作為樞軸元素,下面是隨機化快速排序劃分的偽代碼—利用原有的快速排序的劃分操作,請?zhí)畛淦渲械目杖碧?。其?RANDOM(i,j)表示隨機取i到j(luò)之間的一個數(shù),包括i和j。RANDOMIZED-PARTITION(A,p,r){i=RANDOM(p,r);交換(8)和(9);//注:空(8)和空(9)答案可互換,但兩空全部答對方可得分returnPARTITION(A,p,r);}(2)隨機化快速排序是否能夠消除最壞情況的發(fā)生?(10)。(是或否試題五(共15分)閱讀下列說明和C代碼,將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。【說明】棧(Stack)結(jié)構(gòu)是計算機語言實現(xiàn)中的一種重要數(shù)據(jù)結(jié)構(gòu)。對于任意棧,進(jìn)行插入和刪除操作的一端稱為棧頂(StackTop),而另一端稱為棧底(StackBottom)。棧的基本操作包:創(chuàng)建棧(NewStack)、判斷棧是否為空(IsEmpty)、判斷棧是否已滿(IsFull)、獲取棧頂數(shù)據(jù)(Top)、壓棧/入棧(Push)、彈棧/出棧(Pop)。當(dāng)設(shè)計棧的存儲結(jié)構(gòu)時,可以采取多種方式。其中,采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧中各數(shù)據(jù)項不必連續(xù)存儲(如圖5-1)。以下C代碼采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)一個整數(shù)棧操作?！綜代碼】typedefstructList{intdata;//棧數(shù)據(jù)structList*next;//上次入棧的數(shù)據(jù)地址}List;typedefstructStack{List*pTop;//當(dāng)前棧頂指針}Stack;Stack*NewStack(){return(Stack*)calloc(1,sizeof(Stack));}intIsEmpty(Stack*S){//判斷棧S是否為空棧if((1))return1;return0;}intTop(Stack*S){//獲取棧頂數(shù)據(jù)。若棧為空,則返回機器可表示的最小整數(shù)if(IsEmpty(S))returnINT_MIN;return(2);}voidPush(Stack*S,inttheData){//將數(shù)據(jù)theData壓棧List*newNode;newNode=(List*)calloc(1,sizeof(List));newNode->data=theData;newNode->next=S->pTop;S->pTop=(3);}voidPop(Stack*S){//彈棧List*lastTop;if(IsEmpty(S))return;lastTop=S->pTop;S->pTop=(4);free(lastTop);}#defineMD(a)a<<2intmain(){inti;Stack*myStack;myStack=NewStack();Push(myStack,MD(1));Push(myStack,MD(2));Pop(myStack);Push(myStack,MD(3)+1);while(!IsEmpty(myStack)){printf("%d",Top(myStack));Pop(myStack);}return0;}以上程序運行時的輸出結(jié)果為:(5)試題六(共15分)閱讀下列說明和C++代碼,將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。【說明】已知某企業(yè)欲開發(fā)一家用電器遙控系統(tǒng),即用戶使用一個遙控器即可控制某些家用電器的開與關(guān)。遙控器如圖6-1所示。該遙控器共有4個按鈕,編號分別是0至3,按鈕0和2能夠遙控打開電器1和電器2,按鈕1和3則能遙控關(guān)閉電器1和電器2。由于遙控系統(tǒng)需要支持形式多樣的電器,因此,該系統(tǒng)的設(shè)計要求具有較高的擴展性。現(xiàn)假設(shè)需要控制客廳電視和臥室電燈,對該遙控系統(tǒng)進(jìn)行設(shè)計所得類圖如6-2所示。圖6-2中,類RomoteController的方法onPressButton(intbutton)表示當(dāng)遙控器按鍵按下時調(diào)用的方法,參數(shù)為按鍵的編號;Command接口中on和off方法分別用于控制電器的開與關(guān);Light中turnLight(intdegree)方法用于調(diào)整電燈燈光的強弱,參數(shù)degree值為0時表示關(guān)燈,值為100時表示開燈并且將燈光亮度調(diào)整到最大;TV中setChannel(intchannel)方法表示設(shè)置電視播放的頻道,參數(shù)channel值為0時表示關(guān)閉電視,為1時表示開機并將頻道切換為第1頻道。【C++代碼】classLight{//電燈類public:voidturnLight(intdegree){//調(diào)整燈光亮度,0表示關(guān)燈,100表示亮度最大};};classTV{//電視機類public:voidsetChannel(intchannel){//調(diào)整頻道,0表示關(guān)機,1表示開機并切換到1頻道};};classCommand{//抽象命令類public:virtualvoidon()=0;virtualvoidoff()=0;};classRemoteController{//遙控器類protected:Command*commands[4];//遙控器有4個按鈕,按照編號分別對應(yīng)4個Command對象public:voidonPressButton(intbutton){//按鈕被按下時執(zhí)行命令對象中的命令if(button%2==0)commands[button]->on();elsecommands[button]->off();}voidsetCommand(intbutton,Command*command){(1)=command;//設(shè)置每個按鈕對應(yīng)的命令對象}};classLightCommand:publicCommand{//電燈命令類protected:Light*light;//指向要控制的電燈對象public:voidon(){light->turnLight(100);};voidoff(){light->(2);};LightCommand(Light*light){this->light=light;};};classTVCommand:publicCommand{//電視機命令類protected:TV*tv;//指向要控制的電