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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、期內(nèi)，每一步都要有一個(gè)合理的說(shuō)明信息，來(lái)表明這個(gè)線程中包括哪個(gè)老師，哪個(gè)學(xué)生，進(jìn)行到什么程度了；(6) 要特別注意防范死鎖問(wèn)題的發(fā)生。以上六點(diǎn)都是最后評(píng)分的要點(diǎn)。4、測(cè)試用例(注：僅供參考，不作為程序?qū)崿F(xiàn)的標(biāo)準(zhǔn)格式)說(shuō)明信息的格式提供如下：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