题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
更多“a)试证明，在从堆顶通往任一叶节点的沿途上，各节点对应的关键…”相关的问题
中从任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。
A．二叉排序树
B．大顶堆
C．小顶堆
D．最优二叉树
从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列。
A．二叉排序树
B．大顶堆
C．小顶堆
D．平衡二叉树
设B为A=(1，2，3，...，n)的任一排列。
a)试证明，B是A的一个栈混洗，当且仅当对于任意1≤i＜j＜k≤n，P中都不含如下模式：{...，k，...，i，...，j，...}
b)若对任意1≤i＜j＜k＜n，B中都不含模式{...，j+1，...，i，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。
c)若对任意1＜i＜j＜k≤n，B中都不含模式{...，k，...，j-1，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。
范围查询的另一解法需要借助范围树(range tree)。
为此，首先仿照如图8.37(教材240页)和图8.38(教材241页)所示的策略，按x坐标将平面上所有输入点组织为一棵平衡二叉搜索树，称作主树(main tree)。
于是如图x8.10(a)和(b)所示，该树中每个节点各自对应于一个竖直的条带区域;左、右孩子所对应的条带互不重叠，均由父节点所对应的条带垂直平分而得;同一深度上所有节点所对应的条带也互不重叠，而且它们合并后恰好覆盖整个平面。
接下来，分别对于主树中每一节点，将落在其所对应条带区域中的输入点视作一个输入子集，并同样采用以上方法，按照y坐标将各个子集组织为一棵平衡二叉搜索树，它们称作关联树(associative tree)。于是如图x8.10(a)和(c)所示，每棵关联树所对应的竖直条带，都会进而逐层细分为多个矩形区域，且这些矩形区域也同样具有以上所列主树中各节点所对应条带区域的性质，至此，主树与这o(n)棵关联树构成了一个两层的嵌套结构，即所谓的范围树。
利用范围树，可按如下思路实现高效的范围查询，对于任一查询范围R=[x1，x2]×[y1，y2]，首先按照[x1，x2]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x1，x2]范围内的所有输入点。
接下来，深入这些节点各自对应的关联树，分别按照[y1，y2]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y1，y2]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。
a)试证明，如此实现的范围树，空间复杂度为o(nlogn);
b)按照以上描述，试利用你的范围树实现新的范围查询算法;
c)试证明，以上范围查询算法的时间复杂度为O(r+log2n)，其中r为实际命中并被报告的点数;
d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。
在从时钟节点的定时设备内，用（）使本节点的时钟频率锁定在时钟源的基准频率上。
A.存储技术
B.锁相技术
C.锁存技术
D.同步技术
