精品文档 义为图中所有顶点到达顶点v的最长路径长度(路径上的边数)。下面算法完成对有向无环图G中每个顶点的MPL值，如果g无回路，则求出各顶点的MPL，并返回SUCCESS；否则返回FAIL。 template Status FillMPL(const AdjListDirGraph &g) // 初始条件：存在有向图g // 操作结果：如g无回路,则求出g中每个顶点的MPL,并返回SUCCESS,否则返回FAIL { int *indegree = new int[g.GetVexNum()]; // 顶点入度数组 int v, u, mpl, count = 0, top = -1; for (v = 0; v < g.GetVexNum(); v++) { indegree[v] = 0; // 初始化顶点v的入度为0 g.SetMPL(v, 0); // 初始化v顶点的MPL为0 } for (v = 0; v < g.GetVexNum(); v++) // 统计图g各顶点的入度 for (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)) indegree[u]++; for (v = 0; v < g.GetVexNum(); v++) if (indegree[v] == 0) { // 入度为0的顶点入栈 (1) ; top = v; } while ( (2) ) { // 栈非空 v = top; (3) ; mpl = g.GetMPL(v) + 1; count++; // 已求出MPL的顶点数累加 for (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u)){ // 对v的每个后继顶点u入度减1,并修改其MPL if (mpl > g.GetMPL(u)) (4) ； if (--indegree[u] == 0) {// u入度为0,将u入栈 indegree[u] = top; top = u; } } //end for } //end while delete []indegree; // 释放indegree所占用的存储空间 if ( (5) ) return FAIL; // 图g有回路 else return SUCCESS; // 求MPL成功 } (1) ______________________ (2)_______________ (3) ____________________ (4) _____________________ (5) _______________ 3． (8分)折半插入排序的算法基本思想是：设在排序表中有n个数据元素Arr[0]，Arr[1],…,Arr[n-1]。其中，Arr[0],Arr[1],…,Arr[i-1]是已经排好序的部分数据元素序精品文档 精品文档 列，在插入Arr[i]时，利用折半查找方法寻找Arr[i]的插入位置。在下面算法的 处，填上适当语句，实现上面的算法。 【注】：关键字用成员函数getKey()获取。 template void BinaryInsertSort ( sortlist & table ) { element temp； int low , high, mid ; for ( int i = 1; i < table.CurrentSize; i++) { low = 0; high = i-1; temp = table.Arr[i]; while ( low <= high ) { (1) ; if ((2) ) high = mid - 1; else low = mid + 1; } for (int k = i-1; k >= low; k-- ) (3) ; (4) ； } } (1) __________________________ (3) __________________________ (2) _____________________ (4) _____________________ 得 分 六、算法设计题(10分) 在有向图中顶点的度等于其入度与出度之和，现定义有向图的度为其所有顶点度的最大值。试编写算法CountDegree(g)，在有向图的邻接表存储结构上求有向图g的度。 下面是有向图的邻接表存储结构类模板的部分定义： template class AdjListDirGraph { protected: // 邻接表的数据成员: int vexNum, vexMaxNum, arcNum; // 顶点数目、允许的顶点最大数目和边数 AdjListGraphVex *vexTable; // 顶点表 精品文档 精品文档 public: // 抽象数据类型方法声明及重载编译系统默认方法声明: AdjListDirGraph(ElemType es[], int vertexNum, int vertexMaxNum = DEFAULT_SIZE); // 构造函数 AdjListDirGraph(int vertexMaxNum = DEFAULT_SIZE); //构造函数 ~AdjListDirGraph(); // 析构函数 …… int GetVexNum() const; // 求有向网的顶点个数 int GetArcNum() const; // 求有向网的边数个数 int FirstAdjVex(int v) const; // 求有向网中顶点v的第一个邻接点序号 int NextAdjVex(int v1, int v2) ; // 求顶点v1的相对于v2的下一个邻接点序号 …… }; 编写的算法： template int CountDegree(const AdjListDirGraph &g) // 返回有向图g的度数值 精品文档 精品文档 上海大学2012～2013学年度春季学期试卷A 课程名: 数据结构（二）课程号: 08305010 学分: 4 参考答案和评分标准 数据结构课程组：曹旻，滕中梅，沈俊，张景峤，许庆国，郑宇 一、判断题（10分）（答案惟一，每小题1分） 题号 答案 1 F 2 T 3 F 4 F 5 F 6 T 7 F 8 T 9 F 10 T 二、选择题（15分）（答案惟一，每小题1分） 题号 1 2 6 7 8 9 10 11 12 13 14 15 B C B B C 3 4 5 答案 A B A B C B B B C D 三、填空题（15分）（答案的写法不惟一，意思正确即可） 1． 9 ； 2．入深度优； 3． 克鲁斯卡尔（Kruskal）； 4． 160 ； 5． O(n+e）； 6 501/2 , 9 , 21/2+26/2 = 47/2； 7． 3, 4 ； 8． Nh = Fh+3 – 1, Fh是斐波那契数, 3 / 2 * log2 (n + 1) , ?log2 ( n+1)? -1； 9．5；10．3 四、简答题（共24分）（答案的写法不惟一，可酌情给分） 1. 精品文档 精品文档 2. 1) 2,3) 3. （1）快速排序的第一趟排序结果为：34,10,47,39,47*,58,101,68,70,66,85. （2）希尔排序的第一趟排序结果为：34,85,47,10,66,47*,101,68,39,70,58. （3）二路归并的第一趟排序结果为：58,85,39,47,47*,70,68,101,10,66,34. （4）基数排序的第一趟回收结果是：70,10,101,34,47,47*,66,58,85,68,39. 五、算法分析题（每空2分，共26分）（答案的写法不惟一，可酌情给分） 1. (1) PrintNLT ( p->rightChild, x); (2) exit() or return; (3) p->data; (4) PrintNLT ( p->leftChild, x); 2. (1): indegree[v] = top (2): top != -1 (3): top = indegree[v] (4): g.SetMPL(u, mpl) (5): count < g.GetVexNum() 3. (1): mid = (low + high)/2 (2): temp.getKey ( ) < table.Arr[mid].getKey ( ) (3): table.Arr[k+1] = table.Arr[k] (4): table.Arr[low] = temp; 六、算法设计题(10分) 没有标准答案，故酌情给分。下面为参考答案之一。 template int CountDegree(const AdjListDirGraph &g) // 操作结果：返回图g的度数值 { int *degree = new int[g.GetVexNum()]; // 定义顶点的度数组 int v, u, maxdegree = 0; 精品文档