1、試題一（15分）閱讀下列說明和圖，回答問題1至4,將答案填入答題紙的對應欄內。【說明】某公司擬開發一個共享單車系統，采用北斗定位系統進行單車定位，提供針對用戶的APP以及微信小程序，基于 Web的管理與監控系統。該共享單車系統的主要功能如下。1）用戶注冊登錄。用戶在 APP段端輸入手機號并獲取驗證碼后進行注冊，將用戶信息 進行存儲。用戶登錄后顯示用戶所在位置周圍的單車。2）使用單車。掃碼/手動開鎖。通過掃描二維碼或手動輸入編碼獲取開鎖密碼，系統發送開鎖指令 進行開鎖，系統修改單車狀態，新建單車行程。騎行單車。單車定時上傳位置，更新行程。鎖車結賬。用戶停止使用或手動鎖車并結束行程后，系統根據已設

2、置好的計費規則及使用時間自動結算，更新本次騎行的費用并顯示給用戶，用戶確認支付后，記錄行程的支付狀態，系統還將重置單車的開鎖密碼和單車狀態。3）輔助管理。查詢。用戶可以查看行程列表和行程詳細信息。保修。用戶上報所在位置或單車位置以及單車故障信息并進行記錄。4）管理與監控單車管理及計費規則設置。 商家對單車基礎信息， 狀態等進行管理，對計費規則進行 設置并存儲。單車監控。對單車，故障，行程等進行查詢統計。用戶管理。管理用戶信用與狀態信息，對用戶進行查詢統計。現采用結構化方法對共享單車系統進行分析與設計，獲得如圖1-1所示的上下文數據流 圖和圖1-2所示的0層數據流圖。單隼狀態統計 報衣對色詢統J

3、皓果個人信息,確認支付信息/故障信息LJ/單卑也別信息/行程請求（驗證碼/周圖單車/開鎖密碼，行程，費用用卜仿陽時戶狀態信息1- .2<不鋪指令“林<有嗎任IT下文數據流圖M公司為了便于開展和管理各項業務活動，提高公司的知名度和影響力，擬構建一個 基于網絡的會議策劃系統。【需求分析結果】該系統的部分功能及初步需求分析的結果如下：（1） M公司旗下有業務部，策劃部和其它部門。部門信息包括部門號，部門名，主管,聯系電話和郵箱號。 每個部門只有一名主管，只負責本部門的工作， 且主管參照員工關系的員工號：一個部門有多名員工，每個員工屬于且僅屬于一個部門。 :n匕的制油限【問題1（3分）使用

4、說明中的詞語，給出圖1-1中的實體E1E3的名稱。【問題2】（5分）使用說明中的詞語，給出圖1-2中的數據存儲 D1D5的名稱。【問題3】（5分）根據說明和圖中術語及符號，補充圖1-2中缺失的數據流及其起點和終點。【問題4】（2分）根據說明中術語，說明 使用單車”可以分解為那些子加工？試題二（共15分）閱讀下列說明，回答問題【說明】1至問題4,將解答填入答題紙的對應欄內。肝愎出樹爭方化以1也障切8M V If（2）員工信息包括員工號，姓名，職位，聯系方式和薪資。職位包括主管，業務員， 策劃員等。業務員負責受理用戶申請，設置受理標志。一名業務員可以受理多個用戶申請， 但一個用戶申請只能由一個業務

5、員受理。（3）用戶信息包括用戶號，用戶名，銀行賬號，電話，聯系地址。用戶號唯一標識用 戶信息中的每一個元組。（4）用戶申請信息包括申請號，用戶號，會議日期，天數，參會人數，地點，預算費 用和受理標志。申請號唯一標識用戶申請信息中的每一個元組，且一個用戶可以提交多個申請，但一個用戶申請只對應一個用戶號。（5）策劃部主管為已受理的用戶申請制定會議策劃任務。策劃任務包括申請號，任務 明細和要求完成時間。申請號唯一標識策劃任務的每一個元組。一個策劃任務只對應一個已受理的用戶申請，但一個策劃任務可由多名策劃員參與執行，且一名策劃員可以參與執行多項策劃任務。【概念模型設計】根據需求階段收集的信息，設計的實

6、體聯系圖（不完整）如圖 2-1所示。RT c 業務員用戶南靖【關系模式設計】部門（部門號，部門名，部門主管，聯系電話，郵箱號）員工（員工號，姓名，（a）,聯系方式，薪資）用戶（用戶名，（b）,電話，聯系地址）用戶申請（申請號，用戶號，會議日期，天數，參會人數，地點，受理標志，（c）策劃任務（申請號，任務明顯，（d）執行（申請號，策劃員，實際完成時間，用戶評價）【問題1】（5分）根據問題描述，補充五個聯系，完成圖 2-1的實體聯系圖，聯系名可用聯系1,聯系2,聯系3,聯系4和聯系5表示，聯系的類型為 1:1, 1: n和m： n （或1:1,1： *和*： *）【問題2】（4分）根據題意，將關系

7、模式中的空（a） （d）補充完整，并填入答題紙的位置上。【問題3】（4分）給出用戶申請”和策劃任務”關系模式的主鍵和外鍵。【問題4】（2分）請問執行”關系模式的主鍵為全碼的說法正確嗎？為什么？試題三（共15分）閱讀下列說明，回答問題 1至問題3,將解答填入答題紙的對應欄內。【說明】某大學擬開發一個用于管理學術出版物（Publication）的數字圖書館系統，用戶可以從該系統查詢或下載已發表的學術出版物。系統的主要功能如下：1 .登錄系統。系統的用戶（User）僅限于該大學的學生（Student）,教師（Faculty）和 其它工作人員（Staff）。在訪問系統之前，用戶必須使用其校園賬號和密碼

8、登錄系統。2 .查詢某位作者（Author）的所有出版物。系統中保存了會議文章（ConfPaper）,期刊文章（JournalArticle ）和校內技術報告（TechReport）等學術出版物的信息，如題目，作者 以及出版年份等。除此之外，系統還存儲了不同類型出版物的一些特有信息；（1）對于會議文章，系統還記錄了會議名稱，召開時間以及召開地點；（2）對于期刊文章，系統還記錄了期刊名稱，出版月份，期號以及主辦單位；（3）對于校內技術報告，系統還記錄了由學校分配的唯一ID。3 .查詢制定會議集（Proceedings）或某個期干J特定期（Edition ）的所有文章。會議集包 含了發表在該會議（

9、在某個特定時間段，特定地點召開）上的所有文章。期刊的每一期在特定時間發行，其中包含若干篇文章。4 .下載出版物。系統記錄每個出版物被下載的次數。5 .查詢引用了某篇出版物的所有出版物。在學術出版物中引用他人或早期的文獻作為相關工作或背景資料是很常見的現象。用戶也可以在系統中為某篇出版物注冊引用通知，若有新的出版物引用該出版物，系統將發送電子郵件通知該用戶。現在采用面向對象方法對該系統進行開發，得到系統的初始設計類圖如圖3-1所示。【問題1】（9分）根據說明中的描述，給出圖3-1中C1C9所對應的類名。【問題2】（4分）根據說明中的描述，給出圖3-1中類C6C9的屬性。【問題3】（2分）圖3-1

10、中包含了那種設計模式？實現的是該系統的哪個功能？試題四（共15分）閱讀下列說明和 C代碼，回答問題1至問題2,將解答寫在答題紙的對應欄內 【說明】一個無向連通圖 G上的哈密爾頓（Hamilton ）回路是指從圖 G上的某個頂點出發，經 過圖上所有其他頂點一次且僅一次， 最后回到該頂點的路徑。 一種求解無向圖上的哈密爾頓 回路算法的基本思想如下：假設圖G存在一個從頂點 u0出發的哈密爾頓回路 u0u1u2u3.u0un-1u0。算 法從頂點Uo出發，訪問該頂點的一個未被訪問的領接頂點Ui ,接著從頂點Ui出發，訪問Ui的一個未被訪問的領接頂點U2,。對頂點Ui,重復進行以下操作：訪問 Ui的一個

11、為被訪問的領接頂點Ui+1 ;若Ui的所有領接頂點均已被訪問，則返回到頂點Ui-1,考慮Ui-1的下一個未被訪問的領接頂點，仍記為Ui；直到找到一個哈密爾頓回路或者找不到哈密爾頓回路，算法結束。【C代碼】下面是算法的C語言實現。（1）常量和變量說明n：圖G中的頂點數 c川：圖G的領接矩陣 k：統計變量，當前已經訪問的頂點數為k+1xk:第k個訪問的頂點編號，從 0開始visitedxk:第k個頂點的訪問標志，0表示未訪問，1表示已訪問(2) C程序#include<stdio.h>#include<stdlib.h>#define MAX 4Void Hamilton(

12、int n,int xMAX,int cMAXMAX) int i;int visitedMAX;int k;/*初始化x數組和visited數組*/ for(i=o;i<n;i+)xi=0;Visitedi=0;/*訪問起初頂點*/K=0; ；x0=0;k=k+1;/*訪問其它頂點*/while(k>0)xk=xk+1;while(xk<n)if( (2)&&cxk-1xk=1)/*領接頂點 xk未被訪問過 */break;else xk=xk+1;if(xk<n&&k=n-1&&(3) )/* 找到一條哈密爾頓回路*/

13、for(k=0;k<n;k+)printf(-% d,xk);/喻出哈密爾頓回路*/ printf("r% d ,x0);return;else if(xk&&k<n-1)/*設置當前頂點的訪問標志，繼續下一個頂點 */(4)；k=k+1;*/else /*沒有未被訪問過的領接頂點，回退到上一個頂點x止0;visitedxk=0;；【問題1】（10分）根據題干說明，填充 C代碼中的空（1） （5）。【問題2】（5分）根據題干說明和C代碼，算法采用的設計策略是（61,該方法在遍歷圖的頂點時，采用的是（7）方法（深度優先或廣度優先）。試題五（共15分）閱讀下列

14、說明和 C+代碼，將應填入（n）處的字句寫在答題紙的對應欄內。【說明】某圖像預覽程序要求能夠查看BMP, JPEG和GIF三種格式的文件，且能夠在 Windows和Linux兩種操作系統上運行。程序需具有較好的擴展性以支持新的文件格式和操作系統。為滿足上述需求并減少所需生成的子類數目，現采用橋接（Bridge）模式進行設計，得到如圖5.1所示的類圖。【C+代碼】#include<iostream>#include<string>Using namespace std;class matrix各種格式的文件最終都被轉化為像素矩陣此處代碼省略；class Implement

15、Public:（1） 顯示像素矩陣m；class WinImp:public ImplementorPublic:Void doPaint（Matrix m）/*調用 Windows系統的繪制函數繪制像素矩陣*/;class LinuxImp: public Implementorpublic:Void doPaint（Matrix m）/*調用Linux系統的繪制函數繪制像素矩陣*/;class Imagpublic:void setImp（Implementor *imp）this.imp=imp;virtual void parseFile（String fileName）=0;prot

16、ected:Implenentor *imp;；class BMPImage:public Image此處代碼省略；class GIFImage:public Imagepublic:void parseFile(String fileName)此處解析GIF文件并獲取一個像素矩陣對象m(2)，顯示像素矩陣m；class JPEGImage:public Image此處代碼省略;int main()public static void main(String口 args)/在Linux操作系統上查看 demo.gif圖像文件Imag imag= (3);Implementor imageImp

17、= (4);(5);image.parseFile( "demo.gif ");試題六共15分)閱讀下列說明和 Java代碼，將應填入(n)處的字句寫在答題紙的對應欄內。【說明】某圖像預覽程序要求能夠查看BMP, JPEG和GIF三種格式的文件，且能夠在 Windows和Linux兩種操作系統上運行。程序需具有較好的擴展性以支持新的文件格式和操作系統。為滿足上述需求并減少所需生成的子類數目，現采用橋接(Bridge)模式進行設計，得到如圖5.1所示的類圖。Java代碼】import Java。Util 。 *;class matrix各種格式的文件最終都被轉化為像素矩陣此處

18、代碼省略；abstract class Implementpublic (1) 顯示像素矩陣m；class WinImp:public Implementorpublic Void doPaint(Matrix m)/* 調用 Windows系統的繪制函數繪制像素矩陣*/;class LinuxImp: public Implementorpublic Void doPaint(Matrix m)/* 調用Linux系統的繪制函數繪制像素矩陣*/ ；class Imagpublic void setImp(Implementor *imp)this.imp=imp;public virtual

19、 void parseFile(String fileName)=0;protected Implenentor *imp;class BMPImage:public Image此處代碼省略；class GIFImage:public Imagepublic Void parseFile(String fileName)此處解析GIF文件并獲取一個像素矩陣對象m;/顯示像素矩陣m；class JPEGImage:public Image此處代碼省略;class main()public static void main(String口 args)/在Linux操作系統上查看 demo.gif圖

20、像文件Imag imag= (3);Implementor imageImp= (4);(5);image.parseFile( "demo.gif ");試題答案與解析試題【問題一】E1:用戶；E2:商家；E3:單車【問題二】D1:用戶信息文件；D2:單車信息文件；D3:行程信息文件;D4:計費規則信息文件： D5:單車故障信息文件【問題三】起點絳盧"1f /名稱P3E1開鎖密碼P3E1行程/費用P3D2單車狀態P3E3開鎖指令D3P3行程信息或使用時間D2P3計費規則D3P7行程信息P4D2單車狀態【問題四】掃碼/手動開鎖，騎行單車，鎖車結賬【試題分析】本題考

21、查面向結構化軟件開發方法中需求分析階段使用的數據流圖（DFD圖）。作答時，建議先看問題，劃出關鍵詞，然后邊閱讀文字描述邊作答，每閱讀一句都需仔細分析是否存在對應的數據流，檢查相應的數據流圖是否缺少相應的數據流。【問題一】需要填寫外部實體，外部實體為不屬于軟件本身但是又與當前軟件有交互關 系的外部的人，軟件，硬件，組織結構，數據庫系統等。在做的是需仔細的對每一個閱讀到 的外部實體（一般為名詞）高度重視。【問題二】考察數據存儲文件，還需要對閱讀到的“文件”或“表”等能夠存儲數據的媒介詞匯高度重視。【問題三】不僅僅通過閱讀文字描述來作答，同時也要使用父圖與子圖的數據守恒原則進行作答。根據描述“用戶在

22、 app端輸入手機號并獲取驗證碼后進行注冊，將用戶信息進行存儲” 并對照圖1-2中P1加工和E1實體處可知E1為實體“用戶”，D1為數據存儲文件“用戶信 息文件”。根據描述“通過掃描二維碼或手動輸入編碼獲取開鎖密碼，系統發送開鎖指令 進行開鎖，系統修改單車斗犬態,新建單車行程”并對照圖1-2的加工P3處可知缺少一條從P3至實體E3的數據了 “開鎖指令”，且缺少一條從 P3至D2的數據流“單車狀態”；根 據P4流入D2的數據流“單車基礎信息”容易知道D2為“單車信息文件”；根據P3流入D3的數據流名稱“單車行程/費用”可知D3為“行程信息文件”；根據描述“用戶停止使用 或手動鎖車并結束行程后，系

23、統根據已設置好的計費規則及使用時間自動結算，更新本次騎行的費用并顯示給用戶， 用戶確認支付后，記錄行程的支付狀態。 系統還將重置單車的開鎖 密碼和單車狀態。”并對比P3加工處可知缺少一條由 D3流向加工P3的數據流“計費規則” 和D3流向P4的數據流“使用時間”以便 P3計算行程費用，同時缺少一條由P3流向實體E1的數據流“行程及費用”。根據描述“查詢。用戶可以查看行程列表和行程詳細信息。”并對比加工 P4處可知D5為“單車故障信息文件”；根據描述“商家對單車基礎信息，狀態等進行管理，對計費 規則進行設置并存儲。”并對比加工P4周邊處可知E2為“商家”，且缺少一條從 P4流向D2 的數據流“狀

24、態信息”；根據“單車監控。對單車，故障，行程等進行查詢統計。”值缺少一條由D3流向加工P7的數據流“行程信息”。最后根據圖1-1以及圖1-2的對比，即子圖和父圖數據守恒原則，知圖 1-2中還缺少一 條由加工P3流向E1的數據流“開鎖密碼”。根據“2）使用單車”下方的描述，使用單車可以分解為“掃碼/手動開鎖，騎行單車，鎖車結賬”三個子加工。試題二：【問題一】其中粗線部分是答案。【問題二】（a）部門號，職位（b）用戶號，銀行賬號（c）預算費用，業務員（d）要 求完成時間，主管【問題三】“用戶申請”關系模式主鍵：申請號，外鍵：申請號，業務員，用戶號； “策劃任務”關系模式主鍵：申請號，外鍵：主管，申

25、請號 【問題四】“執行”關系模式的主鍵為全碼是錯誤的，因為“申請號”與“策劃員”的組合（申請 號，策劃員）即使唯一確定執行關系中的一個元組數據。【試題解析】此類題先閱讀問題， 畫出關鍵字，再一邊仔細閱讀文字描述，一邊看圖，一邊看關系模式一邊作答。根據文字描述“每個部門只有一名主管，只負責本部門的工作，且主管參照員工關系的 員工號”可知圖2-1 （后統稱E-R圖）中實體“部門”與“主管”之間應補充 1:1的聯系； 根據“一個部門有多名員工，每名員工屬于且僅屬于一個部門”可知E-R中實體“部門”和“員工”之間缺少1: *的聯系，且關系模式“員工”中空（ a）處填寫“部門號”字段作為 外鍵以實現兩表

26、的參照完整性。根據描述“員工信息包括員工號，姓名，職位，聯系方式和 薪資。”可知（a）處還缺“職位”字段。根據“一名業務員可以受理多名用戶申請，但一個 用戶申請只能由一個業務員受理。”可知E-R圖中“業務員”與“用戶申請”之間缺少 1: * 的聯系，且應將“ 1”端（業務端）的主鍵（業務員）加入到“* ”端（用戶申請端）中，為了方便理解，加入的字段為“業務員”作為外鍵使用，故空（c）處應包括“業務員”。根據“用戶信息包括用戶號，用戶名，銀行賬號，電話，聯系地址。用戶號唯一標識用戶信息中 的每一個元組。”可知（b）處應填“用戶號”和“銀行賬號”，且“用戶號”是主鍵。根據“用戶申請信息包括申請號，

27、用戶號，會議日期，天數，參會人數，地點，預算費用和受理 標志。申請號唯一標識用戶申請信息中的每一個元組，且一個用戶可以提供多個申請，但一個用戶申請只對應一個用戶號。”可知E-R圖中“用戶”與“用戶申請”之間缺 1: *的聯系， 且空（c）處為“預算費用”，該表主鍵為“申請號”。根據“申請號”。根據“策劃任務包括 申請號，任務明顯和要求完成時間。申請號唯一標識策劃任務的每一個元組。”可知“申請號”為“策劃任務”的主鍵。根據“一個策劃任務只對應一個已受理的用戶申請，但一個策 劃任務可由多名策劃員參與執行，且一名策劃員可以參與執行多項策劃任務。”可知E-R圖中的“策劃員”與“策劃任務”之間缺少 *:

28、 *的聯系，此聯系其實就對應關系模式“執行”。在作答時，要注意概念模型（E-R圖）與邏輯模型（關系模式）的對應關系，在E-R圖中的部門，員工，策劃任務，用戶，用戶申請，策劃員與策劃任務之間的聯系都有對應的關 系模式（E-R圖中的子實體就對應父實體的關系模式），而聯系“制定”未轉換為關系模式，那么主管與策劃任務之間的參照關系需要將主管（1”員端）的主鍵“員工號”加入到策劃任務（*端）中作為外鍵，為了方便識別，更名為“主管編號”或“主管”。由于主管已經與策劃任務之間建立了參照關系，而策劃任務與用戶申請又是1對”的聯系，故主管與用戶申請之間的參照關系可通過主管與策劃任務之間的參照關系間接體現，故用戶

29、申請中無須加入主管的主鍵字段。“執行”關系模式的主鍵為全碼是錯誤的，因為“申請號”與“策劃員”的組合即能唯 一確定關系中的一個元組數據。試題三【問題一】C1:用戶；C2：系統用戶或 User; C3:學生或Student; C4：教師或Factual; C5:其他工作人員或 Staff; C6:出版物或 Publication ; C7:會議文章或 ConfPaper; C8:期 刊文章或JournalArticle ; C9:校內技術報告或 TechReport （注意：C3, C4, C5可交換）【問題二】C6的屬性：題目，作者，出版年份，下載次數；C7:會議名稱，召開時間，召開地點；C8

30、的屬性：期刊名稱，出版月份，期號，主辦單位；C9的屬性：ID【問題三】使用了觀察者設計模式（又稱“發布-訂閱”模式），定義了一種一對多的依賴關系，在題中，某出版物是觀察者，當被觀察者（引用某出版物的其他出版物）出現時， 則出版物會收到其被引用的通知，從而系統發送郵件給相應的作者。【試題解析】根據描述“系統的用戶（User）僅限于該大學的學生（Student）,教師（Faculty） 和其他工作人員（Staff）。”可知用戶（User）應為父類型，而學生，教師，其他工作人員都 是子類型，它們之間是一種“is-a”的泛化關系，這四個類可對應到類圖中C2為父類，C3,C4以及C5為子類處，C2為“系

31、統用戶”，C3, C4, C5依次“學生”，“教師”，“其他工作人 員”。根據描述“查詢某個作者（Author）的所有出版物。系統中保存了會議文章（ConfPaper）, 期刊文章（JournalArticle ）和校內技術報告（TechReport）等學術出版物的信息"可知"會 議文章”，“校內技術報告”都是“出版物”的子類型，對應到類圖中，C6應為“出版物”，C7與會議集（Proceedings）有聚合關系，故 C7為“會議文章”，同理C8應為“期刊文章”， C9為“校內技術報告”。縱觀整個類圖，C1為C2 （系統用戶（User）和Author的父類型， 故C1填寫“用

32、戶”，其中包括了學生，教師，其它工作人員，作者的共同屬性如登錄信息等。根據描述“查詢某位作者（Author）的所有出版物 等學術出版物的信息，如題目，作 者以及出版年份等。”及“下載出版物。系統記錄每個出版物被下載的次數。”可知C6中應包含屬性“題目”，“作者”，“出版年份”，“下載次數”，這些信息都是每個派生類型所共用 的，故抽象到共同的父類型中，派生類繼承使用即可；派生類C7, C8以C9除了擁有從父類型繼承下來的屬性外，還擁有自己特定的屬性。根據題目文字描述C7應該定義的特殊屬性為“會議名稱”，“召開時間”，“召開地點”，C8應該自己定義的特殊屬性為“期刊名稱” ， “出版月份”，“期號

33、”，“主辦單位”，C9的是“ID”。使用了觀察者設計模式，定義了一種一對多的依賴關系，讓多個觀察者對象同時監聽某個主題對象。這個主題對象在狀態發生變化時，會通知所有觀察者對象，是它們能夠自動更新自己。在本題中，某出版物是觀察者，當被觀察者（引用某出版物的其他出版物）出現時，則出版物會收到其被引用的通知，從而系統發送郵件給相應的作者。試題四（1） visited0=1（2） visitedxk=0 （3） cxk0=1 （4） visitedxk=1（5） k=k-1或k-或-k （6）回溯法（7）深度優先試題解析：問題（1）處及上下幾行代碼（while循環之前）是默認從 0號頂點開始，&quo

34、t;x=0=0"表示0號頂點被訪問過了，"k=k+1”也表示已經找到一個滿足條件的頂點，故空（1）處肯定是設置0號頂點已經被訪問過了，應該填“ visited0=1空（2）處根據注釋知領接頂點 xk未被訪問過則執行 break,則xk號頂點未被訪問成 立的判斷條件是“ visitedxk=0 "，即（2）的答案。"cxk-1xk=1 ”是判斷之前已經被 訪問過的頂點（xk-1）與xk是否為相鄰頂點。空（3）處的if判斷表達式“找到一條哈密爾頓回路”，成立條件為xk<n,且k=n-1,同時還要滿足第 xk頂點為被訪問過（空（2）處已經判斷），最后還要保證 xk號頂點與0 號頂點之間有邊（判斷條件 cxk0=1 ）才行，故空（3）處應該填寫“ c岡k0=1 " .空（