设在路径Px1x2..xs和Py1y2..yt上，但不在T2*中的边e1，将e1加入T2*中构成回路，在回路上找一条在T2*但不在T1中的边e3删除得T2*’
A． 若W(e1) 那么与T2*是与T1具有相同边数最多的假设矛盾 C． W(e1)>W(e3)即W(e3) Prim算法复杂度为O(n2) 每次加一个点，一条边，在选定起始点之后，最后G’为n个点，n-1条边 贪心策略：每次加一条边，这条边满足：一个端点在Tree中，另一个端点没在，且边权值是满足先前条件的最小边。 性质：T是G的生成树，如果对于任意一条在G而不在T中的边，将它加入T中，若产生回路，且加入的边是环中最大权值的边，那么生成树T就是最小生成树。 2.写出一个怎样找到一个图中的割点的算法描述。 由于上述算法是一个遍历的过程，因此求关键点的事假复杂度为O(n+e). 3.n个节点的二叉树有多少棵？给出证明。 可以分析，当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1; h(0)=1; 当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2， 则能组成2种形态的二叉树。 当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5，则能组成5种形态的二叉树。 以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式得出结果。 令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2) 该递推关系的解为： h(n)=C(2n,n)/(n+1) (n=1,2,3,...) 4． Floyd算法求出任意两点间的最短距离。 例：有向图中有四个点，点之间的距离如下所示： 解答： ?for(k=0;k ?02430? for(i=0;i ? A [ i，j ] = min { A [ i，j ]，A [ i，k ] + A [ k，j ] } ??14 算法思想： 从图的带权邻接矩阵A=[a(i,j)] n×n开始， 递归地进行n次更新，即由矩阵D(0)=A， 按一个公式，构造出矩阵D(1)； 又用同样地公式由D(1)构造出D(2)； 最后又用同样的公式由D(n-1)构造出矩阵D(n)。 矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度 5、对于矩阵乘法： 第1个乘号 第(n-1)个乘号 A1 × A2 × … × An d0 × d1 d1 × d2 dn-1 × dn 给出每个乘法运算的执行顺序，使得进行整个矩阵乘法运算过程中进行的数值乘法次数最少。 解答： 定义函数cost(low, high)，表示计算矩阵A(low)×…×A(high)所需的最少数值乘法次数，root(low, high)表示相应于上述cost(low, high)的进行的最后一次乘法的位置。 则状态转移方程为： 当low == high时，cost(low, high) = 0，root(low, high) = -1 3?3?3??0??当low < high 时， cost(low, high) = min{cost(low, k) + cost(k+1, high) + d(low-1)×dk×d(high) | low<=k<=high-1} 式(1) root(low, high) = k (式(1)中的k) 伪代码实现： 定义两个二维数组cost[1...n][1…n]和root[1…n][1…n] // 初始化数组的对角线元素 for( i=1; i<=n; i++ ) cost[i][i] = 0; root[i][i] = -1; // 按一定的顺序填充数组 for( low=n-1; low>=1; low-- ) for( high=low+1; high<=n; high++) cost[low][high] = maxNum; //maxNum表示无穷大 for (k=low; k 最终，cost[1][n]即为进行该矩阵乘法所需的最少代价。 对root数组进行如下的后序遍历，即可得到代价最少的乘法次序，乘法进行的次序存储在数组multOrder[]中 int multOrderNext; extractOrderWrap(int n, int root[], multOrder[]) { multOrderNext = 1; extractOrder(1, n, multOrder); } extractOrder(int low, int high, int root[], int multOrder[]) { Int k; If (low < high) k = root[low][high]; extractOrder(low, k, multOrder); extractOrder(k+1, high, multOrder); multOrder[multOrderNext] = k; multOrderNext++; } 举例 A1 × A2 × A3 × A4 30×1 1×40 40×10 10×25 d0×d1 d1×d2 d2 × d3 d3 × d4 注：以下cost[i][j]用Cij表示，root[i][j]用Rij表示 C11 = C22 = C33 = C44 = 0 C12 = C11 + C22 + 30×1×40 = 1200 R12 = 1 C23 = C22 + C33 + 1×40×10 = 400 R23 = 2 C34 = C33 + C44 + 40×10×25 = 10000 R34 = 3 C13 = C11 + C23 + 30×1×10 = 700 ok C12 + C33 + 30×40×10 = 13200 R13 = 1 C24 = C22 + C34 + 1×40×25 = 11000 C23 + C44 + 1×10×25 = 650 ok R24 = 3 C14 = C11 + C24 + 30×1×25 = 1400 ok C12 + C34 + 30×40×25 > 1400 C13 + C44 + 30×10×25 > 1400 R14 = 1 所以最小代价C14 = 1400 根/代价 1 2 3 4 1 -1/0 1/1200 1/700 1/1400 2 3 -1/0 2/400 -1/0 3/650 3/10000 4 -1/0 6、给定长度为n的有序元素序列K1， K2， …，Kn，其各个元素被查找的概率（或频率）分别为p1，p2， …， pn。描述构造最优二分树的算法 解答： 定义函数cost(low, high)，表示用K(low)…K(high)构造得到的最优二分树的总代价，root(low, high)表示相应二分树的树根位置。 则状态转移方程为： 当 low>high (low = high-1)时， 令cost(low, high = 0) root(low, high) = -1 当low <= high 时， cost(low, high) = p(low)+…+p(high) + min{cost(low, k-1) + cost(k+1, high) | low<=k<=high} 式(1) root(low, high) = k ( 式(1)中对应cost(low, high)的k ) 伪代码实现： 定义两个二维数组cost[1...n+1][0…n]和root[1…n+1][0…n] // 初始化数组的对角线元素，即(t+1, t) for( i=1; i<=n+1; i++ ) cost[i][i-1] = 0; root[i][i-1] = -1; // 按一定的顺序填充数组 for( low=n; low>=1; low-- ) for( high=low; high<=n; high++) cost[low][high] = maxNum;//maxNum表示无穷大 for (k=low; k<=high; k++)//选取不同的元素作为当前树的树根 currentCost = low…high的概率和 + cost(low, k-1) + cost(k+1, high) if (currentCost < cost[low][high]) cost[low][high] = currentCost; root[low][high] = k; 最终，cost[1][n]即为最优二分树的代价。 对root数组进行先序遍历，即可得到最优二分树。 元素编号 代表字母 1 A 2 B 3 C 4 D 5 E 6 F 概率 5 6 4 7 1 2 C10 = C21 = C32 = C43 = C54 = C65 = C76 = 0 R10 = R11 = R22 = R33 = R44 = C65 = C76 = -1 C66 = C65 + C76 + 2 = 2 OK R66 = 6 C55 = C54+ C65 + 1 = 1 OK R55 = 5