东南大学1999年研究生入学考试：数据结构试题
注意事项: (1)答卷上需写清题号,不必抄题；回答问题字迹工整,卷面清洁。 (2)编程中所用的数据结构及主要变量需加以说明,必要时程序中加以注释。 一、简要回答下列问题(共40分) 1、利用两个栈s1,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空运算.请简述算法思想。(7分) 2、二叉树有n个顶点,编号为1,2,3,……n,设: T中任一顶点V的编号等于左子树中最小编号减一； T中任一顶点V的右子树中最小编号等于其左子树中最大编号加一； 试描绘该二叉树。(7分) 3、设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,并要求三趟归并完成排序,归并路数最少为多少?(5分) 4、若一棵树中有度数为1至m的各种结点数分别为n1,n2,...nm(nm表示度数为m的结点个数),请推导出该树中共有多少个叶结点n0的公式。(8分) 5、试举例分析,堆排序法是否稳定。(5分) 6、试利用KMP算法和改进算法分别求p1='abcabaa'和p2='aabbaab'的NEXT函数和NEXTVAL函数。(8分) 二、阅读下列算法,指出算法A的功能和时间复杂性。(10分) procedureA(h,g:pointer)； (h,g分别为单循环链表(singlelinkedcircularlist)中两个结点指针) procedureB(s,q:pointer)； varp:pointer； begin p:=s； whilep^.next<>qdop:=p^.next； p^.next:=s； end；(ofB) begin B(h,g)；B(g,h)； end；(ofA) 三、已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法。(10分) 四、线性表中有n个元素,每个元素是一个字符,存在向量R[1..n]中,试写一个算法,使R中的字符按字母字符,数字字符和其它字符的顺序排列.要求利用原空间,且元素移动次数最少。(15分) 五、四阶B树中(如图所示),插入关键字87,试画出插入调整后树的形状。(10分) |306080| //\\ |2025||3550||607075||828590| 六、试编写一算法对二叉树按前序线索化。(15分)页:
[1]