设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表 ...

李老师

设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表
中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
二、解答题（20分）
(一)       
已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。

三、画图题（20分）
(一)       
设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。







第二组：
一、编程题（每小题30分，共60分）
(一)       
已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。