考研专业课：东南大学计算机真题（1998）

考研族

　　2014 考研专业课大纲已经发布，考生要对照大纲的变化好好复习，调整自己的规划。同时要关注各高校历年真题，利用真题和大纲做好考前的强化备考。文都教育 考研专业课频道为考生提供10大高校计算机复习考题，希望考生认真利用这些真题，仔细研究，寻找突破点，及时的查漏补缺，复习好计算机专业课，下面请看。
　　东南大学1998年考研试题(数据结构)
　　一:简要回答下列问题(共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=1 do
　　begin
　　A:=0;
　　i:=i-1;
　　end;
　　A:=1;
　　end;
　　四:下面是一改进了的快速分类算法:
　　1 procedure qsort1(var list:afile;m,n:integer);
　　2 (设list[m].key
　　3 var i,j,k:integer;
　　4 begin
　　5 while m
　　6 begin
　　7 i:=m;j:=n+1;k:=list[m].key;
　　8 repeat
　　9 repeat i:=i+1 until list.key>=k;
　　10 repeat j:=j-1 until list[j].key
　　11 if i
　　12 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行中的>=,,
　　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年考研专业课 计算机的数据结构真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取精确、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!
　　更多考研专业课信息关注 文都教育