一:简要回答下列问题(共32分)
1.在表达式中,有的运算符要求从右到左运算,如A^B^C的计算次序应为(A^(B^C)),
这在由中缀生成后缀的算法中是怎样实现的?(8分)
2.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的
技术特点是什么?(8分)
3.Fibonacci查找算法(fibsrch)中为什么要求m4.为什么在倒排文件(inverted
files)组织中,实际记录中的关键字域(key fields)可删除以节约空间?而在多表
(multilists)结构中这样做为什么要牺牲性能?(8分)
二:
试写一算法,建立无向图G的邻接多表(adjacency multilists),要求说明算法中主
要数据结构和变量的意义.(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分)