PAT (Advanced Level) Practice（更新中）

超、凢脫俗 2021-12-20 06:31 295阅读 0赞

Source:

PAT (Advanced Level) Practice

Reference:

[1]胡凡,曾磊.算法笔记[M].机械工业出版社.2016.7

Outline:

  • 基础数据结构：

    • 线性表：栈，队列，链表，顺序表
    • 树：二叉树的建立和遍历，完全二叉树，二叉查找树，平衡二叉树，堆，哈夫曼树
    • 图：图的存储和遍历

  • 经典高级算法：

    • 深度优先搜索，广度优点搜索，回溯剪枝
    • 贪心，并查集，哈希映射
    • 最短路径（只考察过单源），拓扑排序（18年9月第一次涉及相关概念，未正式考过），关键路径（未考过）

  • 实现对复杂实际问题的模拟求解

    • 模拟题

Catalogue:

  • PAT A1155 Heap Paths (30 分)【完全二叉树】【堆】【深度优先搜索】
  • PAT A1154 Vertex Coloring (25 分)【图的存储和遍历】【哈希映射】
  • PAT A1153 Decode Registration Card of PAT (25 分)【模拟题】
  • PAT A1152 Google Recruitment (20 分)【素数】
  • PAT A1151 LCA in a Binary Tree (30 分)【二叉树的建立】【二叉树的遍历】
  • PAT A1150 Travelling Salesman Problem (25 分)【图的存储和遍历】
  • PAT A1149 Dangerous Goods Packaging (25 分)【哈希映射】
  • PAT A1148 Werewolf - Simple Version (20 分)【模拟题】
  • PAT A1147 Heaps (30 分)【堆】【二叉树的遍历】
  • PAT A1146 Topological Order (25 分)【图的存储和遍历】【拓扑排序】
  • PAT A1145 Hashing - Average Search Time (25 分)【哈希映射】
  • PAT A1144 The Missing Number (20 分)【哈希映射】
  • PAT A1143 Lowest Common Ancestor (30 分)【二叉查找树】【二叉树的建立】【二叉树的遍历】
  • PAT A1142 Maximal Clique (25 分)【图的存储和遍历】
  • PAT A1141 PAT Ranking of Institutions (25 分)【模拟题】
  • PAT A1140 Look-and-say Sequence (20 分)【模拟题】
  • PAT A1138 Postorder Traversal (25 分)【二叉树的遍历】
  • PAT A1137 Final Grading (25 分)【模拟题】
  • PAT A1136 A Delayed Palindrome (20 分)【模拟题】
  • PAT A1135 Is It A Red-Black Tree (30 分)【二叉查找树】
  • PAT A1134 Vertex Cover (25 分)【图的存储和遍历】
  • PAT A1133 Splitting A Linked List (25 分）【链表】【哈希映射】
  • PAT A1132 Cut Integer (20 分)【模拟题】
  • PAT A1129 Recommendation System (25 分)【模拟题】
  • PAT A1128 N Queens Puzzle (20 分)【模拟题】
  • PAT A1127 ZigZagging on a Tree (30 分)【二叉树的建立】【二叉树的遍历】
  • PAT A1126 Eulerian Path (25 分)【图的存储和遍历】
  • PAT A1125 Chain the Ropes (25 分)【哈夫曼树】【贪心】
  • PAT A1123 Is It a Complete AVL Tree (30 分)【平衡二叉树】【完全二叉树】【二叉树的遍历】
  • PAT A1122 Hamiltonian Cycle (25 分)【图的存储和遍历】
  • PAT A1120 Friend Numbers (20 分)【模拟题】
  • PAT A1119 Pre- and Post-order Traversals (30 分)【二叉树的建立】
  • PAT A1118 Birds in Forest (25 分)【并查集】
  • PAT A1116 Come on! Let’s C (20 分)【素数】
  • PAT A1115 Counting Nodes in a BST (30 分)【二叉查找树】
  • PAT A1114 Family Property (25 分)【并查集】
  • PAT A1113 Integer Set Partition (25 分)【模拟题】
  • PAT A1111 Online Map (30 分)【最短路径】
  • PAT A1110 Complete Binary Tree (25 分)【完全二叉树】
  • PAT A1109 Group Photo (25 分)【模拟题】
  • PAT A1108 Finding Average (20 分)【字符串处理】
  • PAT A1107 Social Clusters (30 分)【并查集】
  • PAT A1106 Lowest Price in Supply Chain (25 分)【二叉树的建立和遍历】
  • PAT A1105 Spiral Matrix (25 分)【模拟题】
  • PAT A1099 Build A Binary Search Tree (30 分)【二叉树的建立】【二叉树的遍历】【二叉查找树】
  • PAT A1098 Insertion or Heap Sort (25 分)【堆】【插入排序】
  • PAT A1094 The Largest Generation (25 分)【二叉树的建立和遍历】
  • PAT A1090 Highest Price in Supply Chain (25 分)【二叉树的建立和遍历】
  • PAT A1087 All Roads Lead to Rome (30 分)【最短路径】
  • PAT A1079 Total Sales of Supply Chain (25 分)【二叉树的建立和遍历】
  • PAT A1078 Hashing (25 分)【哈希映射】【素数】
  • PAT A1076 Forwards on Weibo (30 分)【图的存储和遍历】【广度优先搜索】
  • PAT A1072 Gas Station (30 分)【最短路径】
  • PAT A1066 Root of AVL Tree (25 分)【平衡二叉树】
  • PAT A1064 Complete Binary Search Tree (30 分)【完全二叉树】【二叉查找树】【二叉树的遍历】
  • PAT A1053 Path of Equal Weight (30 分)【二叉树的建立和遍历】
  • PAT A1043 Is It a Binary Search Tree (25 分)【二叉查找树】【二叉树的建立】【二叉树的遍历】
  • PAT A1034 Head of a Gang (30 分)【图的存储和遍历】【深度优先搜索】
  • PAT A1030 Travel Plan (30 分)【最短路径】
  • PAT A1021 Deepest Root (25 分)【图的存储和遍历】【深度优先搜索】
  • PAT A1018 Public Bike Management (30 分)【最短路径】
  • PAT A1015 Reversible Primes (20 分)【进制转换】【素数】
  • PAT A1013 Battle Over Cities (25 分)【图的存储和遍历】
  • PAT A1004 Counting Leaves (30 分)【二叉树的建立和遍历】
  • PAT A1003 Emergency (25 分)【最短路径】

转载于:https://www.cnblogs.com/blue-lin/p/10940646.html

发表评论

表情：
评论列表 （有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读