东南大学数据结构考研真题1999
- 格式：pdf
- 大小：59.17 KB
- 文档页数：1
东南大学99考研题
试题科目：数据结构
一．简要回答下列问题 （共40分）
1．利用两个栈s1，s2模拟一个时，如何用栈的运算实现队列的插入删除及判队空算法。请
简述算法思想。 （7分）
2．二叉树有n个顶点，编号为1，2，3，、、、、、n设：
*T中任一定点V的编号等于左子树中最小编号减1；
*T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加1；
试描绘该二叉树。（7分）
3．设某文件经内排序后得到100个初始归并段，若使用多路归并排序算法，并要求三趟归
并完成排序，归并路数最少为多少？ （5分）
4．若一棵树中有度数为1至m的各种结点数分别为n1，n2、、、、nm（nm表示度数n为的
结点个数，试推导出该树中共有多少个叶结点n0的公式。 （8分）
5．试举例分析堆排序法是否稳定 （5分）
6．试利用KMP算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’的NEXT函数和
NEXTVAL函数。 （ 8分）
二．阅读下列算法，指出算法的功能和时间复杂性 （10分）
procedure A(h,g:pointer);
(h,g分别为单循还列表中两个结点指针)
procedure B(s,q:pointer)
var p:pointer;
begin
p:=s;
while p^.next<>q do p:=p^.next;
p^.next:=s;
end;
begin
B(h,g); B(g,h);
End;
三．已知无向图采用邻接表存储方式，试写出删除边（ i，j ）的算法。 （10分）
四．线性表中有个n元素，每个元素是一个字符，存在向量R[1。。。n]中，试一写算法， 使
其中的字符按字母字符，数字字符和其字符的顺序排列，要求利用原空间。且元素移动的
次数最少。 （15分）
五．四阶B树中（如图所述），插入关键字87，试画出插入调整 后树的形状
30 60 80
20 25 35 50 60 70 75 82 85 90
六．试编写一算法对二叉树按前序线索化 （15分）
