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

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

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

  试题编号:451

  试题名称:数据结构

  一、回答下列问题(共32分)

  1、最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说明如何利用一页链接表时刻跟踪最近最少使用页?(8分)

  2、已知无向图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分)

  3、欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?

  (a)插入分类(b)快速分类(c)合并分类(d)堆(heap)分类(e)基数分类(radix sort)(8分)

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

  二、下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性。(15分)

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

  procedure Inc(var A:Num);;

  var j:integer;

  begin i:=n;;

  while A[i]=1 do

  A[i]:=0;i:=i-1;

  end;

  A[i]:=1;

  end Inc;

  三、给定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中。(17分)

  四、设图G有n个点,利用从某个源点到其余各点最短路径算法思想,设计一产生G的最小生成树的算法。(18分)

  五、字符序列的子序列由删除该序列任意位置的任意个元素而得。序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大。例如,adcbcb是x=abdcbcbb和y=adacbcb的最长公共子序列。设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m)。(18分)

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

微信公众账号cnedu_cn

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