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

《东南大学1998年研究生入学考试数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、东南大学1998年研究生入学考试数据结构试题一、简要回答下列问题（共40分）　　1、设胜者树（selectiontree）由k个记录缓冲区和k-1个非叶结点构成。概念上非叶结点表示其两个子女中关键字较小者，而实际上非叶结点存放的是什么？（5分）　　2、索引顺序存取方法（ISAM）中，主文件已按主关键字（primarykey）排序，为什么还需要主关键字索引？（6分）　　3、一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，

2、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的邻接多表（AdjacencyMultilists），并说明，若

3、已知点i，如何根据邻接多表找到与i相邻的点j？（8分）　　二、写出用堆排序（heapsort）算法对文件F=（12，3，15，30，9，28）进行排序时，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树（treeofloser）的一个主要区别。（8分）　　三、设数组A存放一n位二进制数，试说明下列算法X的功能。假设无溢出，算法X的最坏时间复杂度是什么？分析它的平均时间复杂性。（8分）　　typeNum=array[1、、n]of[0、、1]；　　procedureX（varA：

4、Num）；；　　varj：integer；　　begini：=n；；　　，n：integer）；　　2、（设list[m]、key<list[n+1]、key）　　3、vari，j，k：integer；　　4、begin　　5、<ndo　　6、begin　　7、i：=m；j：=n+1；k：=list[m]、key；　　8、repeat　　9、repeati：=i+1untillist[i]、key>=k；　　10、repeatj：=j-1untillist[j]、key<=

5、k；　　11、ifi<jtheninterchange（list[i]，list[j]）；；　　12、untili>=j；；　　13、interchange（list[m]，list[j]）；　　14、ifn-j>=j-m　　15、thenbeginqsort1（list，m，j-1）；m：=j+1；end　　16、elsebeginqsort1（list，j+1，n）；n：=j-1；end　　17、end；（of，n的值。（5分）　　4、若输入文件有n个记录，简要说明支持qso

6、rt1递归所需最大栈空间用量（设一层递归用一个单位栈空间）。（5分）　　五、给定AOE网络各事件（标号1、、n）的ee，le值和邻接表，写一算法求该AOE的所有活动（用相应边的两端点表示）的关键度（criticality）（10分）　　六、给出中序线索树的结点结构，并画出一个具有头结点和六个树结点的中序线索树，试写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析它的时间复杂性。（18分）［教育资源网］edu..，。