期末课程设计题
1．图遍历的演示
试写一个程序，完成以下两个任务：
（1）演示在连通网上访问全部结点
（2）获取深度优先生成树或广度优先生成树，并显示构成生成树的所有边。
测试数据：教科书7.33，忽略里程，起点为北京
实现提示：
（1）存储结构可以自己选定
（2）遍历算法可以自己选定
2.管道铺设施工的最佳方案选择
N（N>10）个居民区之间需要铺设煤气管道。
假设任意两个居民区之间都可以铺设煤气管道，但代价不同。
事先将任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。
设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最少。
测试数据：自己指定
实现提示：
利用Prim算法
3．宿舍管理查询软件
为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
（1）采用交互工作方式
（2）建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)
（3）查询菜单: (用折半查找实现以下操作)
A.按姓名查询
B.按学号查询
C.按房号查询
（4）打印任一查询结果（可以连续操作）
测试数据：自己指定
实现提示：
姓名是字符串，比较时注意
4.教学计划的编制问题
大学的每个专业都要制定教学计划，每个专业开设的课程都是确定的，而且课程在开始时间的安排上必须满足先修关系，试设计一个教学计划编制程序。
要求：
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（字母加2位数字）、学分和直接先修课的课程号
（2）允许用户指定两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
测试数据：6个学期；学生上限10；课程号、先修关系见教科书图7.26
实现提示：
修改拓扑排序算法
5．校园导游咨询
设计一个校园导游程序，为来访客人提供各种信息服务。
设计要求：
（1）设计学校的平面图，至少包括10个以上的场所，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询
（3）为来访客人提供图中任意景点的问路查询，即查询两个景点之间的最短路径
测试数据：自己设计
实现提示：
注意简介信息的存储
6.哈希表的设计与实现
设计哈希表实现电话号码查找系统。
基本要求
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；
（3）采用一定的方法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户名的记录。
测试数据：自己指定
实现提示：
以电话号码和用户名分别实现两个哈希表，（4）（5）是在不同哈希表中实现，哈希函数不同，哈希表不同，解决冲突的方法也可以不同。
7.构造可以使n个城市连接的最小生成树
问题描述：给定一个地区的n个城市间的距离网，用Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：
(1)城市间的距离网采用邻接矩阵表示
(2)要求至少6个城市，10条边
测试数据：自己指定
实现提示：
8．关键路径问题
设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。
基本要求：（1）对一个描述工程的AOE网，应判断其是否能够顺利进行。
（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。
测试数据：教科书图7.29
完成提示：
9．二叉排序树的实现
设计一个程序，实现二叉排序树的应用。
基本要求：
（1）从空树开始，通过插入，建立一棵二叉排序树
（2）检验所建立的二叉树是否是二叉排序树
（3）实现二叉排序树的删除
测试数据：数据元素包括两个域（key, name）
7, zhen
2, qian
12, wei
3, sun
5, zhou
15, han
6, wu
16, yang
14, shen
9, feng
10, chen
11, chu
8, wang
1, zhao
13, jian
4, li
实现提示：
10. 表达式求值
一个表达式可以表示为一棵二叉树，写一个程序，实现基于二叉树表示的算术表达式求值。
基本要求：
（1）假设算术表达式内可以含有变量（a-z）、常量（0-9）和算术运算符（+，-，*，/）（2）在程序中，能够给变量指定值（从键盘输入）
（3）能够计算表达式的最后值
测试数据：a*(b+c); 7*3+9/(7-4)
实现提示：
（1）先画出表达式的二叉树逻辑表示（无括号），获得其前缀式，通过键盘以字符串方式输入前缀式（应该是扩展先序系列），经过识别，创建表达式的二叉树表示。
（2）二叉树中的数据元素包括操起符合和操作数，数据元素存储结构可考虑设计为：typedef struct BiTnode{
char name;
int value;
struct BiTnode *lchild,*rchild;
}BiTnode,BiTree;
说明：
元素是变量：name存变量名，value存指定的值
元素是常量: name存空字符，value存指定的值
元素是运算符：name存运算符，value存INT_MAX
(3)利用后序遍历求值。