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

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

◇ 编辑推荐
·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元  购买