《数据结构与算法》教育大纲.doc

《 数据结构与算法 》实验报告要求实验报告首先要求有一个清晰醒目的报告标题，例如：《数据结构课程设计实验一：xxxxxxxxxx》报告至少要求具备以下四部分内容：一、简介这一部分需简单介绍题目内容，即该实验到底要做什么如果涉及明确的算法，最好再简单介绍一下算法产生的背景基本要求：实验内容必须覆盖完备二、算法说明这一部分需详细描述解决问题所需要用到的算法和重要的数据结构，即该实验到底应该怎么做基本要求：所有处理问题中所用到的关键算法都要描述清楚，而不是仅描述主函数算法和数据结构用伪码和图示描述，千万不要只写源代码加注释这一部分的目的是让读者在短时间内对作者解决问题的整体思路有个清楚的了解，表达方式必须比源代码通俗易懂如果读者感觉还不如直接读源代码来得明白，这一部分就失去了意义三、测试结果这一部分需根据题目类型设计提供相应的测试方法和结果对于需要比较不同算法性能优劣的题目，应设计并填写一张性能比较表格，列出不同算法在同一指标下的性能表现但仅仅罗列出一堆数据是不够的，还应将数字转化为图象、曲线等，帮助读者更直观地理解测试结果对于需要利用某算法解决某问题的题目，应设计并填写一张测试用例表每个测试用例至少应包括下列内容：l 测试输入：设计一组输入数据；l 测试目的：设计该输入的目的在于测试程序在哪方面可能存在的漏洞；l 正确输出：对应该输入，若程序正确，应该输出的内容；l 实际输出：该数据输入后，实际测试得到的输出内容；l 错误原因：如果实际输出与正确输出不符，需分析产生错误的可能原因；l 当前状态：分为“通过”（实际输出与正确输出相符）、“已改正”（实际输出与正确输出不符，但现在已修改正确）、“待修改”（实际输出与正确输出不符，且尚未改正）三种状态。

四、分析与探讨这一部分应是整篇报告中最令读者感兴趣的部分，分为两块内容：l 测试结果分析需详细解释测试策略，对得到的数据进行分析，总结出算法的时空复杂度，得出自己对算法性能等方面分析的结论l 不局限于题目要求使用的算法，探讨更多解决问题的途径，或者提出自己的见解，给出改进算法以得到更好结果的建议附录：源代码源代码列在附录中，要求程序风格清晰易理解，有充分的注释有意义的注释行少于30%的代码将不能得分本课程的考核实验报告可以选择以下任一实验，也可以自己选择其他实验1、第1个可选题目设计一个模拟简单整数计算器的程序该程序可以接受整数数据，运算符可以接受包含(, ), +, -, *, /, %, 和 ^ (求幂运算符, a^b = ab )的中缀表达式，并求出结果如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息输入要求：程序从“input.txt”.文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERROR IN INFIX NOTATION”输入例子：499+599+699*1(3*5*(4+8)%2)2^2^31+2(2/0(2-4)^32%22%5输出例子：17970256ERROR IN INFIX NOTATIONERROR IN INFIX NOTATION-8022、第2个可选题目完成字符串模式匹配的KMP算法即完整程序。

对给定的文本文件，查找所有给定的子串具体的要求可以自主确定3、第3个可选题目设计并实现一种快速排序（quicksort）的最优化的版本，并且比较在下列组合情况下的算法的性能表现：(1) Cutoff值从0~20 Cutoff值的作用是只有当数组的长度小于等于这个值时，才使用另一种排序方法对其排序，否则继续使用quicksort算法排序2) 选定pivot（支点）的方法分别是“第一个元素”，“三个元素的中值”，“五个元素的中值”对上述的测试分别要采用如下三种类型的input文件：(1) 顺序的input(2) 逆序的input(3) 随机的input输入文件中测试数组的大小可以从1000个数到10000个数不等程序输入input.txt文件，输出output文件例如：input.txt内容如下5 //数字的个数5 4 3 2 1 //数字用空格分开 //两组测试数据中间空一行104 6 8 7 5 1 3 9 2 0相应的output.txt内容如下Case number: 1Number of elements: 51 2 3 4 5Case number: 2Number of elements: 100 1 2 3 4 5 6 7 8 9程序的重点在于对每种组合情况下算法性能的比较。

不同的运行时间（run time）要用图表表示出来，在图表中要区分由于文件大小的不同而产生的差别实验成绩的评分依据：一：程序设计（50分）其中：1、完成程序的设计，程序能够正常运行（20分）；2、输入测试数据，能够得到正确的结果，并且能够能对输入内容进行数据合法性检测并进行相应的异常处理（20分）；3、程序结构合理，有充足的（30%以上）注释（10分）；4、数据结构、算法设计巧妙，在正确的基础上提高效率或者增加创新的一些功能，提供友好的输入、输出界面，可相应加分二、程序测试（20分）其中：5、设计充足合理的测试用例（15分）；6、完成测试结果分析（5分）；7、测试用例没有涵盖各种情况的，相应扣3－6分；测试用例考虑全面、测试结果分析透彻，可相应加分三、实验报告（30分）其中：8、完成实验报告，第一章中描述程序所解决的问题以及算法背景等（5分）；9、第二章中使用伪代码等手段对算法做出详细的分析设计（15分）；10、第四章分析与探讨（8分）；文档风格统一（2分）；11、实验题目分析透彻，算法、数据结构描述恰当，可相应加分。