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

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

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

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

  1、设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成。概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?(5分)

  2、索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还需要主关键字索引?(6分)

  3、一棵前序序列为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分)

  4、构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)

  5、将两个栈存入数组V[1、、m]中应如何安排最好?这时栈空栈满的条件是什么?(6分)

  6、已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)

  二、写出用堆排序(heap sort)算法对文件F=(12,3,15,30,9,28)进行排序时,初始堆及以后每挑好一个元素重新调整后堆的状态,并指出这里的堆和败者树(tree of loser)的一个主要区别。(8分)

  三、设数组A存放一n位二进制数,试说明下列算法X的功能。假设无溢出,算法X的最坏时间复杂度是什么?分析它的平均时间复杂性。(8分)

  type Num=array[1、、n] of [0、、1];

  procedure X(var A:Num);;

  var j:integer;

  begin i:=n;;

  while A[i]=1 do

  begin

  A[i]:=0;;

  i:=i-1;

  end;

  A[i]:=1;

  end;

  四、下面是一改进了的快速分类算法:

  1、procedure qsort1(var list:afile;m,n:integer);

  2、(设list[m]、key<list[n+1]、key)

  3、var i,j,k:integer;

  4、begin

  5、while m<n do

  6、begin

  7、i:=m;j:=n+1;k:=list[m]、key;

  8、repeat

  9、repeat i:=i+1 until list[i]、key>=k;

  10、repeat j:=j-1 until list[j]、key<=k;

  11、if i<j then interchange(list[i],list[j]);;

  12、until i>=j;;

  13、interchange(list[m],list[j]);

  14、if n-j>=j-m

  15、then begin qsort1(list,m,j-1);m:=j+1;end

  16、else begin qsort1(list,j+1,n);n:=j-1;end

  17、end;(of while)

  18、end;

  问:(共20分)

  1、将第9,10行中的>=,<=分别改成>,<行吗?为什么?(5分)

  2、该排序算法稳定否,举例说明、(5分)

  3、对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用qsort1时的状态及相应m,n的值。(5分)

  4、若输入文件有n个记录,简要说明支持qsort1递归所需最大栈空间用量(设一层递归用一个单位栈空间)。(5分)

  五、给定AOE网络各事件(标号1、、n)的ee,le值和邻接表,写一算法求该AOE的所有活动(用相应边的两端点表示)的关键度(criticality)(10分)

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

◇ 编辑推荐
·2018年医学硕士辅导_刘应科团队
·2018年考研大纲汇总
·2018考研公共课网上辅导课程
·2018考研管理类联考网上辅导热招!!
·2018考研英语全程班620元_夏徛荣!
·2018考研政治全程班580元_郭继承!
 考研教育网官方微信

微信公众账号cnedu_cn

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

辅导课程

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

医学硕士

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

管理类联考

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