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

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

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

  1、在磁带文件上进行二分查找行吗?为什么?(6分)

  2、分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式)。(6分)

  k:=1;i:=k;

  while i<n do

  begin k:=k+1;i=i+k;end;

  3、外排序中为什么采用k-路合并而不采用2-路合并?这种技术用于内排序有意义吗?为什么?(8分)

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

  5、满二叉检索树(full binary search tree)符合B树定义吗?B树的插入(insetb)和删除(deleteb)算法适用于满二叉检索树吗?为什么?(10分)

  6、设无向图G有n个点e条边,写一算法建立G的邻接多表(adjacency multilists),要求该算法的时间复杂性为O(n+e),且除邻接多表本身所占空间外只用O(1)辅助空间。(16分)

  7、写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度<=1+log2(n),并说明你的算法满足这一要求。(17分)

  8、定义前序排列(preorder permutation)为1,2,……n的全部二叉树的中序排列(inorder permutation)集合为IP;再定义将1,2,……n从右到左经过一个栈可得到的全部排列集合为SP.例如,当n=3,SP={123,132,213,231,321}、问:IP包含于SP成立否?证明你的结论。(16分)

  9、设记录R[i]的关键字为R[i].key(1<=i<=k),树结点T[i](1<=i<=k-1)指向败者记录,T&#0;为全胜记录下标。写一算法产生对应上述R[i](1<=i<=k)的败者树(tree of loser),要求除R[1……k]和T[0……k-1]以外,只用O(1)辅助空间。(15分)

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

微信公众账号cnedu_cn

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