东南大学1994年研究生入学考试：数据结构试题
试题编号:451 试题名称:数据结构 一、回答下列问题(共32分) 1、最近最少使用(Least-Recently-Used)页替换是虚拟存储系统中常用的策略,试说明如何利用一页链接表时刻跟踪最近最少使用页?(8分) 2、已知无向图G,V(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},试画出G的邻接多表(AdjacencyMultilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分) 3、欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法? (a)插入分类(b)快速分类(c)合并分类(d)堆(heap)分类(e)基数分类(radixsort)(8分) 4、构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分) 二、下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性。(15分) typeNum=array[1..n]of[0..1]； procedureInc(varA:Num);； varj:integer； begini:=n;； whileA[i]=1do A[i]:=0；i:=i-1； end； A[i]:=1； endInc； 三、给定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中。(17分) 四、设图G有n个点,利用从某个源点到其余各点最短路径算法思想,设计一产生G的最小生成树的算法。(18分) 五、字符序列的子序列由删除该序列任意位置的任意个元素而得。序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是x=abdcbcbb和y=adacbcb的最长公共子序列。设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m)。(18分)页:
[1]