专业课程设计II题目和分组情况

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