东南大学研究生入学考试数据结构试题

《东南大学研究生入学考试数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学一九九四年攻读硕士学位研究生入学考试试题试题编号:451试题名称:数据结构一:回答下列问题(共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的邻接多表(AdjacencyMultilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)3.欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什

2、么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?(a)插入分类  (b)快速分类  (c)合并分类  (d)堆(heap)分类  (e)基数分类(radixsort)  (8分)4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8分)二:    下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性.(15分)typeNum=array[1..n]of[0..1];procedureInc(varA:Num);varj:inte

3、ger;begini:=n;  whileA[i]=1do    A[i]:=0;i:=i-1;  end;A[i]:=1;endInc;三:    给定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分)五:    字符序列的子序列由删除该序列任意位置的任意个

4、元素而得.序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是x=abdcbcbb和y=adacbcb的最长公共子序列.设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m).(18分)_______________________________________________________________________________                  东南大学一九九五年攻读硕士学位研究生入学考试试题试题编号:451试题名称:数据结

5、构1.在磁带文件上进行二分查找行吗?为什么?(6分)2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式).(6分)k:=1;  i:=k;whilei

6、和删除(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从右到左经过一个

7、栈可得到的全部排列集合为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)的败者树(treeofloser),要求除R[1..k]和T[0..k-1]以外,只用O(1)辅助空间.(15分)_________________________________________________