DS上机实验的目的、要求和评分标准.doc

上机实验的目的、要求和评分标准一、实验目的上机实践是各位对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合，使你们学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析（需求分析）、总体结构设计和用户界面设计（概要设计）、程序设计基本技能和技巧等，即一整套软件工程规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。为了达到上述目的，本课程共安排了10个实验单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。各实验单元与教科书的各章具有紧密的对应关系。二、要求： 做好每一次上机前的准备以提高上机效率： 预先认真阅读相关实验内容，做到心中有明确的目的要求和任务，要有备而来，应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。对于个别目前基础较差的同学，实在是没法完成任务的建议你先参考其他同学的算法，勤学好问，最终自己独立完成，以增强你的感性认识，强化你的实践基础，提高你的实践能力。 按照实验内容规定的习题题目，事先在实验预习报告上编写好源程序及运行程序所需的典型数据，并经人工静态检查认为无误；手编程序应书写整齐，应在每个题目之间留出一定的空间，以备记录上机调试情况和运行结果等；对程序中自己有疑问的地方，应作出记号，以便上机时给以注意。 将想要上机验证的问题草拟提纲；制定一个简捷的程序调试计划。 上机时输入和调式自己所编写的程序。对“出错信息”，应善于自己分析判断，并充分利用开发工具提供的错误信息和调试手段解决出现的问题，及时修改与完善算法、源程序，随时记录有价值的内容。解决问题是学习调式程序的良好机会。切不可不编程序或抄别人的程序去上机，应从养成严谨的科学作风。 程序调试通过后，应运行程序并根据事先准备的典型数据验证结果，在运行时要注意在输入不同数据时所得到的不同结果。 为便于教师、助教检查和以后复习，请不要删除已通过的程序，包括有问题待答疑的程序，应保存在自己的工作目录内。源程序名应能反映哪一次实验的哪一个题目，如Lab1_1.c表示实验一的第1题，若有未完成调试的源程序，可以作存盘保存处理，待课后继续完成。三、实验报告规范：上机结束后，应整理出实验报告，每份实验报告总分100分，实验报告必须在该次实验后的下次实验课前交到学习委员处，由学习委员按学号整理好，在上课前上交。实验报告必须包括以下七个部分，详细要求见课程教学大纲，模板见实验指导书（习题集）： 需求分析（10分） 概要设计（20分） 抽象数据类型的描述 程序结构图（功能模块图） 详细设计（30分） 存储结构的描述（含描述对象和算法中工具的存储结构） 算法的详细设计（对复杂算法，最好画出其N-S流程图） 函数的调用关系图 调试分析（10分） 用户使用说明（10分） 测试结果（10分） 附录（10分） 源程序清单（包括注释）实验一：线性表的顺序存储结构（验证性实验）上机前的预习：阅读所给的源程序1，上机输入该程序，并调试、运行，分析该源程序的功能；在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：设计并实现以下算法：有两张单调递减有序的线性表A和B，采用顺序存储结构，将这两张表合并成C表，要求C表单调递增有序。实验二：线性表的链式存储结构（验证性实验）上机前的预习：阅读所给的源程序2，上机输入该程序，并调试、运行，分析该源程序的功能；在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：设计并实现以下算法：判定一个带头结点的单向链表的元素值是否为非递增的，如果是非递增的，请删除值相同的多余元素，并就地逆置该链表。实验三：栈和队列的应用（一）（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：设计并实现将一个中缀表达式转换成逆波兰式，然后对此逆波兰表达式求值的算法。题二：设计并实现求杨辉三角的递归算法。实验四：栈和队列的应用（二）（综合性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。（题一为必做题，题二、题三中必须完成其中一题）题一：假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意：不设头指针），试编写相应的队列初始化、入队列和出队列算法。题二：假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为(1，1)，出口坐标为(m，n)，试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。要求：随机生成迷宫，用队列实现路径的查找，用栈输出路径。不允许使用递归算法。题三：（习题集P97）魔王语言解释。一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： 12m (12n)(nm-1 1)在这两种形式中，从左到右均表示解释；从右到左均表示抽象。试写一个魔王语言的解释系统，将魔王的话解释成人能听懂的话。要求：设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。用下述两条规则和上述规则实现： BtAdA Asae实验五：稀疏矩阵的存储和快速转置（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：假设稀疏矩阵A采用三元组表表示，编写程序实现该矩阵的快速转置(教材算法5.2)。要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组表，由程序将其转换成矩阵形式后输出。题二：（习题集P136）设计并实现稀疏矩阵运算器。（选做）实验六：二叉树的递归遍历及其应用（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：假设二叉树采用二叉链表结构。设计并实现如下算法：先序递归建树，中序非递归遍历该二叉树，输出各个结点的值，并求该二叉树的高度。实验七：二叉树的其他典型算法（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：假设二叉树采用二叉链表结构。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，按层次遍历该二叉树，并求该树中叶结点的个数。题二：（习题集P149）哈夫曼编/译码器。（选做）实验八：图的遍历（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：图采用邻接表结构表示。实现无向图的广度优先搜索算法与有向图的深度优先搜索算法(教材算法7.4、算法7.5、算法7.6)。题二：（习题集P151）校园导游咨询模拟。（选做）实验九：查找（验证性实验）上机前的预习：在实验预习报告上编写好上机题的源程序及运行程序所需的典型数据，并给程序加上适当的注释。题一：二叉树采用二叉链表结构表示。设计并实现如下算法：按输入的关键字序列建立一棵二叉排序树，并删除该二叉排序