1、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）
（1）下面所示的序列中哪些是合法的？
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
2、给出折半查找的递归算法，并给出算法时间复杂度性分析。
3、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。 4、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。
typedef struct
{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack;
stack s[],s1[];//栈，容量够大
BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0)
{while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下
if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。
for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝
while(top!=0 && s[top].tag==1) top--; //退栈
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历 }//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor
5、假设K1，„，Kn是n个关键词，试解答：
试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
6、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）
7、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
