《数据结构》课程考核课题
专业： 数学 年级： 2022 级
正文内容要求
1．概要设计
说明本课题所涉及的理论知识以及课题实验的理论依据，阐明实验中用到的所有数
据结构的定义、主程序的流程以及各程序模块之间的层次（调用）关系。
2．详细设计
实现概要设计中定义的所有数据结构，对每个操作写出完整的算法，要求用 C/C++
语言完成，对程序加详细的注释。这是本部分的必要内容。
如果程序代码行较多，可以将程序放在附录中。但是，本部分必要内容不能省略。
3．设计和调试分析
⑴ 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
⑵ 算法的时间复杂度和空间复杂度分析和改进设想；
⑶ 经验和体会等。
4．用户使用说明
要给出实验结果，并说明如何使用你编写的程序，详细列出每一步的操作步骤。
5．测试数据与测试结果
列出测试数据和测试结果，包括输入和输出。
附录 包括所有源程序清单。（可选，如果程序较少，可以将程序放在第 2 部分）
注：以上章节内容适用于第一题至第二十题，正文提纲仅供参考。
要求及注意事项
1．所有同学从上述课题中任选一题完成，不能选择多题，所有同学所选择的课题
只能一人独立完成。不同的学生可以选择相同的课题，但必须独立完成所选课题。
2．提交的报告用 word 排版后再打印，报告内容不得雷同，第一题至第二十题的课
题报告雷同率不能超过 40%，第二十一题的学习报告雷同率不能超过 50%，否则，雷同
的报告均以不及格计分。
3．第一题至第二十题的课题报告须提交打印稿，正文至少 5000 字（正文不包括目
录、附录），有封面（见模板）和《课程考核成绩评定表》（见模板），装订成册。报告
含封面、目录、正文、参考文献、附录（可选），不含中英文摘要。提交的报告中，《课
程考核成绩评定表》打印后放在报告最后装订，便于评分。报告须按照课程考核撰写要
求撰写，编排格式请严格按照《课程考核撰写规范样张》撰写。
第二十一题报告须提交手写稿，至少 5000 字，用信笺纸撰写，在第一页上面页眉
处写上班级、学号、姓名，装订成册，不需要封面，也不需要《课程考核成绩评定表》，
手写报告不需要目录。
4．所有学生必须在第十九周周一（2024 年 1 月 8 日）前完成课题任务。各班学习
委员须于第十九周周一下午 2:30 前将本班所有学生的报告交任课教师，地点：能源楼
612。凡逾期提交报告的学生一律计为不及格。
5．所提交的第二十一题的学习报告最高计 85 分。
6. 期末总评成绩按照平时成绩与课程考核报告得分的比例计算。课程考核报告是
本学期《数据结构 B》和《数据结构实验》课程的期末成绩评定重要依据，请同学们认
真对待。
课 题
注：以下课题用 C/C++语言实现，不得用其它高级程序设计语言实现
一、简单数据库管理
[问题描述]
(1) 有 5 个学生，每个学生有 3 门课的成绩，从键盘输入以上数据（包括学号、姓
名、3 门课程成绩），建立带表头结点的单链表(用尾插法)；计算出平均成绩，按平均分
进行排序处理，使之成为一个有序链表。
(2) 将已经排序的链表按学号进行插入和删除处理。插入和删除一个学生的 3 门课
程成绩：程序先计算新插入学生的平均成绩，然后将它按成绩高低顺序插入；找到被删
除的学生，删除即可。
[实现提示]
(1) 用户界面设计为菜单方式。程序运行后，显示如下功能菜单：
1. 建立链表；2. 插入；3. 删除；4. 查找；5. 输出；0. 退出
用户每键入一个选择数字，程序就执行相应的功能并再次显示菜单，直至某次用户
选择了“0. 退出”为止。
(2) 退出时，要先销毁链表，再退出。
(3) 在执行插入、删除和查找操作时，均要求输入学生学号。查找操作只需要回答
找到了还是没找到。
(4) 输出就是按次序输出线性表中所有元素的值。
二、八皇后问题
在 8 行 8 列的棋盘上放置 8 个皇后，使任一个皇后都不能吃掉其他的 7 个皇后（注：
皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子），并将结果以图形方式显
示出来。（最好能绘出所有 92 种情况）
例如，当求出下述的一个解时，画出如下图
(1,1) (5,2) (8,3) (6,4) (3,5) (7,6) (2,7) (4,8)
Q
Q
Q
Q
Q
Q
Q
Q
提示:
（1） 通过“int LineNum[9]; bool a[9], b[15], c[15];”说明具有全局作用域
的 4 个数组。其中的：
LineNum[i]表示第 i 列的皇后要放的行位置（只用其中的列号 1 到 8）；
a[i]为 true（i =1，2，„，8）表示第 i 行上尚未放皇后；
b[i]为 true（i =0，1，2，„，14）表示第 i 条斜对角线上尚未放皇后（斜对角线
指的是“/”状对角线，该对角线上各点的行列号之和 i+j 为一个常数）；
c[i]为 true（i=0，1，2，„，14）表示第 i 条反斜对角线上尚未放皇后（反斜对
角线指的是“\”状对角线，该对角线上各点的行列号之差 i-j 为一个常数）。
从而当使用语句“if ( a[j] && b[i+j-2] && c[i-j+7] ) LineNum[i]=j;”时，
可用于判断并实现：如果在第 j 行的第 i 列上放置皇后安全的话，则将一枚皇后放置到
那儿。
（2）编制一个具有如下原型的递归函数 solve，它负责往第 i 列开始的连续 8-i+1
列上均放上皇后，若成功则通过引用参数 ok 返回 true（否则返回 false）。
void solve(int i, bool& ok);
摆放皇后之后，若 i=8 即已放满时则递归出口；否则通过 solve(i+1,ok);进行递归
调用。
（3）编制主函数，首先初始化一个“空棋盘”，即将 a、b、c 数组的各元素均置
为 true（表示当前棋盘的 8 个行、15 条斜对角线以及 15 条反斜对角线上都尚未摆放皇
后）。而后执行调用语句“solve(1, ok);”，它负责往第 1 列开始的连续 8 列上均放
上皇后，若成功则通过引用参数 ok 返回 true（否则返回 false）。
三、有序线性表 (用单链表实现)
[问题描述]
有序线性表的元素是按值从小到大的顺序排列的。本题要求用顺序表或带表头结点
的单链表两种方式实现有序线性表。将线性表元素类型设为整型，任意输入一些测试数
据。用带表头结点的单链表作为存储结构。
[基本要求]
有序线性表的基本操作如下：
(1) Clear(L)： 该函数清除表中的所有元素, 使表 L 回到初始化(空)状态。
(2) Insert(L, x)： 该函数在表 L 中插入元素 x，使表 L 仍然保持有序。
(3) Remove(L, x)： 该函数从表 L 中删除元素 x。若 x 在 L 中出现多次，则多次删除
x。
(4) IsEmpty(L)： 如果表 L 为空表(长度为 0)，则返回 TRUE，否则返回 FALSE。
(5) Find(L, x)： 该函数返回元素 x 在表 L 中的位置。考虑 x 在 L 中出现多次的情况。
当 x 不在 L 中时，函数值为 NULL。
(6) PrintList(L)： 该函数输出表 L 中所有元素的值。
(7) DeleteMin(L, x)： 删除表 L 中的最小值，并由 x 返回该最小值。
(8) Average(L, x)： 求表 L 中所有元素的平均值。
[实现提示]
(1) 用户界面设计为菜单方式。程序运行后，显示如下功能菜单：
1．建立空表；2. 置空表；3. 插入；4. 删除；5. 查找；6. 输出；0. 退出
用户每键入一个选择数字，程序就执行相应的功能并再次显示菜单，直至某次用户
选择了“ 0. 退出”为止。
(2) 置空表就是清除表中的所有元素, 使线性表成为一个空表。
(3) 在执行插入、删除和查找操作时，均要求输入元素 x 的值。查找操作只需要回答
找到了还是没找到。
(4) 输出就是按次序输出线性表中所有元素的值。
