PAT考試重點真題選做(儘量參考學習)

NO IMAGE

因為PAT考試真題有100多道,這裡選取我做過的一些題目作為樣例,以供大家學習參考。

附件PAT.tar.gz中即為原始碼和註釋,媽的狗日CSDN還不讓傳點小檔案了還,

改為百度盤分享連結https://pan.baidu.com/s/1c2eaDt2,

萬一垃圾度娘黑了資源,請務必在評論中回覆指出,我一看到就會補種的。

./圖論演算法:

1003 無向圖Dijkstra求最大最短路(圖輸入用鄰接列表)注意詳見正文.cpp

1013 無向圖求連通數(圖輸入用鄰接列表)注意詳見正文.cpp

1018 無向圖DFS求最短路(圖輸入用鄰接列表)注意多個點權的路徑操作和最終比較.cpp

1021 無向連通圖求最長路徑端點(圖輸入用鄰接列表)注意詳見正文.cpp

1030 無向圖Dijkstra求雙邊權最短路(圖輸入用鄰接列表)注意詳見正文.cpp

1034 有向圖求連通數(圖輸入用鄰接列表)注意詳見正文.cpp

1072.cpp

1076 有向圖廣搜起點可達點集(圖輸入用鄰接列表)注意詳見正文.cpp

./二叉樹操作:

1020 二叉樹構造(樹輸入用鍵值作中序和後序構造).cpp

1043 二叉樹反轉和遍歷(樹輸入用鍵值作插入構造).cpp

1064 完全二叉樹構造(樹輸入用鍵值作中序構造).cpp

1086 二叉樹構造(樹輸入用鍵值作中序和後序構造)注意當中序遍歷時入棧為先序且出棧為中序.cpp

1099 固定結構二叉樹填充鍵值(樹輸入用行號作結點、行內是子點).cpp

1102 二叉樹反轉和遍歷(樹輸入用行號作結點、行內是子點)注意需用父點欄位找到根點.cpp

./樹狀圖搜尋:

1004 樹狀圖廣搜每層葉點計數(圖輸入用父點和子點列表).cpp

1053 樹狀圖深搜路徑點權求和(圖輸入用父點和子點列表)注意遞減排序鄰邊保證輸出順序.cpp

1079 樹狀圖廣搜葉點求和(圖輸入用行號作父點、行內是子點).cpp

1090 樹狀圖廣搜葉點計數(圖輸入用位置作子點、數值是父點).cpp

1094 樹狀圖廣搜層點計數(圖輸入用父點和子點列表).cpp

1106 樹狀圖廣搜最短葉點(圖輸入用行號作父點,行內是子點列表).cpp

浙大PAT考試技巧要點:

1. 樹狀圖:PAT 1090 1079 1094
通常題目的輸入格式有所變化,特別是PAT 1079 1090非常噁心,
    《要通過多加練習例項熟悉各種格式!》
通常題目給圖都不是二叉樹而是多叉樹,因此不適用struct Node { int left, right, parent; },
    應當改用struct Edg { int vtx, adj; }
通常題目要求都是結點深度,這實際上是廣搜距離即dsts[],但要注意層深可能從1開始(例如POJ 1094),
    也可能因為題意隱式給出從0開始(例如POJ 1079 1090),《應當特別注意層深計數問題!》
通常題目內容都是層次遍歷即廣搜遍歷,樹圖DAG可以不用vsts[],
BFS標準型:
queue<int> vq;
// svtx = 0;(可能為1,詳見題設,注意只為樹圖特用)
InitSVtx(svtx);
vq.push(svtx);
while (! vq.empty()) {
    int v = vq.front(); vq.pop();
    // vsts[v] = 1;(注意只為樹圖特用)
    DscVtx(v);
    for (int i = 0; i < edgs[v].size(); i = 1) {
        int av = edgs[v][i].adj;
        // if (vsts[av] == 0) {(注意只為樹圖特用)
            TreeEdg(v, av);
   vq.push(av);
        // }
    }
}

2. 二叉樹
通常題目的輸入格式有所變化,《特別是PAT 1102需用父點欄位找到根點》
通常都是四序遍歷,注意xords.push_back(nd)和(nodes[nd].val)
注意PAT 1043實際考察二叉樹的插入和反轉操作,《提醒練習二叉樹的基本增刪查等操作》
注意PAT 1099 1102用固定結構和鍵值構造二叉樹,
套路都是先求得結點的中序陣列,再求得鍵值的排序陣列,後對應位置賦等鍵值即可
注意PAT 1020 1086用中序和先序/後序構造二叉樹,
套路都是先在先序/後序的開首/結尾找到根點鍵值,再在中序的中間找到根點位置,
則中序根點左右兩側為左右子樹,用左右子樹的結點個數可得其在先序/後序的前後半部位置,
後遞迴尋找前後子樹區間,結束條件為區間為0

3. 圖論演算法
注意某些題目的結點序號從1開始,例如PAT 1013 1021,必須將NVTX_MAX設值增一,
同理段錯誤或異常退出通常都是NVTX_MAX不足夠大引起