试编写一个算法，把一个新结点1作为结点s的左子女插人到一棵线索二叉树中，s原来的左子女变成1的左子女。

若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：（1)统计二叉树中叶结点的个数。（2)以二叉树为参数，交换每个结点的左子女和右子女。

有中序线索树T，结点形式为：(LL，LT, D，RT,RL)，试编写非递归算法找到数据域为A的结点，并在其左子树中插入值为Q的已知新结点X：

注意：可能A有左孩子或无左孩子，插入后考虑线索的状态应作何修改。【上海大学1998六(1 7分)】

已知一个带附加头结点的单链表中包含有三类字符（数字字符、字母字符和其他字符)，试编写一个函

数，构造三个新的单链表，使每个单链表中只包含同一类字符.要求使用原表的空间，附加头结点可以另辟空间。

链表合并成一个非递增有序的单链表，要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间，表中允许有重复的数据。

。请将哈夫曼算法推广到M叉树，构造具有最小带权外部路径长度的扩充M叉树的算法。

个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate(x) 操作时， 令元素值为x的结点的访问频度freq加1， 并将该结点前移，链接到与它的访问频度和等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。

判断一个带附加头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的（)处填人正确

的语句。

A.连接到集线器的所有结点属于一个冲突域

B.连接到集线器的结点发送数据时，将执行CSMA/CD算法

C.通过在网络链路中串接一个集线器，可以监听经过该链路的MAC帧

D.连接到集线器上的多个结点不能同时接收MAC帧

指向其直接前趋。