数据结构与算法课程设计计划书级.docx
- 文档编号:9682411
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:15
- 大小:23.51KB
数据结构与算法课程设计计划书级.docx
《数据结构与算法课程设计计划书级.docx》由会员分享,可在线阅读,更多相关《数据结构与算法课程设计计划书级.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构与算法课程设计计划书级
计算机科学与工程学院
集中性实践教学计划书
(2011-2012学年第二学期
课程名称:
数据结构与算法课程设计
专业:
计算机科学与技术
软件工程、网络工程
班级:
计算机科学与技术101-6
软件工程101-4
网络工程101-4
课程负责人:
李锡祚、王玲芬、李威
指导教师分配情况:
专业指导教师
计算机科学与技术李威、李笑牛、张恒博、云健、刘爽、包书哲软件工程王玲芬、王鹏杰、王存睿、孙世昶、
网络工程李锡祚、姜楠、王晓强、王波
教学起止周:
第1至3教学周
一、教学目的与要求:
数据结构与算法课程设计的目的是使同学们能够根据数据对象的特性,合理的组织数据并能综合运用数据结构与算法基本知识和程序设计基本知识解决实际问题,培养基本的、良好的程序设计技能。
二、主要阶段、内容、时间及地点安排(以天为单位计:
阶段与内容
第1阶段:
指导教师布置设计任务并解析有关题目的设计指标和任务的具体内容,学生选择题目,明确问题描述和要求,查阅资料。
(1天;
各班长或学习委员将本班的选题表交给辅导教师,一人一题,每道题的选择人数原则上不能超过3人,第一天课程设计结束后,每名学生都要确定题目。
第2阶段:
明确题目要求、确定数据结构、设计算法,编写程序、调试程序、测试程序(11天;
第一周,学生应明确题目要求、确定数据的逻辑结构和存储结构、实现基本操作的编码与调试、实现主菜单。
第二周,完成核心算法的设计、编码与调试。
第三周,完成剩余任务的编码与调试,准备足够的测试数据,对软件进行测试与调试。
第3阶段:
完成设计任务,准备验收、答辩(1天;
第4阶段:
答辩(上机演示,回答教师提问(1天;
第5阶段:
撰写课程设计报告(2天。
地点与时间
地点:
金石滩校区图书馆
时间:
计算机科学与技术:
课程设计上机时间表
周一周二周三周四周五
第一周上午、下午上午第2大节、下午
第二周上午、下午上午第2大节、下午
第三周上午、下午上午第2大节、下午(验收
软件工程:
课程设计上机时间表
周一周二周三周四周五
第一周上午、下午上午、下午下午
第二周上午、下午上午、下午下午
第三周上午、下午上午、下午下午(验收
网络工程:
课程设计上机时间表
周一周二周三周四周五
第一周上午、下午上午下午上午
第二周上午、下午上午下午上午
第三周上午、下午上午下午上午(验收
注:
上午8:
30~11:
10
下午1:
40~4:
20
三、课程设计题目及具体要求:
1.成绩管理
问题描述:
给出n个学生的考试成绩表,成绩表包括学生的学号、姓名、考试成绩(高等数学、英语、物理,设计一个简单的成绩管理程序。
基本要求:
(1建立成绩表,能够插入、删除、修改学生的成绩记录;
(2按任一单科成绩排序;
(3计算每名学生的平均成绩;
(4统计任一单科成绩不及格的学生人数,输出不及格人数及不及格的学生名单
(5根据平均成绩将成绩表按由高到低的次序排列,统计每名学生在考试中获得的名次,分数相同的为同一名次,按名次输出成绩表。
(6成绩表保存在文件中,可以从文件读取数据。
测试数据:
学生可以根据自己班级的考试成绩单,任意截取一部分做为测试数据
提高要求:
成绩表用链式结构表示,实现上述全部要求。
考核要求:
(1用顺序结构表示成绩单,完成任务(1~(6,成绩为及格;
(2用链表表示成绩单,完成任务(1~(6,且软件容错能力强,成绩为中等
2.一元多项式简单计算
问题描述:
设计一个简单一元多项式计算器。
基本要求:
(1输入并建立多项式;
(2输出多项式;
(3两个多项式相加,输出结果多项式;
(4两个多项式相减,输出结果多项式。
测试数据:
可任意选取两个一元多项式,可以是一般的多项式,也可以是稀疏多项式。
提高要求:
可以根据输入变量的值,计算出多项式的结果,且算法的效率高。
考核要求:
(1用链表表示多项式,完成任务(1~(4,成绩为及格
(2满足考核(1的要求,同时能够输入变量的值,计算出多项式的结果,成绩中等,特别注意不能用X^N计算,否则等同于没有完成提高要求。
3.舞伴问题
问题描述:
一班有m个女生、n个男生(m不等于n,举办一场舞会.男女生分别编号坐在舞池两边的椅子上,每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴,设计一个程序模拟舞伴配对过程。
基本要求:
输入男、女学生的姓名、性别,由程序自动为男女生编号,可以顺序编号,也可以随机编号,输出每曲配对情况(包括男、女生的姓名、性别和编号。
原始数据和结果数据要保存到文件中。
测试数据:
分别选择男生多于女生、女生多于男生、男女生相等的三组测试数据
提高要求:
计算出任意一位男生(编号为X和任意一位女生(编号为Y,在第K曲配对跳舞的情况。
考核要求:
(1用队列表示男、女学生,能够从文件中读取数据,文件中至少包括三组测试数据,分别为男生多于女生、女生多于男生、男女生人数相等。
顺序输入舞曲的编号,对于每支舞曲,输入配对跳舞的男、女学生信息。
并把本支舞曲的配对情况保存到文件中。
完成上述任务,成绩为及格。
(2在完成考核要求(1的基础上,直接输出第K支舞曲的配对情况,能够处理异常,如文件空、只有男生或只有女生等。
成绩为中等。
4.文学研究助手(*
问题描述:
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。
试写一个实现这一目标的文字统计系统,称为“文学研究助手”。
基本要求:
英文小说存于一个文本文件中,待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。
文本文件名和待统计的词汇从键盘输入,程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计,结果保存到文件中。
提高要求:
包含是否区别大、小写两种匹配模式,且让用户选择。
测试数据:
以你的C/C++/JAVA源程序模拟英文小说,相应语言的保留字集作为待统计的词汇集。
考核要求:
(1用线性结构表示文本文件和待统计的单词,动态分配内存,完成基本要求的功能,成绩为中等。
(2在完成基本要求的基础上,完成提高要求,且用户界面友好,能够处理异常,成绩为良好。
5.哈希表的设计与实现(*
问题描述:
针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。
基本要求:
设每个记录有下列数据项:
电话号码、用户名、住址。
从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。
可以插入、查找、删除并显示给定用户名的记录,并计算查找长度,哈希表保存到文件中,并能从文件中读取数据。
测试数据:
取某个单位电话号码簿中的30个记录。
提高要求:
(1将电话号码薄以文件形式保存到盘上,能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。
(2对于相同的哈希函数,采用两种或两种以上的处理冲突的方法,如线性探测法和拉链法,比较不同的处理冲突的方法平均查找长度的变化。
测试时,采用同一组测试数据,分别用不同的方法处理冲突,记录并输出各自的平均查找长度。
(3设计图形用户界面
考核要求:
(1能够从键盘和文件输入原始数据,能够把变化的哈希表重新写回到文件中,同时完成其它的基本要求,成绩为中等。
(2达到提高要求中的(1或(2,或者同时达到(1和(2,成绩为良好。
(3用C++或MFC实现图形用户界面,成绩为良好
6.管道铺设施工的最佳方案(*
问题描述:
需要在某个城市的n个小区铺设管道,则在这n个小区之间铺设n-1条管道即可,
假设任意两个居民区之间都可以架设管道,但由于地理环境的不同,所需经费不同,选择最优的施工方案使总投资尽可能的少。
基本要求:
输入表示小区间关系的图及每条管道的权值,选择出n-1条管道,使总投资最小。
图的信息输入一次后,保存到文件中,选择的n-1条管道输出到显示器的同时,也保存于文件中。
测试用例:
任意选择一个图,模拟小区间可能铺设的管道及费用。
提高要求:
(1显示原始图及选择n-1条管道后的图。
(2用两种以上的算法找到最小生成树。
(3设计图形用户界面
考核要求:
(1注意,本题要求能够从键盘和文件中读取原始图的数据,且选择出的最佳方案也要保存到文件中,如果不能达到这个要求,成绩为不及格。
完成基本要求,成绩为中等。
(2达到提高要求中的(1或(2,或者同时达到(1和(2,成绩为良好。
(3用C++或MFC实现图形用户界面,实现友好的图形用户界面,成绩为良好
7.安排教学计划(**
问题描述:
大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限,每学年含两个学期,每学期的时间长度和学分上限值均相等。
每个专业开设的课程都是确定的,而且课程在开设时间的安排上必须满足先修关系。
每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。
每门课程恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
基本要求:
输入参数包括学期总数,一学期的学分上限,每门课程的课程号、学分和直接先修课的课程号;允许两种策略,一是使学生在各学期的学习负担尽量均匀,二是使课程尽量集中在前几个学期;若根据给定的条件问题无解,则报告适当的信息,否则输出教学计划表(如每个学期所开设的课程的课程号及学分,同时将教学计划输出到用户指定的文件中。
教学计划的表格格式自行设定,可以从键盘读取数据也可以从文件读取数据,结果保存到文件中。
测试数据:
学期总数为6,学分上限为10,该专业共开设12门。
以10级某专业必修课与选修课为例,选择12门课程及相应学分,制定一个表明各门课程先后约束关系的有向图。
提高要求:
产生多种不同的方案,并使方案之间的差异尽可能地大。
考核要求:
(1达到基本要求,成绩为良好,如果不能把结果保存到文件中,成绩为不及格。
(2在达到基本要求的基础上,产生3种以上的解决方案,且用户界面友好,成绩为优秀。
8.计算表达式的值(**
问题描述:
对于给定的一个表达式,表达式中可以包括常数、算术运行符(“+”、“-”、“*”、“/”和括号,编写程序计算表达式的值。
基本要求:
从键盘输入一个正确的中缀表达式,将中缀表达式转换为对应的后缀表达式,计算后缀表达式的值。
测试数据:
任意选取一个符合题目要求的表达式。
提高要求:
(1对于表达式中的简单错误,能够给出提示;
(2不仅提示错误,也能给出错误信息
(3表达式中可以包括单个字母表示的变量
(4能够处理多种操作符
(5实现包含简单运算的计算器
(6实现一个包含简单运算和函数运算的计算器
考核要求:
(1表达式中的数据可以是整数或小数,达到基本要求,成绩为良好。
如果仅能处理个位数,成绩为及格,如果仅能处理整数,成绩为中等。
(2在达到基本要求的基础之上,如果达到提高要求的2项或以上,成绩可以为优秀。
鼓励设计图形用户界面。
9.设计Huffman编码器与解码器(**
问题描述:
利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。
对于双工信道(即可以双向传输信息的信道,每端都需要一个完整的编/译码系统。
试为这样的信息收发站编写一个哈夫曼码的编/译码系统。
基本要求:
根据某字符文件统计字符出现频度,构造Huffman树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件。
(要求按二进制位表示编码
提高要求:
改进Huffman编码,产生两种以上的编码方案,对同一组测试数据,用不同的编码方案编码,从文件长度、算法复杂度等方面进行比较。
测试数据:
英文文档文件或中文文档文件。
考核要求:
(1对原文件编码后,保存到新建文件中,将原文件与新文件比较,如果新文件长度大于原文件,则编码失败,成绩不及格。
如果达到题目的基本要求,成绩为良好。
(2达到提高要求,成绩可以为优秀。
10.银行业务模拟(**
问题描述:
设银行有四个服务窗口,一个等待队列,每个窗口均可以办理存款、取款、挂失、还贷业务,每种业务所需的服务时间不同,客户到达银行后,先到打号机上打号,号票上包括到达时间、编号和需要办理的业务,然后在银行内等候,当任一服务窗口空闲时,处理等候客户中排在最前面的客户的业务。
写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。
基本要求:
每个客户到达银行的时间和需要办理的业务随机产生,输出一天客户在银行的平
均逗留时间和每个窗口每天办理的客户数和每种业务数。
提高要求:
设计图形用户界面,模拟中国银行真实的打号机操作界面,当用户选择一种业务后,要提示用户排在前面的人数。
测试数据:
营业时间为8小时,其他模拟量自行设定。
考核要求:
(1数据结构选择合理,达到题目的基本要求,成绩为良好。
(2达到提高要求,用户界面友好,能够处理异常,成绩可以为优秀
11.程序源代码的相似性(***
问题描述:
对于两个C++语言的源程序代码,用哈希表的方法分别统计两个程序中使用C++语言关键字的情况,并最终按定量的计算结果,得出两份程序的相似性。
基本要求:
建立C++语言关键字的哈希表,统计在每个源程序中C++关键字出现的频度,得到两个向量X1和X2,通过计算向量X1和X2的相对距离来判断两个源程序的相似性。
例如:
关键字VoidIntForCharifelsewhiledobreakclass
程序1关键字频度4304307002
程序2关键字频度4205405201
X1=[4,3,0,4,3,0,7,0,0,2]
X2=[4,2,0,5,4,0,5,2,0,1]
设s是向量X1和X2的相对距离,s=sqrt(∑(xi1-xi22,当X1=X2时,s=0,反映出可能是同一个程序;s值越大,则两个程序的差别可能也越大,分析计算结果,给出相似度的结论。
测试数据:
选择若干组编译和运行都无误的C++程序,程序之间有相近的和差别大的,用上述方法求s,对比两个程序的相似性。
提高要求:
建立源代码用户标识符表,比较两个源代码用户标识符出现的频度,综合关键字频度和用户标识符频度判断两个程序的相似性。
考核要求:
从源代码中分解单词,判断是否为关键字要采用效率高的方法,设计的哈希函数尽量产生较少的冲突,任选处理冲突的方法,选择的测试数据要尽量包含多种情况,能够处理异常,达到这些要求成绩为优秀,否则成绩向下浮动。
鼓励按关键字和用户标识符判断相似性,鼓励设计图形用户界面。
12.小型文本编辑器(***
问题描述:
设计一个行编辑程序,使其具有通常行编辑器(如Vi、Edlin应具备的基本功能。
基本要求:
编辑器应具备对文本文件的查找、插人、删除、修改、字符串替换、统计字数,统计行数等功能,对于超过一屏的长文件,应能够分页显示,查找功能用字符串匹配算法实现。
设计用户接口命令,实现对文本的编辑。
具体的编辑命令,可参考数据结构算法网络教学平台上提供的edlin、Vi的命令集。
测试数据:
任一文本文件。
提高要求:
1.可以支持“*”、“?
”等通配符;
2.支持复制、粘贴等功能
3.支持多文档同时编辑;
考核要求:
(1界面可以是菜单形式,完成基本要求,成绩可为优秀,如果只实现了基本要求的部分功能,成绩向下浮动。
(2可以用MFC设计界面,但其中的功能实现不能用类库中的类。
提示:
可以考虑用双向链表实现,每一结点表示一行字符,注意每行字符不能超过255。
13.小型英汉词典(***
问题描述:
设计一个英汉词典,支持Member的查找、插入、删除操作。
基本要求:
实现字典的常用方法有:
有序线性表(用二分检索实现、AVL树(二叉搜索树、PatriciaTree、散列表等,任选一种方法实现字典的操作,查找单词、插入单词(插入时,先查找,找不到插入,找到提示用户、删除单词(删除时,先查找,找到删除,找不到提示用户。
字典是按字母顺序排列的,不能用顺序查找,插入或删除单词后,要保持字典的有序性。
测试数据:
任一英文单词。
提高要求:
选用两种以上的方法实现字典的操作,要比较不同实现算法的时间复杂度和空间复杂度。
考核要求:
(1如果采用线性结构且无序,成绩为不及格。
(2选择合适的数据结构,达到了基本要求,成绩为优秀。
(3鼓励设计图形用户界面。
提示:
字典可以自己建立,但必须按字母a~z建立26个文件,建议从网上下载,文件类型为txt。
14.地图着色(***
问题描述:
对中国地图进行着色,两个共同边界的省份染不同的颜色,当可以选择7、6、5、4种不同的颜色的情况下,由程序自动进行处理,给出具体的染色方案。
基本要求:
(1建立以省为节点,以是否相邻为边的一个无向图;
(2从颜色模板中选取一个颜色赋值给每个节点;
(3相邻节点颜色不能相同;
测试数据:
学生可以自己选取颜色模板做为测试数据;分别需要测试7、6、5、4种不同的颜色。
提高要求:
当用4种颜色染色时,给出不同的染色方案,计算染色的效率。
考核要求:
(1可以不实际画图,用数字或文字表示颜色,给出着色方案,达到基本要求,成绩可为优秀。
(2鼓励画出彩色图。
15.漫游中国(***
问题描述:
从任一省会出发,走遍所有省会,给出某种评价指标,然后根据该指标由计算机选择最优的漫游路线。
基本要求:
(1建立以省会为节点,以是否相邻为边的一个无向赋权图;
(2只能选择陆路和水路交通;
(3每条边的权重为两地之间的距离,以公里为单位;
测试数据:
学生可以自己选取评价指标,如费用最少、时间最短等等。
提高要求:
不同的出发点结果是否一致,并讨论多目标模型。
考核要求:
(1不要求画图,用数字或文字表示省会,给出漫游路线,达到基本要求,成绩可为优秀。
(2鼓励画图,用不同颜色的线画出漫游路线。
21~23为附加题,有能力完成的学生可以选择。
Ply格式解析
这里以big_porsche.ply为例解析其格式:
1、文件的头部:
参看图1,文件的头两行构成文件的头部,其中第一行说明文件有多少个顶点(比如big_porsche.ply共有“elementvertex5247”表示有5247个顶点;第二行表示文件有多少个面(比如比如big_porsche.ply共有“elementface10474”表示有10474个面。
图1红色方框内就是文件的头部
2、文件的体:
2.1点表部分
文件头部紧接的下面就是文件的顶点部分,按照头部说明,应该有5247行顶点数据,图2中只是显示了10行。
每个顶点有x、y、z三个浮点数代表三维坐标。
图2红色方框内是10行顶点数据2.2面表部分紧接这顶点数据的是10474行面表。
每个行表示一个面,如果这个行的第一个值是3,表示此面为三角形,后面的三个数顺次是三角形三个顶点的索引。
如图3所示,面表的第一行是个三角形,第一个顶点为0号顶点(即2.1中点表的第一个顶点)、第二个顶点为1号顶点(即2.1中点表的第二个顶点)、第三个顶点为2号顶点(即2.1点表中的第三个顶点)。
图3红色方框内是9行面表数据3、绘制结果由这样一个文件就能绘制出一个三维的车的模型,如下图所示:
10
和这个文件相关的三个题目21、表排序并维护面表的索引的一致性(***)过程如下:
1)首先对整个点表数据按照X坐标从小到大排序。
2)定义一个值lengthX,从上到下的切分X值段,每段的长度为lengthX。
3)在每个lengthX行数据内,按Y值进行排序。
4)在每个lengthX内再切分出lengthY。
5)在lengthY内按Z值排序。
两点需要注意的:
⑴整个排序的过程中每个点(即点表的一行数据)是一个整体。
⑵点的编号改变,请同时维护面表的一致性(即维护面表和点表初始时的对应关系)。
22、对大的点表序列排序,请设计基于外存的排序算法(即即使对大的文件排序,占用的内存也非常小,比如对1G的文件整体排序,整个运行过程只需要占用2M的内存)(***23、完成对ply文件的压缩(***定义点表中两个顶点(x1,y1,z1)和(x2,y2,z2之间的距离定义为:
dis=(x1−x22+(y1−y22+(z1−z22。
对ply文件压缩过程如下:
1)请以以上距离作为两点之间的权值,构建一个最小生成树。
2)请存储两种必须的信息到两个文件中:
①最小生成树的树形结构;②沿最小生成树存储父子节点的差值。
3)对2)中的②数据用Huffman编码进行编码压缩。
解压缩的过程为以上过程的逆过程。
需要注意的是在整个的处理过程中需维护面表索引与点表的一致性。
备注:
1.每道题目后面的*号,表示题目的难度系数;对应的评定成绩等级为及格(无*号)、中等(*号)、良好(**号)、优秀(***号),学生完成题目的基本要求,即可得到程序设计部分的相应等级成绩,完成题目提高要求,成绩可以向上浮动,如果没有完成基本要求,成绩向下浮动,直至不及格。
2.所有题目原则上需用C++完成,不能用C,也不能用类库中的类完成题目,如用MFC,则只能用MFC实现界面部分。
3.选择附加题目的学生,对题目有疑问,找老师咨询。
4.特别注意:
每道题的选择人数不能超过3人,开学第一天,各班长将选题情况表报给各班负责教师。
11
四、应阅读的基本文献:
[1]王红梅,胡明,王涛编著.数据结构(C++版).北京:
清华大学出版社,2005.7.[2]谭浩强编著.C++面向对象程序设计.北京:
清华大学出版社,2006.1.面向对象程序设计、数据结构、算法分析与设计相关的其它书籍和资料五、考核方式(包括总成绩的组成及分配比例):
课程设计总成绩=平时出勤(20%)+设计报告(40%)+上机验收及答辩(40%)题目中给出的考核要求,相应的成绩仅仅是上机验收部分,课程设计总成绩要结合学生的实践能力、独立分析解决问题的能力和创新精神,总结报告和答辩水平以及学习态度综合考评。
成绩分为优、良、中、及格和不及格五个档次。
六、其他有关问题的说明:
无年课程负责人(签字):
月日年专业教研室主任(签字):
月日年主管院长(签字):
月日年月日12
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 课程设计 计划书