若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：支持以上操

Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：

将每个顶点视作一棵树，并将所有边按权重非降排序;

依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;

如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。

试证明：

a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);

b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;

在附加某些特定条件之后，问题的难度往往会有实质的下降。比如，若待编码字符集已按出现频率排序，则Huffman编码可以更快完成。在编码过程中，始终将森林中的树分为两类：单节点(尚未参与合并)和多节点(已合并过)。每经过一次迭代，后者虽不见得增多，但必然有一个新成员。

a)试证明，在后一类树中，新成员的权重(频率)总是最大;

b)试利用以上性质设计一个算法，在O(n)时间内完成Huffman编码。

为什么在迭代过程中有时需要经过几个循环的迭代?

迭代法的一个缺点是算法的逻辑结构复杂。()

为求方程x³-x²-1=0在1.5附近的一个根，现将方程改写成下列的等价形式，且建立相应的迭代公式：

 

   试分析每一种迭代公式的收敛性，并任取一种收敛的迭代公式计算方程在1.5附近的根，要求|x_k+1-x_k|＜10^-6．

为求方程x³-x²-1=0在x₀=1.5附近的一个根，设将方程改写成下列等价形式，并建立相应的迭代公式．

试分析每种迭代公式的收敛性，并选取一种公式求出具有四位有效数字的近似根．

试证：在原仿射尺度算法的迭代公式x^(k+1)=x^(k)+α_kd^(k)中的步长系数若取为，则当迭代点x^(k+1)的某分量x_j^(k+1)=0时，x^(k+1)必为L的最优解．

3．试证：在原仿射尺度算法的迭代公式x^(k+1)=x^(k)+α_kd^(k)中的步长系数若取为，则当迭代点x^(k+1)的某分量x_j^(k+1)=0时，x^(k+1)必为L的最优解．

已知方程x³-x²-0.8=0在x₀=1.5附近有一个根．将此方程改写成如下两个等价形式：

    

构造如下两个迭代格式：

  判断这两个迭代格式是否收敛．选一种收敛较快的迭代格式，求出具有4位有效数字的近似根．

已知方程

  x³-x²-0.8=0在x₀=1.5附近有一个根，将此方程改写成如下2个等价形式：

判断这两个迭代格式是否收敛。