1.在磁带文件上进行二分查找行吗?为什么?(6分)
2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为
O(f(n))的形式).(6分)
k:=1; i:=k;
while ibegin k:=k+1; i=i+k; end;
3.外排序中为什么采用k-路合并而不采用2-路合并?这种技术用于内排序有意义吗
?为什么?(8分)
4.索引顺序存取方法(ISAM)中,主文件已按主关键字(primary key)排序,为什么还
需要主关键字索引?(6分)
5.满二叉检索树(full binary search tree)符合B树定义吗?B树的插入(insetb)和
删除(deleteb)算法适用于满二叉检索树吗?为什么?(10分)
6.设无向图G有n个点e条边,写一算法建立G的邻接多表(adjacency multilists),要
求该算法的时间复杂性为O(n+e),且除邻接多表本身所占空间外只用O(1)辅助空间
.(16分)
7.写一改进的递归快速排序算法,要求对于n个记录,该算法的递归深度
<=1+log2(n),并说明你的算法满足这一要求.(17分)
8.定义前序排列(preorder permutation)为1,2,……n的全部二叉树的中序排列
(inorder permutation)集合为IP;再定义将1,2,……n从右到左经过一个栈可得到
的全部排列集合为SP.例如,当n=3,SP={123,132,213,231,321}.问:IP包含于SP成立
否?证明你的结论.(16分)
9.设记录R[i]的关键字为R[i].key(1<=i<=k),树结点T[i](1<=i<=k-1)指向败者记
录,T�为全胜记录下标.写一算法产生对应上述R[i](1<=i<=k)的败者树(tree of
loser),要求除R[1..k]和T[0..k-1]以外,只用O(1)辅助空间.(15分)
