东南大学1997年研究生入学考试：数据结构试题
一、简要回答下列问题(共32分) 1、在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),这在由中缀生成后缀的算法中是怎样实现的?(8分) 2、给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么?(8分) 3、Fibonacci查找算法(fibsrch)中为什么要求m<F(a-1),试用图示说明。(8分) 4、为什么在倒排文件(invertedfiles)组织中,实际记录中的关键字域(keyfields)可删除以节约空间?而在多表(multilists)结构中这样做为什么要牺牲性能?(8分) 二、试写一算法,建立无向图G的邻接多表(adjacencymultilists),要求说明算法中主要数据结构和变量的意义。(15分) 三、给出中序线索树的结点结构并画出一个具有头结点的中序线索树,使其树结点至少应有6个,写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析其时间复杂性。(18分) 四、若S是n个元素的集合,则S的幂集P(S)定义为S的所有子集的集合。例如,S=(a,b,c),P(S)={(),(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}。给定S,写一递归算法求P(S)。(15分) 五、已知在llink-rlink存储法表示的二叉树中,指针t指向该二叉树的根结点,指针p,q分别指向树中的二个结点,试写一算法,求距离这两个结点最近的共同的祖先结点。(20分)页:
[1]