專業(yè)課程設計II題目和分組情況

1、南京郵電大學專業(yè)課程設計指導老師：黃海平計算機學院. 計算機科學與技術系專業(yè)課程設計的目的與要求課程設計是教學計劃的重要組成部分，是學生在校學習期間進行實踐的一個重要教學環(huán)節(jié)。本次課程設計是在學生完成了計算機網(wǎng)絡、數(shù)據(jù)庫、操作系統(tǒng)、數(shù)據(jù)結構和編譯原理等一系列計算機專業(yè)相關課程的學習后進行的綜合應用這些課程知識和技能的一個重要教學環(huán)節(jié)，通過課程設計達到培養(yǎng)和提高解決實際問題的能力和所學知識的綜合應用能力。為使學生通過課程設計切實受到鍛煉，增長知識，達到教學計劃的要求，提出如下具體要求：嚴格遵守紀律，按計劃進度完成課程設計任務。嚴格遵守實驗室的各項規(guī)章制度，嚴禁做與實驗無關的任何事情。在課程設計過

2、程中，要求理論聯(lián)系實際，注意所學知識的綜合運用，注重創(chuàng)造力的培養(yǎng)。課程設計過程中，要始終堅持嚴肅認真、實事求是、獨立思考、虛心學習、刻苦鉆研的態(tài)度，要加強對基礎理論、基本知識與基本技能的掌握和運用。請注意保存和備份自己的文檔。禁止利用實驗室條件進行看電影、打游戲、聊天等與老師布置的上機任務不相干的事情。上機時間和地點：第1-2周周一周四下午13:45-17:10，教五-5樓(具體哪個房間請看走廊上玻璃窗所張貼的安排)。二、設計題目與任務要求題目1題 目 1：詞法分析程序的構造題目描述：通過狀態(tài)轉(zhuǎn)換圖構造C或者PASCAL語言子集的詞法分析程序。原理解析：選取語言，例如選取了C語言，選取其中一個

3、子集，例如包含了部分關鍵字main、float、if、for等等，特殊符號( 、=、+等等，特殊定義的標識符變量以及部分常量等，采用編譯原理詞法分析中有窮自動機的思想構建出該語言子集的狀態(tài)轉(zhuǎn)換圖，并編碼實現(xiàn)。基本要求：（1）將選取的語言子集編寫一個簡單程序，放在一個文本文件中；（2）不管選取的是C語言還是PASCAL語言的子集，編程時采用C語言或者C+語言實現(xiàn)該詞法分析程序；（3）要將一個個單詞區(qū)分清楚并歸類(例如for屬于關鍵字)。提高要求：（1）能做出好的圖形化界面，便于人機交互；（2）能夠?qū)崿F(xiàn)實時的詞法編譯。設計提示：可以先畫出該詞法分析程序的狀態(tài)轉(zhuǎn)換圖，然后再進行分析。參考資料：1 王

4、汝傳. 編譯技術原理及其實現(xiàn)方法. 成都: 成都科技大學出版社, 1998.2 呂映芝 等編著. 編譯原理. 北京: 清華大學出版社, 1998.3 陳火旺 等編著. 程序設計語言編譯原理. 北京: 國防工業(yè)出版社, 2000.4 王 雷 等編著. 編譯原理課程設計. 北京: 機械工業(yè)出版社, 2004.學號(此題最多6人選擇)姓名(此題最少3人選擇)題目2題 目 2：民航票務管理與售票系統(tǒng)題目描述：按照軟件工程思想，以SQL Server 2000為后臺數(shù)據(jù)庫，以Visual Studio、Eclipse、Delphi或VC+等為前端開發(fā)工具，設計并實現(xiàn)一個民航票務管理與售票系統(tǒng)。(1) 可

5、以進行航班信息、票務信息的添加、修改和刪除。相關信息如下：航班號、起點、終點、日期、起飛時刻、到達時刻、預設座位數(shù)、剩余座位數(shù)、票價、航班所屬航空公司。(注意：(a)該功能由管理員使用；(b) 修改或刪除前加以確認)(2) 允許普通用戶和各類人員查詢起點為本市機場的有關民航航班的時刻表，包括航班號、起點、終點、日期、起飛時刻、到達時刻、剩余座位數(shù)、票價、航班所屬航空公司等方面的準確信息。也可以按照終點和日期進行查詢。(3) 允許售票員售票。每個售票記錄應包括：航班號、購票者姓名、身份證號碼、日期、起飛時刻、到達時刻、票價、是否保險等信息。售票結束后，剩余座位數(shù)隨售票過程實時更新。基本要求：（1

6、）編程實現(xiàn)上述的功能；（2）實物演示時要求講出程序原理。提高要求：（1）應用軟件有良好的演示效果和人機交互界面；（2）有很好的魯棒性和健壯性。設計提示：(1) 要注重庫表結構的設計，后臺數(shù)據(jù)庫的連接，瀏覽和編輯數(shù)據(jù)庫表數(shù)據(jù)的方法，向數(shù)據(jù)庫表回傳數(shù)據(jù)的方法。(2) 座位不分等級(即同一航班的各座位票價相同)，不考慮折扣，座位號從1開始遞增。參考資料：1 周興華. Delphi 7數(shù)據(jù)庫項目案例導航. 北京: 清華大學出版社, 2005.2 薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論. 北京: 高等教育出版社, 2009.學號(此題最多6人選擇)姓名(此題最少3人選擇)題目3題 目 3：數(shù)據(jù)通信加密程序題目

7、描述：數(shù)據(jù)通信為了確保安全，往往采用加密技術，將明文通過加密算法進行變換后成為密文傳輸，在終端解密。本課題要求同時采用對稱密碼體制和非對稱密碼體制，實現(xiàn)在網(wǎng)絡中的密鑰和數(shù)據(jù)的安全傳輸，并且能夠?qū)⑼ㄐ诺臄?shù)據(jù)保存下來。基本要求：（1）在發(fā)送端采用非對稱密碼體制（RSA密碼機制）實現(xiàn)數(shù)據(jù)的加密和傳輸，在接收端進行數(shù)據(jù)接收和解密，顯示明文數(shù)據(jù)。（2）對于RSA密碼機制中私鑰的傳輸，采用對稱密碼體制進行（不考慮對稱密鑰機制的密鑰分發(fā)的實現(xiàn)問題）。（3）要求保存明文和加密后的密文數(shù)據(jù)。（4）程序設計的原理請用流程圖描述；程序要求模塊結構清晰規(guī)范，程序關鍵代碼的注釋詳細；程序操作友好。（5）程序輸出結果正確

8、，并對設計和編程中遇到問題進行歸納總結。提高要求：（1）以MFC的界面顯示結果，界面美觀。（2）通過網(wǎng)絡協(xié)議分析工具Wireshark等軟件捕獲程序通信的數(shù)據(jù)包，并對捕獲到的數(shù)據(jù)包進行分析，從而驗證程序的正確性。參考資料：1 吳功宜 等編著.計算機網(wǎng)絡課程設計. 北京：機械工業(yè)出版社，2005.2 謝希仁. 計算機網(wǎng)絡. 第4版. 北京：電子工業(yè)出版社，2003.3 汪曉平,劉韜. Visual C+ 6.0開發(fā)網(wǎng)絡典型應用實例導航. 北京：人民郵電出版社,2005.4 羅軍舟,黎波濤,楊明. TCP/IP協(xié)議及網(wǎng)絡編程技術. 北京：清華大學出版社，2005.學號(此題最多6人選擇)姓名(此題

9、最少3人選擇)題目4題 目 4：網(wǎng)絡延時測量程序題目描述：網(wǎng)絡延時是網(wǎng)絡的重要性能指標之一，本課題通過主動產(chǎn)生數(shù)據(jù)報，并接收回應的數(shù)據(jù)報，通過測量時間的差值，計算出網(wǎng)絡的時延性能，并通過多種報文產(chǎn)生與測試，分析網(wǎng)絡的性能。從而熟悉網(wǎng)絡管理員分析排查網(wǎng)絡故障的方法。基本要求：（1）實現(xiàn)ICMP、TCP和UDP協(xié)議報文產(chǎn)生和接收的程序，主動發(fā)送這些報文，并在接收端進行接收和立即回應相應的數(shù)據(jù)。（2）通過兩次的ICMP、TCP和UDP協(xié)議報文和回應信息的時間間隔，測算網(wǎng)絡的時延性能，并給出相關的分析數(shù)據(jù)。（3）程序保存發(fā)送數(shù)據(jù)和接收數(shù)據(jù)的時間和內(nèi)容等關鍵信息，便于分析。（4）程序設計的原理請用流程圖

10、描述；程序要求模塊結構清晰規(guī)范，程序關鍵代碼的注釋詳細；程序操作友好。（5）程序輸出結果正確，并對設計和編程中遇到問題進行歸納總結。提高要求：（1）以MFC的界面顯示結果，界面美觀。（2）通過網(wǎng)絡協(xié)議分析工具Wireshark等軟件捕獲程序通信的數(shù)據(jù)包，并對捕獲到的數(shù)據(jù)包進行分析，從而驗證程序的正確性。參考資料：1 吳功宜 等編著.計算機網(wǎng)絡課程設計. 北京：機械工業(yè)出版社，2005.2 謝希仁. 計算機網(wǎng)絡. 第4版. 北京：電子工業(yè)出版社，2003.3 汪曉平,劉韜. Visual C+ 6.0開發(fā)網(wǎng)絡典型應用實例導航. 北京：人民郵電出版社,2005.4 羅軍舟,黎波濤,楊明. TCP/

11、IP協(xié)議及網(wǎng)絡編程技術. 北京：清華大學出版社，2005.學號(此題最多6人選擇)姓名(此題最少3人選擇)題目5題 目 5：紅黑樹的紅色內(nèi)結點問題題目描述：紅黑樹是一類特殊的二叉搜索樹，其中每個結點被“染成”紅色或黑色。若將二叉搜索樹結點中的空指針看作是指向一個空結點，則稱這類空結點為二叉搜索樹的前端結點。并規(guī)定所有前端結點的高度為-1。一棵紅黑樹是滿足下面“紅黑性質(zhì)”染色二叉搜索樹：(1) 每個結點被染成紅色或黑色；(2) 每個前端結點為黑色結點；(3) 任一紅結點的兒子結點均為黑結點；(4) 在從任一結點到其子孫前端結點的所有路徑上具有相同的黑結點數(shù)。從紅黑樹中任一結點x 出發(fā)(不包括結點

12、x)，到達一個前端結點的任意一條路徑上的黑結點個數(shù)稱為結點x的黑高度，記作bh(x)。紅黑樹的黑高度定義為其根結點的黑高度。圖示的二叉搜索樹是一棵紅黑樹。標在結點旁邊的數(shù)字是相應結點的黑高度。給定正整數(shù)n，試設計一個算法，計算出在所有含有n個結點的紅黑樹中，紅色內(nèi)結點個數(shù)的最小值和最大值。輸入輸入的文件的第一行是正整數(shù)n，1n5000。輸出輸出紅色內(nèi)結點個數(shù)的最小值和最大值。第1行是最小值，第2行是最大值。樣例輸入8樣例輸出minimum 1maximum 4基本要求：對于任意一個n的取值，計算出正確的結果。提高要求：(1) 能夠設計出較低時間復雜性的算法；(2) 能夠動態(tài)演示具有最小(大)紅

13、結點數(shù)目的紅黑樹的生成過程。設計提示：首先確定生成樹的方法(自頂向下還是自底向上遞歸生成)，這個方法必須滿足上述的紅黑樹的4個基本條件；其次可采用回溯的方法進行試探，或者給定紅結點的具體數(shù)值進行試探；最后找出滿足條件的紅黑樹。參考資料：1 陳慧南 編著. 數(shù)據(jù)結構-使用C+語言描述. 北京：人民郵電出版社，2006.2 嚴蔚敏 編著. 數(shù)據(jù)結構. 北京：清華大學出版社，2000.學號(此題最多6人選擇)姓名(此題最少3人選擇)題目6題 目 六：教師對學生的項目評分進程的同步與互斥題目描述：在一個班上有S個學生。每個學生都要做一個項目，每一個項目由K個老師一起評分?？偣灿蠱個老師。每個老師最多給

14、N個項目評分。其中，S*KD。每一個學生的項目由K個老師共同來檢查。在T分鐘的時間段內(nèi)，學生可以在任何時間進入教室(random)，除了在最后的D分鐘內(nèi)。所有的老師一直保持工作狀態(tài)直到他檢查完N個項目或者是T分鐘過去后。T分鐘過去后，所有的老師和同學都必須離開教室。另外，在T分鐘結束前的D分鐘內(nèi)(即在最后的D分鐘內(nèi))，如果有任何老師或者是學生都處在沒有任務的狀態(tài)下，都必須離開教室，因為已經(jīng)沒有時間讓他完成任務了(因為一個項目檢查的時間是整整D分鐘)。該課題主要考察操作系統(tǒng)中PV操作知識點，涉及到多進程管理和死鎖的相關知識?；疽螅河靡粋€程序來模擬上面描述的作業(yè)檢查過程。每一個學生和每一個老師

15、應該用不同的線程來完成。可以選用C、C+和Java作為開發(fā)語言，但是考慮到專業(yè)課程設計I的實驗大綱，請盡可能使用Java語言。提高要求：(1) 考慮到跨平臺的特性，請盡量使用posix線程標準(采用該標準有額外的加分)；(2) 實現(xiàn)良好的圖形用戶界面；(3) 在程序演示過程中能清晰的展示多個學生線程和多個老師線程的同步和互斥流程。設計提示：1、當一個學生進入教室后，他立即開始找K個沒有任務的老師(一次找一個老師，假如沒有空閑的老師，則等到有老師為止)，找齊K個老師之后給老師檢查，然后離開教室。剛開始每一個老師都是處于空閑狀態(tài)直到他被學生找到，被學生找到后只能等待，直到學生找齊K個老師(在等待學

16、生找其他老師的時間里，他是不能接受其他同學檢查作業(yè)的請求的)，當學生找齊K個老師后，老師們執(zhí)行完檢查任務，然后重新變成空閑狀態(tài)。每個老師在總共檢查了N個學生的作業(yè)后，離開教室。注意，并不保證所有的學生都在T分鐘的時間段內(nèi)完成了檢查，還要注意不能發(fā)生死鎖問題。2、學生線程和老師線程：一個學生線程執(zhí)行下面的步驟：(1) 選擇一個進入的時間(random()%(T-D)minutes ；(2) 進入教室；(3) 選擇K個空閑的老師，若找不齊，則等待；(4) 找齊后，做D分鐘的檢查；(5) 檢查完畢離開教室。一個老師線程執(zhí)行下面的步驟：(1) 在教室中空閑；(2) 直到被一個學生選擇后等待(所有K個老

17、師聚集)；(3) 等待結束項目檢查開始；(4) 做D分鐘的項目檢查； (1)(4)步驟重復N次(5) N次檢查完畢或者T分鐘時間到，離開教室。3、注意事項(1) 在剩余時間小于D時，一個已創(chuàng)建的學生線程只能執(zhí)行第(5)步，不能再創(chuàng)建新的學生線程；(2) 在剩余時間小于D時，一個老師進程只能在執(zhí)行(3)(4)步或者直接執(zhí)行第(5)步；(3) 對于所有合理的S, M, K, N, T, D數(shù)值(這些數(shù)必須都是正整數(shù)并且滿足條件：S*KD)，你的程序都能夠運行成功；(4) 你的程序?qū)λ械臅r間安排策略都必須運行成功。例如不管線程的相對速度，例如要把握好sleep的毫秒數(shù)；(5) 在每一個線程的生命周

18、期內(nèi)，每一步都要有一個合理的說明信息，來表明這個線程中包括哪個老師，哪個學生，進行到什么程度了；(6) 要特別注意防范死鎖問題的發(fā)生。以上六點都是最后評分的要點。4、測試用例(注：僅供參考，不作為程序?qū)崿F(xiàn)的標準格式)說明信息的格式提供如下：S=5 M=3 K=2 N=3 T=150 D=200 student 0: starts panicking0 student 1: starts panicking0 student 2: starts panicking0 student 3: starts panicking0 student 4: starts panicking0 marker

19、0: enters lab0 marker 1: enters lab0 marker 2: enters lab14 student 0: enters lab14 marker 0: grabbed by student 0 (job 0)14 marker 1: grabbed by student 0 (job 0)14 student 0: starts demo35 student 0: ends demo35 student 0: exits lab (finished)35 marker 1: finished with student 0 (job 0)35 marker 0

20、: finished with student 0 (job 0)38 student 2: enters lab38 marker 2: grabbed by student 2 (job 2)38 marker 1: grabbed by student 2 (job 2)38 student 2: starts demo54 student 4: enters lab54 marker 0: grabbed by student 4 (job 4)59 student 2: ends demo59 student 2: exits lab (finished)59 marker 2: finished with student 2 (job 2)59 marker 2: grabbed by student 4 (job 4)59 marker 1: finished with student 2 (job 2)59 student 4: starts demo80 student 4: ends demo80 student 4: exits lab (finished)80 marker 2: finished with student 4