数据结构课设选题_2

问题描述：在n×n的棋盘上放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋中的一个问题。皇后是棋盘上最具杀伤力的一个棋子，她可以捕捉与她在同一行，或同一列，或同一斜线（有两条）上的所有棋子。如下图所示，红线经过的格子都会被皇后捕捉。

要求：

（1）皇后的个数n由用户输入，其值不能超过20。 （2）采用非递归方法求解。 21．由遍历序列构造二叉树

我们知道，由先序遍历序列和中序遍历序列（或后序遍历序列和中序遍历序列）可以唯一确定一棵二叉树。请编写一个程序，实现由先序遍历序列和中序遍历序列以及由中序遍历序列和后序遍历序列构造一棵二叉树的功能，要求以括号表示法（广义表表示法）和凹入表示法输出该二叉树。 测试数据：

（1）先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列“DBJHLKMNEAFCGI”； （2）中序遍历序列“DBJHLKMNEAFCGI”和后序遍历序列“DJLNMKHEBFIGCA”；

22．分油问题

问题描述：

设有大小不等的三个无刻度的油桶，分别能盛满x、y、z升油。初始时，第一个油桶盛满油，第二、三个油桶为空。寻找一种最少步骤的分油方式，在某一个油桶上分出targ升油。 基本要求：

输入三个油桶的盛油量，要分出的油量targ，输出分油的结果。 测试数据：

三个油桶盛油量分别为：8 、5、3 要分出的油量为：4

23．实现英文单词按字典序排列的基数排序算法

试设计一个将一组英文单词按字典序排列的基数排序算法。设单词均由小写字母或空格构成，最长的单词有MaxLen个字母。

24．二元多项式乘法运算

编写一个程序，能够完成两个二元多项式的乘法运算，并能给出明确的等式形式。

25．词典变位词检索系统

在英文中，把某个单词字母的位置（顺序）加以改变所形成的新字词，英文叫做anagram，不妨译为变位词。譬如said（say的过去式）就有dais（讲台）这个变位词。在中世纪，这种文字游戏盛行于欧洲各地，当时很多人相信一种神奇的说法，认为人的姓名倒着拼所产生的意义可能跟本性和命运有某种程度的关联。所以除了消遣娱乐之外，变位词一直被很严肃地看待，很多学者穷毕生精力在创造新的变位词。本设计要求词典检索系统实现变位词的查找功能。

26．纸牌游戏——21点

“21点”是一种古老的扑克牌游戏，游戏规则是，各个参与者设法使自己的牌达到总分21而不超过这个数值。扑克牌的分值取它们的面值，A充当1分或者11分（由玩家自己确定选择一种分值），J,Q和K人头牌都是10分。

庄家对付1~7个玩家。在一局开始时，包括庄家在内的所有参与者都有两张牌。玩家可以看到他们自己的所有牌以及总分，而庄家有一张牌暂时是隐藏的。接下来，只要愿意，各个玩家都有机会依次再拿一张牌。如果某个玩家的总分超过了21（称为“引爆”），那么这个玩家就输了。在所有玩家都拿了额外的牌后，庄家将显示他隐藏的牌。只要庄家的总分等于或小于16，那么他就必须再拿牌。如果庄家引爆了，那么还没有引爆的所有玩家都将获胜。否则，将余下的各玩家的总分与庄家的总分作比较，如果玩家的总分大于庄家的总分，则玩家获胜。如果二者的总分相同，则玩家与庄家打成平局。

编写程序实现游戏，计算机作为玩家，1~7个人作为普通玩家参与游戏。

27．用二叉树实现家谱的相关运算

编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能： （1）文件操作功能：记录输入，记录输出，清除全部文件记录和将家谱记录存盘。

（2）家谱操作功能：用括号表示法和凹入表示法输出家谱二叉树，查找某人所有儿子，查找某人所有祖先。

28．猜拳游戏

在游戏中，用手表示“石头”、“剪刀”或“布”中的一个，出拳头表示石头，伸出两根手指表示剪刀，伸出五根手指表示布，孩子们面对面地数到3时做出他们的选择，如果所作选择是一样的，则表示平局，否则就按如下规则决定胜负： （1）石头砸坏剪刀；

（2）剪刀剪碎布； （3）布覆盖石头。

编程实现计算机与人游戏。

29．求复杂表达式的值

设计一个程序，计算含有如下标识符的表达式的值： （1）数值：包括整数和实数，数值可带正、负号。

（2）一般运算符：正号、负号、加、减、乘、除、求模和乘方，其中可以包括括号。 （3）单词（即运算函数）：abs、sqrt、exp、ln、log10、sin、cos和tanh。

30．关键路径算法

AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解： （1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键?

在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完 成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路 径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。 1 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。 2 调查并分析和预测这个工程计划每个阶段的时间。 3 用调查的结果建立AOE网，并用图的形式表示。

4 用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存 储到相应存储结构中。

5 用SearchMaxPath()函数求出最大路径，并打印出关键路径。 6 编写代码并调试、测试通过。

利用教材p185的图7.30（a）中的数据调试程序。

[实现提示] 实现的关键和难点在于对四个术语的理解和应用即：ei表示顶点vi所代表的事件 的最早发生时间；li表示顶点vi所代表的事件的最迟发生时间；Tes(i,j)表示活动ak的最早开 工时间；Tls(i,j)表示活动ak的最迟开工时间。活动ak为关键活动的充分必要条件是活动ak 的最早开工时间与它的最迟开工时间相等。

31．扫雷游戏

做一个N x M的扫雷游戏，每个方格包 含两种状态：关闭（closed）和打开（opened），初 始化时每个方格都是关闭的，一个打开的方格也会 包含两种状态：一个数字（clue）和一个雷 （bomb）。你可以打开（open）一个方格，如果你打开的是 一个bomb，那么就失败；否则就 会打开一个数字，该数字是位于[0，8]的一个整数，该数字表示其所有 邻居方格（neighboring squares）所包含的雷数。

1.能够打开一个方格，一个已打开的方格不能再关闭。

2.能够标记一个方格，标记方格的含义是 对该方格有雷的预测（并不表示真的一定有雷），当一 个方格标记后该方格不能被打开，只能执行取消 标记的操作，只能在取消后才能打开一个方格。 3.能够给出游戏结果（输、赢、剩余的雷数、用掉 的时间按秒计）。

32．Betsy的旅行(USACO)

题目简述：一个正方形的小镇被分成N2个小方格，Betsy要从左上角的方格到达左下角的方格，

并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目。

33．文字研究助手问题

问题描述：文字研究人员需要统计某篇英文小说中某些特定单词的出现次数和位置，试写出 一个实现这一目标的文字统计系统。这称为“文学研究助手”。 算法输入：文本文件和词集。

算法输出：单词出现的次数，出现位置所在行的行号（同一行出现两次的只输出一个行号）。 算法要点：（1）文本串非空且以文件形式存放。

（2）单词定义：用字母组成的字符序列，中间不含空格，不区分大小写。 （3）待统计的单词不跨行出现，它或者从行首开始，或者前置一个空格。

（4）数据结构采用二维链表，单词结点链接成一个链表，每个单词的行号组成一个链表，单词 结点作为行号链表的头结点。

34．任意大非负整数的任意大非负整数次方

实现任意大非负整数的任意大非负整数次方的算法

35．特殊矩阵的压缩存储算法的实现

编写一个程序，实现对称矩阵、上（下）三角矩阵、三对角矩阵的压缩存储，要求具有如下功能： （1）输入：以行序为主序输入矩阵的全部元素，压缩存储于一维数组中。 （2）输出：顺序输出压缩存储于一维数组中的矩阵元素。

（3）简单算术运算：利用压缩存储的数据实现两个特殊矩阵（属于同一类特殊矩阵）的加法 运算，并输出运算结果。

36．专家系统应用——动物游戏 问题描述：

动物游戏是一个古老的游戏，游戏有两个参与者——玩者和猜者。玩者要求想一个动物， 猜者要尽力猜它。猜者要问玩者一系列的是/否的问题，举例如下。

猜者：是陆生的吗？假如玩者回答“是”，那么猜者可以不考虑那些不生活在陆地上 的动物，并且用这个信息产生下一个问题。

猜者：有翅膀吗？问题的答案允许猜者不考虑有翅膀动物或没有翅膀动物来猜测。基于玩 者的答复，仔细陈述每一个问题让猜者不考虑一大群动物，最后，通过这些给定的特征，猜 者知道仅有一种动物。

猜者：你想的动物是大象吗？假如猜者是对的，那么他或她就赢了这个游戏。否则，玩者 赢了该游戏。

猜者：你想的什么动物呢？ 玩者：猪。

猜者：大象和猪有什么不同？

玩者：大象有长鼻子，而猪则没有。

通过记住新的动物以及他或她所想的动物与新动物的区别，猜者学会了区分这两种动物。 基本要求：

（1）程序的用户作为玩者的角色，计算机是猜者的角色。

（2）程序保存了一个基本问题的知识，每一个问题让它减少考虑中的动物数。当程序已 经减少它的考虑到仅一只动物，它就猜这个动物。如果猜者是对的，程序赢了。否则，程序 问玩者他或她想的动物名字。然后，问如何区分新的动物和所猜的动物。然后保存这个问题 并且储存这个新的动物在下一次玩的游戏的基本知识中。

（3）每一次学到的新动物的特征，就被这个程序加入到基本知识中。随着时间的流逝， 程序的基本知识在增长，玩者想出不在基本知识中的动物变得越来越难——这个程序在猜动 物时变成一位专家。在某些领域通过用一些基本知识来陈述专家见解的程序叫专家系统，并 且这个系统的研究是人工智能的一个分支。尽管大部分专家系统的程序不能修改固有的知识， 动物游戏的程序是一个特殊的自学习专家系统的例子，因为当它们遇见新的情况时它们增加 新的动物到它的基本知识里。这个改变基本知识的能力，使得动物程序能模仿学习的过程。

37．用二叉树来表示代数表达式

编写一个程序，先用二叉树来表示代数表达式，树的每个结点包括一个运算符或运算数，代 数表达式中只包含+、-、*、/ 和一位整数且没有错误，并且要按照先乘除后加减的原则构造 二叉树（参见教材第六章），然后由对应的二叉树计算该表达式的值。

38．病人看病模拟程序

编写一个程序，反映病人到医院看病，排队看医生的情况。在病人排队过程中，主要重 复两件事：

（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。

（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。

要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下： （1）排队——输入排队病人的病历号，加入到病人排队队列中。

（2）就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除。 （3）查看排队——从队首到队尾列出所有的排队病人的病历号。

（4）不再排队，余下顺序就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行。 （5）下班——退出运行。

39．螺旋方阵

下面是一个5*5阶螺旋方阵，设计一个算法输出此形式的n*n（n<20）阶阵（逆时针方向旋转）。

1 16 15 14 132 17 24 23 12 3 18 25 22 114 19 20 21 105 6 7 8 9 要求：n由用户输入。

40．实现索引文件建立和查找算法

编写一个程序，实现文件访问。设有两个文件：数据主文件data.dat和索引文件index.dat。

数据主文件由记录学生基本情况的若干条记录组成。其记录格式如下：

数据项名称 Num Name Sex Age Addr Dep Spec 数据长度 8 10 1 2 30 20 20 数据类型 string string int int string string string 其中string表示字符串。索引文件的每个记录由两个字段组成：学好及学生基本情况记录 在数据文件中相应的位置，格式如下：

数据项名称 Num Offset 数据长度 8 4 数据类型 string long 索引文件中的记录按学号升序排列。要求完成如下功能： （1）输入主文件记录，同步建立或修改对应的索引文件。 （2）输出主文件的全部记录。 （3）输出索引文件的全部记录。

（4）根据用户输入的学号，在索引文件中采用二分查找法找到对应的记录号，再通过主文件输出该记录。

41．排课软件

问题描述：大学的每个专业都要进行排课。假设任何专业都有固定的学习年限，每学年含两学期，每 个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有 哪些先修课程是确定的。每门课恰好占一个学期，假定每天上午与下午各有5节课。试在这 样的前提下设计一个教学计划编制程序。 基本要求：

（1）输入数据包括：各学期所开的课程数（必须使每学期所开的课程数之和与课程总数相等），课 程编号，课程名称，周学时数，指定开课学期，先决条件。如指定开课学期为0，表示由电脑自动指 定开课学期。

（2）如输入数据不合理，比如每学期所开课程数之和与课程总数不相等，应显示适当的提示信息。 （3）用文本文件存储输入数据。

（4）由文本文件存储产生的各学期的课表。

42．在一个田径运动会上，已知有m个选手参加比赛，运动项目共有n个，这包括若干个诸如100m之类的以个人形式参加的单项和4*100m之类的多人同时参加的集体项目。另外，每位选手最多可参加3个单项，集体项目则不限制。为使选手能正常进行比赛，需要对赛程作合理安排。请构造出有关模型和数据结构，设计出合理安排赛程的算法和程序，以使每位选手都能正常地参加比赛，并要求比赛时间尽可能短。

43．车厢调度

问题描述：假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3，．．．，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。