一、回答下列问题(共46分)

1.线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i+1)(1<=i<>

2.一棵前序序列为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分)