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

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

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

  一、简要回答下列问题(共40分)

  1、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。(6分)

  2、简单比较文件的多重表和倒排表组织方式各自的特点。(6分)

  3、画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程。(6分)

  4、找出所有满足下列条件的二叉树6分)

  a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;

  b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;

  c)它们在先序遍历和后序遍历时,得到的结点访问序列相同。

  5、对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行多少次比较?(8分)

  6、已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段。试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的次数。(8分)

  二、已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点。(10分)

  a)在P结点后插入S结点的语句序列是______

  b)在P结点前插入S结点的语句序列是______

  c)在表首插入S结点的语句序列是______

  d)在表尾插入S结点的语句序列是______

  (1)P^.next:=S;

  (2)P^.next:=P^.next^.next;

  (3)P^.next:=S^.next;

  (4)S^.next:=P^.next;

  (5)S^.next:=L;

  (6)S^.next:=NIL;

  (7)Q:=P;

  (8)WHILE P^.next<>Q DO P:=P^.next;

  (9)WHILE P^.next<>NIL DO P:=P^.next;

  (10)P:=Q;

  (11)P:=L;

  (12)L:=S;

  (13)L:=P;

  三、设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个标识符X的操作在O(1)的时间内。假设1<=x<=m,n为要插入的个数,所需空间为m+n.(10分)

  四、试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程中各步的状态。(10分)

  ____________

  / 4 \

  ↓6 \

  b——→e___9 \

  15↑↑\ /

  / 2 /8↓/

  a——→c g(和严蔚敏习题集上题目相同)

\ \4 ↑↑

  12↓5↓10/ /

  d←——f__/ /

\___________/

  3

  五、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。(15分)

  六、写出按后序序列遍历中序线索树的算法。(15分)

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

微信公众账号cnedu_cn

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