文档介绍：北京大学信息学院 2007 年秋季学期《数据结构与算法 A(实验班)》课程作业
第 13 次作业,高级数据结构选做题,可以不交。

利用广义表的 Head 和Tail 运算,把原子 d 分别从下列广义表中分离出来,L1=
(((((a),b),d),e));L2=(a,(b,((d)),e))。
设计一个算法,判断两个广义表是否相等。
组织成循环链表的可利用空间表附加什么条件时,首次适配策略就转变为最佳适配策
略?
将关键码 1,2,3,...,(2k-1)依次插入到一棵初始为空的 AVL 树中,试证明结果是
一棵高度为 k 的完全满二叉树。
已知元素个数为 12 的字典,其元素集合为∶
{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec}
(1) 试按元素的次序依次插入一棵初始时为空的二叉搜索树,请画出插入完成之后的二
叉搜索树,并求其在等概率情况下查找成功的平均查找长度。
(2) 按元素顺序构造一棵 AVL 树,并求其在等概率情况下查找成功的平均查找长度。
使用 Trie 数据结构设计一个程序对变长字符串排序,程序所做的工作与所有字符串中
字母总数要成比例。有些字符串可能很长,而大多数则很短。
对于一段英文材料,构造 PATRICIA 树,并统计每个字母出现的次数。
一个字符串的后缀字符串( suffix strings )集合包括这个字符串本身,这个字符串去掉第
1 个字符得到的字母串,这个字符串去掉前 2 个字符得到的字符串,等等。例如,
“HELLO”的后缀字符串集合是:
{ HELLO,ELLO,LLO,LO,O }.
一个后缀树( suffix tree )是对于一个给定字符串,包含其所有后缀字符串的 PAT Trie
结构。后缀树的好处是它允许使用通配符( wildcard )对字符串进行检索。例如,检索关
键码“EL∗”表示找到所有以“EL*”作为前两个字符的字符串。这可以很容易地使用一个普
通 Trie 结构实现。在一个普通 Trie 结构中检索“*EL”效率很低,但是在一个后缀树中却
是高效率的。对于一个词典中的单词或短语实现后缀树。
利用半伸展树,存储文件中单词词频。
半伸展(semi-splaying)树是伸展树的变体,它对于同构的“一字型”(zig-zig 型)的情况
(即类似于 AV L 树的 LL、RR 型的情况)只需要进行一次单旋转;而且,已经处理过的结
点不参与下一轮的伸展,而从结点的父结点位置开始旋转。如图 1 所示:
假设 T 是当前被访问的结点,核心算法如下:
While T 不是根结点{
if (T 的父结点是根)
进行一次单一旋转;
else if (T 与其前驱是同构的“一字型”) {
进行一次同构旋转(即先将其父绕祖旋转,图中 S 绕 R);
T = T->parent;(即把 T 的父 S 看作 T 再从头处理,就像图中使 Q
绕 p);
}
else (如