图5 遗传算法基本结构
其中P(t)为t 时刻的父代，而P''(t)为t 时刻的子代。对于计算机问题而言，一般要将问题的解进行编码，编码成二进制字符串，杂交和变异就在这些字符串上进行。遗传算法可以很好解决很多的优化问题。 (2) 课程设计目的 体会遗传算法思想，能够设计并编写遗传算法的相关操作函数，并能够应用遗传算法求解具体问题。 (3) 基本要求
① 编写遗传算法的基本操作函数，包括选择，变异，交叉等。 ② 应用遗传算法实现求解如下函数的极值 f(x)=x*sin(10*π*x)+1.0 x∈[-1,2] ③ 结果精度要求在小数点后六位。 ④ 给出算法效率分析的实验结果。 (4) 实现提示
根据精度要求确定个体的二进制编码位数，同时要确定该编码和[-1,2]间数的换算规则，由于是求最大值的问题，所以适应度函数就可选为f(x)，值越大的个体适应度越好。关于交叉和变异的方法参阅相关资料。
7. 蚁群算法在旅行商问题中的应用 (1) 问题描述
蚁群算法是在对真实蚂蚁的观测基础上提出的，单个蚂蚁是不具智能的，但生活在一起的蚁群却总是能够在蚁穴和食物间找到一条几乎是最短的路径。这就要靠蚁群的智能，蚁群算法就基于这一智能。下面的图例给出蚁群智能的基本思想。
蚂蚁会在自己走过的路径上留下生化信息素，同时它也会选择地面上信息素较多的路径行走。对于下图的第二种情况，因为路上有了障碍物，所以蚂蚁需要绕过障碍物，该咋么样绕过障碍物，由于没有信息素作为指导，所以起先只能是随机的选择从左或从右走（第三个图所示）；但是随着行走次数的增加，较短的路径上留下的信息素就会较多，就有更多的蚂蚁
5
行走，信息素进一步增多，最终较短的路就成为了选择的路（第四个图）。这就是蚁群智能的基本原理。
图6 蚁群算法的基本思想
蚁群算法就是应用蚁群智能实现的算法，可以用它来实现在解空间上进行最优解的搜索，很多计算机问题可以转化为搜索最优解的问题。如旅行商问题（求解遍历全部城市的最短路经），就可用蚁群算法求解，在旅行商问题中，蚁穴到食物就对应遍历全部城市，蚂蚁就对应旅行商。
(2) 课程设计目的
了解蚁群算法的思想，并能应用蚁群算法求解具体问题。 (3) 基本要求
① 应用蚁群算法求解TSP 问题。
② TSP 中的城市数量不少于30 个，组成完全图，边上的权值自定。 ③ 蚂蚁数量可配置，迭代次数可配置。
④ 给出较全面的实验结果：结果路经及长度；蚁群算法执行时间；不同参数值（蚂蚁数量，迭代次数）的影响等。
⑤ 迭代过程需要用图形界面表示(可用C 的图形库)。
8. 汽车租借公司的管理 (1) 问题描述
设计数据结构及算法完成某个汽车租借公司日常工作的组织与管理。该管理系统的基本管理对象为汽车，每台汽车用一个license number 进行唯一标识。每个汽车存在三种可能状态： ·可以租借（available for rent） ·已借（rented）
·修理中（in repair）
其中在available 队列中汽车应该依据汽车行驶过的路程进行排序，行驶路程最少的汽车排在最前面。在rented 队列中的汽车应依据其预期返回时间进行排序，排在最前的应是预期最早返回的汽车。 (2) 课程设计目的
应用线性数据结构存储信息，并能够应用上面的基本操作实现事务管理。 (3) 基本要求
① 用三个链表组织三种状态的汽车。
6
② 能够实现租借的日常事务：引入新车，租借，收费，修理等。
③ 租借收费应根据汽车行驶的路程及借去的时间综合计算得出，路程收费标准如下：
1. 低于100Km 收费20.00 元
2. 100Km 以外的路程枚Km 收费0.15 元
④ 汽车根据行驶的路程定期进行维护。
⑤ 还需实现辅助操作：汽车查询，打印全部信息，计算并打印收入、成本及收益。 ⑥ 管理系统应有完整地界面（最好是图形化界面）。 (4) 实现提示
主要集中在链表的基本操作上。
9. 学生成绩管理系统 (1) 问题描述
设计数据结构完成一个学院学生相关信息的存储，并在此基础上编写算法实现学生成绩管理。
(2) 课程设计目的
应用线性数据结构存储信息，并能够合理的应用排序及查找算法，学会应用散列法。 (3) 基本要求
① 一个学院由若干个班组成；所有学生修相同的考试课和考查课。
② 管理系统能够实现：学生加入，学生毕业，学生成绩统计，学生查询，学生排名等管理操作。（要考虑考试课和考查课的比重关系）
③ 为方便查找，要求针对学生姓名进行散列法查找。 ④ 管理系统应有完整地界面（最好是图形化界面）。 (4) 实现提示
主要集中在散列函数的构造和冲突的解决上。
10. 迷宫的生成与路由 (1) 问题描述
设计算法生成一个N×M(N 行M 列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。 (2) 课程设计目的
理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。 (3) 基本要求
① N 和M 是用户可配置的，缺省值为50 和50。
② 迷宫的入口和出口分别在第0 行和第N-1 行上，随机选择。 ③ 生成的迷宫要求是连通的。
④ 实现图形化界面(可用VC++，也可用C 语言的图形库)。
⑤ 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。 (4) 实现提示
多考虑栈上的运算。
11．文档集合上的查询 (1) 问题描述
设计数据结构完成在一个文档集合的存储，并构造算法实现其内容的查询。该设计包括三个部分：
7
(一)应用数据结构完成文档集合的内容(基于单词的)存储，并为下一步的查询建立索引。 (二)就单个单词的查询请求，设计算法进行查询。
(三)对多个单词通过AND 和OR 构造的复杂查询进行处理(此处可只做两个单词的情况)。 具体情形如下面的例子：
Example
Doc1: I like the class on data structures and algorithms. Doc2: I hate the class on data structures and algorithms.
Doc3: Interesting statistical data may result from this survey. Here are the answers to some queries: Query 1: data Doc1, Doc2, Doc3
Query2: data AND structures Doc1, Doc2
Query 3: like OR survey Doc1, Doc3
图15 文档集合上的查询实例
(2) 课程设计目的
用线性结构组织信息，查找算法的选择与应用。 (3) 基本要求
① 文档集合中的文档数不能少于20 个。
② 数据结构的设计以及查找算法的构造应考虑如何最大程度的提高查询效率。 ③ 查询效率的提高应是综合多种查询的，而不是只针对一种查询的优化。 ④ 给出查询效率的模拟实验数据。 (4) 实现提示
AND 和OR 查询可转变为单个单词查询结果的组合。
12. 模拟文件目录系统 (1) 问题描述
本设计需完成两部分工作：一个是定义并实现一称为CatalogTree 的ADT，用它来表达字符串集合组成的有序树；另一个是一个Shell 的应用程序，用它来模拟文件目录系统，并提供模拟操作界面。CatalogTree 的组织结构如下图(带父结点指针的儿子—兄弟链树)：
图7 CatalogTree 的结构示意图
8