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&#0;为全胜记录下标.写一算法产生对应上述r[i](1<=i<=k)的败者树(tree ofloser),要求除r[1..k]和t[0..k-1]以外,只用o(1)辅助空间.(15分)