在二叉搜索树中,任一结点所具有的关键码值都大于它的左子女(如果存在)的关键码值,同时小于其右子女(如果存在)的关键码值。()
此题为判断题(对,错)。
此题为判断题(对,错)。
设有一个关键码的输入序列(55,31,11,37,46,73,63,02,07):
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需进行的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
A、顺序搜索
B、折半搜索
C、前两者都不正确
以二叉链表作为二叉树的存储结构,编写以下算法:
(1)统计二叉树的叶结点个数。
(2)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。
(3)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。
(4)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。
(5)求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。
(6)输出二叉树中从每个叶子结点到根结点的路径。
所谓半无穷范围查询(semi-infinite range query),是教材8.4节中所介绍一般性范围查询的特例,具体地,这里的查询区域是某一侧无界的广义矩形区域,比如R=[-1,+1]x[0,﹢∞),即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域,当然,对查询的语义功能要求依然不变——从某一相对固定的点集中,找出落在任意指定区域R内部的所有点。
范围树(176页习题[8-20])稍作调整之后,固然也可交持半无穷范围查询,但若能针对这一特定问题所固有的性质,改用优先级搜索树(priority search tree,PST)之类的数据结构,则不仅可以保持O(r+logn)的最优时间效率,而且更重要的是,可以将空间复杂度从范围树的O(nlogn)优化至O(n)。
如图x10.3所示,优先级搜索树除了首先在拓扑上应是一棵二叉树,还同时遵守以下三条规则。
①首先,各节点的y坐标均不小于其左右孩子(如果存在)——因此,整体上可以视作为以y坐标为优先级的二叉堆。
②此外,相对于任一父节点,左子树中节点的x坐标均不得大于右子树中的节点。
③最后,互为兄弟的每一对左、右子树,在规模上相差不得超过一。
a)试按照以上描述,用C/C++定义并实现优先级搜索树结构;
b)试设计一个算法,在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;
c)试设计一个算法,利用已创建的优先级搜索树,在O(r+logn)时间内完成每次半无穷范围查询,其中r为实际命中并被报告的点数。
A、13,48
B、24,48
C、24,53
D、24,90
根结点的数据,LT和RT是括号形式的左子树和右子树。要求空树不打印任何信息,一个结点的树的打印形式是x,而不应是(x,)的形式。
A、4
B、5次
C、7次
D、10次