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

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

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

  一、简要回答下列问题(共32分)

  1、在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分)

  2、给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分)

  3、Fibonacci查找算法(fibsrch)中为什么要求m<F(a-1),试用图示说明。(8分)

  4、为什么在倒排文件(inverted files)组织中,实际记录中的关键字域(key fields)可删除以节约空间?而在多表(multilists)结构中这样做为什么要牺牲性能?(8分)

  二、试写一算法,建立无向图G的邻接多表(adjacency multilists),要求说明算法中主要数据结构和变量的意义。(15分)

  三、给出中序线索树的结点结构并画出一个具有头结点的中序线索树,使其树结点至少应有6个,写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析其时间复杂性。(18分)

  四、若S是n个元素的集合,则S的幂集P(S)定义为S的所有子集的集合。例如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}.给定S,写一递归算法求P(S)。(15分)

  五、已知在llink-rlink存储法表示的二叉树中,指针t指向该二叉树的根结点,指针p,q分别指向树中的二个结点,试写一算法,求距离这两个结点最近的共同的祖先结点。(20分)

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

微信公众账号cnedu_cn

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