课程设计题目（2012 年版）： （1-6 题必做， 做完 9 题以上并演示答辩参评优秀） 1、学生成绩管理（必做）（链表） [问题描述] 设计一个程序，记录并统计班级学生的成绩情况。每次输入一门课程成绩后，根 据相关要求调整记录的次序。 [基本要求] （1） 该题目要求使用双向链式线性表。每个结点存储的信息包括学号，姓名，各科 成绩，总分等。排序要求是按照总分自多到少排序。另外，将有不及格成绩的学生单 独存成一个链表。 （2） 初始输入： 从文件读入学号 姓名信息，建立初始链表。 （3） 每门课程成绩也从文件读入并存入链表，动态调整链表结点顺序，不及格成绩 学生结点移到另外一个链表。 （4） 可有补考成绩输入，补考后全及格的学生结点再移入正常链表。 （5） 可进行各种常见的查询输出，比如按学号输出各门课程成绩等。 2、算术表达式求值 (必做) （栈） [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter) 组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括 号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结 束符是为了方便。编程利用“算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘或文件读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 （3） 考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。 3、二叉树的应用 (必做)（二叉树） [问题描述] 编程实现二叉树的建立，先序、中序、后序、层序遍历（递归和非递归方法），二 叉树的高度、繁茂度，交换左右子树，统计叶子节点的数目，判断是否为完全二叉树， 按树的形态在屏幕上打印输出。 [基本要求] （1） 从文件中读入建树信息，树的节点数目不小于 20 个，树的高度不小于 4。 （2） 建树信息采用两行英文字符表示，每个英文字符代表一个结点，第 1 行为树的 中序遍历结果，第 2 行为树的后序遍历结果。 4、Huffman 编码与解码 (必做)（Huffman 编码、二叉树） [问题描述] 对一篇英文文章，统计各字符出现的次数，实现 Huffman 编码，以及对编码结果 的解码。 [基本要求] （1） 输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。 

（2） 在 Huffman 编码后，要将编码表和英文文章编码结果保存到文件中，编码结果 必须是二进制形式，即 0 1 的信息用比特位表示，不能用字符’0’和’1’表示。 （3） 提供读编码文件生成原文件的功能。 5、全国省会城市通信布线问题 (必做) （图） [问题描述] 用无向网表示全国省会城市，图中顶点表示城市信息，图中的边表示城市之间的 距离，存放长度信息。要求能够建立通信网，所花的代价最小。 [基本要求] （1） 原始数据存在文件中，方便读入。 （2） 建立全国通信网，要求所花的代价最小。 6、排序算法比较 （必做）（排序） [问题描述] 利用随机函数产生 N 个随机整数（N = 500，1000，1500，2000，2500，…,30000）， 利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数 排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统 计每一种排序所耗费的时间（即比较次数）。 [基本要求] （1） 原始数据存在文件中，每个整数一行，方便读入。 （2） 屏幕显示每种排序所花的比较次数。 7、模拟队列题目 (选做)（队列） [问题描述] 利用队列操作实现随机队列模拟，例如理发店营业模拟或银行营业模拟。 [基本要求] （1）随机生成模拟数据，队列数不少于 4 个。 （2）给出每个队列的统计结果。 8、Hash 表应用 （选做） （查找） [问题描述] 设计散列表实现身份证查找系统，对身份证号进行 Hash。 [基本要求] （1） 设每个记录有下列数据项：身份证号码（虚构，位数和编码规则与真实一致即 可）、姓名、地址。 （2） 从键盘或文件输入各记录，以身份证号码为关键字建立散列表。 （3） 采用开放定址的方法解决冲突。 （4） 查找并显示给定身份信息的记录。 9、关键路径问题 （选做） （图） [问题描述] 设计并实现关键路径的一种应用。 [基本要求] （1）实现拓扑排序和关键路径的发现。 

（2）给出一个具体的应用环境。 10、 社交网络图实现（选做） （图） [问题描述] 设计并实现一种简单的社交网络模型图。 [基本要求] （1） 每个人的信息是一个结点，人与人的联系构成边。个人信息里要有地理坐标信 息，以便后续应用中能方便找靠近的人。 （2） 根据输入的任意两个人信息，给出他们之间的联系路径，最少经过多少人构成 联系。 （3） 根据位置信息的动态变化，找寻附近能够联络的人，能够通过 1 次中间人能联 络的人等。 （4） 可根据自己的创意添加更多的功能。 成绩评定细则： 1. 正确性：程序是否可以运行，结果是否正确（20 分） 2. 功能的完备性：是否实现要求的所有子功能（40 分） 3. 课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20 分） 4. 独立完成情况( 40 分） 总计：100 分 加分项目： 1.健壮性：异常处理的情况 2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名，‘{ }’的缩进， 关键位置适量注释等 3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善 4.界面的设计：可视化界面，或者交互良好的 DOS 界面 编程语言：C、C++ 或 JAVA 任选其一 检查方式: 1. 总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性,代码量，程 序的结构是否合理；局部检查三个以上函数块 2. 检查程序时同时检查课程设计报告的电子文档 3. 检查时间：每个学生的检查时间 10 分钟 

时间安排： 1 上机时间安排 2 课程设计报告上交时间 3 课程设计检查时间 课程设计报告要求： 1.所有的课程设计报告，均要有封面，包括：课题名称、班级、学号、学生姓名、成 绩和指导教师； 2.给出自己采用的数据结构； 3.给出算法设计思想； 4.给出实现的源程序，并在必要的代码处给出注释； 5.给出测试数据和结果； 6.给出算法的时间复杂度、另外可以提出算法的改进方法； 7.给出结束语：说明完成课程设计的情况，心得体会；课程设计报告的电子文档在上 机检查程序时一并检查；书面文档在指定的时间内上交。