东南大学1996年研究生入学考试：数据结构试题
一、回答下列问题(共46分) 1、线性表(a(1),a(2),……a(n))用顺序映射表示时,a(i)与a(i 1)(1<=i<n)的物理位置相邻吗?链接表示时呢?(5分) 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,MorrisandPratt)算法中所用失败函数f的定义中,为什么要求p(1)p(2)……p(f(j))为p(1)p(2)……p(j)两头匹配的真子串?且为最大真子串?(7分) 4、在union-find问题中,控制union操作的权重(weighting)规则是何含义,有何效果?控制find操作的倒塌(collapsing)规则是何含义,有何效果?(7分) 5、堆排序(heapsort)是稳定排序吗?举例说明。(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分)页:
[1]