计算机程序设计能力考试（PAT）备考通 | PAT考试大纲解读

PAT考题的分数与难度呈正比，每5分一个层级，逐级递增。最简单的基础级考试题目的分值为5分，最难的顶级考试题目的分值为35分。题目的难度取决于两个因素：首先是知识点的层次，即知识点越基础难度越低；其次是题目涉及的编程量，即编程量越小难度越低。

本文将分别介绍PAT各等级考试的大纲，并指出大纲中涉及的知识点需要考生至少掌握到什么程度。

基础级考试分为 5个段位，其对应的考查内容和分数分布如表 2.1所示。下面用例题分别说明各项能力的考查方法。

■ 表 2.1基础级的考查内容

题目一般要求考生按照指定格式读入数据，再按照另一种指定格式输出。

（2）两道 5分题，涉及简单的表达式计算。

题目一般要求考生按照要求读入数据，推导出简单的计算公式，通过计算得到结果并输出。这里的公式推导一般只涉及初级算术，不涉及复杂的计算。

（3）最后一道 10分题涉及简单分支语句的使用。

题目一般要求考生对输入数据做简单处理，然后根据给定条件判断输出内容。考查重点是分支语句的使用，数据处理一般非常简单。

综上，青铜段位考查的是考生使用一门编程语言进行简单的计算、基本的格式化输入 输出，以及解决简单分支问题的能力。

循环是大多数初学者遇到的第一个难点。题目一般给出一个较为简单直接的循环目标，仅考查考生能否正确地使用循环语句的语法。

（3）最后一道 10分题涉及循环与分支的结合使用。

题目一般会在循环体中嵌入分支条件判断的内容，或在分支中嵌入循环。能顺利解出此类题目的考生，应已具备正确理解循环结构并灵活运用的能力。 

数组，特别是字符串是编程初学者遇到的第二个较为困难的门槛。题目一般要求考生将数据存储在数组中，并按照某些规律对数组进行处理。

两道 15分题的侧重点略有不同，另一道可能涉及简单的结构体存储。当然，不用结构体存储也是可以解决问题的。这类题目的编程量一般不是很大，重点考查考生对数组这个难点的掌握程度。

与 15分题相比， 20分题通常对数据处理的要求更高，一般需要更大的编程量或更好的程序结构设计。就上述例题而言，虽然考生可以把所有处理工作都写在一个 main函数中，但专门写一个函数做数字变换会使程序结构更清晰易懂，这在软件工程上是非常重要的。

注意：企业在选拔人才时可能会仔细查阅考生提交的代码，技术主管一般会更青睐有良好专业习惯的考生。

排序是基础算法之一，一般考生会在“数据结构”课程中学习到多种经典的排序算法，用于解决不同情况下的排序问题。对于学习了基础编程技巧的考生，本题并不特别考查考生对多种排序算法的理解，只要考生会使用一门编程语言中的通用排序库函数（如 C语言中的 qsort函数）即可。

二分查找也是基础算法，考生应熟练掌握该算法的实现。

乙级考试对应“大师”段位，重点考查考生的以下能力：

乙级考试一般有 5道题，其中，最简单的一道题为 15分，另有三道 20分题，最后一道是 25分题。

从考查点来看，乙级比基础级“钻石”段位的考查增加了两个重要的知识点，主要体现在后两道题中。最后一道 25分题可能涉及“数据结构”课程才会详细讲解的线性表结构（数组和链表，包括堆栈和队列等应用）的处理，如下面的例题 1所示；或者在多个解决方案中，要求考生只有给出时间复杂度最低的解才能得到满分，如下面的例题 2所示。

与基础级“钻石”段位相比，乙级考试不再有 5分、 10分这种起步难度的题目，而是直接从 15分起，提高了得分的门槛。基础级“钻石”段位能得到 90分的考生，在乙级考试中一般可以得到 60分以上的成绩。

乙级考试考生不仅要能够写出一个程序以解决问题，而且需要具有算法的时间复杂度、空间复杂度和算法稳定性的概念，能够写出效率充分高的程序。如例题 2中的问题就有多种解法，最优解只需要 O(N)的时间复杂度，给出时间复杂度为 O(N²)算法的考生虽然也可以得分，但得不了满分。

所有题目都旨在考查考生的综合编程能力，而不是单一知识点的掌握，因此才能得到企业的认可。

甲级考试对应“王者”段位，在乙级考试的基础上，还重点考查考生的以下能力：

首先，甲级考试的题目描述使用英文，且考试中不允许考生查字典——当然，出题者也会为个别较为生僻的单词标出译文。这对考生的英文阅读理解能力提出了较高要求。之所以这样设置，是因为计算机行业发展迅速，这就要求从业人员具备终身自主学习的能力，才能不被快速发展的新技术淘汰。而目前大部分前沿的新技术、新知识的第一手材料都是用英文撰写的，所以阅读英文原版技术资料是计算机工程师必备的能力之一。IT、互联网领域的大部分头部企业都对求职者的英文阅读理解能力有所要求。

甲级考试一般有 4道题，其中，前两题的分值为 20分和 25分，内容与乙级考试的后两题相同，即乙级考试最后两题的英文版，在此不再赘述。后两题的分值为 25分和 30分，对应考试大纲中核心能力的考查。

甲级考试特有的考查点都是计算机专业基础课程“数据结构”的核心内容。对于计算机相关专业的学生而言，在课堂上了解这些知识点的定义并不代表就具备了应用这些知识解决实际问题的能力。而 PAT的特点就是考查考生应用知识进行实战编程的能力。

对数据结构知识的考查集中在两道 25分题和一道 30分题上，这三题通常会分别涉及线性表、树、图这三大核心内容，以及围绕它们展开的经典算法。25分题与 30分题体现的难度区别主要体现在两个维度：一是编程量，二是复杂度。

最难的 30分题一般有两种出题风格：一种俗称“难死你”，即设计出巧妙高效的满分解题算法是一件比较困难的事，考生的时间会主要花费在构思算法上，而一旦想通了，编程量其实并不大；另一种俗称“繁死你”， 即采用的算法很容易想到，但要想正确实现，却不是一件简单的事情，考生的时间会主要花费在编写和调试代码上。

很明显，例题 2考查的是图的最短路径问题，并且加入了一些额外条件，考查考生是否能够对算法进行灵活运用。题目考查的算法比较经典且非常容易想到，但编程时需要全面考虑各种细节条件的处理，快速得到满分是不容易做到的，这就是一道典型的 30分题。

例题 3看上去是关于堆栈的题目，但实际上 PeekMedian这个特殊操作的实现很有讲究。考生必须想办法把这个特殊操作的时间复杂度控制到最优，例如可以采用树状结构“堆”辅助解决问题。本题目需要考生对一个没有现成解决方案的问题进行分析，花时间找出最优算法，这是另一种典型的 30分题。

与乙级考试相比，甲级考试是从难度最大的 20分题起步的，再次提高了得分的门槛。乙级考试能得到 90分的考生，在甲级考试中一般可以得到 60分以上的成绩。

甲级考试要求考生不仅会写程序，而且要会写“好”的程序，即必须善用合适的数据存储方法，采用最高效的算法解决更复杂的问题。甲级成绩优秀说明考生不仅基础扎实、头脑灵活、动手能力强，而且英文阅读能力也不错，通常会更受企业的欢迎。

顶级考试对应“大圣”段位，在甲级考试的基础上，还重点考查考生的以下能力：

顶级考试一般只有 3道题，其中，第一题的分值为 30分，内容与甲级考试中最难的一题相同，在此不再赘述。后两题的分值均为 35分，对应考试大纲中对核心能力的考查。

顶级考试是为头部企业选拔能力出众的人才而设计的，只配合企业的秋招和春招开设考试，冬季 PAT没有设置顶级考试。从考试大纲可以看出，顶级考试的考查范围超过了绝大多数高校“数据结构”“算法分析”类课程的教学大纲，并且题目描述也使用英文。从 2015年首场举办以来，每年参加顶级考试的考生大约仅占考生总数的 1%，能够获得好成绩的考生更是凤毛麟角。

在考试大纲列出的众多知识点中，动态规划和图论高级应用是最常考查的内容，通常出现在难度相对较低的 35分题中，最后一道 35分题一般涉及多个知识点的融会贯通。