提高应用——算法与数据结构实验指导书

《提高应用——算法与数据结构实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法与数据结构实验指导书目录实验要求3试验一、约瑟夫环4试验二、长整数四则运算运算4实验三、八皇后5实验四、骑士遍历5实验五、桌而计算器6实验六、平衡排序二叉树6试验七、多重集合的实现7试验八、图论8实验八、内部排序性能的比较8教材及主要参考文献9北京邮电大学计算机科学•技术学院算法与数据结构实验指导书实验耍求一、木课程在讲课期间需要做上机实验，H的之一是检杳学生对所学算法的掌握和理解程度；其次是锻炼学生的团队合作精神。二、成绩：1、编码：占整个实验成绩的50%；2、测试：占整个实验成绩的20%；3、文档：占整个实验成绩的30%o

2、三、按时提交上机文档，实验文档包含以下各项：1、问题描述：实验题口、内容和要求；2、算法思路：实验小组对问题的解决方法的文字描述；3、算法描述：用类算法语言等对算法进行描述；4、源程序及驱动程序：上机实验编制的代码源程序及程序运行环境；5、测试数据：对算法的测试用例；6、结果分析和结论：对算法及测试结果的分析及结论；7、心得体会：通过实验获得的心得体会；8、分工及签名：最后是小组成员的分工及签名。北京邮电人学计算机科学与技术学院・1■算法与数据结构实验指导书实验一、约瑟夫环一、实验类别：设计型实验。二、问题描述：约瑟夫环问题是：n

3、个人po,pi,...pn围坐成一个圆环。每个人pk持有一个秘密的数字Ck。0

4、和非循环线性表、动态链表和静态链表以及向量（数组）之间选择三种。从空表开始，为每个人生成一个随机数。然后将此人加入到线性表之中。九、可研究与探索的问题：给出各种实现的优缺点比较。十、验收及实验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。给出各种线性表实现的优缺点分析。实验二、长整数四则运算一、实验类别：验证实验。二、问题描述：计算机CPU木身可以做32位或者64位的整数四则运算。木试验要求对任意大小的整数实现其四则运算。将一个整数N表示为N=±（d0+d1*B+d2*B?+....+bk*

5、Bk）其中1

6、译通过并且正确运行。给出试验报告。能够得出用向量（数组）实现的线性表速度最快。实验三、八皇后问题一、实验类别：设计型实验。二、问题描述：在n*n的国际象棋棋盘上放置n个皇后，使每个皇后不受其他皇后的攻击。三、实验目的：检杳学生对堆栈和递归程序掌握程度。四、实验学时：2小时五、实验组人数：1人。六、实验设备环境：计算机。七、实验原理及要点（知识点）：递归程序与堆栈八、实验内容和要求：分别用递归和堆栈完成此试验。统计程序运行时间与问题规模n的关系。九、可研究与探索的问题：问题的复杂度。当n比较大时，讨论捉高程序运行的方法。十、验收及实

7、验报告要求：现场操作及运行效果验收。要求程序必须上机编译通过并且正确运行。给出试验报告。找出程序运行速度的瓶颈。实验四、骑士遍历一、实验类别：设计型实验。二、问题描述：在国际象棋的棋盘中，一匹马从棋盘中任意一格Hl发，要求用步走完所有的I?个格子。每个格子走且只走过一次。应如何走？试给出算法实现。三、实验目的：检查学生对堆栈与冋溯算法的掌握。四、实验学时：2小时五、实验组人数：3人。六、实验设备环境：计算机。七、实验原理及要点（知识点）：堆栈与回溯八、实验内容和要求：用堆栈完成此试验。统计程序运行时间与问题规模n的关系。九、可研究

8、与探索的问题：怎样枚举所有马下一步对走的位置。选择下一步所走位置的策略。注意由于这个程序非常耗时，在初期程序调试时应取较小的n。十、验收及实验报告要求：现场操作及运行效杲验收。要求程序必须上机编译通过并冃正确运行。给岀试验报告。找出程序运行速度的瓶