2023年湖北省資料總結摘要

1、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）

（1）a和d是合法序列，b和c 是非法序列。

（2）設被判定的操作序列已存入一維陣列a中。

int judge(char a)

判斷字元陣列a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。

i++; //不論a[i]是『i』或『o』，指標i均後移。}

if(j!=k)

else

演算法結束。

2、若第n件物品能放入揹包，則問題變為能否再從n-1件物品中選出若干件放入揹包（這時揹包可放入物品的重量變為s-w[n]）。若第n件物品不能放入揹包，則考慮從n-1件物品選若干件放入揹包（這時揹包可放入物品仍為s）。若最終s=0,則有一解；否則，若s<0或雖然s>0但物品數n<1,則無解。

（1）s-w[n],n-1 //knap(s-w[n],n-1)=true

（2）s,n-1knap←knap(s,n-1)

3、設有乙個陣列中存放了乙個無序的關鍵序列k1、k2、…、kn。現要求將kn放在將元素排序後的正確位置上，試編寫實現該功能的演算法，要求比較關鍵字的次數不超過n。

51. 借助於快速排序的演算法思想，在一組無序的記錄中查詢給定關鍵字值等於key的記錄。設此組記錄存放於陣列r[l..

h]中。若查詢成功，則輸出該記錄在r陣列中的位置及其值，否則顯示「not find」資訊。請編寫出演算法並簡要說明演算法思想。

4、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。

void pretopost(elemtype pre ,post,int l1,h1,l2,h2)

//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。

}//pretopost

32. .葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。

設定前驅結點指標pre，初始為空。第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。

linkedlist head,pre=null; //全域性變數

linkedlist inorder(bitree bt)

//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head

//處理第乙個葉子結點

else //將葉子結點鏈入鍊錶

inorder(bt->rchild中序遍歷左子樹

pre->rchild=null設定鍊錶尾

}return(head); } //inorder

時間複雜度為o(n),輔助變數使用head和pre,棧空間複雜度o(n)