一、回答下列问题(共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的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)

3.欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?

(a)插入分类(b)快速分类(c)合并分类(d)堆(heap)分类(e)基数分类

(radix sort) (8分)4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)

二、下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性.(15分)

type Num=array[1..n] of [0..1];

procedure Inc(var A:Num);

var j: integer;

begin i:=n;

while A[i]=1 do

A[i]:=0;i:=i-1;

end;

A[i]:=1;

end Inc;

三、给定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分)<=a[i+1,j](a<=i<=b-1,c<=j<=d),<><=a[i,j+1](a<=i<=b,c<=j<=d-1)<>

四、设图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分)