数据结构与算法课程设计计划书.doc

《数据结构与算法课程设计计划书.doc》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计计划书.doc（11页珍藏版）》请在三一办公上搜索。

1、计算机科学与工程学院集中性实践教学计划书（ 2014-2015 学年第 一 学期）课程名称： 数据结构与算法课程设计 专 业：计算机科学与技术 软件工程、网络工程班 级：计算机科学与技术131-6软件工程131-4网络工程131-4课程负责人： 李锡祚 指导教师分配情况：专业指导教师计算机科学与技术孟佳娜(1班) 张恒博(2班) 王巍(3班)刘爽(4班) 李威(5班) 李笑牛(6班) 软件工程王玲芬(1班) 赵丹丹(2班) 王存睿(3班) 宋海玉(4班)网络工程王晓强(1班) 郭海(2班) 于艳莉(3班) 王波(4班)教学起止周：第 17 至 19 教学周一、 教学目的：使学生能够根据数据对象

2、的特性，合理的组织数据并能综合运用数据结构与算法基本知识和程序设计基本知识解决实际问题，培养基本的、良好的程序设计技能。二、 主要阶段、内容、时间及地点安排（以天为单位计）：1、阶段与内容第1阶段（17周，校企合作指导）在为期一周校企合作模式的训练中，让学生对数据结构有一定的掌握，熟悉数据结构的常用算法并灵活运用，熟练使用开发工具，简单了解开发流程和团队协作的开发模式，并充分认识到数据结构在以后实际的项目开发中的重要作用。（具体流程见企业实训计划书）第2阶段：(18-19周，校内教师指导)通过为期二周的课程设计集中训练, 使学生能够根据数据对象的特性，合理的组织数据并能综合运用数据结构与算法基

3、本知识和程序设计基本知识解决实际问题。1. 指导教师布置设计任务并解析有关题目的设计指标和任务的具体内容，学生选择题目，明确问题描述和要求，查阅资料（要求：各班长或学习委员将本班的选题表交给辅导教师，一人一题，每道题的选择人数原则上不能超过3人，第一天课程设计结束后，每名学生都要确定题目）（1天）。2. 明确题目要求、确定数据结构、设计算法，编写程序、调试程序、测试程序（7天）（要求：准备足够的测试数据，对软件进行测试与调试。）。3. 验收与答辩（上机演示，回答教师提问）（1天）；4. 撰写课程设计报告（1天）。2、地点与时间 地点：金石滩校区计算机科学与工程学院实验中心计科131-2班: F

4、401、计科133-4班F405、计科135-6班F409软件工程131、4班: F209、软件工程132-3班: F205网络工程131-2班: F303、网络工程123-4班: F307时间：上午8:3011:20 下午1:304:20计算机科学与技术：课 程 设 计 上 机 时 间 表周一周二周三周四周五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午、下午上午计科12班I405计科56班I301元旦放假上午、下午(串到周日)19周上午、下午上午计科34班I405计科56班I301上午、下午（验收）撰写报告软件工程： 课 程 设 计 上 机 时 间 表周一周二周三周四周

5、五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午上午上午元旦休息上午(串到周日)19周上午下午上午下午(验收)撰写报告网络工程： 课 程 设 计 上 机 时 间 表周一周二周三周四周五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午下午上午元旦休息上午(串到周日)19周上午下午上午下午(验收)撰写报告三、课程设计题目及具体要求：1. 日历系统问题描述：设计并实现输出日历的程序,根据用户输入的年份,按格式输入该年度的日历,包括月份,星期。基本要求:输入任一年份, 显示出该年的所有月份日期，对应的星期, 注意闰年情况显示格式：1）月份：中文英文都可以，2）下一

6、行显示星期，从周日到周六，中英文都可以3）下一行开始显示日期从1号开始，并按其是周几实际情况与上面的星期数垂直对齐测试数据：以2004年度为例输入年份:2004输入该年1月1日是星期几：4输出日历如下：The calendar of the year 2004. Januray 1 February 2 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12 13 14 11 12 13 14 15 16 17 15 16 17 18 19 2

7、0 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29 = = March 3 April 4 Sun Mon Tue Wed Thu Fri Sat Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26

8、27 28 29 30 = =提高要求: 如果能自动对应星期，可得到良好成绩。2. 舞伴问题问题描述：一班有m个女生、n个男生(m不等于n), 举办一场舞会. 男女生分别编号坐在舞池两边的椅子上，每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号）。原始数据和结果数据要保存到文件中。测试数据：分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据提高要求：计算出任意一位男生(编号为

9、X)和任意一位女生(编号为Y), 在第K曲配对跳舞的情况。考核要求：（1） 用队列表示男、女学生，能够从文件中读取数据，文件中至少包括三组测试数据，分别为男生多于女生、女生多于男生、男女生人数相等。顺序输入舞曲的编号，对于每支舞曲，输入配对跳舞的男、女学生信息。并把本支舞曲的配对情况保存到文件中。完成上述任务，成绩为及格。（2） 在完成考核要求（1）的基础上，直接输出第K支舞曲的配对情况，能够处理异常，如文件空、只有男生或只有女生等。成绩为中等。3. 安排教学计划问题描述：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两个学期，每学期的时间长度和学分上限值均相等。每个

10、专业开设的课程都是确定的，而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求：输入参数包括学期总数，一学期的学分上限，每门课程的课程号、学分和直接先修课的课程号；允许两种策略，一是使学生在各学期的学习负担尽量均匀，二是使课程尽量集中在前几个学期；若根据给定的条件问题无解，则报告适当的信息，否则输出教学计划表（如每个学期所开设的课程的课程号及学分），同时将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文

11、件中。待添加的隐藏文字内容1测试数据：学期总数为6，学分上限为10，该专业共开设12门课。以12级某专业必修课与选修课为例，选择12门课程及相应学分，制定一个表明各门课程先后约束关系的有向图。提高要求：产生多种不同的方案，并使方案之间的差异尽可能地大。考核要求：（1） 达到基本要求，成绩为良好，如果不能把结果保存到文件中，成绩为不及格。（2） 在达到基本要求的基础上，产生3种以上的解决方案，且用户界面友好，成绩为优秀。4. 计算表达式的值问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。基本要求：从键盘输入一个正确

12、的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。测试数据：任意选取一个符合题目要求的表达式。提高要求：（1）对于表达式中的简单错误，能够给出提示；（2）不仅提示错误，也能给出错误信息（3）表达式中可以包括单个字母表示的变量（4）能够处理多种操作符（5）实现包含简单运算的计算器（6）实现一个包含简单运算和函数运算的计算器考核要求：（1） 表达式中的数据可以是整数或小数，达到基本要求，成绩为良好。如果仅能处理个位数，成绩为及格，如果仅能处理整数，成绩为中等。（2） 在达到基本要求的基础之上，如果达到提高要求的2项或以上，成绩可以为优秀。鼓励设计图形用户界面。5. 设计Huff

13、man 编码器与解码器问题描述：利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）提高要求：改进Huffman编码，产生两种以上的编码方案，对同一组测试数据，用不

14、同的编码方案编码，从文件长度、算法复杂度等方面进行比较。测试数据：英文文档文件或中文文档文件。考核要求：（1） 对原文件编码后，保存到新建文件中，将原文件与新文件比较，如果新文件长度大于原文件，则编码失败，成绩不及格。如果达到题目的基本要求，成绩为良好。（2） 达到提高要求，成绩可以为优秀。6. 银行业务模拟问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时,处理等候客户中排在最前面的客户的业务。写一个上述银

15、行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。基本要求：每个客户到达银行的时间和需要办理的业务随机产生，输出一天客户在银行的平均逗留时间和每个窗口每天办理的客户数和每种业务数。提高要求：设计图形用户界面，模拟中国银行真实的打号机操作界面，当用户选择一种业务后，要提示用户排在前面的人数。测试数据：营业时间为8小时，其他模拟量自行设定。考核要求：（1） 用队列实现;（2） 数据结构选择合理，达到题目的基本要求，成绩为良好。（3） 达到提高要求，用户界面友好，能够处理异常，成绩可以为优秀7. 航空订票系统问题描述：航空客运订票的业务活动包括：查

16、询航线，客票预订，办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。基本要求: 每条航线涉及的信息：航班号，起飞城市，终到城市，中转城市(可选项)，起飞时间，到达时间，机型，飞行班期(星期几)，乘员定额，余票量，已订票的客户名单(包括姓名，订票量，舱位等级），等候替补的客户名单(包括姓名，所需票量)，乘客信息（身份证号、姓名等），票价等。系统实现的功能：（） 查询功能：航班查询：根据出发地、目的地、出发时间查询，依据航班号查询等输出信息包括：航班号，出发地，终到地，星期几飞行，最近一天航班的日期和余票额；按航班号查询时，要求采用二分查找法，航班号是字母、数字混编的，因此

17、需要首先采用基数排序进行排序。订票人查询：输入订票人身份证号码或姓名查询订票人详细信息并输出。 乘客查询：输入乘客的身份证号码或姓名查询乘客的详细信息并输出。 (）录入功能航班信息录入：录入航班的相关信息。订票：根据输入的订票人身份证号验证订票人身份后，输入详细的乘客信息并进行保存。取消订票：取消订票信息。(）修改功能修改乘客信息：将查找到的乘客信息，进行修改，然后进行保存。修改订票人信息：将查找到的订票人的信息进行修改然后进行保存。修改航班信息：将查找到的 的航班信息进行修改后保存。(） 删除功能删除乘客信息：将查找到的乘客信息，进行删除。删除订票人信息：将查找到的订票人的信息进行删除。删除

18、航班信息：将查找到的航班信息进行删除。()航班推荐功能：要求按最省钱和最省时间两种方式对顾客进行推荐，要求如果有中转站要给出详细的出发到终点的路线，中转时需包括候机的时间。提高要求：（） 设计图形用户界面。（） 增加会员管理功能，包括保存常旅客、积分管理、优惠信息通知等，也可自行设计其它功能。测试数据：至少选择50组数据（测试数据保存在文件中），包括航班号、起飞地、目的地、起飞时间、到达时间、最大乘客数、票价、飞行时间、经停等信息，其他信息自行设定。考核要求：（） 数据结构选择合理，达到题目的基本要求，成绩为良好。（） 达到提高要求，用户界面友好，能够处理异常，成绩可以为优秀。8. 最小满覆盖

19、问题问题描述：在88的国际象棋棋盘上，如果在放置若干个马以后，使得整个棋盘的任意空位置上所放置的棋子均能被这些马吃掉，则称这组放置为棋盘的一个满覆盖。若去掉满覆盖中的任意一个棋子都会使这组放置不再是满覆盖，则称这一满覆盖为极小满覆盖。设计程序完成如下功能。基本要求:求解一个极小满覆盖，按照矩阵形式给出，用特殊符号表示马。并验证你的方法满足极小满覆盖。提高要求：（1） 得到最优满覆盖问题，并能证明。能画出棋盘的图形形式，或在其上动态演示试探过程；（2） 程序能方便地移植到其他规格的棋盘上，如1616等。提示：国际象棋中马吃其他棋子的方式为马走32格的对角线，有点像中国象棋中的马走日，没有“蹩马腿

20、”的规定。可以用这个方法判定走棋是否正确：如果马在白格，走一步后一定落在黑格。测试数据：8*8的矩阵。考核要求：达到基本要求，成绩为良好；达到提高要求（1）和（2）成绩为优秀。9. 迷宫游戏问题描述：程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。基本要求：（1） 老鼠形象可以辨认，可用键盘操纵老鼠上下左右移动；（2） 迷宫的墙足够结实，老鼠不能穿墙而过；（3） 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，并给出一条路径，否则提示失败。提高要求：（1） 添加编辑迷宫功能，可修改当前迷宫，修改内

21、容：墙变路、路变墙；（2） 增加闯关和计分功能；（3） 找出走出迷宫的所有路径，以及最短路径。测试数据：要求用10*10及以上的方阵或长方阵。考核要求：达到基本要求（1）（3），成绩为良好；达到提高要求（1）（3）成绩为优秀。10. 程序源代码的相似性问题描述：对于两个C+语言的源程序代码，用哈希表的方法分别统计两个程序中使用C+语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。 基本要求：建立C+语言关键字的哈希表，统计在每个源程序中C+关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2的相对距离来判断两个源程序的相似性。例如: 关键字： Void Int Fo

22、r Char if else while do break class程序1关键字频度： 4 3 0 4 3 0 7 0 0 2程序2关键字频度： 4 2 0 5 4 0 5 2 0 1 X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1 设s是向量X1和X2的相对距离，s=sqrt( (xi1-xi2) 2 )，当X1=X2时，s=0, 反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大，分析计算结果，给出相似度的结论。测试数据: 选择若干组编译和运行都无误的C+程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。 提高要

23、求：建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。考核要求：从源代码中分解单词，判断是否为关键字要采用效率高的方法，设计的哈希函数尽量产生较少的冲突，任选处理冲突的方法，选择的测试数据要尽量包含多种情况，能够处理异常，达到这些要求成绩为优秀，否则成绩向下浮动。鼓励按关键字和用户标识符判断相似性，鼓励设计图形用户界面。11. 小型文本编辑器问题描述：设计一个行编辑程序，使其具有通常行编辑器(如Vi、Edlin)应具备的基本功能。基本要求：编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数，统计行数等功能，对于超过

24、一屏的长文件，应能够分页显示，查找功能用字符串匹配算法实现。设计用户接口命令，实现对文本的编辑。具体的编辑命令，可参考数据结构算法网络教学平台上提供的edlin、Vi的命令集。测试数据：任一文本文件。提高要求：（1）可以支持“* ”、“? ”等通配符； （2）支持复制、粘贴等功能； （3）支持多文档同时编辑。考核要求：（1） 界面可以是菜单形式，完成基本要求，成绩可为优秀，如果只实现了基本要求的部分功能，成绩向下浮动。（2） 可以用MFC设计界面，但其中的功能实现不能用类库中的类。提示：可以考虑用双向链表实现，每一结点表示一行字符，注意每行字符不能超过255。12. 小型英汉词典问题描述：设计

25、一个英汉词典，支持Member的查找、插入、删除操作。基本要求：实现字典的常用方法有：有序线性表（用二分检索实现）、AVL树（二叉搜索树）、Patricia Tree、散列表等，任选一种方法实现字典的操作，查找单词、插入单词（插入时，先查找，找不到插入，找到提示用户）、删除单词（删除时，先查找，找到删除，找不到提示用户）。字典是按字母顺序排列的，不能用顺序查找，插入或删除单词后，要保持字典的有序性。测试数据：任一英文单词。提高要求：选用两种以上的方法实现字典的操作，要比较不同实现算法的时间复杂度和空间复杂度。考核要求：（1） 如果采用线性结构且无序，成绩为不及格。（2） 选择合适的数据结构，达

26、到了基本要求，成绩为优秀。（3） 鼓励设计图形用户界面。提示：字典可以自己建立，但必须按字母az建立26个文件，建议从网上下载，文件类型为txt。备注：1. 所有题目原则上需用C+完成，不能用C，也不能用类库中的类完成题目，如用MFC，则只能用MFC实现界面部分。2. 每道题的选择人数不能超过3人，开学第一天，各班长将选题情况表报给各班负责教师。四、应阅读的基本文献：1王红梅，胡明，王涛编著.数据结构（C+版）. 北京：清华大学出版社，2005.7.2谭浩强编著.C+面向对象程序设计.北京：清华大学出版社，2006.1.面向对象程序设计、数据结构、算法分析与设计相关的其它书籍和资料五、考核方式（包括总成绩的组成及分配比例）： 课程设计总成绩 = 平时出勤（10%）+设计报告（30%）+上机验收及答辩（60%）题目中给出的考核要求，相应的成绩仅仅是上机验收部分，课程设计总成绩要结合学生的实践能力、独立分析解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。成绩分为优、良、中、及格和不及格五个档次。六、其他有关问题的说明： 无年 月 日课程负责人（签字）：年 月 日专业教研室主任（签字）：年 月 日主管院长（签字）：年 月 日