KS3计算 算法 分解抽象 搜索排序 伪代码
算法是本学期计算机课的核心词，也是 GCSE 计算机科学两份笔试卷里分值最重的部分。教育部官网的纲要把 KS3 的要求写得很直接：理解若干反映计算思维的关键算法，并且用逻辑推理比较同一问题的不同解法。很多学生以为算法就是背下来的代码，其实它更像一份写给别人看的操作说明。下面把 KS3 需要掌握的算法要点、查找与排序的比较次数、以及 KS3 到 GCSE 的衔接一次讲清。
Algorithms sit at the centre of the key stage 3 computing curriculum, and the national curriculum for England, published by the Department for Education on 11 September 2013, asks pupils to understand several key algorithms that reflect computational thinking, including ones for sorting and searching. The same content returns in the GCSE papers, where algorithms and programming carry half of the marks. This guide works through the definitions, the standard search and sort routines, the trace table technique, and the binary and Boolean content that key stage 3 expects.
算法与程序的区别 输入 处理 输出
一份合格的算法要满足三件事：步骤有限、顺序明确、每一步都没有歧义。教育部官网的纲要从 KS1 就写明，程序靠精确且无歧义的指令一步步执行，这条要求在 KS3 仍然成立。动笔写算法时先找输入，再定处理，最后写输出，这三样在试卷里往往各占一行分值。很多学生以为算法必须能直接跑在电脑上，其实写在草稿纸上的伪代码也算算法。算法回答的是怎么算，程序回答的是用什么语言把它写出来，两者不要混为一谈。常见的错误是把循环条件写成永远为真的形式，步骤数于是失去上限。检查办法很简单：拿一组数据手跑一遍，看最后能不能停下来。
A workable algorithm is finite, ordered and free of ambiguity in every step. The national curriculum for England makes the same point from key stage 1, where pupils must understand that programs execute by following precise and unambiguous instructions, and key stage 3 keeps that standard while adding abstraction. Before writing anything, identify the inputs, the processes and the outputs, because examiners award separate marks for each of the three; then trace your draft with a small data set to check that every loop can terminate.
计算思维 分解 抽象 模式识别 算法设计
计算思维不是一句口号，纲要的第一条要求就是设计、使用并评估计算抽象，用它描述现实问题的状态与行为。分解是把大问题切成小块，抽象是只保留与问题有关的细节，模式识别是发现重复出现的结构。算法设计把这些结果排成一组可执行的步骤。很多学生以为抽象等于简化题目，其实抽象是主动丢掉无关信息，比如画地铁图时不管实际距离。模式识别用得好的学生，会把三段相似的循环改成一段带参数的函数。这四步不必按顺序各做一遍，多数时候需要来回调整。
Computational thinking is written into the curriculum rather than bolted on: the first key stage 3 requirement is to design, use and evaluate computational abstractions that model the state and behaviour of real-world problems and physical systems. Decomposition breaks a problem into smaller parts, abstraction keeps only the details that matter, and pattern recognition spots the repeated structure. Algorithm design then turns those results into an ordered set of steps, and a block of code copied three times is usually a sign that pattern recognition was skipped.
顺序 选择 循环 三种控制结构
任何一种程序都由三种结构拼出来：顺序、选择、循环。纲要的 KS2 部分已经要求学生使用 sequence、selection 与 repetition，KS3 在此基础上加深，要求嵌套的选择与嵌套的循环。顺序是默认的执行方式，代码从上往下读。选择靠条件判断走哪一条分支，循环靠计数或条件决定重复多少次。常见的错误是循环体里改了不该改的变量，条件于是永远不满足。写代码前先把结构画一遍，改起来省力很多。
Every program is built from three constructs: sequence, selection and repetition. The key stage 2 programme of study already requires pupils to use sequence, selection and repetition in programs, and key stage 3 deepens that requirement with nested selection and nested iteration. Sequence is the default reading order, selection picks a branch on a condition, and repetition runs a block a fixed number of times or until a condition changes; a loop that edits the wrong variable is the usual reason a program never stops.
伪代码与流程图 两种写法各有所长
伪代码和流程图是同一份算法的两种写法，一个偏文字，一个偏图形。伪代码不绑定具体语言，改一行就能换思路；流程图把分支和循环画出来，一眼能看出程序有多少条可能路径。OCR 的 J277 考纲明确允许考生用伪代码、流程图、参考语言或高级语言作答 Component 02 的 Section A，评的是结构是否清楚，而不是语法细节。很多学生以为必须写成某一种样式才给分，其实关键是把每一步写清楚。步骤多的算法用伪代码更省纸，条件复杂的算法用流程图更直观。改错时先改图再改代码，逻辑错误更容易定位。
Pseudocode and flowcharts are two notations for the same algorithm, one leaning on words and the other on shapes. OCR's J277 specification allows candidates to answer section A of component 02 in pseudocode, flowcharts, bullet points, the exam reference language or a high-level programming language, because the marks reward a logical structure rather than syntactic precision. Heavy branching is easier to check on a diagram, long sequential routines are faster to write in words, and correcting the notation before the code usually exposes a logic error sooner.
追踪表 手工跑一遍程序
追踪表把程序的执行过程摊在纸面上，一列一个变量，一行一条语句。做法是先写出所有变量名，再逐行记录每次赋值后的值，遇到条件就把判断结果标出来。OCR 的 J277 把追踪表写进必考清单，考生被要求用它跟随算法的执行过程。很多学生以为追踪表只是选择题用的草稿，其实它是找逻辑错误最直接的办法，某一行的值和预期不符，问题就在那里。填表时不要把程序根本执行不到的语句填进去，也不要把中间结果四舍五入。手跑一遍花五分钟，往往能省下二十分钟的改错时间。
A trace table lays the execution of a program out on paper, one column per variable and one row per statement. Write the variable names first, then record the value after every assignment and the outcome of every condition, because OCR lists trace tables among the standard techniques for following an algorithm in J277. The row where a value differs from your expectation is where the fault sits, so resist rounding intermediate values or filling in lines that the program never reaches.
线性查找 逐个比对的最坏情况
线性查找从头往尾逐个比较，只看当前这一项是不是目标。它的前提只有一个，数据摆在那里就行，不需要提前排好顺序。比较次数算得清楚：一千项数据最坏要比较一千次，也就是目标在末尾或者根本不存在的情形。很多学生以为线性查找没什么用，其实数据量小或者只查一次时，它的代码最短、出错最少。常见的错误是一边找一边改动原数据，比对的基准被自己破坏。用一个标记变量记住有没有找到，循环结束之后再判断，比在循环里中途跳出来更容易检查。
Linear search compares the target with each item in turn, from the first element to the last. It needs no preparation at all, which is why it stays useful for short lists and one-off lookups, and its worst case is easy to state: a thousand items can need a thousand comparisons when the target sits last or is absent. Keep a found flag instead of editing the list while you search, and decide what to report once the loop has finished.
二分查找 必须先有序 每次砍一半
二分查找每次都去看中间那一项，比目标大就往左半边找，比目标小就往右半边找。它的前提是数据已经按顺序排好，这一点没有商量余地。剩下多少项可以算出来：一千项最多十次比较，一百万项最多二十次，每比较一次候选范围就减半。很多学生以为二分查找总是更快，其实乱序数据上它给出的结果是错的，先排序的成本也要算进去。常见的错误是取中间位置时忘记取下界，下标算出小数就出了错。查找范围用左指针和右指针表示，循环条件是左不超过右，写起来只有几行。
Binary search inspects the middle item, then discards the half that cannot contain the target. The data must be sorted first, and each comparison halves the remaining candidates, so a thousand items take at most ten comparisons and a million take at most twenty. Forgetting to round the middle index down, or running binary search on unsorted data, are the two mistakes that cost marks most often.
冒泡排序 相邻交换与比较次数
冒泡排序一遍一遍地扫，比较相邻两项，顺序不对就换过来。一趟走完，最大的那一项就沉到了末尾，下一趟可以少比一次。比较次数有公式：一百项数据最坏要四千九百五十次，也就是 n 乘 n 减一再除以二。很多学生以为冒泡排序只是入门练习，其实它有一个优势，数据基本有序时一两趟就能停。常见的错误是内层循环的范围没有随趟数缩小，白比了很多次。用一个开关记录本趟有没有交换过，可以提前结束排序，这个细节在试卷上经常出现。
Bubble sort sweeps through the list comparing neighbours and swapping any pair that is out of order. After each pass the largest remaining item sits at the end, so the next pass can be one comparison shorter, and for a hundred items the worst case is four thousand nine hundred and fifty comparisons, which is n times n minus one, divided by two. A swapped flag lets the sort stop early on nearly sorted data, while an inner loop that never shrinks simply wastes work.
归并排序 分而治之的合并过程
归并排序把列表一直对半切，切到每段只剩一项，再两两合回去。合并时只比较两段各自最前面的那一项，小的先放进结果，指针往后移。一千项数据的比较次数大约一万次，比冒泡排序的四十九万九千五百次少得多。代价是要多一个同样长的数组存放中间结果，内存开销上去了。很多学生以为分治法只是写法好看，其实数据量大时它才是可行的选择。常见的错误是合并时漏掉某一段剩下的元素，最后的结果少了几项。递归写法要把基例写清楚，切到只剩一项就返回。
Merge sort keeps splitting the list in half until each piece holds a single item, then merges the pieces back in pairs. Each merge only compares the front items of the two runs, so a thousand items take roughly ten thousand comparisons against about four hundred and ninety-nine thousand for bubble sort. The trade-off is memory, since a second array of the same length is needed, and dropping the remainder of one run is the classic merge bug.
效率怎么比 比较次数 趟数 内存
判断两个算法谁更好，考试局给了三个角度：比较次数、趟数、内存占用。AQA 的 8525 把这些写进 Fundamentals of algorithms，要求考生比较同一问题的不同解法。数据基本有序时插入排序只挪动很少的项，冒泡排序也能提前收工；数据随机而且量大时，归并排序和二分查找的优势才明显。很多学生以为代码短就跑得快，其实行数和执行次数没有必然关系，一个嵌套循环的十行代码可能比三十行顺序代码慢得多。回答案例题时把次数算出来写进去，比只说更快更容易拿到分。常见的错误是拿不同数据量去比较两个算法，结论自然站不住。
Examiners judge efficiency on the number of comparisons, the number of passes and the use of memory, and AQA's 8525 specification asks candidates to compare alternative algorithms for the same problem. Insertion sort moves very few items when a list is nearly sorted, while merge sort and binary search only pull ahead once the data gets large and unsorted. Shorter code is not automatically faster, and comparing two algorithms on different sized data sets proves nothing.
布尔逻辑 AND OR NOT 与真值表
布尔逻辑只有三个基本运算：AND、OR、NOT。纲要的 KS3 部分明确要求理解简单布尔逻辑以及它在电路和程序里的用法。AND 要求两边都成立，OR 只要一边成立，NOT 把真假反过来。真值表把每种输入组合的结果列全，两个变量四行，三个变量八行。很多学生以为 OR 在两个条件都成立时结果不同，其实只要有一边为真整句就为真。常见的错误是把 NOT 的括号漏掉，整个表达式的意思就反了。条件里混用 AND 和 OR 时用括号分组，读代码的人会少犯很多错。
Boolean logic comes down to three operators: AND, OR and NOT. The key stage 3 programme of study requires pupils to understand simple Boolean logic and some of its uses in circuits and programming, and a truth table simply lists every input combination with its result, four rows for two variables and eight for three. A missing bracket around a NOT, or an ungrouped mix of AND and OR, is what turns a correct condition into the wrong one.
二进制 八位一个字节 加法与转换
计算机里的数字、文字、图片，最终都是一串 0 和 1。一个位是一个 0 或一个 1，八位算一个字节，一个字节能表示 0 到 255 共 256 个取值。换算的方法是按位取值：从右往左依次对应 1、2、4、8、16、32、64、128，把为 1 的那几位加起来。二进制加法只有四条规则，0 加 0 得 0，0 加 1 得 1，1 加 1 得 0 进 1，1 加 1 再加进位得 1 进 1。很多学生以为进位规则要背很久，其实它和十进制的满十进一是一回事，只是满二进一。常见的错误是把位和字节混着说，两者的单位差了八倍。考纲还要求能在二进制与十进制之间来回转换。
Numbers, text and images all end up as strings of zeros and ones inside a computer. One bit holds a single zero or one, eight bits make a byte, and one byte covers 256 values from zero to 255, so converting from binary means adding the place values 1, 2, 4, 8, 16, 32, 64 and 128 wherever a one appears. The four rules of binary addition work exactly like carrying in base ten, and confusing bits with bytes is a factor of eight error.
KS3 到 GCSE 计算机科学 卷面衔接
KS3 学的算法直接进 GCSE 的卷面。AQA 的 8525 有两份笔试，Paper 1 两小时、九十分、占五成，考算法基础与编程；Paper 2 一小时四十五分、九十分、占五成，考数据表示、计算机系统、网络、网络安全与数据库。OCR 的 J277 两份卷各一小时三十分、各八十分，Component 02 里 Section A 五十分考算法与编程，Section B 三十分考设计、编写、测试与改进程序。很多学生以为追踪表到 GCSE 才需要练，其实 J277 的必考清单里就有它，KS3 阶段练熟最划算。这两个考纲都不要求 KS3 使用大 O 记号，先把比较次数算清楚比背符号有用。把 KS3 的查找与排序写顺，到 Paper 1 的算法题就是同一套动作。
The algorithm work at key stage 3 feeds straight into the GCSE papers. AQA's 8525 sets two written papers of 90 marks each, with Paper 1 running two hours on algorithms and programming and Paper 2 running one hour and forty five minutes on data representation, computer systems, networks, cyber security and databases; OCR's J277 splits 160 marks evenly across two ninety minute components, where section A of component 02 carries 50 marks for algorithms and programming and section B carries 30 marks for designing, writing, testing and refining programs. Trace tables and comparison counts are examined in both, so the routines practised at key stage 3 need no new vocabulary later.
戴睿（dere）Neo优选系列 创意双触摸屏高性能笔记本电脑大学生AI学习商务办公设计炒股娱乐手提轻薄本32/1TB¥4586.0📱 去京东购买京东精选
需要一对一辅导？Need One-on-One Tutoring?
A-Level / GCSE / IB / KS2-KS3 全科辅导
16621398022 同微信
Visit aleveler.com
或截图后用「扫一扫 → 相册」选择本图