一: 回答下列问题(共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分)
四:
设图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分)
