算法与数据结构实验指导书

《算法与数据结构实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》编程作业指导书课程教学大纲一、课程基本信息1、课程代码：EI3722、课程名称（中/英文）：算法与数据结构AlgorithmsandDataStructures3、学时/学分：54/34、先修课程：程序设计、微机原理5、面向对象：生物医学工程专业学生、电子信息类学科学生6、开课院（系）、教研室：生命科学技术学院生物医学工程系7、教材、教学参考书：《算法与数据结构》（讲义）,钱晓平、程国英编,2004《算法与数据结构》,傅清祥、王晓东，电子工业出版社，1999《DataStructuresandAlgorithmAnalysis

2、》,CliffordA.Shaffer，张铭、刘晓丹译，电子工业出版社，1998二、课程性质和任务本课程为计算机软件基础理论与基本技术课。本课程贯彻《计算机学科教学计划1993》，把算法与数据结构融合在一起,消除冗余内容,注重实践,注重知识与技术的更新,讲究思想方法,剔除计算机专业性过强的内容,强调应用。课堂教学54学时。算法与数据结构是计算机理论与软硬件开发应用的基础，是计算机学科的公共科目之一。主要为非计算机专业的电子类学生开设。通过本课程的学习，要求学生掌握基本的数据结构、计算复杂性的基本理论和方法和非数值算法的设计与分析。主要讲解内容为

3、:三类基本数据结构表、树、图的构造与操作;常用非数值算法的设计与分析;排序与查找;NP完全问题等。三、教学内容和基本要求第一章引论（6）1.算法、数据结构、抽象数据类型的定义、关系、描述（2）2.软件设计方法的发展及其对算法与数据结构的影响,介绍软件设计方法的演变及对算法和数据结构的影响。（2）3.计算复杂性：空间复杂性与时间复杂性的概念，复杂程度的分阶，计算模型，复杂性的一般估算。（2）要求：掌握算法与数据结构的定义、抽象数据类型的定义与面向电信的实现方法，理解计算模型，掌握计算复杂性的概念、分阶及一般的估计方法。第二章线性表（10）1.数组

4、的逻辑结构和物理结构、线性表的定义及其顺序分配与链接分配。（2）2.栈的定义、功能与实现。（2）3.递归的定义、设计，一般递归算法的复杂性估算，递归的消除。（2）4.队列的定义、功能与实现。5.压缩存储、索引存储和散列存储:三元组与十字链表、各种索引、散列函数及散列冲突分析。（2）6.字符串的处理，模式匹配。（2）要求：掌握线性表按顺序分配和链接分配的定义及方法、栈和队列的定义和方法、递归思想及递归算法的设计与复杂性估算，理解压缩存储及索引存储的实现，着重分析散列存储的冲突；理解字符串的处理及模式匹配的各种算法。第三章树（8）1.树的基本概念、

5、二叉树的定义及其遍历（2）2.二叉树的检索与平衡（2）3.优化检索树,Huffman树及编码，排序检索树。（2）4.树在集合运算中的应用、判定树与对策树（2）要求：掌握一般树与二叉树的定义、遍历及转换，理解二叉树的平衡及优化检索，着重学习Huffman树及编码；掌握不相交集合的查找与合并，了解判定树与对策树的应用。第四章图（6）1.图的术语与表示法、图的遍历、连通分支和生成树（2）2.最短路径,Dijkstra算法（2）3.拓扑排序与关键路径（2）要求：掌握图的定义、遍历及最小生成树、最短路径的Dijkstra算法、拓扑排序与关键路径算法。第五

6、章排序与查找（6）1.内排序：插入排序、选择排序、交换排序、Shell排序、堆排序、快速排序、合并排序、基数排序（3）2.外排序：磁盘排序、磁带排序（1）3.查找：线形查找，包括二分查找、Fibonacci查找、插值查找、索引块查找；树查找，包括二叉树查找、B树查找(2)要求：掌握内排序的各种简单排序算法和高级排序算法，了解外排序的耗费因素、磁盘排序与磁带排序中的败方树及广义Fibonacci级数的应用。掌握各种基本查找算法，了解B树的实际应用。第六章算法设计技术（12）1.分治与平衡：实例比较、整数乘法、矩阵乘法、顺序统计（2）2.动态规划：

7、最优化原理、最短路径、矩阵相乘的动态规划、旅行商问题的动态规划解法（2）3.贪心法：背包问题、用启发式算法求解旅行商问题（2）4.回溯法：一般性描述、高斯皇后问题、子集和数问题、图的可着色问题0/1背包问题（2）5.分支限界法：LC-搜索、限界、效率分析、0/1背包问题的分支限界算法、旅行商问题的分支限界算法（2）6.局部搜索法：旅行商问题的局部搜索、组件布局（2）要求：在算法设计中贯彻分治与平衡的思想，以旅行商问题的求解为主线，掌握动态规划、贪心法、回溯法、分支限界法纪局部搜索法。第七章NP完全问题（6）1.确定型图林机与非确定型图林机模型的

8、定义（2）2.P类与NP类问题、COOK定理（2）3.NP完全性的证明方法、NP完全问题的近似算法（2）要求：通过对确定型图林机与非确定型图林机模型的