一:简要回答下列问题(共40分)
1.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶
结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么?(5分)
2.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还
需要主关键字索引?(6分)
3.一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的
前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树
.(7分)
4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不
如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)
5.将两个栈存入数组V[1..m]中应如何安排最好?这时栈空栈满的条件是什么?(6分
)
6.已知无向图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分)
二:
写出用堆排序(heap sort)算法对文件F=(12,3,15,30,9,28)进行排序时,初始堆及
以后每挑好一个元素重新调整后堆的状态,并指出这里的堆和败者树(tree of
loser)的一个主要区别.(8分)
三:
设数组A存放一n位二进制数,试说明下列算法X的功能.假设无溢出,算法X的最坏时
间复杂度是什么?分析它的平均时间复杂性.(8分)
type Num=array[1..n] of [0..1];
procedure X(var A:Num);
var j: integer;
begin i:=n;
while A[i]=1 do
begin
A[i]:=0;
i:=i-1;
end;
A[i]:=1;
end;
四:
下面是一改进了的快速分类算法:
1 procedure qsort1(var list:afile;m,n:integer);
2 (设list[m].key3 var i,j,k:integer;
4 begin
5 while m6 begin
7 i:=m;j:=n+1;k:=list[m].key;
8 repeat
9 repeat i:=i+1 until list[i].key>=k;
10 repeat j:=j-1 until list[j].key<=k;
11 if i12 until i>=j;
13 interchange(list[m],list[j]);
14 if n-j>=j-m
15 then begin qsort1(list,m,j-1);m:=j+1;end
16 else begin qsort1(list,j+1,n);n:=j-1;end
17 end;(of while)
18 end;
问: (共20分)
1.将第9,10行中的>=,<=分别改成>,<行吗?为什么?(5分)
2.该排序算法稳定否,举例说明.(5分)
3.对输入文件(22,3,30,4,60,11,58,18,40,16),列表表示该文件在每次调用
qsort1时的状态及相应m,n的值.(5分)
4.若输入文件有n个记录,简要说明支持qsort1递归所需最大栈空间用量(设一层递
归用一个单位栈空间).(5分)
五:
给定AOE网络各事件(标号1..n)的ee,le值和邻接表,写一算法求该AOE的所有活动(
用相应边的两端点表示)的关键度(criticality).(10分)
六:
给出中序线索树的结点结构,并画出一个具有头结点和六个树结点的中序线索树,试
写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析它的时间复杂
性.(18分)
东南大学1998年考研真题-数据结构试题
本站小编 FreeKaoyan/2018-01-22
相关话题/考研真题 东南大学 试题 数据结构
东南大学1997年考研真题-数据结构试题
一:简要回答下列问题(共32分)1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分)2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分)3.Fibonacci查找 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-管理原理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-光学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-电子线路基础
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-管理学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-电磁场理论
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-电动力学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-半导体物理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-薄膜物理与技术
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2004年考研真题-历史
一名词解释雅典卫城巴黎圣母院佛光寺大殿包豪斯帆拱举折屋面画法叉柱造天坛五色图圣马可广场里坊制二简答题谈谈西方近现代建筑思潮谈谈设计结合自然并举例说明 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2001年考研真题-半导体集成电路
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2003年考研真题-中外建筑史和城建史
东大的中外建筑史和城建史2003年的考题考六道主观题,其中选5题做。1:试论述比较古代长安城和北京城。2:试论述雅典卫城的布局、经验手法和单体成就。3:试论述中国古建筑的形式特征和屋顶。4:试论述西方古典建筑的起源和发展。5:试论述霍华德的规划理论和现代城市理论。6:谈现代西方建筑思潮。(每题30分 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2004年考研真题-规划设计附多张精美图片
1.某中学规划设计.(只要求总图A2大小)2.小别墅空间设计.(平立剖)3.别墅效果图题型分布大约有:填空20分名词解释30左右画图题大约占50分左右最后大题部分占50分总共150应各位同学要求,版主特精选了部分东大学生的优秀作业,与大家分享!内容:南京某单位为关心青少年课余活动,拟在市内某风景优美 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2002年考研真题-西方经济学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22东南大学2002年考研真题-信号与系统
专业课考研经验 本站小编 FreeKaoyan 2018-01-22