东南大学1995年研究生入学考试：数据结构试题
1、在磁带文件上进行二分查找行吗?为什么?(6分) 2、分析确定下列程序中语句k:=k 1执行次数与n所成的数量级关系(即表示为O(f(n))的形式)。(6分) k:=1；i:=k； whilei<ndo begink:=k 1；i=i k；end； 3、外排序中为什么采用k-路合并而不采用2-路合并?这种技术用于内排序有意义吗?为什么?(8分) 4、索引顺序存取方法(ISAM)中，主文件已按主关键字(primarykey)排序，为什么还需要主关键字索引?(6分) 5、满二叉检索树(fullbinarysearchtree)符合B树定义吗?B树的插入(insetb)和删除(deleteb)算法适用于满二叉检索树吗?为什么?(10分) 6、设无向图G有n个点e条边，写一算法建立G的邻接多表(adjacencymultilists)，要求该算法的时间复杂性为O(n e)，且除邻接多表本身所占空间外只用O(1)辅助空间。(16分) 7、写一改进的递归快速排序算法，要求对于n个记录，该算法的递归深度<=1 log2(n)，并说明你的算法满足这一要求。(17分) 8、定义前序排列(preorderpermutation)为1，2，……n的全部二叉树的中序排列(inorderpermutation)集合为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)的败者树(treeof
loser)，要求除R[1..k]和T[0..k-1]以外，只用O(1)辅助空间。(15分)
页:
[1]