2023年香港特別行政區資料總結深入

1、若第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)

2、我們可用「破圈法」求解帶權連通無向圖的一棵最小代價生成樹。所謂「破圈法」就是「任取一圈，去掉圈上權最大的邊」，反覆執行這一步驟，直到沒有圈為止。請給出用「破圈法」求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細演算法，並用程式實現你所給出的演算法。

注：圈就是迴路。

3、將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。

int bpgraph (adjmatrix g)

判斷以鄰接矩陣表示的圖g是否是二部圖。

//初始化，各頂點未確定屬於那個集合

q[1]=1; r=1; s[1]=1;//頂點1放入集合s1

while(f //鄰接點入佇列

else if (s[j]==s[v]) return(0);} //非二部圖

}//if (!visited[v])

}//while

return(1); }//是二部圖

[演算法討論] 題目給的是連通無向圖，若非連通，則演算法要修改。

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)