一、(15分)已知三个带头结的线性链表A。B和C中的结点均已元素值自小至大非递减排列可能存在两个值相同的结点)，编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有结点。限定算法的时间复杂度为O(m+n+p)，其中m、n和p分别为三个表的长度。

　　二、(10分)画出下列广义表的存储结构图，并利用取表头和表尾的操分离出原子e

　　( a. (　(　). b )， (((e))))。

　　三、(10分写出如何判别给定序列p1，p2，。。。。。。。pn能否由车厢1，2。。。。。n经调度得到的准则，并证明之。(其中p1，p2。。。。。。pn为1，2。。。。n的一个排列)。

　　四、(10分)何谓trie树?试构造一棵对应关键字的trie树，请注意应该使树的深度尽可能小。

　　{program, programmer, programming, processor,or｝

　　五、(15分)假设串的存储结构如下所示，编写算法实现串的置换操作。

　　TYPE strrp =RECORD

　　ch:ARRAY[1..maxlen] OF char;

　　curlen:0..maxlen

　　END;

　　六、(20分)编写递归算法，依据树的双亲表示法及其根结点创建树的孩子-兄弟链表存储结构。要求写算法以前先写出这两种存储结构的类型说明。

　　七、(20分)编写对有序表进行顺序查找的算法，并写出对有序表进行顺序查找的判定树。假设每次查找时的给定为随机值，又查找成功和不成功的概率也相等，试求进行每一次查时给定值进行比较的关键字个数的期望值。