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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、期內，每一步都要有一個合理的說明信息，來表明這個線程中包括哪個老師，哪個學生，進行到什么程度了；(6) 要特別注意防范死鎖問題的發生。以上六點都是最后評分的要點。4、測試用例(注：僅供參考，不作為程序實現的標準格式)說明信息的格式提供如下：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