算法及数据结构实验指导书.doc

《算法与数据结构》编程作业指导书 课程教学大纲 一、课程基本信息 1、课程代码：EI372 2、课程名称（中/英文）：算法与数据结构Algorithms and Data Structures 3、学时/学分：54/3 4、先修课程：程序设计、微机原理 5、面向对象：生物医学工程专业学生、电子信息类学科学生 6、开课院（系）、教研室：生命科学技术学院生物医学工程系 7、教材、教学参考书： 《算法与数据结构》（讲义）,钱晓平、程国英编,2004 《算法与数据结构》,傅清祥、王晓东，电子工业出版社，1999 《Data Structures and Algorithm Analysis》,Clifford A.Shaffer，张铭、刘晓丹译，电子工业出版社，1998 二、课程性质和任务 本课程为计算机软件基础理论与基本技术课。本课程贯彻《计算机学科教学计划1993》，把算法与数据结构融合在一起, 消除冗余内容, 注重实践, 注重知识与技术的更新,讲究思想方法, 剔除计算机专业性过强的内容, 强调应用。课堂教学54学时。 算法与数据结构是计算机理论与软硬件开发应用的基础，是计算机学科的公共科目之一。主要为非计算机专业的电子类学生开设。通过本课程的学习，要求学生掌握基本的数据结构、计算复杂性的基本理论和方法和非数值算法的设计与分析。主要讲解内容为: 三类基本数据结构表、树、图的构造与操作; 常用非数值算法的设计与分析;排序与查找; NP完全问题等。 三、教学内容和基本要求 第一章 引论（6）1.算法、数据结构、抽象数据类型的定义、关系、描述（2）2.软件设计方法的发展及其对算法与数据结构的影响,介绍软件设计方法的演变及对算法和数据结构的影响。（2）3.计算复杂性：空间复杂性与时间复杂性的概念，复杂程度的分阶，计算模型，复杂性的一般估算。（2） 要求：掌握算法与数据结构的定义、抽象数据类型的定义与面向电信的实现方法，理解计算模型，掌握计算复杂性的概念、分阶及一般的估计方法。 第二章 线性表（10）1.数组的逻辑结构和物理结构、线性表的定义及其顺序分配与链接分配。（2）2.栈的定义、功能与实现。（2）3.递归的定义、设计，一般递归算法的复杂性估算，递归的消除。（2）4.队列的定义、功能与实现。5.压缩存储、索引存储和散列存储:三元组与十字链表、各种索引、散列函数及散列冲突分析。（2）6.字符串的处理，模式匹配。（2） 要求：掌握线性表按顺序分配和链接分配的定义及方法、栈和队列的定义和方法、递归思想及递归算法的设计与复杂性估算，理解压缩存储及索引存储的实现，着重分析散列存储的冲突；理解字符串的处理及模式匹配的各种算法。 第三章 树（8）1.树的基本概念、二叉树的定义及其遍历（2）2.二叉树的检索与平衡（2）3.优化检索树,Huffman树及编码，排序检索树。（2）4.树在集合运算中的应用、判定树与对策树（2） 要求：掌握一般树与二叉树的定义、遍历及转换，理解二叉树的平衡及优化检索，着重学习Huffman树及编码；掌握不相交集合的查找与合并，了解判定树与对策树的应用。 第四章 图（6）1.图的术语与表示法、图的遍历、连通分支和生成树（2）2.最短路径,Dijkstra算法（2）3.拓扑排序与关键路径（2） 要求：掌握图的定义、遍历及最小生成树、最短路径的Dijkstra算法、拓扑排序与关键路径算法。 第五章 排序与查找（6）1.内排序：插入排序、选择排序、交换排序、Shell排序、堆排序、快速排序、合并排序、基数排序（3）2.外排序：磁盘排序、磁带排序（1）3.查找：线形查找，包括二分查找、Fibonacci查找、插值查找、索引块查找；树查找，包括二叉树查找、B树查找(2) 要求：掌握内排序的各种简单排序算法和高级排序算法，了解外排序的耗费因素、磁盘排序与磁带排序中的败方树及广义Fibonacci级数的应用。掌握各种基本查找算法，了解B树的实际应用。 第六章 算法设计技术（12）1.分治与平衡：实例比较、整数乘法、矩阵乘法、顺序统计（2）2.动态规划：最优化原理、最短路径、矩阵相乘的动态规划、旅行商问题的动态规划解法（2）3.贪心法：背包问题、用启发式算法求解旅行商问题（2）4.回溯法：一般性描述、高斯皇后问题、子集和数问题、图的可着色问题0/1背包问题（2）5.分支限界法：LC-搜索、限界、效率分析、0/1背包问题的分支限界算法、旅行商问题的分支限界算法（2）6.局部搜索法：旅行商问题的局部搜索、组件布局（2） 要求：在算法设计中贯彻分治与平衡的思想，以旅行商问题的求解为主线，掌握动态规划、贪心法、回溯法、分支限界法纪局部搜索法。 第七章 NP完全问题（6）1.确定型图林