《数据结构》课程设计

一． 图的同构问题

给定两个有限                           和                         ，如果在结点集合之间存在一个双射，

，使得下列结论成立： 当且仅   ，则称两图同构。 判断两图是否同构在计算理论中是一个有趣的问题。迄今为止，找不到一个多项式时间的算法来实现同构判断，也不知道是不是 NP 完全问题。人们已经解决了其中的一小部分特例， 比如数的同构（我们在实验中实现过有根二叉树的同构判断）。请大家查找、阅读、理解文献中对于这个问题的研究成果，撰写一份研究报告。在研究报告中需要包括，但不限于以下内容：问题描述、当前研究的成果、典型算法、算法实现与测试、潜在应用、研究结论。研究报告篇幅应在 5000 字左右。

二． 序列对齐算法

核苷酸序列是指 DNA 或 RNA 中碱基的排列顺序。由 A、T、C、G 四种字符组成的核苷酸序列本质上是生物分子的一种符号表示。序列对齐（sequence alignment）的目的是通过两个或多个核酸序列或蛋白质序列进行对齐，并将其中相似的结构区域突出显示。通过比较未知序  列与已知序列（尤其是功能和结构已知的序列）之间的同源性，往往可以很容易地预测未知  序列的功能。研究者在序列对齐问题中已经取得了很多有效的成果，例如使用动态规划算法  来实现两两对齐问题的求解，或者是使用 BLAST 软件来完成大规模对齐问题的求解。在互联网上，也很容易找到开放的数据集来实现算法的测试。请大家查找、阅读、理解文献中对于  这个问题的研究成果，撰写一份研究报告。在研究报告中需要包括，但不限于以下内容：问  题描述、当前研究的成果、典型算法、算法实现与测试、性能评价、研究结论。研究报告篇  幅应在 5000 字左右。

三． 数独游戏

在数独游戏中，玩家需要根据大小为 9×9 的盘面上的已知数字，推理出所有剩余空格的数

字，并满足每一行、每一列、每一个 3×3 宫内的数字均含 1-9 且不重复。请大家设计并实现一个基本的数独游戏。功能包括根据用户选择的级别给出初始盘面的数字（级别越低，数字越多）；允许用户在空白格中填写数字，并且能实时监测并提示冲突；当用户完成之后，保存最近十次的成绩（完成一次所需时间）以及最好成绩。实现上述功能并测试通过后，撰  写一份文档。在文档中需要包括，但不限于以下内容：问题描述、算法设计、软件架构、实   现与测试、性能评价、总结。文档篇幅应在 5000 字左右。