内容发布更新时间 : 2024/12/29 0:32:28星期一 下面是文章的全部内容请认真阅读。

程序员 http://www.educity.cn/jiaocheng/zg14.html

程序员考试考点分析与真题详解（第4版 ）

第 1 章 数据结构与算法

数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为S=（D,R）。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点与结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。

数据结构按逻辑结构不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可分为树结构和二叉树结构。

按照考试大纲的要求，在数据结构与算法方面，要求考生掌握以下知识点。 1.常用数据结构

数组（一维数组、二维数组、静态数组、动态数组）、线性表、链表（单向链表、双向链表、环形链表）、队列、栈、树（二叉树、查找树）和图（邻接矩阵、邻接表）等的定义、存储和操作。 2.常用算法

（1）排序算法、查找算法、数值计算算法、字符串处理算法、递归算法、最小生成树、拓扑排序和单源点最短路径求解算法、图的相关算法。

（2）算法与数据结构的关系、算法效率、算法设计、算法描述（流程图、伪代码、决策表）、算法的复杂性。

1.1 算法设计概述

程序员 http://www.educity.cn/jiaocheng/zg14.html

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。 （1）有穷性：一个算法（对任何合法的输入值）必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。

（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）输入：一个算法有零个或多个输入，以确定运算对象的初始情况。所谓零个输入是指算法本身定出了初始条件。这些输入取自于某个特定对象的集合。

（4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

（5）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

算法设计要求正确性、可读性、健壮性、高效率与低存储量需求。

效率指的是算法执行的时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。 算法的复杂性是算法效率的度量，是算法运行所需要的计算机资源的量，是评价算法优劣的重要依据。可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素。 （1）硬件的速度。例如，使用486还是使用586.

（2）书写程序的语言。实现语言的级别越高，其执行效率就越低。

程序员 http://www.educity.cn/jiaocheng/zg14.html

（3）编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。

（4）问题的规模。例如，求100以内的素数与求1 000以内的素数其执行时间必然是不同的。

显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述的各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。 1.时间复杂度

一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。

一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该操作重复执行的次数作为算法的时间度量。在一般情况下，算法中原操作重复执行的次数是规模n的某个函数T（n）。

许多时候要精确地计算T（n）是困难的，我们引入渐近时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。

定义（大Ο记号）：如果存在两个正常数c和n0,对于所有的n,当n≥n0时有： f（n） ≤ cg（n） 则有：

f（n） = Ο（g（n））

也就是说，随着n的增大，f（n）渐近的不大于g（n）。例如，一个程序的实际执行