《数据结构与算法课程设计计划书_2011_2012_2(10级)》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计计划书_2011_2012_2(10级)（18页珍藏版）》请在金锄头文库上搜索。
1、. . . . .计算机科学与工程学院集中性实践教学计划书( 2011-2012 学年第二学期课程名称:数据结构与算法课程设计专业:计算机科学与技术软件工程、网络工程班级:计算机科学与技术101-6软件工程101-4网络工程101-4课程负责人:李锡祚、王玲芬、李威指导教师分配情况:专业指导教师计算机科学与技术李威、李笑牛、张恒博、云健、刘爽、包书哲软件工程王玲芬、王鹏杰、王存睿、孙世昶、网络工程李锡祚、姜楠、王晓强、王波教学起止周:第1 至3 教学周一、教学目的与要求:数据结构与算法课程设计的目的是使同学们能够根据数据对象的特性,合理的组织数据并能综合运用数据结构与算法基本知识和程序设计基本
2、知识解决实际问题,培养基本的、良好的程序设计技能。二、主要阶段、内容、时间及地点安排(以天为单位计:阶段与内容第1阶段:指导教师布置设计任务并解析有关题目的设计指标和任务的具体内容,学生选择题目,明确问题描述和要求,查阅资料。(1天;各班长或学习委员将本班的选题表交给辅导教师,一人一题,每道题的选择人数原则上不能超过3人,第一天课程设计结束后,每名学生都要确定题目。第2阶段:明确题目要求、确定数据结构、设计算法,编写程序、调试程序、测试程序(11天;第一周,学生应明确题目要求、确定数据的逻辑结构和存储结构、实现基本操作的编码与调试、实现主菜单。第二周,完成核心算法的设计、编码与调试。第三周,完
3、成剩余任务的编码与调试,准备足够的测试数据,对软件进行测试与调试。第3阶段:完成设计任务,准备验收、答辩(1天;第4阶段:答辩(上机演示,回答教师提问(1天;第5阶段:撰写课程设计报告(2天。地点与时间地点:金石滩校区图书馆时间:计算机科学与技术:课程设计上机时间表周一周二周三周四周五第一周上午、下午上午第2大节、下午第二周上午、下午上午第2大节、下午第三周上午、下午上午第2大节、下午(验收软件工程:课程设计上机时间表周一周二周三周四周五第一周上午、下午上午、下午下午第二周上午、下午上午、下午下午第三周上午、下午上午、下午下午(验收网络工程:课程设计上机时间表周一周二周三周四周五第一周上午、下
4、午上午下午上午第二周上午、下午上午下午上午第三周上午、下午上午下午上午(验收注:上午8:3011:10下午1:404:20三、课程设计题目及具体要求:1.成绩管理问题描述:给出n个学生的考试成绩表,成绩表包括学生的学号、姓名、考试成绩(高等数学、英语、物理,设计一个简单的成绩管理程序。基本要求:(1建立成绩表,能够插入、删除、修改学生的成绩记录;(2按任一单科成绩排序;(3 计算每名学生的平均成绩;(4 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5 根据平均成绩将成绩表按由高到低的次序排列,统计每名学生在考试中获得的名次,分数相同的为同一名次,按名次输出成绩表。(6
5、 成绩表保存在文件中, 可以从文件读取数据。测试数据:学生可以根据自己班级的考试成绩单,任意截取一部分做为测试数据提高要求:成绩表用链式结构表示,实现上述全部要求。考核要求:(1用顺序结构表示成绩单,完成任务(1(6,成绩为及格;(2用链表表示成绩单,完成任务(1(6,且软件容错能力强,成绩为中等2.一元多项式简单计算问题描述:设计一个简单一元多项式计算器。基本要求:(1输入并建立多项式;(2输出多项式;(3两个多项式相加,输出结果多项式;(4两个多项式相减,输出结果多项式。测试数据:可任意选取两个一元多项式,可以是一般的多项式,也可以是稀疏多项式。提高要求:可以根据输入变量的值,计算出多项式
6、的结果,且算法的效率高。考核要求:(1用链表表示多项式,完成任务(1(4,成绩为及格(2满足考核(1的要求,同时能够输入变量的值,计算出多项式的结果,成绩中等,特别注意不能用XN计算,否则等同于没有完成提高要求。3.舞伴问题问题描述:一班有m个女生、n个男生(m不等于n, 举办一场舞会. 男女生分别编号坐在舞池两边的椅子上,每曲开始时, 依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴,设计一个程序模拟舞伴配对过程。基本要求:输入男、女学生的姓名、性别,由程序自动为男女生编号,可以顺序编号,也可以随机编号,输出每曲配对情况(包括男、女生的姓名、性别和编号。原始数据和结
7、果数据要保存到文件中。测试数据:分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据提高要求:计算出任意一位男生(编号为X和任意一位女生(编号为Y, 在第K曲配对跳舞的情况。考核要求:(1用队列表示男、女学生,能够从文件中读取数据,文件中至少包括三组测试数据,分别为男生多于女生、女生多于男生、男女生人数相等。顺序输入舞曲的编号,对于每支舞曲,输入配对跳舞的男、女学生信息。并把本支舞曲的配对情况保存到文件中。完成上述任务,成绩为及格。(2在完成考核要求(1的基础上,直接输出第K支舞曲的配对情况,能够处理异常,如文件空、只有男生或只有女生等。成绩为中等。4.文学研究助手(*问题描述:文学研
8、究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为“文学研究助手”。基本要求:英文小说存于一个文本文件中,待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。文本文件名和待统计的词汇从键盘输入,程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计, 结果保存到文件中。提高要求:包含是否区别大、小写两种匹配模式,且让用户选择。测试数据:以你的C/C+/JAVA源程序模拟英文小说,相应语言的保留字集作为待统计的词汇集。考核要求:(1用线性结构表示文本文件和待统计的单词,动态分配内存,完成基本要求的功能,成绩为中
9、等。(2在完成基本要求的基础上,完成提高要求,且用户界面友好,能够处理异常,成绩为良好。5.哈希表的设计与实现(*问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中,并能从文件中读取数据。测试数据:取某个单位电话号码簿中的30个记录。提高要求:(1将电话号码薄以文件形式保存到盘上,能够按用户名和电话号码两种形式建立哈希表并实现插入、查
10、找、删除表中元素的功能。(2对于相同的哈希函数,采用两种或两种以上的处理冲突的方法,如线性探测法和拉链法,比较不同的处理冲突的方法平均查找长度的变化。测试时,采用同一组测试数据,分别用不同的方法处理冲突,记录并输出各自的平均查找长度。(3设计图形用户界面考核要求:(1能够从键盘和文件输入原始数据,能够把变化的哈希表重新写回到文件中,同时完成其它的基本要求,成绩为中等。(2达到提高要求中的(1或(2,或者同时达到(1和(2,成绩为良好。(3用C+或MFC实现图形用户界面,成绩为良好6.管道铺设施工的最佳方案(*问题描述:需要在某个城市的n个小区铺设管道,则在这n个小区之间铺设n-1条管道即可,假
11、设任意两个居民区之间都可以架设管道,但由于地理环境的不同,所需经费不同,选择最优的施工方案使总投资尽可能的少。基本要求:输入表示小区间关系的图及每条管道的权值,选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。测试用例:任意选择一个图,模拟小区间可能铺设的管道及费用。提高要求:(1显示原始图及选择n-1条管道后的图。(2用两种以上的算法找到最小生成树。(3设计图形用户界面考核要求:(1注意,本题要求能够从键盘和文件中读取原始图的数据,且选择出的最佳方案也要保存到文件中,如果不能达到这个要求,成绩为不及格。完成基本要
12、求,成绩为中等。(2达到提高要求中的(1或(2,或者同时达到(1和(2,成绩为良好。(3 用C+或MFC实现图形用户界面,实现友好的图形用户界面,成绩为良好7.安排教学计划(*问题描述:大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限,每学年含两个学期,每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的,而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门课程恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。基本要求:输入参数包括学期总数,一学期的学分上限,每门课程的课程号、学分和直接先修课的课程号;允
13、许两种策略,一是使学生在各学期的学习负担尽量均匀,二是使课程尽量集中在前几个学期;若根据给定的条件问题无解,则报告适当的信息,否则输出教学计划表(如每个学期所开设的课程的课程号及学分,同时将教学计划输出到用户指定的文件中。教学计划的表格格式自行设定, 可以从键盘读取数据也可以从文件读取数据, 结果保存到文件中。测试数据:学期总数为6,学分上限为10,该专业共开设12门。以10级某专业必修课与选修课为例,选择12门课程及相应学分,制定一个表明各门课程先后约束关系的有向图。提高要求:产生多种不同的方案,并使方案之间的差异尽可能地大。考核要求:(1达到基本要求,成绩为良好,如果不能把结果保存到文件中
14、,成绩为不及格。(2在达到基本要求的基础上,产生3种以上的解决方案,且用户界面友好,成绩为优秀。8.计算表达式的值(*问题描述:对于给定的一个表达式,表达式中可以包括常数、算术运行符(“+”、“-”、“*”、“/”和括号,编写程序计算表达式的值。基本要求:从键盘输入一个正确的中缀表达式,将中缀表达式转换为对应的后缀表达式,计算后缀表达式的值。测试数据:任意选取一个符合题目要求的表达式。提高要求:(1对于表达式中的简单错误,能够给出提示;(2不仅提示错误,也能给出错误信息(3表达式中可以包括单个字母表示的变量(4能够处理多种操作符(5实现包含简单运算的计算器(6实现一个包含简单运算和函数运算的计
15、算器考核要求:(1表达式中的数据可以是整数或小数,达到基本要求,成绩为良好。如果仅能处理个位数,成绩为及格,如果仅能处理整数,成绩为中等。(2在达到基本要求的基础之上,如果达到提高要求的2项或以上,成绩可以为优秀。鼓励设计图形用户界面。9.设计Huffman 编码器与解码器(*问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道,每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。基本要求:根据某字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件。(要求按二进制位表示编码提高要求:改进Huffman编码,产生两种以上的编码方案,对同一组测试数据,用不同的编码方
