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

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

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

  一、

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

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

  3、是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了。

  4、求有向图中任意一对顶点之间最短路径的弗洛伊德算法(allcosts-Floyd)中,要求有向图满足什么前提条件?

  二、在二叉树的结点结构中增加一个域:leftsize,t^.leftsize表示t结点的左子树中结点的总个数,试编写算法alloc(k),在二叉树中查找中序序号为k的结点,要求时间复杂度为O(log2(n))。

  三、编写算法输出从n个自然数中取k个(k<=n)的所有组合。例如,当n=5,k=3时,你的算法应该输出:543,542,541,532,531,521,432,431,421,321.

  四、设有向图G用邻接表的方式存储,u,v是G中的任意两个结点,写一算法,求出G中从u到v的所有简单路径。

  五、下面是一改进了的快速分类算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少?

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

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

  var i,j,k:integer;

  begin

  while m<n do

  begin

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

  repeat

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

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

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

  until i>=j;;

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

  if n-j>=j-m

  then begin qsort1(list,m,___);______;end

  else begin qsort1(list,___,n);______;end

  end;(of while)

  end;

  六、给定n*m矩阵A[a……b,c……d],并设A[i,j]<=A[i,j+1](a<=i<=b,c<=j<=d-1)和A[i,j]<=A[i+1,j](a<=i<=b-1,c<=j<=d),设计一算法以O(n+m)的时间复杂度判定值x是否在A中

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

微信公众账号cnedu_cn

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