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

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

第一篇：算法与数据结构实验指导书北京邮电大学计算机科学与技术学院算法与数据结构实验指导书杨俊、徐塞虹、漆涛编著2006年9月算法与数据结构实验指导书目录实验要求....................................................................................................................................3试验一、约瑟夫环..............................................................................…………………..……4试验二、长整数四则运算运算………………………………………………………………4实验三、八皇后.....................................……..........................................................................5实验四、骑士遍历......................................……………………..............................................5实验五、桌面计算器...............................……………..............................................................6实验六、平衡排序二叉树....................…...…….....................................................................6试验七、多重集合的实现……......................................………………………………………7试验八、图论………………………………………………………………………….……..8实验八、内部排序性能的比较..........………………….............................................................8教材及主要参考文献………………………………………………………………………………..92北京邮电大学计算机科学与技术学院算法与数据结构实验指导书实验要求一、本课程在讲课期间需要做上机实验，目的之一是检查学生对所学算法的掌握和理解程度；其次是锻炼学生的团队合作精神。二、成绩：1、编码：占整个实验成绩的50%；2、测试：占整个实验成绩的20%；3、文档：占整个实验成绩的30%。三、按时提交上机文档，实验文档包含以下各项：1、问题描述：实验题目、内容和要求；2、算法思路：实验小组对问题的解决方法的文字描述；3、算法描述：用类算法语言等对算法进行描述；4、源程序及驱动程序：上机实验编制的代码源程序及程序运行环境；5、测试数据：对算法的测试用例；6、结果分析和结论：对算法及测试结果的分析及结论；7、心得体会：通过实验获得的心得体会；8、分工及签名：最后是小组成员的分工及签名。北京邮电大学计算机科学与技术学院-1-算法与数据结构实验指导书实验一、约瑟夫环一、实验类别：设计型实验。二、问题描述：约瑟夫环问题是：n个人p0,p1,…pn围坐成一个圆环。每个人pk持有一个秘密的数字ck。0三、实验目的：检查学生对各种线性表的实现的掌握程度。四、实验学时：2小时五、实验组人数：1人。六、实验设备环境：计算机。七、实验原理及要点（知识点）：各种队列的实现。八、实验内容和要求：至少用3种以上的线性表来完成此试验。可以在带头节点的和不带头节点的线性表、循环的和非循环线性表、动态链表和静态链表以及向量（数组）之间选择三种。从空表开始，为每个人生成一个随机数。然后将此人加入到线性表之中。九、可研究与探索的问题：给出各种实现的优缺点比较。十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出各种线性表实现的优缺点分析。实验二、长整数四则运算一、实验类别：验证实验。二、问题描述：计算机CPU本身可以做32位或者64位的整数四则运算。本试验要求对任意大小的整数实现其四则运算。将一个整数N表示为N=±(d0+d1*B+d2*B2+….+bk*Bk)其中1三、实验目的：对具体的问题选择适当的线性表实现。四、实验学时：2小时五、实验组人数：3人。六、实验设备环境：计算机。七、实验原理及要点（知识点）：各种队列的实现。八、实验内容和要求：至少用2种以上的线性表来完