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

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

◇ 编辑推荐
·2019年医学硕士辅导
·2018年考研大纲汇总
·2019考研公共课网上辅导课程
·2019考研管理类联考网上辅导热招!!
·2019考研英语全程班620元
·2019考研政治全程班580元
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询

辅导课程

特色班精品班实验班
方案价格购买方案价格购买方案价格购买
    考研政治 方案 580元  购买 方案 1500元  购买 方案 3500元  购买
    考研英语 方案 620元  购买 方案 1500元  购买 方案 3500元  购买
    考研数学 方案 620元  购买 方案 1500元  购买 方案 3500元  购买

医学硕士

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
    中医综合 方案 420元  购买 方案 360元  购买 方案 300元  购买 方案 880元  购买
    西医综合 方案 420元  购买 方案 360元  购买 方案 300元  购买 方案 880元  购买

管理类联考

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
    管理类联考 方案 1600元  购买 方案 1600元  购买 方案 1200元  购买 方案 4500元  购买
    英语二 方案 900元  购买 方案 800元  购买 方案 800元  购买 方案 2700元  购买
    两科联报 管综+英语二(比单报 优惠1400元) 方案 5800元  购买