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

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

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

微信公众账号cnedu_cn

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