2010年香港特别行政区数据分析深入

1、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)

//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。

{if(h1>=l1)

{post[h2]=pre[l1]; //根结点

half=(h1-l1)/2; //左或右子树的结点数

PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列

} }//PreToPost

32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

LinkedList head,pre=null; //全局变量

LinkedList InOrder(BiTree bt)

//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head

{if(bt){InOrder(bt->lchild); //中序遍历左子树

if(bt->lchild==null && bt->rchild==null) //叶子结点

if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点

else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表

InOrder(bt->rchild); //中序遍历左子树

pre->rchild=null; //设置链表尾

}

return(head); } //InOrder

时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)

2、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j]

void search(datatype A[ ][ ], int a,b,c,d, datatype x)

//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.

{i=a; j=d; flag=0; //flag是成功查到x的标志

while(i<=b && j>=c)

if(A[i][j]==x) {flag=1;break;}

else if (A[i][j]>x) j--; else i++;

if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.

else printf(“矩阵A中无%d 元素”，x)；

}算法search结束。

[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x

3、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。

4、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。

48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）