2013级经典算法与程序设计题目列表

经典算法与程序设计安排1.各题目要求讲解2.题目选择3.开题4.过程检查5.答辩1.每个题目每个同学独自完成。2.完成后才用答辩的形式，对自己所做系统的功能、特色讲解，并能正确对老师指定的代码做出解释。同一个题目的同学，在同一时段答辩，以检查是否有相似性，以及就水平不同进行比较。3.每个题目的难易不同，对应的成绩会不同；每个题目所做的功能及质量的不同，会打出不同的成绩。4.每个功能的核心算法必须自己实现，可以调用一些必要的基本函数。5.最后提交作品代码、报告电子版。同时报告打印一份上交（主要是流程图与心得，代码不打印）。综合设计要求题目分类•一类题目（65分）（最多8人可选择）(未交作业的同学必选)一元多项式的各种运算•二类题目（70分）(每题目2人)（适合基础一般的同学选）1.离散事件模拟2.建立索引词表3.所有矩阵的压缩存储实现4.实现所有的静态查找表题目分类•三类题目（85分）(每题目4人)（适合基础较好的同学选）1.迷宫求解2.计算器的实现3.记事本之文本编辑的实现4.二叉树遍历算法5.给定一图，求其拓朴排序6.实现经典的哈希函数构造法和解决冲突法7.实现经典的排序方法题目分类•四类题目（90分）(每题目4人)（适合能力较强的同学选）1.树的遍历和树的计数2.对一西文文本提供最优的编、解码方案，并给出编码与解码结果3.给定一图，在遍历的基础上确定其是否是连通4.给定一图，用普里姆算法求其最小生成树5.给定一图，在其拓朴排序的基础上，求关键路径题目分类•五类题目（95分）(每题目3人)（适合自学能力较强的同学选）1.给定一图，用克鲁斯卡尔算法求其最小生成树2.实现二叉排序树与与二叉平衡树得动态查找表3.实现B+树4.实现B-树5.实现键树题目分类•六类题目（最多5人可选择）题目自拟，经老师审核。分数由作品难度、工作量及质量由答辩老师决定。游戏中要考虑的因素:可以实现二维游戏,也可以是三维游戏。二维游戏要求考虑:碰撞检测\加截场景\声音加载\文件保存与加载\鼠标拾取与操作\地图之生成。三维游戏要求考虑:碰撞检测\骨骼动画之实现\灵活摄像机设置\粒子系统之实现\地形生成\天空生成\动态流体之模拟\场景之渲染\输入之交互处理。关于游戏类题目的要求（媒体专业可选，其它专业不可选）1.实体的描述:根据提供的数据,能显示该实体,并对实体进行裁剪等功能。（人数不限）该设计内容主要涉及到面、线、点的表示，主要用线性表链式存储方面的知识，会采用多级链表，因此要比书中相应的知识的复杂很多。该题目出自教图形图像方面的老师，题目所涉及的内容会在大三、大四或毕业设计时使用。建议能力强的同学，选择此题目。2.飞机游戏的实现（2人）该游戏的基本要求：飞机能飞，有声音，鼠标与键盘控制灵活、合理，能发射子弹，碰雷爆炸。3.精灵动画之实现（2人）。4.游戏中部分主要功能之模拟，如寻路功能、地图之生成之模拟。（2人）游戏可以设计的简单，也可以复杂，这取决于你个人的能力，但界面一定要美观，操作方便。5.一元多项式的各种运算除了考虑书中已提供的加法功能外，可以实现更多的运算。该算法主要涉及线性表的链式操作，是数据结构中最基本，也是日后应用最常用的操作，也是后续课程认为学生在这方面编程能力最差的一部分知识。没有达到基本要求的同学只能选择此题目，因为这是最基本的知识，必须掌握。非游戏类题目的要求6.自拟题目交由老师审查通过后，允许选择自拟。7.迷宫求解。主要利用栈实现，要求静态迷宫能准确找到路径，且能动态生成迷宫，显示所有路径。用图形界面显示所找到的路径。8.离散事件模拟。主要利用队列实现。要求能用图形界面显示模拟的整个过程。9.计算器的实现。主要利用栈实现表达式求值，要求功能与界面模拟WINDOWS计算器，可支持鼠标。10.记事本之文本编辑的实现。要求功能与界面模拟WINDOWS记事本（或TC编辑器）。因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，并可保存为文件。11.建立索引词表。主要利用串的知识实现。12.所有矩阵的压缩存储实现。包括特殊矩阵与稀疏矩阵的压缩存储，并在上面实现一定的应用，比如显示与转置等。涉及数学知识较多，对算法本身的练习并不强。13.二叉树遍历算法。要求实现前、中、后序、层序遍历的递归与非递归算法，及存储加索引的算法和在索引上的遍历算法。要求动画演示遍历过程。14.树的遍历和树的计数。要求动画演示遍历过程。15.对一西文文本提供最优的编、解码方案，并给出编码与解码结果。建议已掌握并实现线性表操作的同学，但编程能力仍不算高的同学可选择此题目，毕竟书中已提供了主要源码，自己可发挥的余地较小。16.给定一图，在遍历的基础上确定其是否是连通。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。书中虽然有源码，但离实现有一些距离，加上老师没有讲解，考验分析代码之能力。用图形界面把连通部分标识出来。17.给定一图，用普里姆算法求其最小生成树，用动画演示生成过程。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。书中提到的一个方法有源码，关于算法的讲解也很详细；另一个方法只有思想，完全没有代码，实现它考验有算法的基础上，如何表示与实现算法之能力。18.给定一图，求其拓朴排序。要求存储采用邻接矩阵与邻接链表两种方法，其入度为零的点可以采用进栈和进队列两种方法。尤其是书中未提到的方法必须实现。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。要求以图形界面呈现拓朴排序过程，并比较不同方式的优劣。19.给定一图，在其拓朴排序的基础上，求关键路径。该算法虽然较复杂，涉及到的知识也比较多，但书中毕竟有源码，而且讲解也较为详细。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。要求以图形界面呈现关键路径。20.给定一图，求任意两点间的最短路径。该算法有一定的复杂性，老师的讲解尽管不详细，但书中毕竟有源码。建议已掌握并实现线性表操作、编程有一定能力的同学，选此题目。要求以图形界面呈现过程及结果。21.实现所有的静态查找表。该部分算法较好理解，不太复杂，已掌握并实现线性表操作的同学，可选此题目。要求最后关于各种静态查找表的性能比较得出一个结论。22.实现二叉排序树与与二叉平衡树得动态查找表。该部分算法有一定的难度，涉及树的插入与删除等复杂操作。实现不易，尽管书中给出的代码较为详细。要求平衡后是否提高性能做出说明。建议能力强的同学选择此题目。23.实现B+树。书中算法只有思想，没有代码，实现不易。已掌握并实现线性表操作的同学，可选此题目。24.实现B-树。书中算法只有思想，没有代码，实现不易。已掌握并实现线性表操作的同学，可选此题目。25.实现键树。书中算法只有思想，没有代码，实现不易。已掌握并实现线性表操作的同学，可选此题目。26.实现所有的哈希函数构造法和解决冲突法。书中算法只有思想，没有代码，实现不易。已掌握并实现线性表操作的同学，可选此题目。要求所有各方法做出一个性能对比及说明。27.实现所有的排序方法。书中大多数算法有代码，讲解较为详细。有一些算法有难度。已掌握并实现线性表操作的同学，可选此题目。也许不能实现全部的算法，可以实现部分算法（会相应减分），但一定要实现几个有难度的算法，不要只实现几个简单的算法。这样编程能力没有显著的提高。要求所有各方法做出一个性能对比及说明。