题目内容
（请给出正确答案）
若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：
支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;
b)按你的实现，find()和union()接口的复杂度各是多少？相应地，Kruskal算法的复杂度呢？
如果结果不匹配，请 联系老师 获取答案
更多“若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过…”相关的问题
当元素类型为字符串时，为避免复杂的散列码转换，可以改用键树(trie)结构来实现词典ADT。
a)remove()接口复杂度中的因子r可否消除？
b)put()接口复杂度中的因子r可否消除？
c)试举例说明，以上实现方式在最坏情况下可能需要多达Ω(nr)的空间，其中n=|S|为字符串集的规模。
d)试改用列表来实现各节点，使所需空间的总量线性正比于S中所有字符串的长度总和——当然，get()接口的效率因此会降至O(hr)，其中h为树高，同时也是Ss中字符串的最大长度。
e)键树中往往包含大量的单分支节点。试如图x9.5所示，通过折叠合并相邻的单分支节点，进一步提高键树的时、空效率。改进之后，键树的时、空复杂度各是多少？
f)习题[8-19](173页)曾介绍过四叉树(quadtree)结构，并指出其深度不受限制的缺陷。若将四个象限的二进制编码视作字符，即将字符表取作∑={00，01，10，11}，则四叉树可以看作键树的特例，试基于这一理解，仿照以上技巧对四叉树进行压缩，使其深度不致超过O(n)。
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：
将每个顶点视作一棵树，并将所有边按权重非降排序;
依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;
如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。
试证明：
a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;
A.在Contoso森林中配置客户端计算机使用TailspinToysDNS服务器作为备用DNS服务器
B.在ActiveDirectory中创建一个新的条件转发和存储。复制新的条件转发到Contoso林中的所有DNS服务器
C.在Contoso林中创建一个新的应用程序目录分区。让所有DNS服务器支持目录分区
D.在Contoso林的一台DNS服务器上创建新的全局名称主机(A)记录。配置主机(A)使用TailspinToys域名和TailspinToys林的DNS服务器的IP地址记录
