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

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

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

  注意事项:

    (1)答卷上需写清题号,不必抄题;回答问题字迹工整,卷面清洁。

    (2)编程中所用的数据结构及主要变量需加以说明,必要时程序中加以注释。

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

  1、利用两个栈s1,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空运算。请简述算法思想。(7分)

  2、二叉树有n个顶点,编号为1,2,3,……n,设:

  T中任一顶点V的编号等于左子树中最小编号减一;

  T中任一顶点V的右子树中最小编号等于其左子树中最大编号加一;

  试描绘该二叉树。(7分)

  3、设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,并要求三趟归并完成排序,归并路数最少为多少?(5分)

  4、若一棵树中有度数为1至m的各种结点数分别为n1,n2,……nm(nm表示度数为m的结点个数),请推导出该树中共有多少个叶结点n0的公式。(8分)

  5、试举例分析,堆排序法是否稳定。(5分)

  6、试利用KMP算法和改进算法分别求p1=‘abcabaa’和p2=‘aabbaab’的NEXT函数和NEXTVAL函数。(8分)

  二、阅读下列算法,指出算法A的功能和时间复杂性。(10分)

  procedure A(h,g:pointer);

  (h,g分别为单循环链表(single linked circular list)中两个结点指针)

  procedure B(s,q:pointer);

  var p:pointer;

  begin

  p:=s;

  while p^.next<>q do p:=p^.next;

  p^.next:=s;

  end;(of B)

  begin

  B(h,g);B(g,h);

  end;(of A)

  三、已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法。(10分)

  四、线性表中有n个元素,每个元素是一个字符,存在向量R[1……n]中,试写一个算法,使R中的字符按字母字符,数字字符和其它字符的顺序排列。要求利用原空间,且元素移动次数最少。(15分)

  五、四阶B树中(如图所示),插入关键字87,试画出插入调整后树的形状。(10分)

  |30 60 80|

  / / \ \

  |20 25| |35 50| |60 70 75| |82 85 90|

  六、试编写一算法对二叉树按前序线索化。(15分)

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

微信公众账号cnedu_cn

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