《数据结构》课程实验教学大纲 Data Structure

《数据结构》实验教学大纲 课程英文名称：Data Structure 课程编码：Z108006课程类别：口基础☑专业基础口专业 学时：16学分：2面向专业：计算机科学与技术、电子信息工程、信息管理与信息系统 大纲制定者：高攀 大纲审定者： 审定日期： 课程简介： 《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各 种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必 须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同 时提高解决计算机应用实际问愿的能力 一、教学目标及任务 本实验课程与《数据结构》课堂教学有机结合，相辅相成。在课堂教学中，比较全面、概括性 地讲述数据结构学科中一些基础性知识、重要概念及各种算法，而在本实验课程中，将这些基础性 知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标： (①)、掌握计算机处理数据的基本方法 (②)、了解算法需用的时间及空间分析方法 3)、能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法 (④)、通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。 二、实验项目及学时分配 ①实验项目名称要准确规范。②学时分配合计数要等于或大于实验总学时数（其中超出的学时 数可为选开实验)。③实验类型指演示性、验证性、综合性或设计性等实验。④实验要求指必做/ 选做。 每细 序号 实验项目名称 要 1 顺序表的表示与实现 2 验证 必做 2 链表的表示与实现 验证 必做 3 表达式的计算 验证 必做 Huffman编码 验证 必做 5 关键路径 验证 选做 6 最短路经 2 设计 1 必做

1 《数据结构》实验教学大纲 课程英文名称：Data Structure 课程编码：Z108006 课程类别：□基础 专业基础 □专业 学时：16 学分： 2 面向专业：计算机科学与技术、电子信息工程、信息管理与信息系统 大纲制定者： 高攀 大纲审定者： 审定日期： 课程简介： 《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各 种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必 须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同 时提高解决计算机应用实际问题的能力。 一、教学目标及任务 本实验课程与《数据结构》课堂教学有机结合，相辅相成。在课堂教学中，比较全面、概括性 地讲述数据结构学科中一些基础性知识、重要概念及各种算法，而在本实验课程中，将这些基础性 知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标： ⑴、掌握计算机处理数据的基本方法 ⑵、了解算法需用的时间及空间分析方法 ⑶、能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法 ⑷、通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。 二、实验项目及学时分配 ①实验项目名称要准确规范。②学时分配合计数要等于或大于实验总学时数（其中超出的学时 数可为选开实验）。③实验类型指演示性、验证性、综合性或设计性等实验。④实验要求指必做/ 选做。 序号 实验项目名称 学时 分配 实验 类型 每组 人数 实验 要求 1 顺序表的表示与实现 2 验证 1 必做 2 链表的表示与实现 2 验证 1 必做 3 表达式的计算 2 验证 1 必做 4 Huffman 编码 4 验证 1 必做 5 关键路径 2 验证 1 选做 6 最短路经 2 设计 1 必做

二叉排序树 2 验证 必做 8 希尔排序 2 验证 1 选做 9 快速排序 2 验证 1 必做 10堆排序 验证1选做 三、实验内容及教学要求 以“实验项目”为单位说明每个实验的主要内容，重点和难点，并按“了解”、“理解”、“掌 握”三个层次说明每个实验项目的教学要求和所需主要仪器设备。具体格式如下： 实验项目一：顺序表的表示与实现 实验内容及教学要求： 1、顺序表的表示： 2、顺序表的初始化、插入、别除、查找等操作 主要仪器设备：计算机 实验项目二：链表的表示与实现 实验内容及教学要求： 1、链表的表示： 2、链表的初始化、插入、删除、查找等操作。 主要仪器设备：计算机 实验项目三：表达式计算 实验内容及教学要求： 1、先将中缀表达式转换为后缀表达式，比如a+b*c+d要变成abc*+d+: 2、转换的方法用栈来实现，涉及到运算符的优先级： 3、然后用另一个栈来对表达式计算结果。 主要仪器设备：计算机 实验项目四：Huffman编码 实验内容及教学要求： 1、根据给定一串字符（或一个文本文件），自动生成n个权值(1,2，m)构成n棵二叉 树的集合=T1,T2,Tm,其中每棵二叉树Ti中只有一个带树为Ti的根结点： 2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点 的权值为其左右子树权值之和： 3、在F中刑除这两棵树，同时将新得到的二叉树加入F中： 4、重复2,3，直到F只含一棵树为止

2 7 二叉排序树 2 验证 1 必做 8 希尔排序 2 验证 1 选做 9 快速排序 2 验证 1 必做 10 堆排序 2 验证 1 选做 三、实验内容及教学要求 以“实验项目”为单位说明每个实验的主要内容，重点和难点，并按“了解”、“理解”、“掌 握”三个层次说明每个实验项目的教学要求和所需主要仪器设备。具体格式如下： 实验项目一：顺序表的表示与实现 实验内容及教学要求： 1、顺序表的表示 ； 2、顺序表的初始化、插入、删除、查找等操作。 主要仪器设备：计算机 实验项目二：链表的表示与实现 实验内容及教学要求： 1、链表的表示 ； 2、链表的初始化、插入、删除、查找等操作。 主要仪器设备：计算机 实验项目三：表达式计算 实验内容及教学要求： 1、先将中缀表达式转换为后缀表达式，比如 a+b*c+d 要变成 abc*+d+ ； 2、转换的方法用栈来实现，涉及到运算符的优先级； 3、然后用另一个栈来对表达式计算结果。 主要仪器设备：计算机 实验项目四：Huffman 编码 实验内容及教学要求： 1、根据给定一串字符（或一个文本文件），自动生成 n 个权值(w1, w2,.,wn)构成 n 棵二叉 树的集合 F={T1, T2,.,Tn}，其中每棵二叉树 Ti 中只有一个带树为 Ti 的根结点； 2、在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点 的权值为其左右子树权值之和； 3、在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中； 4、重复 2, 3，直到 F 只含一棵树为止

主要仪器设备：计算机 实验项目五：关键路径 实验内容及教学要求： 1、根据输入的弧，生成AOE-网。从始点开始，找出到终点的多条路径，求这些路径上的关 键活动： 2、由关键活动组成的从始点到终点的路径，即为关键路径。 主要仪器设备：计算机 实验项目六：最短路经 实验内容及教学要求： 1、给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值），求从指定路由 器（始点v0)开始： 2、到其它各路由器（其余各顶点）的最短路径，直到所有路由器（顶点）计算完成为止。 主要仪器设备：计算机 实验项目七：二叉排序树 实验内容及教学要求： 1、给定一个记录关健字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左 子树查找： 2、如果大于根结点的值，则向右子树查找。如果查找到叶子结点1a,仍没有找到记录， 则：如果关键字的值小于leaf的值，则插入该1leaf结点的左边，做leaf的左孩子，否则做leaf 的右孩子。 主要仪器设备：计算机 实验项目八：希尔排序 实验内容及教学要求： 1、先将整个待排记录序列分割成为若干子序列分别进行直接插入排序： 2、待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 主要仪器设备：计算机

3 主要仪器设备：计算机 实验项目五：关键路径 实验内容及教学要求： 1、根据输入的弧，生成 AOE-网。从始点开始，找出到终点的多条路径，求这些路径上的关 键活动； 2、由关键活动组成的从始点到终点的路径，即为关键路径。 主要仪器设备：计算机 实验项目六：最短路经 实验内容及教学要求： 1、给定若干个路由器（顶点）及各路由器之间的代价值（顶点之间的权值），求从指定路由 器（始点 v0）开始； 2、到其它各路由器（其余各顶点）的最短路径，直到所有路由器（顶点）计算完成为止。 主要仪器设备：计算机 实验项目七：二叉排序树 实验内容及教学要求： 1、给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左 子树查找； 2、如果大于根结点的值，则向右子树查找。如果查找到叶子结点 leaf，仍没有找到记录， 则：如果关键字的值小于 leaf 的值，则插入该 leaf 结点的左边，做 leaf 的左孩子，否则做 leaf 的右孩子。 主要仪器设备：计算机 实验项目八：希尔排序 实验内容及教学要求： 1、先将整个待排记录序列分割成为若干子序列分别进行直接插入排序； 2、待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 主要仪器设备：计算机

实验项目九：快速排序 实验内容及教学要求： 1、通过一趟将待排记录分制成独立的两个部分，其中一部分记录的关键字均比另一部分记录 的关键字小： 2、再对两个部分分别进行快速排序。 主要仪器设备：计算机 实验项目十：堆排序 实验内容及教学要求： 1、首先将一个无序序列建成一个堆： 2、然后输出堆项元素：在输出堆顶元素之后，调整剩余的元素成为一个新堆。 主要仪器设备：计算机 四、考核方式及要求 1、设计型实验 考核方式：现场检查与实验报告 评分方法：(1)、实验态度20分，(2)、实验设计40分，(3)、实验结果40分 2、验证型实验 考核方式：实验报告与现场检查 评分方法：(1以、实验态度20分，(2)、实验结果80分 实验总成绩=工各单项实验项目成绩（实验报告）/实验项目数，（教师可根据学生完成实 验的具体情况，对结果做适度调整) 五、教材及教学主要参考书 [】《数据结构》，严蔚敏吴伟民编著，清华大学出版社 [②】《数据结构题集》严蔚敏吴伟民米宁编著，清华大学出版社 六、教改说明和其他

4 实验项目九：快速排序 实验内容及教学要求： 1、通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录 的关键字小； 2、再对两个部分分别进行快速排序。 主要仪器设备：计算机 实验项目十：堆排序 实验内容及教学要求： 1、首先将一个无序序列建成一个堆； 2、然后输出堆顶元素；在输出堆顶元素之后，调整剩余的元素成为一个新堆。 主要仪器设备：计算机 四、考核方式及要求 1、设计型实验 考核方式：现场检查与实验报告 评分方法：⑴、实验态度 20 分，⑵、实验设计 40 分，⑶、实验结果 40 分 2、验证型实验 考核方式：实验报告与现场检查 评分方法：⑴、实验态度 20 分，⑵、实验结果 80 分 实验总成绩 = ∑各单项实验项目成绩（实验报告）/ 实验项目数， （教师可根据学生完成实 验的具体情况，对结果做适度调整） 五、教材及教学主要参考书 [1] 《数据结构》，严蔚敏 吴伟民 编著，清华大学出版社 [2] 《数据结构题集》严蔚敏 吴伟民 米宁 编著，清华大学出版社 六、教改说明和其他