您的位置:考研教育网>  > 考试大纲 > 考研专业课 正文

东南大学1996年研究生入学考试数据结构试题

   2007-01-19 15:53 【 】【我要纠错

  一、回答下列问题(共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,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分)

◇ 编辑推荐
·2016年考研调剂信息汇总(更新中)
·2016年考研国家线
·2017考研网上辅导招生简章
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询
考研网上辅导课程 精品班 实验班
学费 购买 学费 购买
公共课 政 治 1500元 购买 3500元 购买
英 语 1500元 购买 3500元 购买
数 学 1500元 购买 3500元 购买
专业课 考研名师编写,网校独创考研管理类、法律类、教育等专业课电子书正在热卖!