第二部分 课程设计题目.doc

第二部分 课程设计题目一、说明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，题号就是5B 选择难度较大的题目： 则可以任意选择题6-18中的一题二、题目1. 长整数四则运算。 （1） 问题描述：设计一个实现任意长的整数进行加法运算的演示程序。 （2）基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1)(215 - 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棋盘Bord88的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部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 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。 实现AVL 树的ADT，包括其上的基本操作：结点的加入和删除；另外包括将一般二元查找树转变为AVL 树的操作。(4) 实现提示主要考虑树的旋转操作。6遗传算法的模拟(1) 问题描述遗传算法是以达尔文生物进化论为基础，借鉴自然界中物种进化原理，依据优胜劣汰而达到优化的规律而创建的一种数学模型和算法，如下图所示。图4 遗传算法的生物学背景该图以小麦品种改良的过程为例说明遗传算法（也可称为基因算法）的基本原理：优化问题的可能解被称为是个体（individuals），首先考虑可能解（个体）组成的集合，即群体（population）；然后依据环境特征（优化问题特征）评定各个体的优劣（其适应度（fitness）来定义）；对适应度较差的个体进行淘汰，选取适应度好的个体（类比生物选择），在其上进行杂交，变异等操作形成新的群体；最后再进入下一轮遗传进化，上述过程不断迭代，直到群体满足了某条件，此时出现了满足要求的优化解。将上述过程形式化后就得到如下图所示的遗传算法结构框图：图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) 问题描述蚁群算法是在对真实蚂蚁的观测基础上提出的，单个蚂蚁是不具智能的，但生活在一起的蚁群却总是能够在蚁穴和食物间找到一条几乎是最短的路径。这就要靠蚁群的智能，蚁群算法就基于这一智能。下面的图例给出蚁群智能的基本思想。蚂蚁会在自己走过的路径上留下生化信息素，同时它也会选择地面上信息素较多的路径行走。对于下图的第二种情况，因为路上有了障碍物，所以蚂蚁需要绕过障碍物，该咋么样绕过障碍物，由于没有信息素作为指导，所以起先只能是随机的选择从左或从右走（第三个图所示）；但是随着行走次数的增加，较短的路径上留下的信息素就会较多，就有更多的蚂蚁行走，信息素进一步增多，最终较短的路就成为了选择的路（第四个图）。这就是蚁群智能的基本原理。图6 蚁群算法的基本思想蚁群算法就是应用蚁群智能实现的算法，可以用它来实现在解空间上进行最优解的搜索，很多计算机问题可以转化为搜索最优解的问题。如旅行商问题（求解遍历全部城市的最短路经），就可用蚁群算法求解，在旅行商问题中，蚁穴到食物就对应遍历全部城市，蚂蚁就对应旅行商。(2) 课程设计目的了解蚁群算法的思想，并能应用蚁群算法求解具体问题。(3) 基本要求 应用蚁群算法求解TSP 问题。 TSP 中的城市数量不少于30 个，组成完全图，边上的权值自定。 蚂蚁数量可配置，迭代次数可配置。 给出较全面的实验结果：结果路经及长度；蚁群算法执行时间；不同参数值（蚂蚁数量，迭代次数）的影响等。 迭代过程需要用图形界面表示(可用C 的图形库)。8. 汽车租借公司的管理(1) 问题描述设计数据结构及算法完成某个汽车租借公司日常工作的组织与管理。该管理系统的基本管理对象为汽车，每台汽车用一个license number 进行唯一标识。每个汽车存在三种可能状态：可以租借（available for rent）已借（rented）修理中（in repair）其中在available 队列中汽车应该依据汽车行驶过的路程进行排序，行驶路程最少的汽车排在最前面。在rented 队列中的汽车应依据其预期返回时间进行排序，排在最前的应是预期最早返回的汽车。(2) 课程设计目的应用线性数据结构存储信息，并能够应用上面的基本操作实现事务管理。(3) 基本要求 用三个链表组织三种状态的汽车。 能够实现租借的日常事务：引入新车，租借，收费，修理等。 租借收费应根据汽车行驶的路程及借去的时间综合计算得出，路程收费标准如下：1. 低于100Km 收费20.00 元2. 100Km 以外的路程枚Km 收费0.15 元 汽车根据行驶的路程定期进行维护。 还需实现辅助操作：汽车查询，打印全部信息，计算并打印收入、成本及收益。 管理系统应有完整地界面（最好是图形化界面）。(4) 实现提示主要集中在链表的基本操作上。9. 学生成绩管理系统(1) 问题描述设计数据结构完成一个学院学生相关信息的存储，并在此基础上编写算法实现学生成绩管理。(2) 课程设计目的应用线性数据结构存储信息，并能够合理的应用排序及查找算法，学会应用散列法。(3) 基本要求 一个学院由若干个班组成；所有学生修相同的考试课和考查课。 管理系统能够实现：学生加入，学生毕业，学生成绩统计，学生查询，学生排名等管理操作。（要考虑考试课和考查课的比重关系） 为方便查找，要求针对学生姓名进行散列法查找。 管理系统应有完整地界面（最好是图形化界面）。(4) 实现提示主要集中在散列函数的构造和冲突的解决上。10. 迷宫的生成与路由(1) 问题描述设计算法生成一个NM(N 行M 列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。(2) 课程设计目的理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。(3) 基本要求 N 和M 是用户可配置的，缺省值为50 和50。 迷宫的入口和出口分别在第0 行和第N-1 行上，随机选择。 生成的迷宫要求是连通的。 实现图形化界面(可用VC+，也可用C 语言的图形库)。 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。(4) 实现提示多考虑栈上的运算。11文档集合上的查询(1) 问题描述设计数据结构完成在一个文档集合的存储，并构造算法实现其内容的查询。该设计包括三个部分：(一)应用数据结构完成文档集合的内容(基于单词的)存储，并为下一步的查询建立索引。(二)就单个单词的查询请求，设计算法进行查询。(三)对多个单词通过AND 和OR 构造的复杂查询进行处理(此处可只做两个单词的情况)。具体情形如下面的例子：ExampleDoc1: 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: dataDoc1, Doc2, Doc3Query2: data AND structuresDoc1, Doc2Query 3: like OR surveyDoc1, Doc3图15 文档集合上的查询实例(2) 课程设计目的用线性结构组织信息，查找算法的选择与应用。(3) 基本要求 文档集合中的文档数不能少于20 个。 数据结构的设计以及查找算法的构造应考虑如何最大程度的提高查询效率。 查询效率的提高应是综合多种查询的，而不是只针对一种查询的优化。 给出查询效率的模拟实验数据。(4) 实现提示AND 和OR 查询可转变为单个单词查询结果的组合。12. 模拟文件目录系统(1) 问题描述本设计需完成两部分工作：一个是定义并实现一称为CatalogTree 的ADT，用它来表达字符串集合组成的有序树；另一个是一个Shell 的应用程序，用它来模拟文件目录系统，并提供模拟操作界面。CatalogTree 的组织结构如下图(带父结点指针的儿子兄弟链树)：图7 CatalogTree 的结构示意图针对于目录系统，CatalogTree 的结点存放的数据内容为字符串，每个结点对应一个目录项，该目录项可以是目录，也可以是文件，如果是目录就可以再存放其它目录或文件，即非叶结点；如果是文件就是叶结点。从根结点到该结点路经所有结点的字符串用“/”进行组合后就是该目录项的绝对路径，用来唯一的标识该目录。例如：/usr/li/email/student/。目录系统具有如下基本操作：1) dir 列出当前目录下的所有目录项2) cd 打出当前目录的绝对路经3) cd .当前目录变为当前目录的父目录4) cd str当前目录变为str 所表示路径的目录5) mkdir str 在(当前目录下)创建一个子目录(名为str)6) mkfile str 在(当前目录下)创建一个文件(名为str)7) delete str 删除(当前目录下)名为str 的目录或文件(2) 课程设计目的应用树知识模拟一个目录管理系统。(3) 基本要求 描述并实现CatalogTree 的ADT，包括其上的基本操作：如插入一个结点，寻找一个结点，返回一个结点的最左儿子等（具体情况依据应用自定）。 应用CatalogTree 的ADT 实现一个完成文件目录系统的Shell 应用程序。 该Shell 是一个不断等待用户输入命令的解释程序，根据用户输入的命令完成相关操作，直到退出（quit）。命令名及其含义如上所述。 目录树结构可以保存（save）到文件中，也可从文件中读出（load *.dat）。 dir 命令的结果应能够区分是子目录和还是文件。 应对命令4)7)中的str 区分是绝对路经，还是相对路径。(4) 实现提示关键是树上基本操作的实现。13. 集合的等价划分(1) 问题描述构造集合结构的抽象数据型，并在此基础上进行集合的等价划分。(2) 课程设计目的掌握集合的表示方法，并设计等价划分算法。(3) 基本要求 选择合理的结构完成集合的表示(要求以ADT 的形式给出)。 在进行等价划分前，等价关系需用户输入(从文件输入，格式自定)。 需要验证用户输入的关系是否为等价关系。 对集合进行等价划分，且要分析该划分的时空复杂性。(4) 实现提示可用树结构来表示集合，如果能进行适当的优化并给出理由和实验分析结果将更好。14. 哈夫曼编码与译码(1) 问题描述针对一段文本(推荐为英语)，就这段文本进行相应的哈夫曼编码和译码。(2) 课程设计目的掌握哈夫曼树的构造。(3) 基本要求 完成文本的频率统计。 构造哈夫曼树。 编写编码程序和译码程序。 计算压缩率，并和任一种压缩算法(自己去找)比较(比较复杂性和压缩效果)。(4) 实现提示无。15. 小型文本编辑器的设计(1) 问题描述设计一个文本编辑器，使其具有通常编辑器(如Notepad)所应具备的基本功能。(2) 课程设计目的较大规模软件系统的设计与实现，字符串上的基本操作。(3) 基本要求 要求该编辑器在串基本抽象数据型上构建。 编辑器应具备如字符串查找，字符串替换，统计字数，统计行数等基本功能。 具备图形化界面(最好用VC+完成)。(4) 实现提示字符串抽象数据型需要为文本编辑器的实现提供足够的支持，所以在此部分需仔细分析、设计；可以行编辑器作为该编辑器的基础。16多项式链式存储结构及其代数运算(1) 问题描述设计并建立一个链式存储分配系统来表示和操作多项式。为了避免对零和非零多项式进行不同的处理，使用带头结点的循环链表。为了充分利用多项式中不再使用的结点，维护一个可用空间表avail,把不再使用的多项式的结点链入其中。当需要一个新结点时，就查看这个单链表avail。如果表非空，那么可以使用它的一个结点。只有当该表为空时，才使用动态存储分配来创建新结点。（2）设计目的掌握循环链表的存储结构及其操作；能够运用循环链表的存储结构表示多项式，并进行代数运算。(3) 基本要求设计多项式的存储结构，编写并测试下列函数：a) get_node 和ret_node，从/向可用空间表申请和插入一个多项式结点。b) pread，读取一个多项式，并将其转换成循环存储表示。返回指向该多项式的头结点的指针。c) pwrite，输出多项式，采用能够清楚显示的形式。d) padd，计算d = a+b。不改变a 和b。e) psub，计算d = a-b。不改变a 和b。f) pmult，计算d = a*b。不改变a 和b。g) eval，计算多项式在某点a 的值，其中a 是一个浮点型常量。返回结果为浮点数。h) perase，把存储表示为循环链表的多项式返还给可用空间表。（4）实现提示为了进一步简化加法算法，把多项式的头结点的指数域设为-117稀疏矩阵的完全链表表示及其运算(1) 问题描述稀疏矩阵的每个结点包含down，right，row，col 和value 五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right 域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down 链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。（2）设计目的认识和掌握稀疏矩阵的完全链表