第二部分 课程设计题目

一、说明

1-5题难度相对较小，6题以上难度较大，每位同学可以自己选择难度大小，在下面A、B中选择一题即可，做好后上传如下材料：程序、可执行文件、课程设计报告（pdf格式）。如果程序运行时要从键盘上输入数据的，请在屏幕上给出提示或者在readme.txt文件中说明程序的操作步骤。

A 选择难度较小的题目：请根据自己的学号计算相应的题号，不能随意选择题目，题号计算方法如下：

题号 = 学号末两位 除以5的余数 + 1 比如：

学号末两位是01，则 01除以5的余数为1，题号就是2 学号末两位是05，则 05除以5的余数为0，题号就是1 学号末两位是09，则 09除以5的余数为4，题号就是5

B 选择难度较大的题目： 则可以任意选择题6-18中的一题

二、题目

1. 长整数四则运算。

（1） 问题描述：设计一个实现任意长的整数进行加法运算的演示程序。

（2）基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)?(2^15 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 （3）测试数据：

① 0；0；应输出“0”。

② -2345,6789；-7654,3211；应输出“-1,0000,0000”。

③ -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 ④ 1,0001,0001；-1,0001,0001；应输出“0”。

⑤ 1,0001,0001；-1,0001,0000；应输出“1”。

⑥ -9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。

⑦ 1,0000,9999,9999；1；应输出“1,0001,0000,0000”。 （4）实现提示：

① 每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。

② 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。

2. 马踏棋盘

(1)基本要求：将马随机放在国际象棋的8?8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋

1

规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，?，64依次填入—个8?8的方阵，输出之。

(2)测试数据：由读者指定,可自行指定一个马的初始位置。

(3)实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。

3. 校园导游咨询

（1）基本要求：

① 设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

② 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

③ 为来访客人提供图中任意景点相关信息的查询。 （2）测试数据：由读者根据实际情况指定。

（3）实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。

4. B-Trees 的实现及分析 (1) 问题描述

B-Trees 是一类满足特殊条件的M 路查找树。首先说明M 路查找树，M 路查找树是二元查找树的一般化，其结构如下图所示的3 路查找树：M 路查找树中的任一结点至多存放M-1个数据，并至多拥有M棵子树；每个结点中的数据按升序排列V1 < V2 < ...Vk (k <= M-1)，每个数据Vi 都存在一棵左子树和一棵右子树，如果左子树不空的话，该子树中所有结点的值都小于Vi,如果右子树不空的话，该子树中所有结点的值都大于Vi。

图1 3-路查找树的结构示意图

B-Trees 是满足如下两个条件的M 路查找树： ① 所有叶结点的高度相同。

② 除根之外的所有结点都至少是半满的，即该结点包含M/2 或更多的值。 下图是一个B-树的实例。

2

图2 3-路B-树的结构示意图

(2) 课程设计目的 认识并分析B-树。 (3) 基本要求

① 实现在B-树上的查找，并分析其时间复杂性。

② 实现B-树的ADT，包括其上的基本操作：结点的加入和删除。 ③ 要求B-树结构中的M=3 或5，实现其中的一种即可。 ④ 实现基本操作的演示。 (4) 实现提示

主要考虑结点的分裂和和并。

5. AVL Tree 的实现及分析 (1) 问题描述

AVL(Adelson-Velskii and Landis)树是一株平衡的二元查找树。一株平衡的二元树就是指对其每一个结点，其左子树和右子树的高度之差不超过1。下图就是一个AVL 树的实例。

图3 AVL 树的结构示意图

(2) 课程设计目的

认识AVL Tree 数据结构。

编写程序实现AVL 树的判别；并实现AVL 树的ADT，包括其上的基本操作：结点的加入和删除。BST 和AVL 的差别就在平衡性上，所以AVL 的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。 (3) 基本要求

① 编写AVL 树判别程序，并判别一个二元查找树是否为AVL 树。二元查找树用其先序遍历结果表示，如：5，2，1，3，7，8。

3

② 实现AVL 树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为AVL 树的操作。 (4) 实现提示

主要考虑树的旋转操作。

6．遗传算法的模拟 (1) 问题描述

遗传算法是以达尔文生物进化论为基础，借鉴自然界中物种进化原理，依据优胜劣汰而达到优化的规律而创建的一种数学模型和算法，如下图所示。

图4 遗传算法的生物学背景

该图以小麦品种改良的过程为例说明遗传算法（也可称为基因算法）的基本原理：优化问题的可能解被称为是个体（individuals），首先考虑可能解（个体）组成的集合，即群体

（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。将上述过程形式化后就得到如下图所示的遗传算法结构框图：

4