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

　　一、

　　1、设胜者树（selection tree）由k个记录缓冲区和k-1个非叶结点构成。概念上非叶结点表示其两个子女中关键字较小者，而实际上非叶结点存放的是什么？

　　2、给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？

　　3、是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题，具体题目记不得了。

　　4、求有向图中任意一对顶点之间最短路径的弗洛伊德算法（allcosts-Floyd）中，要求有向图满足什么前提条件？

　　二、在二叉树的结点结构中增加一个域：leftsize，t^.leftsize表示t结点的左子树中结点的总个数，试编写算法alloc（k），在二叉树中查找中序序号为k的结点，要求时间复杂度为O（log2（n））。

　　三、编写算法输出从n个自然数中取k个（k<=n）的所有组合。例如，当n=5，k=3时，你的算法应该输出：543，542，541，532，531，521，432，431，421，321.

　　四、设有向图G用邻接表的方式存储，u，v是G中的任意两个结点，写一算法，求出G中从u到v的所有简单路径。

　　五、下面是一改进了的快速分类算法，试补充其中的空白语句，并分析该算法所需的最大递归空间是多少？

　　procedure qsort1（var list：afile；m，n：integer）；

　　（设list[m].key　　var i，j，k：integer；

　　begin

　　while m　　begin

　　i：=m；j：=n+1；k：=list[m].key；

　　repeat

　　repeat i：=i+1 until list[i].key>=k；；

　　repeat j：=j-1 until list[j].key<=k；

　　if i　　until i>=j；；

　　interchange（list[m]，list[j]）；

　　if n-j>=j-m

　　then begin qsort1（list，m，___）；______；end

　　else begin qsort1（list，___，n）；______；end

　　end；（of while）

　　end；

　　六、给定n*m矩阵A[a……b，c……d]，并设A[i，j]<=A[i，j+1]（a<=i<=b，c<=j<=d-1）和A[i，j]<=A[i+1，j]（a<=i<=b-1，c<=j<=d），设计一算法以O（n+m）的时间复杂度判定值x是否在A中