文档介绍：前言
公共基础只是的考核方式是笔试， 与程序设计语言的笔试部分组合成一张试卷， 公共基础占 30 分（选
择题 10 个和填空题 5 个）；
一、基本数据结构与算法
算法概念；算法复杂度的概念和意义（时间复杂度和穷性 (finiteness)
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终
止。
算法的有穷性还应包括合理的执行时间的含义。
拥有足够的情报
一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不
够或输入错误时，算法本身也就无法执行或导致执行有错。
综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明
确的，此顺序将在有限的次数下终止。
2．算法的基本要素
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
算法中对数据的运算和操作
通常，计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的
集合，称为该计算机系统的指令系统。在一般的计算机系统中，基本的运算和操作有以下四类：
①算术运算：主要包括加、减、乘、除等运算。
②逻辑运算：主要包括“与”、“或”、“非”等运算。
③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。
④数据传输：主要包括赋值、输入、输出等操作。
算法的控制结构
算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反
映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、 N-s 结构化流程图、算法描述
语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
3．算法设计基本方法
工程上常用的几中算法设计方法有：
（1）列举法
根据所需要解决的问题，把所有可能的情况一一列举出来，并用问题中给定的条件来检验哪些是需要的，哪些是不需要的 .
通常用来解决“有多少种可能”等类型的问题。 ( 不能解决无线复杂的问题 )
归纳法 （从特殊到一般）
通过列举少量的特殊情况，经过分析，最后找出一般的关系。（解决列举量为无限的问题）
递推
从条件到结论，逐次推出所要求的各种中间结果和最终结果。
递归
函数的自调用：将问题逐层分解，最后归结为一些最简单的问题。
减半递推技术
所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
回溯法
通过对问题的分析，出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，
若试探成功，就得到 f 题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。
回溯法在处理复杂数据结构方面有着广泛的应用。
算法复杂度
1． 1．2 算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1．算法的时间复杂度
所谓算法的时间复杂度，是