? ? ? ?這次學校數據結構機考，題目很奇怪，簡直讓我覺得這是算法考試……三道題，撐死了用到樹的遍歷和并查集，連個隊列都沒用，也是醉了-.-

第一題 高精度加法

　　?兩個數相加，數最多5000位，也就是和最多5001位，而且連數的長度都會給。直接兩個數組相加就好。

第二題 給出樹的前序、中序遍歷，要求寫出樹的后序遍歷。

　　?一棵樹，若知道兩種遍歷，且其中一種是中序遍歷，那么必然可以確定下這棵樹，自然也可以求出第三種遍歷。而這道題中，樹最多有26個點（還是52個？記不清了），這就是告訴我們：你們隨便搞吧，別進死循環就不會超時~~因此，我們只需要在紙上手動操作一下樣例，看看如何構造出這棵樹，然后用計算機搞定這個過程，最后后序遍歷一下就好了。

第三題 給出兩個N×M的矩陣，問只通過交換兩行和交換兩列，是否可以從其中一個矩陣構造出另一個。

?????? 分析一下這兩種操作，以交換兩行為例：操作過程中，原來是一行的那些元素，換完了還是在一行；原來是一列的那些元素，現在還是在一列。而且，還可以想到，一旦滿足這個條件，那么這兩個矩陣一定可以互相構造出來，證明略。（因為這個很明顯是對的，但是我暫時只能想到很麻煩的證明方法，所以就先不寫了，等我想到很簡潔漂亮的方法，會在此更新的。）因此，我們只要去判斷這個就好了：A矩陣中隨便取一行元素，在B矩陣中找相同的元素，應當也是在同一行；列同上。我暫時想到的有兩種方法——

?????? 方法一：并查集。在此只說行如何做，列的類似就好了。我們首先初始化并查集，然后掃一遍A矩陣，一行一行掃，把每行的所有數都合并到同一個集合。這樣搞完，兩個數如果在同一個集合中，則說明他們在A中處于同一行。此時，我們再掃一遍B矩陣，也是一行一行掃，每一行的數據判斷下是否都在同一個集合中（判斷方法隨意，保證線性即可，當然此題數據太小，此處平方級別也可以過），這樣如果全都合法，就說明B中在同一行的數據，在A中也處于同一行。如此這般，行列都做完，都合法，也就可以輸出Yes了，否則中間直接跳出輸出No便可。應當注意的是，題目本身保證了一個矩陣中沒有相同的數，在此條件之下，上面判斷過程如果都滿足，則說明兩矩陣中的元素完全一樣，這個無需單獨判斷。

?????? 方法二：存映射。如果你不想用并查集，比如你想提高效率（畢竟并查集的復雜度不是O(1)而是O(α)嘛-.-），或者覺得并查集代碼太麻煩（畢竟有四五行-.-），那么你可以考慮詳細一些。其實，我們只需要做到下面這樣就足夠了：對于A矩陣中的任意一個數，都可以瞬間找到其在B矩陣中的位置。這種思路下，我們只要掃一遍B，存一個下標0~10000的數組siteB（元素的范圍是0~10000），數組中的元素是坐標(i,j)，其意義為：siteB[x]表示x在B中的位置。而后，我們掃一遍A矩陣，一行一行掃，利用siteB數組，判斷每行元素在B中是否也位于同一行。至此，后面均同方法一，略。

　　 ?代碼有時間補上。

轉載于:https://www.cnblogs.com/icedream61/p/4184785.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的大二《数据结构》机考解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。