【題目】已知一棵二叉樹按順序方式存儲在數組 A[1..n]中。設計算法求出下標分別為 i 和 j 的兩個結點的最近的公共祖先結點的值。
【來源】武漢大學2000年第五（1）題（8’）
【解答】
#inlcude <stdio.h>
parent(int A[],int i,int j)
{int k,m;
m=k=0;
if(i==1j==1A[i]==0A[j]==0i==j) // A[i]==0或A[j]==0表示不存在該結點
{printf("Error.
");return;}
while(i!=1&&j!=1){
if(i<j){j=j/2;m=1;} // 結點 j 的最近祖先結點是 ┗ j/2 ┛
else if(j<i){i=i/2;k=1;}
else if(j==i){i=j;break;} // i=j 表示找到共同祖先
}
if(j==1i==1)i=1; // i 或 j 有一個到了根結點
else if(m==0k==0)i=i/2; // m、k 中有一個為 0 ，說明在查找過程中 i 或 j 有一個沒移動
printf("The nearest common parent is A[%d].
",i);
}
【分析】本題思路是使 i 和 j 交替追趕，直到相等。
------------------------------------------------------------------------
【題目】試寫一個判別給定二叉樹是否為二叉排序樹的算法。
【來源】長沙鐵道學院98年第五（1）題（12’）
【解答】
typedef strUCt node{
char data;
struct node *left,*right;
}*T;
issorttree(T)
{
initqueue(Q); // 初始化隊列
inqueue(Q,T); // 樹根結點進隊列
while(!empty(Q)){
outqueue(Q,T);
if(T->data>T->left->data&&T->data<T->right->data){
if(T->left)inqueue(Q,T->left);
if(T->right)inqueue(Q,T->right);
}
else if(T->leftT->right)return 1; // 不符合二叉排序樹的特征，則終止並返回‘ 1 ’
}
return 0; // 是二叉排序樹，則返回 ‘0’
}
【分析】注重隊列的運用，其他如圖的廣度搜索（教材《清華 C 版》）。
------------------------------------------------------------------------------
【題目】設一單向鏈表的頭指針為head,鏈表的記錄中包含著整數類型的key域,試設計算法,
將此鏈表的記錄按照key遞增的次序進行就地排序.（不答應使用數組做輔助存儲）
【來源】中科院計算機技術研究所1999年第五（1）題 （10’）
華中理工大學2000年第八（2）題 （13’）
【解答】
typedef struct CircleList{ // 定義循環鏈表
int key;
struct CircleList *next;
}*listnode;
ListSort(listnode head)
{
int k,min,i,j;
listnode p,q,t;
p=head->next;
while(p->next!=head->next){p=p->next;k+=1;} // 統計鏈表中元素個數，保存在 K 中
p=head;j=1;
for(i=1;i<k;i++){
while(j<=i){p=p->next;j++;} // 找應填入當前最小元素的位置，該位置保存在 q 中
min=p->key;q=p; // 將當前位置元素的值設為初始最小值
while(p->next!=head->next){
if(min>p->key){min=p->key;t=p;} // 找當前最小元素，並保存在 t 所指位置中
p=p->next;
}
t->key=q->key;q->key=min;j=1; // 交換 q 位置元素和最小元素的值
}
}
【分析】本題不需要修改鏈表中的各個指針。
--------------------------------------------------------------------------
前幾天根據快速排序 Quick Sort算法的基本思想，編寫了如下分治策略的算法，供大家討論：
思路：
設輸入的序列L[p..r]，確定支點元素l[p]和l[r],並使l[p].key<=l[r].key
分解(Divide)：將序列L[p..r]劃分成三個子序列L[p..k-1]、L[k+1..m-1]和L[m+1..r]，使L[p..q]中關系為L[p..k-1]、l[k]、L[k+1..m-1]、l[m]、L[m+1..r]任一區間元素的值不大於其後區間元素的值。
遞歸求解(Conquer)：通過遞歸調用快速排序算法分別對L[p..k-1]、L[k+1..m-1]和L[m+1..r]進行排序。
算法的實現（用C語言實現）
QSort(Sqlist &L,int low,int high){
c=high-low; /*循環次數*/
if(c<10)直接調用插入排序法; /*小數時直接調用插入排序法*/
if(L.r[low].key>L.r[high].key)L.r[low]<->L.r[high]; /*確保區間內第一個元素的值不大於區間內最後一個元素的值*/
ilow=low; /*小於區間內第一個元素的值數組邊界下標*/
ihigh=high; /*大於區間內最後一個元素的值數組邊界下標*/
for(i=low+1;i<c;i++){
if(L.r[i].key<L.r[low].key)L.r[i]<->L.r[++ilow]; /*小於區間內第一個元素的值放置ilow區間內*/
else
if(L.r[i].key>L.r[high].key){
L.r[i]<->L.r[--ihigh]; /*大於區間內最後一個元素的值放置ihigh區間內*/
i--; /*下一個比較位置不變*/
c--; /*循環次數減一*/
}
}
L.r[ilow]<->L.r[low]; /*將小於區間內第一個元素的邊界下標元素與第一個元素互換*/
L.r[ihigh]<->L.r[high]; /*將大於區間內最後一個元素的邊界下標元素與最後一個元素互換*/
QSort(L,low,ilow-1);
QSort(L,ilow+1,ihigh-1);
QSort(L,ihigh+1,high);
}
void QuickSort(Sqlist &L)
{
QSort(L,1,L.length);
}
優點：
1、每次快速排序將確定二個元素位置
2、每次快速排序將劃分三個區間，優化後續平均時間和空間復雜度
缺點：
1、存在較多的元素交換（每次需要三步），不及改進快速排序法利用空穴賦值方便
--------------------------------------------------------------------------------------
四階Runge-Kutta法
一階常微分方程：
u'=f(t,u) a<t<b
u(t(0))=u(0)
Runge-Kutta非線性高階單步法，p階R-K法的整體階段誤差為O(h^p)
R-K四階算法：
u(i+1)=u(i)+h*(k1+3*k2+3*k3+k4)/8
k1=f(t(i),u(i))
k2=f(t(i+h/3),u(i+h*k1/3))
k3=f(t(i+h/3),u(i+h*k2/3))
k4=f(t(i+h),u(i+h*k3))
四階程序如下：
class RK{
private:
double k1,k2,k3,k4;
double h,b,u,a;
public:
void seth(double l=0){h=l;} //設步長
void setf(double xa=0,double xb=0,double y=0) //設初值和范圍（xa,xb）
{
b=xb;
a=xa;
u=y;
}
double f(double t,double u) //函數值，修改它以適應各自需要
{
//函數設定
double f=u-2*t/u;
return f;
}
void dork() //R-K 主函數
{
for(int count=0;count<(b-a)/h;count++)
{
k1=f(a+count*h,u);
k2=f(a+count*h+h/3,u+h*k1/3);
k3=f(a+count*h+2*h/3,u-h*k1/3+h*k2);
k4=f(a+count*h+h,u+h*k1-h*k2+h*k3);
u=u+h*(k1+3*k2+3*k3+k4)/8;
count<<u<<endl;
}
}
};
void main()
{
RK my;
my.seth(0.1);
my.setf(0,1,1);
my.dork();
}
--------------------------------------------------------------------------------------
快速排序
算法的基本思想：
快速排序的基本思想是基於分治策略的。對於輸入的子序列ap..ar，假如規模足夠小則直接進行排序，否則分三步處理：
分解(Divide)：將輸入的序列ap..ar劃分成兩個非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大於aq+1..ar中任一元素的值。
遞歸求解(Conquer)：通過遞歸調用快速排序算法分別對ap..aq和aq+1..ar進行排序。
合並(Merge)：由於對分解出的兩個子序列的排序是就地進行的，所以在ap..aq和aq+1..ar都排好序後不需要執行任何計算ap..ar就已排好序。
這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。
算法Quick_Sort的實現：
Pascal實現：
Procedure Quick_Sort(p,r:TPosition;var L:TList); {快速排序}
var
q:TPosition;
begin
if L[p..r]足夠小 then Sort(p,r,L) {若L[p..r]足夠小則直接對L[p..r]排序}
else
begin
q:=Partition(p,r,L); {將L[p..r]分解為L[p..q]和L[q+1..r]兩部分}
Quick_Sort(p,q,L); {遞歸排序L[p..q]}
Quick_Sort(q+1,r,L); {遞歸排序L[q+1..r]}
end;
end;
--------------------------------------------------------------------------------------
【題目】設中序線索二叉樹的結點結構為：leftltagdatartagright. 現已知中序線索
二叉樹的根結點地址root。設計一程序，打印出該線索二叉樹的中序遍歷結果.不得
再使用O(n)級的輔存空間。
【來源】上海交通大學96年第十題（15')
【解答】intravers(root:bitree)
finished:=false;t:=root;
while not finished do
【
while t↑.ltag=0 do t:=t↑.lch // 左孩子不空
write(t↑.data); // 訪問左孩子
if t↑.rtag=1 then
【t:=t↑.rch;{後繼結點}
write(t↑.data);{訪問當前根結點}
t:=t↑.rch{訪問當前根結點的右孩子}
】
else
t:=t↑.rch; // 右孩子不空
