14 数构上机实验题目第三次上机.pdf

第1页：第三次上机验证试验封面

第三次上机验证试验（必作题）：题目：邻接矩阵存储的图及相关算法的实验验证[实验目的]验证邻接矩阵存储的图及其上的基本操作。[实验内容及要求]1、定义邻接矩阵存储的图类Graph_Matrix.2、实验验证如下算法的正确性、各种功能及指标：1创建一个邻接矩阵存储的图；2返回图中指定边的权值；3返回图中某顶点的第一个邻接顶点；

4返回图中某顶点关于另一个顶点的下一个邻接顶点的序号；5实现深度优先遍历算法。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。设计实验（选作题）：题目：设计并实现一个算法，求自由树的直径。

实验内容及要求：无环连通图G=(V,E)亦称为自由树T，其直径是树中所有顶点之间最短路径的最大值，设计一个算法求T的直径；编制程序实现该算法，制定测试方案，并调试通过。1、创建自由树T.2、设计并实现求T的直径的算法。3、为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果。

4、为程序制定测试方案。5、为方便程序测试，程序代码中应包括合适的调试语句。6、测试程序时，对所有输入变量应遍取各种有代表性的值。7、为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。