一:回答下列问题(共46分)
1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i2.一棵前序
序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为
1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树.(7分)
3.在模式匹配KMP(Knuth,Morris and Pratt)算法中所用失败函数f的定义中,为什
么要求p(1)p(2)……p(f(j))为p(1)p(2)……p(j)两头匹配的真子串?且为最大真子
串?(7分)
4.在union-find问题中,控制union操作的权重(weighting)规则是何含义, 有何效
果?控制find操作的倒塌(collapsing)规则是何含义,有何效果?(7分)
5.堆排序(heap sort)是稳定排序吗?举例说明.(6分)
6.给定输入文件:101,48,19,65,3,74,33,17,21,20,99,53,24,并设记录缓冲区个数
k=4,写出基于败者树的外排序顺串生成算法runs输出的顺串.(6分)
7.m阶B树中,m大小的确定与什么因素有关?(8分)
二:
设结点结构为:| data | link |,试用一个全局指针p和某种链接结构实现一个队列
,画出示意图,并给出入队和出队deleteq过程,要求它们的时间复杂性都是O(1)(不
计new和dispose时间).(10分)
三:
设有向图G有n个点(用1,2,……n表示),e条边,写一算法根据G的邻接表生成反向邻
接表,要求时间复杂性为O(n+e).(13分)
四:
设二叉树结点结构为:| left | data | bf | right |,定义二叉树结点T的平衡因
子bf(T)=h(左)-h(右),写一递归算法确定二叉树tree中所有节点的平衡因子bf,同
时返回二叉树tree中非叶结点个数.(15分)
五:
设符号表T重的标识符x满足1<=x<=m,且n为对T表的最大插入次数.设计符号表T的表
示结构,允许使用O(m+n)空间,并写出T的初始化(init),查找(search),插入
(insert)和删除(delete)算法,要求它们的时间复杂性都是O(1).(16分)