《算法与数据结构实验指导书》由会员分享，可在线阅读，更多相关《算法与数据结构实验指导书（8页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构编程作业指导书课程教学大纲一、课程基本信息1、课程代码：EI372 2、课程名称（中/英文）：算法与数据结构Algorithms and Data Structures3、学时/学分：54/34、先修课程：程序设计、微机原理5、面向对象：生物医学工程专业学生、电子信息类学科学生6、开课院（系）、教研室：生命科学技术学院生物医学工程系7、教材、教学参考书：算法与数据结构（讲义）,钱晓平、程国英编,2004算法与数据结构,傅清祥、王晓东，电子工业出版社，1999Data Structures and Algorithm Analysis,Clifford A.Shaffer，张铭、刘
2、晓丹译，电子工业出版社，1998二、课程性质和任务本课程为计算机软件基础理论与基本技术课。本课程贯彻计算机学科教学计划1993，把算法与数据结构融合在一起, 消除冗余内容, 注重实践, 注重知识与技术的更新,讲究思想方法, 剔除计算机专业性过强的内容, 强调应用。课堂教学54学时。算法与数据结构是计算机理论与软硬件开发应用的基础，是计算机学科的公共科目之一。主要为非计算机专业的电子类学生开设。通过本课程的学习，要求学生掌握基本的数据结构、计算复杂性的基本理论和方法和非数值算法的设计与分析。主要讲解内容为: 三类基本数据结构表、树、图的构造与操作; 常用非数值算法的设计与分析;排序与查找; NP
3、完全问题等。 三、教学内容和基本要求第一章 引论（6）1.算法、数据结构、抽象数据类型的定义、关系、描述（2）2.软件设计方法的发展及其对算法与数据结构的影响,介绍软件设计方法的演变及对算法和数据结构的影响。（2）3.计算复杂性：空间复杂性与时间复杂性的概念，复杂程度的分阶，计算模型，复杂性的一般估算。（2）要求：掌握算法与数据结构的定义、抽象数据类型的定义与面向电信的实现方法，理解计算模型，掌握计算复杂性的概念、分阶及一般的估计方法。第二章 线性表（10）1.数组的逻辑结构和物理结构、线性表的定义及其顺序分配与链接分配。（2）2.栈的定义、功能与实现。（2）3.递归的定义、设计，一般递归算法
4、的复杂性估算，递归的消除。（2）4.队列的定义、功能与实现。5.压缩存储、索引存储和散列存储:三元组与十字链表、各种索引、散列函数及散列冲突分析。（2）6.字符串的处理，模式匹配。（2）要求：掌握线性表按顺序分配和链接分配的定义及方法、栈和队列的定义和方法、递归思想及递归算法的设计与复杂性估算，理解压缩存储及索引存储的实现，着重分析散列存储的冲突；理解字符串的处理及模式匹配的各种算法。第三章 树（8）1.树的基本概念、二叉树的定义及其遍历（2）2.二叉树的检索与平衡（2）3.优化检索树,Huffman树及编码，排序检索树。（2）4.树在集合运算中的应用、判定树与对策树（2）要求：掌握一般树与二
5、叉树的定义、遍历及转换，理解二叉树的平衡及优化检索，着重学习Huffman树及编码；掌握不相交集合的查找与合并，了解判定树与对策树的应用。第四章 图（6）1.图的术语与表示法、图的遍历、连通分支和生成树（2）2.最短路径,Dijkstra算法（2）3.拓扑排序与关键路径（2）要求：掌握图的定义、遍历及最小生成树、最短路径的Dijkstra算法、拓扑排序与关键路径算法。第五章 排序与查找（6）1.内排序：插入排序、选择排序、交换排序、Shell排序、堆排序、快速排序、合并排序、基数排序（3）2.外排序：磁盘排序、磁带排序（1）3.查找：线形查找，包括二分查找、Fibonacci查找、插值查找、索
6、引块查找；树查找，包括二叉树查找、B树查找(2)要求：掌握内排序的各种简单排序算法和高级排序算法，了解外排序的耗费因素、磁盘排序与磁带排序中的败方树及广义Fibonacci级数的应用。掌握各种基本查找算法，了解B树的实际应用。第六章 算法设计技术（12）1.分治与平衡：实例比较、整数乘法、矩阵乘法、顺序统计（2）2.动态规划：最优化原理、最短路径、矩阵相乘的动态规划、旅行商问题的动态规划解法（2）3.贪心法：背包问题、用启发式算法求解旅行商问题（2）4.回溯法：一般性描述、高斯皇后问题、子集和数问题、图的可着色问题0/1背包问题（2）5.分支限界法：LC-搜索、限界、效率分析、0/1背包问题的
7、分支限界算法、旅行商问题的分支限界算法（2）6.局部搜索法：旅行商问题的局部搜索、组件布局（2）要求：在算法设计中贯彻分治与平衡的思想，以旅行商问题的求解为主线，掌握动态规划、贪心法、回溯法、分支限界法纪局部搜索法。第七章 NP完全问题（6）1.确定型图林机与非确定型图林机模型的定义（2）2.P类与NP类问题、COOK定理（2）3.NP完全性的证明方法、NP完全问题的近似算法（2）要求：通过对确定型图林机与非确定型图林机模型的学习，理解P类与NP类问题的区别、理解COOK定理的证明方法、NP完全性的证明方法，了解NP完全问题的近似算法四、实验（上机）内容和基本要求1. 用链接分配的线性表程序实
8、现多项式的加减乘除运算。要求掌握指针类数据结构的实现技术。2. 利用平衡树结构程序实现集合运算。要求掌握树结构的插入、删除、查找的基本技术。3. Huffman树及编码的程序实现。要求理解数据压缩的方法，掌握集合的处理及压缩编码的生成。4. 以Patition过程把序列分成不大于10个数据的块，再对每个块用选择排序实现排序。要求体验综合排序的思想。5. 在旅行商的动态规划算法中添加对最小代价的路径的记录。要求深入理解算法及在递归过程中局部变量的作用域。6. 程序实现跳马问题。要求：掌握回溯法解决Hamilton回路问题。7. 程序实现旅行商问题的分支限界法中的二叉树解法。要求掌握分支限界法。五
9、、对学生能力培养的要求本课程属于计算机理论与技术课程，讲究思想方法和软件开发技术。在掌握数据结构的基础上，研究复杂的非数值问题求解的算法。要求在教师引导下，学生逐步学会对NP完全问题的分析、研究和解决，直面科学发展中出现的对人类智力的挑战。同时在掌握高级程序设计语言和计算机原理的基础上，设计出效率高求解难度大的软件，以适应专业领域中对信息处理越来越高的要求。六、其它说明作业规范：1. 以合适的工具完成对算法的描述。2. 提交完整的源代码。3. 估计算法的时间和空间复杂性，如果必要，需包括证明。4. 全部以电子文档的形式在网上提交。个性化的要求：提倡可视化编程。编程实验报告格式要求一、 报告内容
10、：1. 本次编程作业的目的。2. 编程工具或开发平台。3. 课题分析。4. 算法与数据结构的设计思想。5. 算法描述。6. 算法确认。7. 算法实现（源代码）8. 算法分析。9. 测试样本和测试结果。10. 小结。11. 附录：开发文档。二、 报告格式：（按Word文档格式）1. 标题（标题1+居中）2. 子标题（标题2+居中）3. 小标题（标题3）4. 正文（宋体、五号）5. 示图：采用Word的绘图工具，或软件Visio等。6. 表格：采用Word的表格，或软件Excel等。7. 源程序：直接使用开发平台生成的源文件，在报告中注明源文件名。8. 公式：采用Word的公式编辑器，或加载Mat
11、htype。9. 在报告标题之下，写明班级、学号、姓名及提交日期。编程实验课题一、注意事项：1. 根据教学需要，教师可选择指定其中部分课题实施。2. 按软件工程的规范实施作业。编写文档。3. 实施可视化编程。4. 独立完成。5. 完成的作业打包，网上提交。二、作业：大作业一、设计程序，实现对多项式的加、减、乘、除、微分和积分的运算。要求采用链接分配的线性表表示多项式。估计各项运算的算法复杂性。大作业二、解密码。有一个国家的外交信件使用如下方法写成密码：首先颠倒所有的非元音字段的序列（包括空格和标点符号），然后再把全部信件倒着写。该国总理发出密信如下： rn.urtbae hes mevi gi
12、noreppe. pesee chaxtret a thekam 收信人编写了一个程序翻译出信件，实现这个解密程序。（提示：采用栈的操作完成字母的颠倒）大作业三、哈密尔顿回路。在nn的棋盘上，按国际象棋的走马规则，从棋盘的任何一个方格开始，让马走遍所有的方格，每个方格至少并且只准走过一次。设计求解算法。大作业四、散列存储。建立一个Hash表，接受输入为不大于1000个英文单词，采用的Hash函数是：h(FirstCharacter(WordString)=ord(FirstCharacter(WordString)-ord(a)要求用拉链法解决冲突，并对检索进行测试。大作业五、编写求解Huff
13、mann编码的程序以及解码的程序。要求以指针形成的二叉树结构实施算法。大作业六、以最左树作为对象，编写程序实现Hu和Tucker算法。大作业七、修改Dijkstra算法，使之在求出最短路径的长度外，还能把路径输出来。大作业八、编写程序实现快速排序与直接选择排序相结合的排序算法。要求对输入的序列，用Partition过程分割成每10个记录为一组的子序列，然后再对每个子序列实施直接选择排序。大作业九、完善用动态规划求解旅行商问题的程序，使之不仅能求出最短旅行路线的值，而且能输出最短旅行路线的路径。（提示：要求该完善工作在求值的同时进行，不可另行再做一次递归运算）大作业十、用分支限界法编写程序，通过
14、对二叉空间状态树的搜索求解旅行商问题。作业指导意见大作业一、设计程序，实现对多项式的加、减、乘、除、微分和积分的运算。要求采用链接分配的线性表表示多项式。估计各项运算的算法复杂性。【指导意见】本作业的用意在于指针与链接表的操作练习。每个多项式为一条链，按指数从高到低排列。相对于按顺序分配构成的多项式，具有节省系数为0的项所占用的空间的好处。编程时首先定义多项式对象，其中每个节点应包含系数、指数和指针三个字段。运算编程应先做简单的，后做复杂的。例如先完成加减运算，再完成乘除运算。而乘除运算中可直接调用加减运算子程序。显示结果可按BASIC的表达式的格式，在一行上显示多项式。形如：5x6+3x3+
15、2以表示5x6+3x3+2。大作业二、解密码。有一个国家的外交信件使用如下方法写成密码：首先颠倒所有的非元音字段的序列（包括空格和标点符号），然后再把全部信件倒着写。该国总理发出密信如下： rn.urtbae hes mevi ginoreppe. pesee chaxtret a thekam 收信人编写了一个程序翻译出信件，实现这个解密程序。（提示：采用栈的操作完成字母的颠倒）【指导意见】本作业的用意在于栈的操作，使学生明暸后进先出的特定操作有倒转的作用。可以采用两个栈，接受的明文，如果输入是非元音的字符，则逐个压入第一个栈；遇到元音字符则停止压入第一个栈；把第一个栈的内容逐个弹出，压入第二个栈；待第一个栈空，再把后继的元音字符压入第二个栈；后继字符再出现非元音的字符时，再压入逐个第一个栈，如此循序操作到全文输入完成，再从第二个栈逐个弹出字符作为输出。所使用的栈，可直接从教科书上引用。只需使用按顺序分配的栈。大作业三、哈密尔顿回路。在nn的棋盘上，按国际象棋的走马规则，从棋盘的任何一个方格开始，让马走遍所有的方格，每个方格至少并且只准走过一次。设计求解算法。【
