![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
试利用栈实现一个广义表建立的算法,要求从键盘输人一个用字符串表示的广义表,建立它的广义表
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
所谓半无穷范围查询(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,B为线性表C的算法,即使得
线性表A,B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。
假设在算法描述语言中引入指针的二元运算“异或”,若a和b为指针,则的运算结果仍为原指针类型,且
则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域:data域和LRPtr域,其中L RPtr域存放该结点的左邻与右邻结点指针(不存在时为NULL) 的异或。若设指针L.Left指向链表中的最左结点,L.Right指向链表中的最右结点, 则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
A.先进先出分配算法
B.最先适应分配算法
C.最优适应分配算法
D.最坏适应分配算法
已知Ackerman函数定义如下:
(1)根据定义,写出它的递归求解算法;
(2)利用栈,写出它的非递归求解算法。