请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码进入小程序
题目内容
（请给出正确答案）
关于kd-树查找算法kdSearch()(教244页算法8.2)，试证明以下结论：
a)在树中某一节点发生递归，当且仅当与该节点对应的子区域，与查询区域的边界相交;
b)若令Q(n)=规模为n的子树中与查询区域边界相交的子区域(节点)总数，则有：Q(n)=2+2Q(n/4)=o(√n)。
c)kdSearch()的运行时间为：o(r+√n)，其中r为实际命中并被报告的点数。
d)进一步地，试举例说明，单次查询中的确可能有多达Ω(√n)个节点发生递归，故以上估计是紧的。
e)若矩形区域不保证与坐标轴平行，甚至不是矩形(比如圆)，则上述结论是否依然成立？
答案
更多“关于kd-树查找算法kdSearch（)（教244页算法8.2)，试证明以下结论：a)在树中某一节点发生递归，当且”相关的问题
第2题
第4题
Prim算法是另一个求最小生成树的算法,它的基本思想是:从任选一个结点vo(T3)开始,用最小代价连接v0与v0,之外的某个结点,得子树T1;再用最小代价连接T1上某个结点与T之外某个结点得到子树T2.如继续下去,直到所有的结点都被连接起来为止用prim算法求如图9.23所示的最小生成树.
第5题
A.最先适应分配算法
B.最优适应分配算法
C.最坏适应分配算法
D.最快适应分配算法
第6题
Joseph Kruskal于1956年提出了构造极小支撑树的另一算法：
将每个顶点视作一棵树，并将所有边按权重非降排序;
依次考查各边，只要其端点分属不同的树，则引入该边，并将端点所分别归属的树合二为一;
如此迭代，直至累计已引入n-1条边时，即得到一棵极小支撑树。
试证明：
a)算法过程中所引入的每一条边，都是某一割的极短跨越边(因此亦必属于某棵极小支撑树);
b)算法过程中的任一时刻，由已引入的边所构成的森林，必是某棵极小支撑树的子图;
第7题
若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：
支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。
a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;
b)按你的实现，find()和union()接口的复杂度各是多少？相应地，Kruskal算法的复杂度呢？
第8题
(1)用二元位置树表示命题公式
注意,请将一元运算符的运算对象取做运算符结点的右儿子.
(2)用3种遍历算法遍访你做出的二元位置树,写出相应的线性表达式.
第9题
为提高空间利用率，可将内部节点的分支数下限从[m/2]提高至[2m/3]。于是，一旦节点v发生上溢且无法通过旋转完成修复，即可将v与其(已经饱和的某一)兄弟合并，再将合并节点等分为三个节点，采用这一策略之后，即得到了B-树的一个变种，称作B'-树(B'-tree)。
当然，实际上不必真地先合二为一，再一分为三。可通过更为快捷的方式，达到同样的效果：从来自原先两个节点及其父节点的共计m+(m-1)+1=2m个关键码中，取出两个上交给父节点，其余2m-2个则尽可能均衡地分摊给三个新节点。
a)按照上述思路，实现B'-树的关键码插入算法;
b)与B-树相比，B'-树的关键码删除算法又有何不同？
第10题
第11题
比如，在仅能使用直尺的情况下，可通过反复实验，用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变，但毕竟破裂是不可逆的。故若仅有一枚鸡蛋，则我们不得不从0开始，以1毫米为单位逐步增加下落的高度，若蛋壳的硬度不超过n毫米，则需要进行o(n)次实验。就效率而言，这等价于退化到无序向量的顺序查找。
a)若你拥有两枚鸡蛋(假定它们硬度完全相同)，所需实验可减少到多少次？试给出对应的算法;
b)进一步地，如果你拥有三枚鸡蛋呢？
c)一般地，如果共有d枚鸡蛋可用呢？
