数据结构课程设计习题集
（2015 版）
单 位： 合肥工业大学
授课时间： 2015 - 2016 学年 第一学期
命 题 人： 合工大宣城校区
授课年级： 2014 级本科生
总 课 时：
一 出题目的
（1）课程设计对象
2014 级计算机系大二学生。
（2）课程设计对象要求
熟练掌握 C、C++。
（3）课程设计目的
①能够熟练编写数据结构，并利用相应类解决实际问题。
②进一步提高编程能力，初步具备一定的自学能力。
二 课程设计流程
2.1 选题
（1）每位同学选取一道或多道题目完成课程设计。
（2）选题时原则上一个标准班同学的设计题目不能重复，即不能有两名以
上同学完成同一个题目。
（3）可自拟题目，但应向指导老师申请，经指导老师批准后有效。
（4）课程设计应独立完成。
2.2 编码
（1）提倡使用 C 或 C++完成设计任务，也可以选择其它自己熟悉的语言完
成。
（2）鼓励实用图形界面完成出题，对于有较好的界面设计、人机交互的，
答辩时应给予适当加分。
2.3 验收和答辩
在课程设计执行期的最后一个工作日，由指导老师对每个学生设计的完成情
况进行验收和答辩，其流程为由答辩学生向指导老师演示设计的完成情况和效果，
老师针对具体情况向学生提问。
2.4 成果提交
设计工作完成后需提交课程设计报告的纸质文档和电子文档。电子文档首先
提交到班长处，班长打包后再提交给指导老师。
2.5 评分
课程设计成绩按优秀、良好、中等、及格和不及格五个等级评分，评分考察
的因素如下：
（1）设计题目的难度系数。
（2）现场验收答辩情况。
（3）设计的完成情况。
（4）课程设计报告完成情况。
（5）凡未经验收答辩、未按期提交纸质版和电子版设计报告的同学一律按
零分处理。
（6）对于存在抄袭现象的，一律零分处理。
三 课程设计评分标准
（1）需求分析清晰，能清楚地领会题目要求；
（2）思路清晰，数据结构设计合理，算法编写步骤清晰；
（3）对于有交互需求的题目，需要设计界面，要求界面友好，可操作性强；
（4）鼓励采用多种算法解决问题，并要能清晰地阐述多种算法的思想，采
用多种算法解决问题的需要采用科学合理的方法对算法进行测试、比较，并对测
试的结果进行总结、分析、说明；
（5）文档要按照指定格式完成，要求文档格式规范，文字简洁易懂，对于
有图表的，需要对图表进行标号，图表的绘制要符合图表制定的要求，对于文档
没有按照教师意见进行修改的，课程设计得分不能超过 60 分；
（6）答辩要脱稿完成，对于不能够完整、清晰地陈述设计思路、思想的，
其打分不能超过 60 分，对于优秀的课程设计（>=90 分），需要采取公开答辩或
由两位及以上课程设计老师验收；
（7）文档、代码打印部分需在指定时间内上交，对于在指定时间内没有上
交的同学，其课程设计得分不得超过 60 分；
（8）课程设计题目分数为完成了题目需求和文档的分数，原则上最高得分
不能超过该分数，但对于有同学完成了题目要求之外的功能的（创新性功能的），
可给予加分，但加分不能超过 10 分。
四 题目
1 字符串距离（65分）
目的：字符串是一种基础且广泛使用的数据结构，与字符串相关的题目既可
以考察基本程序设计能力和技巧，也可以考查算法设计能力。
题目：求字符串之间距离
要求：设有字符串 X，称在 X 的头尾及中间插入任意多个空格后构成的新
字符串为 X 的扩展串，如字符串 X 为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”
和“abcb□cd□”都是 X 的扩展串，这里“□”代表空格字符。如果 A1 是字符串 A 的
扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么定义字符串
A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定
义为它们的 ASCII 码的差的绝对值，而空格字符与其它任意字符之间的距离为
已知的定值 K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串
中，必定存在两个等长的扩展串 A1、B1，使得 A1 与 B1 之间的距离达到最小，
将这一距离定义为字符串 A、B 的距离。请编写程序，求出字符串 A、B 的距离。
2 求最长公共子串（70分）
求解 2 个字符串的最长公共子串。输入的 2 个字符串可以从键盘读入，也可
以从两个文本文件中读入。
实现提示：对于采用动态规划法和后缀树算法的，要对算法设计思想能够进
行详细阐述，并分析算法的时间复杂和空间复杂度。能够详细阐述多种算法并设
计完成的，总分可达到 80 分。
3 集合运算（60分）
问题描述：
设有两个用单链表表示的集合 A、B，其元素类型是 int 且以递增方式存储，
其头结点分别为 a、b。要求下面各问题中的结果集合同样以递增方式存储，结
果集合不影响原集合。
实现要求：
（1）编写集合元素测试函数 IN_SET，如果元素已经在集合中返回 0，否则
返回 1；
（2）编写集合元素输入并插入到单链表中的函数 INSERT_SET，保证所输
入的集合中的元素是唯一且以递增方式存储在单链表中；
（3）编写集合元素输出函数，对建立的集合链表按递减方式输出；
（4）编写求集合 A、B 的交 C=A∩B 的函数，并输出集合 C 的元素；
（5）编写求集合 A、B 的并 D=A∪B 的函数，并输出集合 D 的元素；
（6）求集合 A 与 B 的对称差 E=（A-B）∪（B-A） 的函数，并输出集合 D
的元素；
（7）设计一个菜单，具有输入集合元素、求集合 A、B 的交 C、求集合 A、
B 的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。
测试数据：由读者自定，但集合 A、B 的元素个数不得少于 16 个。
4 二叉树结点染色问题（70分）
目的：二叉树是常用的重要非线性数据结构，在客观世界中有着广泛的应用。
通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各
种操作。
要求：一棵二叉树可以按照如下规则表示成一个由 0、1、2 组成的字符序列，
我们称之为“二叉树序列 S”：
例如，下图所表示的二叉树可以用二叉树序列 S=21200110 来表示。
任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或
蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，
那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出
这棵树中最多和最少有多少个点能够被染成绿色。
