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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、師聚集)；(3) 等待結(jié)束項目檢查開始；(4) 做D分鐘的項目檢查； (1)(4)步驟重復(fù)N次(5) N次檢查完畢或者T分鐘時間到，離開教室。3、注意事項(1) 在剩余時間小于D時，一個已創(chuàng)建的學(xué)生線程只能執(zhí)行第(5)步，不能再創(chuàng)建新的學(xué)生線程；(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)，每一步都要有一個合理的說明信息，來表明這個線程中包括哪個老師，哪個學(xué)生，進行到什么程度了；(6) 要特別注意防范死鎖問題的發(fā)生。以上六點都是最后評分的要點。4、測試用例(注：僅供參考，不作為程序?qū)崿F(xiàn)的標(biāo)準(zhǔ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