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

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

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