6各种排序算法的性能分析（****）
【问题描述】
排序是一个将记录的无序序列调整成为一个有序序列的过程。排序算法是计算机程序设计中的重要过程，不同的排序算法性能各有不同。在程序中，我们通过随机函数产生规模不同的随机整型数组，然后分别让不同的排序算法来从小到大进行排序。通过排序时间和排序的交换次数上对不同的排序算法进行性能分析。 【基本要求】
（1）每种排序算法在同一规模的数组测试中使用的原始数据是相同的。例如:不同排序算法对一个含有100个元素的无序数组进行排序时，他们的无序序列是相同的。
（2）对用于测试的随机数组规模不少于100个元素，其待测排序数组不少于5组。 （3）对不同的排序算法要求记录排序所需执行时间和移动次数。
（4）对以下排序算法进行性能分析，尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。(直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，直接选择排序，堆排序(加黑的着重要求)，树型选择排序，归并排序以及基数排序) 【实现提示】
（1）通过在程序中插入计数器来实现排序算法中对移动次数的记录。 （2）调用#include
（1）排序算法。 （2）算法性能分析。
7交通咨询系统（最短路径问题） （*****）
【问题描述】
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 【基本要求】
（1）对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能； （2）对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除； （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；
（4）旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，火车至少一小时；
（5）咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。 【实现提示】
（1）数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件中。
（2）数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
（3）数据的存储结构。采用邻接表作为数据的存储结构。
（4）求最优决策（最短路径和最小费用）功能模块：用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)。
（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。 【知识点】
（1）单源最短路径。
（2）一顶点对之间的最短路径。 （3）所有顶点对之间的最短路径。
8重排九宫格（*****）
【问题描述】
将1、2、3、4、5、6、7、8等八个数字随机放在一个3x3的九宫格中，其中有一个格子为空。移动空格可以改变九宫格的状态。移动规则是，每次将与空格（上、下、左、右）相邻的一个数字平移到空格中。假设九宫格的初态和终态分别为图1的（a）和（b）所示，试给出从初态到终态的最少移动步数。
1 2 3 2 8 3 1 7 6 4 5 8 7 6 4 5
（a）九宫格的初态S0 （b）九宫格的终态Sg
图1 九宫格的初态和络态
【基本要求】
（1）空格只能与空格相邻（上、下、左、右）的一个数字交换位置。
（2）空格不能连续两次与同一个数字交换位置（为了防止循环，规定状态不能返回父结点）。
（3）求出从初状态S0到目标状态Sg的调整过程，即从初态到终态的路径。 （4）扩展内容：在屏幕上显示九宫格的图形形式，并能动态演示移动过程。 【实现提示】
（1）隐式图搜索。九宫格求解是一个典型的状态搜索问题。如果用状态空间的显示表示，则应把其全部状态（共有9！个）存入计算机中，这是一个相当大的数字，不现实。一般采用隐式图搜索法，即从初态开始，逐步地生成问题的状态空间并检查解是否在其中。如图2所示，先从S0开始，产生4状态，如果解不在其中，则分别从这4状态开始产生新的状态。为了防止循环，规定不能返回到父结点。 （2）广度优先搜索算法步骤：
1）将初始状态S0压入队列S中。
2）若队列S为空，则搜索失败，问题无解。
3）取队列S首元素结点N取出放入栈K中并将其以顺序编号n。 4）若目标Sg=N，则搜索成功，问题有解。 5）若N无子结点则返回步骤2.
6）扩展N，将其所有子结点配上指向N的返回指针后，再依次放入队列S中，返回步骤2。
注意：返回指针的值要对应编号。 （3）深度优先搜索法
1）将初始状态S0压入栈S中。
2）若栈S为空，则搜索失败，问题无解。
3）取栈S顶元素结点N放入栈K中并将其以顺序编号n。 4）若目标Sg=N，则搜索成功，问题有解。 5）若N无子结点，则返回步骤2.
6）扩展N，将其所有子结点配上指向N的返回指针后，再依次压入栈S中，返回步骤2。
注意：返回指针要对应编号。
图 九宫格图搜索求解过程
【知识点】
（1）图的遍历；
（2）栈、队列和优先级队列； （3）状态空间搜索。
9 野人过河（*****）
【问题描述】
有3个野人和3个传教士来到河边渡河，河岸有一条船，每次至多可供2人乘渡，野人
和传教士都会划船。在河岸，如果野人人数多于传教士人数，则野人会吃掉传教士。请设计一个程序来描述安全过河过程。 【基本要求】
（1）在河两岸和船上要求野人的人数不大于传教士的人数。
（2）要求输出所有可能的过程。(即不同方法的每个步骤如示例1) （3）要求对各个模块的功能及参数作必要的说明。 【实现提示】
（1）先设定两个状态数组确定左岸和右岸，再确定状态变量：野人数，传教士数和船。 （2）先从开始岸考虑传教士数>=野人数，河对岸野人数<=传教士数。并且始终保证开过去两人，开回来一人实现有效转换。
（3）可以考虑使用图搜索方法，通过检测结点来实现路径的输出。 输出示例:
第1次：左岸到右岸，传教士过去1人，野人过去1人 第2次：右岸到左岸，传教士过去1人，野人过去0人 第3次：左岸到右岸，传教士过去0人，野人过去2人 第4次：右岸到左岸，传教士过去0人，野人过去1人 第5次：左岸到右岸，传教士过去2人，野人过去0人 第6次：右岸到左岸，传教士过去1人，野人过去1人 第7次：左岸到右岸，传教士过去2人，野人过去0人 第8次：右岸到左岸，传教士过去0人，野人过去1人 第9次：左岸到右岸，传教士过去0人，野人过去2人 第10次：右岸到左岸，传教士过去0人，野人过去1人 第11次：左岸到右岸，传教士过去0人，野人过去2人 【知识点】
（1）图的遍历。 （2）状态空间搜索。
10校园导游系统（****）
【问题描述】
设计一个校园导游系统，为来访的客人提供导游咨询服务，如景点查询、路径查询等。 【基本要求】
（1）设计所在学校的校园平面图，所含景点不少于10个。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条通路，包括任意两个景点之间的所有路径，任意两个景点之间的最短路径等。
（4）扩展内容：提供景点和道路的扩充及撤销功能。 【实现提示】
（1）用图存储校园平面图中的基本信息。图的顶点表示校园内各景点，存放景点名称、代号、简介等信息；图的边表示景点之间的可达关系；图的边的权植表示两个景点之间的路径长度。
（2）数据的存储结构。采用邻接表作为数据的存储结构。
（3）用迪杰斯特算法（Dijkstra）求出从一个景点到其他所有景点的最短路径，用弗洛伊德算法（Floyd）求所有景点之间的最短路径。
（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。 【知识点】
（1）单源最短路径。
（2）所有顶点对之间的最短路径。
11文本分析（*****）
【问题描述】
编写程序，求出文本中每个单词出现的频次，并比较不同文本的相似度。 【基本要求】
（1）各文本存放在文件中，程序能读取文本文件；
（2）程序能对文本文件进行分词，将分词得到的单词存放到单词表中；
（3）如果一个单词多次出现，要统计单词出现的频率，其频率也要存入到单词表中； （4）扩展内容：根据不同文本各单词出现的频率，建立文本向量，计算文本的相似度。 【实现提示】
（1）定义一个结构体StringCount，其中字符串成员str和整数成员num分别记录单词及其出现的次数。
（2）创建单词表，程序扫描到一个单词后要先在单词表中查找该单词是否存在，如果不存在就把该单词存放到单词表中，并将该单词计数设为1；如果该单词存在，就修改单词表中该单词出现的频次，即把该单词计数增1。
（2）为了提高查找速度，建立平衡二叉搜索树，其结点存放单词基本信息（包括单词字符串和单词出现的频次），插入单词结点时要对平衡二叉搜索树进行动态平衡调整。
（3）建立文本向量，它由单词频次转换而来，通过计算向量距离得出文本之间的相似度。向量距离公式如下：
ii), Wj=(wj,wj,...,wj)，定义向量相似度为： 设有向量: Wi=(w1i,w2,...,wn12nS(Wi,Wj)=(Wi,Wj)(PWiP?PWjP)
,其中(WiWj=)jk?jiiPWP=(?ww为向量内积， kkk=1nnk=1(wki)2)12，
PWjP=(?nk=1(w)2)12为向量的范数(长度)。将S(Wi,Wj)简记为Sij。S(Wi,Wj)的物
理意义是两个向量的空间夹角的余弦数值。
【知识点】
（1）字符串处理。
（2）平衡二叉搜索树。
（3）扩展内容：向量相似度计算。
12大学教学计划编制（***）
【问题描述】
大学每个专业都要制定教学计划。假设某个专业有40门课程，分8个学期开设。每门课程均在一个学期内完成。课程之间存在先修关系，即一门课程只有其所有先修课程都完成后才能开始。教学计划中至少有5门课程没有先修课程，先修关系路径长度不超过7。同一学期内开设的课程不存在先修关系，即可以并行执行。试设计实现一个教学计划编制程序，
把课程分到不同学期，保证所有课程满足先修关系，且能对课程基本信息和上课学期进行查询。
【基本要求】
（1）每门课的信息包括课程基本信息（如课程号、学分等）和课程之间的关系信息（即课程之间的先修关系）。 课程信息存储在文件中。程序从文件中读取课程信息。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀，即每个学期课程门数和学分尽量相近；二是把课程尽可能地排在前几个学期中，即课程安排前紧后松。
（3）课程编排结果也要写入文件中。 【实现提示】 （1）课程基本信息和课程之间先修关系信息用图表示，图的顶点存储课程的基本信息，图的边存储课程之间的先修关系。
（2）先采用拓扑排序生成所有课程的之间的先后关系，再根据拓扑排序把课程分解到不同学期。 【知识点】
（1）程序文件读写； （2）图的邻接表表示法； （3）图的拓扑排序算法。