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

东南大学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分)

◇ 编辑推荐
·2019年医学硕士辅导
·2018年考研大纲汇总
·2019考研公共课网上辅导课程
·2019考研管理类联考网上辅导热招!!
·2019考研英语全程班620元
·2019考研政治全程班580元
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询

辅导课程

特色班精品班实验班
方案价格购买方案价格购买方案价格购买
    考研政治 方案 580元  购买 方案 1500元  购买 方案 3500元  购买
    考研英语 方案 620元  购买 方案 1500元  购买 方案 3500元  购买
    考研数学 方案 620元  购买 方案 1500元  购买 方案 3500元  购买

医学硕士

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
    中医综合 方案 420元  购买 方案 360元  购买 方案 300元  购买 方案 880元  购买
    西医综合 方案 420元  购买 方案 360元  购买 方案 300元  购买 方案 880元  购买

管理类联考

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
    管理类联考 方案 1600元  购买 方案 1600元  购买 方案 1200元  购买 方案 4500元  购买
    英语二 方案 900元  购买 方案 800元  购买 方案 800元  购买 方案 2700元  购买
    两科联报 管综+英语二(比单报 优惠1400元) 方案 5800元  购买