东南大学2001年研究生入学考试：数据结构试题
二○○一年部分 一、 1、设胜者树(selectiontree)由k个记录缓冲区和k-1个非叶结点构成。概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么? 3、给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么? 5、是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了。 6、求有向图中任意一对顶点之间最短路径的弗洛伊德算法(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的所有简单路径。 五、下面是一改进了的快速分类算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少? procedureqsort1(varlist:afile；m,n:integer)； (设list[m].key<list[n 1].key) vari,j,k:integer； begin whilem<ndo begin i:=m；j:=n 1；k:=list[m].key； repeat repeati:=i 1untillist[i].key>=k;； repeatj:=j-1untillist[j].key<=k； ifi<jtheninterchange(list[i],list[j]);； untili>=j;； interchange(list[m],list[j])； ifn-j>=j-m thenbeginqsort1(list,m,___)；______；end elsebeginqsort1(list,___,n)；______；end end；(ofwhile) 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中。页:
[1]