计算机二级公共基础知识正式完整版课件

计算机二级公共基础知识计算机二级公共基础知识1第一章数据结构与算法(30%)

考试大纲

1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。第一章数据结构与算法(30%)考试大纲2知识点归纳算法的基本概念所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：知识点归纳算法的基本概念3输入一批数据时，最好使用输入结束标志平均速度最快排序：快速排序数据的高共享性和低冗余性双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息这种测试又称为功能测试或数据驱动测试。ER图是实体联系模型的直观图形表示。严格限制GOTO语句的使用。概念模型是面向现实世界的，其出发点是有效地模拟显示世界，给出数据的概念化结构。数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。插入运算是指在线性表的某个指定位置增加一个新结点。白盒测试把测试对象看作一个透明的盒子，利用程序内部的逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试。当这些工具被集成起来使得一个工具产生的信息可以被另外一个工具使用时，一个支持软件开发的系统就建立起来了，称为计算机辅助软件工程(CASE)。关系将相关的实体连接在一起并在实体旁标注关系的基数。栈底元素总是最先被插入，也是最后被删除的元素。消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的，消息是一个对象与另一个对象之间传递的信息，它请求对象执行某一处理或回答某一要求的信息。概要设计，即总体设计。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。算法的基本特征一个算法应该具有以下五个重要的特征：

有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行输入一批数据时，最好使用输入结束标志算法的基本特征有穷性一4算法的基本概念算法的组成要素算法中对数据的运算和操作算法的控制结构算法设计基本方法列举法归纳法递推递归减半递推回溯法基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环算法的基本概念算法的组成要素基本运算和操作控制结构5算法的复杂度算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数f(n)。算法的复杂度算法的复杂度可分为时间复杂度和空间复杂度，是衡量6算法的复杂度算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度算法的复杂度算法的空间复杂度7数据结构利用计算机进行数据处理是计算机应用的一个重要领域。数据结构主要研究和讨论以下三个方面的问题：数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构。在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。对各种数据结构进行的运算。数据结构利用计算机进行数据处理是计算机应用的一个重要领域。数8数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关，是独立于计算机的。

数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描9数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素，在存储空间中建立各存储结点之间的关联，来表示数据元素之间的逻辑关系。常见的存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器10线性结构和非线性结构线性结构在数据元素的非空有限集合中，线性结构的逻辑特征如下：存在一个唯一的被称为“第一个”的数据元素存在一个唯一的被称为“最后一个”的数据元素除第一个之外，集合中的每个数据元素均有且只有一个直接前驱除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。线性结构和非线性结构线性结构11线性表 通常以下列n个数据元素的序列”表示线性表：

(a1,a2,...,ai,...,an)序列中数据元素的个数n定义为线性表的表长；n=0时的线性表被称为空表。称i为ai在线性表中的位序。线性表 通常以下列n个数据元素的序列”表示线性表：12线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。

所有数据元素的存储位置均可由第一个数据元素的存储位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一个数据元素所占存储量

线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元13线性表的插入和删除运算插入运算是指在线性表的某个指定位置增加一个新结点。一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。删除运算是指撤销结构中的某个结点。一般情况，要删除第i(1≤i≤n)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。线性表的插入和删除运算插入运算是指在线性表的某个指定位置增加14栈栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和15栈的顺序存储及运算用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。top=0表示栈为空，top=m表示栈满。栈的操作入栈：在栈顶位置插入一个新元素，栈顶指针top加1。退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。栈的顺序存储及运算用一维数组S(1:m)作为栈的顺序存储空间16队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(17循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。循环队列初始状态为空，即front=rear=m。入队操作时，rear加1，若rear=m+1，则置rear=1；退队操作时，front加1，若front=m+1，则置front=1。在循环队列为空或为满时，均有front=rear，因此需要设置标志s进行区分，定义s=0表示队列为空，s=1表示队列非空。循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻18单链表线性表的链式存储结构的特点是用一组任意的存储单元(可以连续，也可以不连续)存储线性表的数据元素，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息(数据域)之外，还需要存储其后继元素的存储位置信息(指针域)。指针域中存储的信息称为指针或链，N个结点链接成一个链表，即为线性表的链式存储结构。由于结点中只包含一个指针域，故称为单链表。单链表线性表的链式存储结构的特点是用一组任意的存储单元(可以19单链表通常以单链表中第一个数据元素的存储地址作为作为单链表的地址，称为头指针。整个链表的存储必须从头指针开始(顺序存取)，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，其指针域为空。单链表通常以单链表中第一个数据元素的存储地址作为作为单链表的20单链表的插入和删除单链表的插入和删除21双向链表和循环链表在双向链表中的结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。HEAD…∧…∧HEAD…HEAD双向链表和循环链表在双向链表中的结点包含两个指针域，其中一个22树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。树是(n≥0)个结点的有限集合，在任意一棵非空树中：

(1)有且仅有一个特定的结点称为根结点。

(2)当n>1时，其余的结点可分为m个互不相交的子集T1,T2,…Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。集合为空的树简称为空树；树中的元素称为结点。树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元23树的主要术语结点的度：结点拥有的子树数。叶节点(终端结点)：度为0的结点。双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。同一个双亲结点的孩子互称为兄弟。层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。深度：树中结点的最大层次称为树的深度或高度。树的主要术语结点的度：结点拥有的子树数。24树型结构的常用术语ABDFECGHIJKM

结点的度一个结点的子树的个数；Q：结点A、G的度数？

树的度树中所有结点度的最大值；Q：右图中树的度？

终端结点度为0的结点；

Q：图中叶子结点有几个？7

非终端结点

度不为0的结点；

Q：图中非终端结点有几个？5树型结构的常用术语ABDFECGHIJKM结点的度一个25树型结构的常用术语ABDFECGHIJKM

结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；树的深度树中所有结点层次的最大值；Q：图中树的深度？①②③④树型结构的常用术语ABDFECGHIJKM结点的层次26二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或27二叉树的基本性质性质1

在二叉树的第i层上至多有2i-1个结点（i≥1）性质2

深度为k的二叉树至多有2k-1个结点（k≥1）性质3

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2

，则：n0=n2+1性质4

具有n个结点的二叉树，其深度至少为[log2n]+1二叉树的基本性质性质1在二叉树的第i层上至多有2i-128满二叉树和完全二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为[log2n]+1。从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树

最大层的结点均向左靠齐

完全二叉树

ADCBEF满二叉树和完全二叉树满二叉树除最后一层外，每一层上的所有结点29二叉树的基本性质性质5

如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序（从第1层到第[log2n]+1层，每层从左到右）从1起开始编号，则对任一编号为i的结点(1≤i≤n)，则:

(1)如果i=1，则编号为i的结点是二叉树的根，无双亲；如果i>1，则其双亲结点parent(i)的编号是[i/2]。

(2)如果2i>n，则编号为i的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)的编号是2i。

(3)如果2i+1>n，则编号为i的结点无右孩子；否则其右孩子结点rChild(i)的编号是结点2i+1。

二叉树的基本性质性质5如果对一棵有n个结点的完全二叉30二叉树的链式存储结构在二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。L(i)V(i)R(i)LchildvalueRchild二叉树的链式存储结构在二叉树的链式存储结构中，每个结点设置三31二叉树的链式存储结构二叉树的链式存储结构32二叉树的遍历二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树"和"遍历右子树"三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。

先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；

否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。若二叉树为空，则空操作；

否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。若二叉树为空，则空操作；

否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。二叉树的遍历二叉树的遍历指不重复地访问二叉树的所有结点。从二33二叉树的遍历先序遍历：ABDEGHCFIJ中序遍历：DBGEHACIJF后序遍历：DGHEBJIFCA二叉树的遍历先序遍历：ABDEGHCFIJ34查找查找是指在一个给定的数据结构中查找某个指定的元素。顺序查找顺序查找一般是指在线性表中查找指定元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中的所有元素与被查找元素都不相等，则查找失败。顺序查找：最好情况比较1次，最坏情况比较n次如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。查找查找是指在一个给定的数据结构中查找某个指定的元素。35查找二分查找(折半查找)二分查找法只适用于顺序存储的有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到0也没有找到目标元素为止。查找过程中，给定值首先和处于待查区间"中间位置"的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到"前半个区间"或"后半个区间"之后继续进行查找。查找二分查找(折半查找)36折半查找二分查找折半查找二分查找37查找二分查找(折半查找)：由于每次都可以减少一半的元素，所以最坏时间复杂度为log(2n)查找二分查找(折半查找)：由于每次都可以减少一半的元素，所以38排序 排序是指将一个无序序列整理成按值递增或递减(本章均采用递增规则)的有序序列。排序可以在各种不同的存储结构上实现，本章所介绍的算法以顺序存储的线性表为排序对象，在程序设计语言中就是一维数组。排序的算法种类很多，主要包括交换类排序、插入类排序、选择类排序等。排序 排序是指将一个无序序列整理成按值递增或递减(本章均采用39排序技术交换类排序法

冒泡排序快速排序插入类排序法简单插入排序希尔排序选择类排序法简单选择排序堆排序排序技术交换类排序法40排序法小结：最坏时间复杂度：冒泡排序法、快速排序、简单选择排序法、简单插入排序：

最坏情况需要n(n-1)/2次比较；希尔排序法：最坏情况需要O(n1.5)次比较；堆排序法,最坏情况需要O(nlog2n)次比较；平均速度最快排序：快速排序最好、最坏、平均三种复杂度都相同的排序方法：堆排序排序法小结：最坏时间复杂度：41第二章程序设计基础(15%)考试大纲1.程序设计方法与风格。

2.结构化程序设计。

3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。

第二章程序设计基础(15%)考试大纲42知识点归纳程序设计方法程序设计是一门技术，需要相应的理论、方法和工具来支持。就程序设计方法和技术的发展而言，主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中，通常采用“自顶向下，逐步求精”的方法，即把一个模块的功能逐步分解，细化为一系列具体的步骤，进而转换成一系列用某种程序设计语言编写的程序。知识点归纳程序设计方法43详细设计：即过程设计。查找是指在一个给定的数据结构中查找某个指定的元素。软件从提出、实现、使用、维护到停止使用的过程称为软件的生命周期。系统测试：将通过确认测试的软件，作为整个计算机系统的一个元素，与计算机硬件、外设、支持软件、数据以及人员等其他系统元素组合在一起，在实际运行环境中对其进行一系列的集成测试和确认测试。整个链表的存储必须从头指针开始(顺序存取)，头指针指示链表中第一个结点的存储位置。在结构化分析的基础上，完成系统的规格说明，建立系统的一个自顶向下的任务分析模型。元组：关系中的行称为元组。结点的度：结点拥有的子树数。数据的高共享性和低冗余性双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。面向对象方法的基本概念后序遍历：DGHEBJIFCA指一个类(子类)直接使用另一个类(父类)的所有属性和方法。程序设计风格除了程序设计设计方法和技术之外，程序风格也是非常重要的。良好的程序设计风格概括起来包括以下及格方面：源程序文档化数据说明的方法语句的结构输入和输出详细设计：即过程设计。程序设计风格除了程序设计设计方法和技术44程序设计风格源程序文档化标识符的命名程序的注释序言性注释功能性注释程序的视觉组织数据的说明数据说明的次序应该规范化说明语句中变量的安排有序化使用注释说明复杂的数据结构程序设计风格源程序文档化45程序设计风格语句结构在一行内只写一条语句程序编写应优先考虑清晰性除非对效率有特殊要求，程序编写要做到清晰第一，效率第二首先要保证程序正确，然后才要求提高速度避免使用临时变量而使程序的可读性下降避免不必要的转移尽可能使用库函数避免使用复杂的条件语句尽量减少使用“否定”条件的条件语句数据结构要有利于程序的简化要模块化，使模块功能尽可能单一化利用信息隐蔽，确保每一个模块的独立性从数据出发构造程序不要修补不好的程序，要重写编写程序设计风格语句结构46程序设计风格输入和输出对所有输入数据检验合法性检查输入项的各种重要组合的合法性输入格式要简单，以使输入的步骤和操作尽可能简单输入数据时，应允许使用自由格式应允许缺省值输入一批数据时，最好使用输入结束标志在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。程序设计风格输入和输出47结构化程序设计结构化程序设计的原则自顶向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求细节，先从最上层总目标开始设计，逐步使问题具体化。逐步求精。对复杂的问题，应设计一些子目标过渡，逐步细化。模块化。一个复杂问题肯定是有若干简单问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，每个小目标成为一个模块。严格限制GOTO语句的使用。结构化程序设计结构化程序设计的原则48结构化程序设计的基本结构和特点程序由一些基本结构组成，任何一个程序都可以用三种基本控制结构组成：顺序结构、选择结构和循环结构，并且具有如下特点：单入口、单出口、结构中无死循环，程序中三种基本控制结构之间形成顺序执行关系。一个大型程序应按功能分割成一些模块，并把这些模块按层次关系进行组织。在程序设计时应采用自顶向下、逐步细化的实施方法。结构化程序设计的基本结构和特点程序由一些基本结构组成，任何一49面向对象程序设计

面向对象方法的基本概念1.对象、类和属性在面向对象程序设计中，对象是程序的基本单位。对象可以表示客观世界中的任何实体，是对问题域中某个实体的抽象。每个对象可以用它本身的一组属性和它可以执行的一组操作来定义。类是对一组具有共同属性和相似行为的对象的一种抽象，描述了属于该类的所有对象的性质。2.方法方法有称为操作或服务，它描述了对象执行的功能，若通过消息传递，还可为其他对象使用。面向对象程序设计面向对象方法的基本概念50面向对象方法的基本概念3.继承：继承是对象方法的一个重要特征。指一个类(子类)直接使用另一个类(父类)的所有属性和方法。它可以减少相似类的重复说明，从而体现一般性和特殊性的原则。4.多态性：多态性可以用“一个对外界面，多个内部实现”来表示。可以通过方法重载和方法重写来实现多态。重载指一个类中可以有多个具有相同名称的方法，由传递给它们的不同个数和类型的参数来决定执行那个方法。重写指子类可以重新实现父类的某些方法，使其具有自己的特征。多态性机制增加了面向对象软件系统的灵活性，提高了软件的可重用性和可扩充性。5.消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的，消息是一个对象与另一个对象之间传递的信息，它请求对象执行某一处理或回答某一要求的信息。面向对象方法的基本概念3.继承：继承是对象方法的一个重要特征51面向对象程序设计的特点按照人的思维方式对客观世界进行抽象稳定性好可重用性好易于开发大型软件可维护性好面向对象程序设计的特点按照人的思维方式对客观世界进行抽象52第三章软件工程基础考试大纲1.软件工程基本概念，软件生命周期的概念，软件工具与软件开发环境。

2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。

3.结构化设计方法，总体设计与详细设计。

4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。

5.程序的调试，静态调试与动态调试。

第三章软件工程基础考试大纲53知识点归纳软件定义和特点计算机软件式计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。计算机软件具有如下特点：软件是一种逻辑实体，具有抽象性软件生产没有明显的制造过程软件在运行、使用期间不存在磨损、老化问题软件的开发、运行对计算机系统具有依赖性软件复杂性高，成本昂贵软件开发涉及诸多社会因素知识点归纳软件定义和特点54软件危机所谓软件危机是指在计算机软件开发和维护过程中所遇到的一系列严重问题，包括：软件需求的增长得不到满足软件开发成本和进度无法控制软件质量难以保证软件不可维护或可维护性低软件成本不断提高软件开发生产率的提高赶不上硬件的发展和应用需求的增长。软件危机所谓软件危机是指在计算机软件开发和维护过程中所遇到的55软件工程为了消除软件危机，提出了软件工程学。软件工程是应用于计算机软件定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程的三要素方法工具过程软件工程为了消除软件危机，提出了软件工程学。软件工程是应用于56软件工程过程软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。它包括两方面含义：1.软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列工程活动。通常包括四种基本活动：P(Plan)：软件规格说明D(Do)：软件开发C(Check)：软件确认A(Action)：软件演进2.从软件开发的观点看，软件工程过程是使用适当的资源，为开发软件进行的一组开发活动，在活动结束时将输入(用户需求)转化为输出(软件产品)。软件工程过程软件工程过程是把输入转化为输出的一组彼此相关的资57软件生命周期软件从提出、实现、使用、维护到停止使用的过程称为软件的生命周期。一般包括以下几个阶段：可行性研究与计划制定需求分析软件设计软件实现软件测试运行和维护软件生命周期软件从提出、实现、使用、维护到停止使用的过程称为58软件工程目标与原则软件工程的目标是在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的软件产品。为达到上述目标，在软件开发的过程中，必须遵循软件工程的基本原则：抽象信息隐蔽模块化局部化确定性一致性完备性可验证性软件工程目标与原则软件工程的目标是在给定成本、进度的前提下，59软件开发工具与软件开发环境软件开发工具对过程和方法提供自动或半自动的支持。当这些工具被集成起来使得一个工具产生的信息可以被另外一个工具使用时，一个支持软件开发的系统就建立起来了，称为计算机辅助软件工程(CASE)。CASE集成了软件、硬件和一个软件工程数据库(包含了有关分析、设计、程序构造和测试的重要信息)从而创建了一个软件开发环境。软件开发工具与软件开发环境软件开发工具对过程和方法提供自动或60结构化分析方法结构化分析方法大多使用自顶向下、逐层分解的系统分析方法来定义系统需求。在结构化分析的基础上，完成系统的规格说明，建立系统的一个自顶向下的任务分析模型。结构化分析方法是一种建模技术，模型的核心是数据辞典，它描述了所有在目标系统中使用和生成的数据对象。结构化分析常用的工具：数据流图(DFD):描述数据在系统中如何被传送或变换以及描述如何对数据流进行变换的功能，用于功能建模。数据字典判定树判定表结构化分析方法结构化分析方法大多使用自顶向下、逐层分解的系统61数据流图数据流图是描述数据处理过程的工具，它从数据传递和加工的角度，来刻画数据流从输入系统到从系统输入的移动变换过程。数据流图的基本元素外部实体数据流处理(加工)数据存储数据流图数据流图是描述数据处理过程的工具，它从数据传递和加工62数据字典数据字典是关于数据的信息的集合，对数据流图中的各个元素进行完整的定义和说明。数据流图和数据字典共同构成系统的逻辑模型。数据字典通常包含的信息有：名称、别名、何处使用、如何使用、内容描述以及补充信息等。数据字典数据字典是关于数据的信息的集合，对数据流图中的各个元63软件需求软件需求包括：功能需求、性能需求、环境需求、可靠性需求、安全保密需求、用户界面需求、资源使用需求、成本消耗需求、开发进度需求等。需求分析应交付的主要文档是软件需求规格说明书(SRS)。软件需求软件需求包括：功能需求、性能需求、环境需求、可靠性需64结构化设计结构化设计就是采用最佳的可能方法设计系统的各个组成部分以及个成分之间的内部联系的技术。也就是说，结构化设计是这样一个过程：它决定用哪些方法把哪些部分联系起来，才能解决好某个具体的有清楚定义的问题。从工程管理的角度看，软件设计分两步完成：1.概要设计，即总体设计。将软件需求转化为数据结构和软件的系统结构。常用的软件结构设计工具是结构图(StructureChart)。2.详细设计：即过程设计。通过对结构表示进行细化，得到软件详细的数据结构和算法。过程设计常用的工具有：程序流程图、N-S图、PAD图、过程设计语言PDL(伪码)。结构化设计结构化设计就是采用最佳的可能方法设计系统的各个组成65软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或弄清预期结果与实际结果之间的差别。软件测试是为了发现错误而执行程序的过程。一个好的测试用例是指可能找到迄今为止尚未发现的错误的用例。一个成功的测试是发现了至今尚未发现的错误的测试。测试不能表明软件中不存在错误，它只能说明软件中存在错误。软件测试定义：66测试技术与方法综述从是否需要执行被测试软件的角度，可将测试分为静态测试和动态测试。静态测试主要包括代码检查、静态结构分析、代码质量度量等。动态测试是基于计算机的测试，是为了发现错误而执行程序的过程，或者说，是根据软件开发的各个阶段的规格说明和程序的内部结构而精心设计的一批测试用例，并利用这些测试用例去运行程序，以发现程序错误的过程。测试技术与方法综述从是否需要执行被测试软件的角度，可将测试分67测试技术与方法综述按照功能划分，可将软件测试分为黑盒测试和白盒测试。黑盒测试将测试对象看作一个黑盒，不考虑程序内部的逻辑结构和内部特性，只依据程序的需求规格说明，检查程序的功能是否符合它的功能说明。这种测试又称为功能测试或数据驱动测试。白盒测试把测试对象看作一个透明的盒子，利用程序内部的逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试。通过在不同点检查程序的状态，确定实际的状态是否与预期的一致。这种测试又称为结构测试或逻辑驱动测试。测试技术与方法综述按照功能划分，可将软件测试分为黑盒测试和白68软件测试的实施软件测试按四个步骤进行：单元测试：对软件设计的最小单位－模块进行正确性的测试，其目的是发现各模块内部可能存在的各种错误。集成测试：是测试和组装软件的过程，它是在把模块按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。确认测试：任务是验证软件的功能和性能以及其他特性是否满足了需求规格说明中确定的各种需求，以及软件配置是否完全、正确。系统测试：将通过确认测试的软件，作为整个计算机系统的一个元素，与计算机硬件、外设、支持软件、数据以及人员等其他系统元素组合在一起，在实际运行环境中对其进行一系列的集成测试和确认测试。软件测试的实施软件测试按四个步骤进行：69程序调试程序调试的任务是诊断和修正程序中的错误。调试的方法：强行排错法回溯法原因排除法程序调试程序调试的任务是诊断和修正程序中的错误。70第四章数据库设计基础考试大纲1.数据库的基本概念：数据库，数据库管理系统，数据库系统。

2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。

3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。第四章数据库设计基础考试大纲71知识点归纳数据库的定义1.长期存放在计算机内，有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储，具有较小的冗余度、较高的数据独立性和易扩展性。2.数据库是由一个互相关联的数据的集合和一组用以访问这些数据的程序组成的。知识点归纳数据库的定义72数据库管理系统(DBMS)数据库管理系统是一个帮助用户创建和管理数据库的应用程序的集合。因此，数据库管理系统也就是一个可以帮助完成定义、构造和操纵数据库等处理目的的通用软件系统。其主要功能如下：数据模式定义数据存取的物理构建数据操纵数据的完整性、安全性定义和检查数据库的并发控制和故障恢复数据的服务为完成上述功能，DBMS提供了相应的语言：数据定义语言(DDL)数据操纵语言(DML)数据控制语言(DCL)数据库管理系统(DBMS)数据库管理系统是一个帮助用户创建和73数据库系统数据库系统是由数据库、数据库管理系统、数据库管理员、硬件平台和软件平台等几个部分组成的完整的运行实体。数据库系统的特点数据的集成性数据的高共享性和低冗余性数据的独立性数据统一管理和控制数据库系统数据库系统是由数据库、数据库管理系统、数据库管理员74数据库系统的内部体系结构三级模式概念模式：数据库系统中全局数据逻辑结构的描述，全体用户的数据视图外模式：又称为用户模式，是每个用户的局部数据描述，用户的数据视图内模式：又称为物理模式，是数据库物理存储结构和物理存取方法的描述二级映射概念模式到内模式的映射外模式到概念模式的映射数据库系统的内部体系结构三级模式75数据模型数据是现实世界符号的抽象，数据模型是现实世界数据特征的抽象，它从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表示和操作提供一个抽象的框架。数据模型描述的内容包括三部分：数据结构数据操作数据约束数据模型按不同的应用层次分成三种类型：概念数据模型逻辑数据模型物理数据模型数据模型数据是现实世界符号的抽象，数据模型是现实世界数据特征76实体联系(ER)模型概念模型是面向现实世界的，其出发点是有效地模拟显示世界，给出数据的概念化结构。实体联系模型是一种广泛使用的概念模型，该模型将现实世界的要求转化为实体、联系和属性等几个基本概念，并用ER图直观地表示出来。实体联系(ER)模型概念模型是面向现实世界的，其出发点是有效77ER模型的基本概念实体：概念世界中的基本单位，它们是客观存在且能相互区别的事物。凡具有共性的实体可以组成一个集合称为实体集。属性：属性用来描述实体的特征。一个实体可以有多个属性，每个属性可以有值，一个属性的取值范围称为该属性的值域。联系：联系反映概念世界中的实体集之间存在的一定关系。一对一联系(1:1)一对多联系(1:M)多对多联系(M:N)ER模型的基本概念实体：概念世界中的基本单位，它们是客观存在78ER图ER图是实体联系模型的直观图形表示。实体用矩形表示，并在矩形中标明实体的名称。属性用标有属性名称的椭圆表示，而且必须用线将属性与其所属的实现相连。关系用标明关系名称的菱形表示，关系的名称一般是动词。关系将相关的实体连接在一起并在实体旁标注关系的基数。

ER图ER图是实体联系模型的直观图形表示。79关系模型1.关系模型的数据结构在用户观点下，关系模型中数据的逻辑结构是一张二维表，它由行和列组成。在关系数据库管理系统中，数据的外部视图就是关系或表的集合。关系数据库中，每一种关系都有唯一的名称。关系模型1.关系模型的数据结构80关系模型的基本概念属性：关系中的每一列都称为属性，每一个属性表示了其下数据的含义。表中的每一列在关系范围内有唯一的名称。元组：关系中的行称为元组。元组定义了一组属性值。主码：表中的某个属性组，它可以唯一确定一个元组。域：属性的取值范围。分量：元组中的一个属性值。关系模式：对关系的描述。关系名（属性1，属性2，…，属性n）例如：学生（学号，姓名，年龄，性别，系，年级）关系模型的基本概念属性：关系中的每一列都称为属性，每一个属性81关系的基本性质元组的个数是有限的。列是同质的，即每一列中的分量是同一类型的数据，来自同一个域。不同的列可以出自同一个域，称其中的每一列为一个属性，不同的属性要给予不同的属性名。列的顺序无所谓，即列的次序可以任意交换。任意两个元组不能完全相同。行的顺序无所谓，即行的次序可以任意交换。分量必须取原子值，即每一个分量都必须是不可分的数据项。关系的基本性质元组的个数是有限的。82关系模型2.关系操纵关系模型的数据操纵即建立在关系上的数据操纵，一般有查询、增加、删除及修改四种操作。3.关系模型的约束实体完整性约束参照完整性约束用户自定义完整性约束关系模型2.关系操纵83关系模型的基本运算查询选择、投影、连接、并、交、差数据更新插入、删除、更新关系操作的特点集合操作方式，即操作的对象和结果都是集合。关系模型的基本运算查询84关系操作：插入、删除、更新关系操作：插入、删除、更新85关系操作：选择选择操作：应用于一个关系并产生一个新关系，新关系中的元组是元关系中元组的子集。选择操作根据要求从原关系中选择部分元组，属性的数量保持不变。关系操作：选择选择操作：应用于一个关系并产生一个新关系，新关86关系操作：投影投影：用于一个关系并产生一个新关系，新关系中的属性是原关系中属性的子集。投影操作中元组的数量保持不变。关系操作：投影投影：用于一个关系并产生一个新关系，新关系中的87关系操作：连接连接：基于共有属性将两个关系组合。关系操作：连接连接：基于共有属性将两个关系组合。88关系的操作(集合操作：并、交、差)关系的操作(集合操作：并、交、差)89数据库设计数据库设计的基本任务是根据用户对象的信息需求、处理需求和数据的支持环境设计出数据模式。数据库的设计通常分为几个阶段：需求分析、概念设计、逻辑设计和物理设计。数据库设计数据库设计的基本任务是根据用户对象的信息需求、处理90数据库设计需求分析：通过详细调查现实世界要处理的对象，充分了解原系统的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。概念设计：目的是分析数据间内在语义关联，在此基础上建立一个数据库的抽象模型。方法有以下两种：集中式模式设计法视图集成设计法数据库设计需求分析：通过详细调查现实世界要处理的对象，充分了91数据库设计逻辑设计：主要工作是将ER图转换成指定的RDBMS中的关系模式，并利用规范化理论对逻辑数据模型进行优化。ER图中的实体和联系都可以表示成关系，ER图中的属性也可以转换成关系的属性。物理设计：主要目标是对数据内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间。数据库设计逻辑设计：主要工作是将ER图转换成指定的RDBMS92谢谢观看谢谢观看93计算机二级公共基础知识计算机二级公共基础知识94第一章数据结构与算法(30%)

考试大纲

1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。第一章数据结构与算法(30%)考试大纲95知识点归纳算法的基本概念所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：知识点归纳算法的基本概念96输入一批数据时，最好使用输入结束标志平均速度最快排序：快速排序数据的高共享性和低冗余性双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入结束时，应在屏幕上给出状态信息这种测试又称为功能测试或数据驱动测试。ER图是实体联系模型的直观图形表示。严格限制GOTO语句的使用。概念模型是面向现实世界的，其出发点是有效地模拟显示世界，给出数据的概念化结构。数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。插入运算是指在线性表的某个指定位置增加一个新结点。白盒测试把测试对象看作一个透明的盒子，利用程序内部的逻辑机构及有关信息，设计或选择测试用例，对程序的所有逻辑路径进行测试。当这些工具被集成起来使得一个工具产生的信息可以被另外一个工具使用时，一个支持软件开发的系统就建立起来了，称为计算机辅助软件工程(CASE)。关系将相关的实体连接在一起并在实体旁标注关系的基数。栈底元素总是最先被插入，也是最后被删除的元素。消息：面向对象系统中的对象之间是通过消息机制彼此相互合作的，消息是一个对象与另一个对象之间传递的信息，它请求对象执行某一处理或回答某一要求的信息。概要设计，即总体设计。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。算法的基本特征一个算法应该具有以下五个重要的特征：

有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行输入一批数据时，最好使用输入结束标志算法的基本特征有穷性一97算法的基本概念算法的组成要素算法中对数据的运算和操作算法的控制结构算法设计基本方法列举法归纳法递推递归减半递推回溯法基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环算法的基本概念算法的组成要素基本运算和操作控制结构98算法的复杂度算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。1.算法的时间复杂度算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数f(n)。算法的复杂度算法的复杂度可分为时间复杂度和空间复杂度，是衡量99算法的复杂度算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。空间复杂度作为算法所需存储空间的量度算法的复杂度算法的空间复杂度100数据结构利用计算机进行数据处理是计算机应用的一个重要领域。数据结构主要研究和讨论以下三个方面的问题：数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构。在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。对各种数据结构进行的运算。数据结构利用计算机进行数据处理是计算机应用的一个重要领域。数101数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。与数据在计算机中的存储位置无关，是独立于计算机的。

数据的逻辑结构数据逻辑结构是对数据元素之间存在的逻辑关系的描102数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器中的表示。存储结构的主要内容是指在存储空间中使用一个存储结点来存储一个数据元素，在存储空间中建立各存储结点之间的关联，来表示数据元素之间的逻辑关系。常见的存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构数据的存储结构数据的存储结构是数据元素及其关系在计算机存储器103线性结构和非线性结构线性结构在数据元素的非空有限集合中，线性结构的逻辑特征如下：存在一个唯一的被称为“第一个”的数据元素存在一个唯一的被称为“最后一个”的数据元素除第一个之外，集合中的每个数据元素均有且只有一个直接前驱除最后一个之外，集合中的每个数据元素均有且只有一个直接后继非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。线性结构和非线性结构线性结构104线性表 通常以下列n个数据元素的序列”表示线性表：

(a1,a2,...,ai,...,an)序列中数据元素的个数n定义为线性表的表长；n=0时的线性表被称为空表。称i为ai在线性表中的位序。线性表 通常以下列n个数据元素的序列”表示线性表：105线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。

所有数据元素的存储位置均可由第一个数据元素的存储位置得到

ADR(ai)=ADR(a1)+(i-1)×C

↑↑ 基地址一个数据元素所占存储量

线性表的顺序存储线性表的顺序存储结构用一组地址连续的存储单元106线性表的插入和删除运算插入运算是指在线性表的某个指定位置增加一个新结点。一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，然后将新元素插入到第i项。删除运算是指撤销结构中的某个结点。一般情况，要删除第i(1≤i≤n)个元素，要从第i+1个元素开始，直到第n个元素，共n-i个元素依次向前移动一个位置。线性表的插入和删除运算插入运算是指在线性表的某个指定位置增加107栈栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和108栈的顺序存储及运算用一维数组S(1:m)作为栈的顺序存储空间，m为栈的最大容量。top=0表示栈为空，top=m表示栈满。栈的操作入栈：在栈顶位置插入一个新元素，栈顶指针top加1。退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。栈的顺序存储及运算用一维数组S(1:m)作为栈的顺序存储空间109队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。队列是一种先进先出的数据结构。向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。队列队列是一种先进先出的线性表，它只允许在表的一端插入元素(110循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。循环队列初始状态为空，即front=rear=m。入队操作时，rear加1，若rear=m+1，则置rear=1；退队操作时，front加1，若front=m+1，则置front=1。在循环队列为空或为满时，均有front=rear，因此需要设置标志s进行区分，定义s=0表示队列为空，s=1表示队列非空。循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻111单链表线性表的链式存储结构的特点是用一组任意的存储单元(可以连续，也可以不连续)存储线性表的数据元素，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息(数据域)之外，还需要存储其后继元素的存储位置信息(指针域)。指针域中存储的信息称为指针或链，N个结点链接成一个链表，即为线性表的链式存储结构。由于结点中只包含一个指针域，故称为单链表。单链表线性表的链式存储结构的特点是用一组任意的存储单元(可以112单链表通常以单链表中第一个数据元素的存储地址作为作为单链表的地址，称为头指针。整个链表的存储必须从头指针开始(顺序存取)，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，其指针域为空。单链表通常以单链表中第一个数据元素的存储地址作为作为单链表的113单链表的插入和删除单链表的插入和删除114双向链表和循环链表在双向链表中的结点包含两个指针域，其中一个指向直接后继，另一个指向直接前驱。循环链表的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。在循环链表中增加了一个表头结点，其指针域指向第一个元素结点，头指针则指向头结点。HEAD…∧…∧HEAD…HEAD双向链表和循环链表在双向链表中的结点包含两个指针域，其中一个115树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。树是(n≥0)个结点的有限集合，在任意一棵非空树中：

(1)有且仅有一个特定的结点称为根结点。

(2)当n>1时，其余的结点可分为m个互不相交的子集T1,T2,…Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。集合为空的树简称为空树；树中的元素称为结点。树及其基本概念树是一种简单的非线性结构，在树中，所有的数据元116树的主要术语结点的度：结点拥有的子树数。叶节点(终端结点)：度为0的结点。双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。同一个双亲结点的孩子互称为兄弟。层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。深度：树中结点的最大层次称为树的深度或高度。树的主要术语结点的度：结点拥有的子树数。117树型结构的常用术语ABDFECGHIJKM

结点的度一个结点的子树的个数；Q：结点A、G的度数？

树的度树中所有结点度的最大值；Q：右图中树的度？

终端结点度为0的结点；

Q：图中叶子结点有几个？7

非终端结点

度不为0的结点；

Q：图中非终端结点有几个？5树型结构的常用术语ABDFECGHIJKM结点的度一个118树型结构的常用术语ABDFECGHIJKM

结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；树的深度树中所有结点层次的最大值；Q：图中树的深度？①②③④树型结构的常用术语ABDFECGHIJKM结点的层次119二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有左右之分，其顺序不能任意颠倒。二叉树二叉树是n(n≥0)个数据元素的有限集，它或为空集,或120二叉树的基本性质性质1

在二叉树的第i层上至多有2i-1个结点（i≥1）性质2

深度为k的二叉树至多有2k-1个结点（k≥1）性质3

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2

，则：n0=n2+1性质4

具有n个结点的二叉树，其深度至少为[log2n]+1二叉树的基本性质性质1在二叉树的第i层上至多有2i-1121满二叉树和完全二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为[log2n]+1。从以上定义可知，满二叉树也是完全二叉树，反之则不然。满二叉树

最大层的结点均向左靠齐

完全二叉树

ADCBEF满二叉树和完全二叉树满二叉树除最后一层外，每一层上的所有结点122二叉树的基本性质性质5

如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序（从第1层到第[log2n]+1层，每层从左到右）从1起开始编号，则对任一编号为i的结点(1≤i≤n)，则:

(1)如果i=1，则编号为i的结点是二叉树的根，无双亲；如果i>1，则其双亲结点parent(i)的编号是[i/2]。

(2)如果2i>n，则编号为i的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)的编号是2i。

(3)如果2i+1>n，则编号为i的结点无右孩子；否则其右孩子结点rChild(i)的编号是结点2i+1。

二叉树的基本性质性质5如果对一棵有n个结点的完全二叉123二叉树的链式存储结构在二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。L(i)V(i)R(i)LchildvalueRchild二叉树的链式存储结构在二叉树的链式存储结构中，每个结点设置三124二叉树的链式存储结构二叉树的链式存储结构125二叉树的遍历二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树"和"遍历右子树"三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。

先序遍历二叉树中序遍历二叉树后序遍历二叉树若二叉树为空，则空操作；

否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。若二叉树为空，则空操作；

否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。若二叉树为空，则空操作；

否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。二叉树的遍历二叉树的遍历指不重复地访问二叉树的所有结点。从二126二叉树的遍历先序遍历：ABDEGHCFIJ中序遍历：DBGEHACIJF后序遍历：DGHEBJIFCA二叉树的遍历先序遍历：ABDEGHCFIJ127查找查找是指在一个给定的数据结构中查找某个指定的元素。顺序查找顺序查找一般是指在线性表中查找指定元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到，即查找成功；若线性表中的所有元素与被查找元素都不相等，则查找失败。顺序查找：最好情况比较1次，最坏情况比较n次如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。查找查找是指在一个给定的数据结构中查找某个指定的元素。128查找二分查找(折半查找)二分查找法只适用于顺序存储的有序表。先确定待查目标元素所在范围(区间)，然后逐步缩小范围直至找到该元素，或者当查找区间缩小到0也没有找到目标元素为止。查找过程中，给定值首先和处于待查区间"中间位置"的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到"前半个区间"或"后半个区间"之后继续进行查找。查找二分查找(折半查找)129折半查找二分查找折半查找二分查找130查找二分查找(折半查找)：由于每次都可以减少一半的元素，所以最坏时间复杂度为log(2n)查找二分查找(折半查找)：由于每次都可以减少一半的元素，所以131排序 排序是指将一个无序序列整理成按值递增或递减(本章均采用递增规则)的有序序列。排序可以在各种不同的存储结构上实现，本章所介绍的算法以顺序存储的线性表为排序对象，在程序设计语言中就是一维数组。排序的算法种类很多，主要包括交换类排序、插入类排序、选择类排序等。排序 排序是指将一个无序序列整理成按值递增或递减(本章均采用132排序技术交换类排序法

冒泡排序快速排序插入类排序法简单插入排序希尔排序选择类排序法简单选择排序堆排序排序技术交换类排序法133排序法小结：最坏时间复杂度：冒泡排序法、快速排序、简单选择排序法、简单插入排序：

最坏情况需要n(n-1)/2次比较；希尔排序法：最坏情况需要O(n1.5)次比较；堆排序法,最坏情况需要O(nlog2n)次比较；平均速度最快排序：快速排序最好、最坏、平均三种复杂度都相同的排序方法：堆排序排序法小结：最坏时间复杂度：134第二章程序设计基础(15%)考试大纲1.程序设计方法与风格。

2.结构化程序设计。

3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。

第二章程序设计基础(15%)考试大纲135知识点归纳程序设计方法程序设计是一门技术，需要相应的理论、方法和工具来支持。就程序设计方法和技术的发展而言，主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中，通常采用“自顶向下，逐步求精”的方法，即把一个模块的功能逐步分解，细化为一系列具体的步骤，进而转换成一系列用某种程序设计语言编写的程序。知识点归纳程序设计方法136详细设计：即过程设计。查找是指在一个给定的数据结构中查找某个指定的元素。软件从提出、实现、使用、维护到停止使用的过程称为软件的生命周期。系统测试：将通过确认测试的软件，作为整个计算机系统的一个元素，与计算机硬件、外设、支持软件、数据以及人员等其他系统元素组合在一起，在实际运行环境中对其进行一系列的集成测试和确认测试。整个链表的存储必须从头指针开始(顺序存取)，头指针指示链表中第一个结点的存储位置。在结构化分析的基础上，完成系统的规格说明，建立系统的一个自顶向下的任务分析模型。元组：关系中的行称为元组。结点的度：结点拥有的子树数。数据的高共享性和低冗余性双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子，该结点称为孩子结点的双亲结点。面向对象方法的基本概念后序遍历：DGHEBJIFCA指一个类(子类)直接使用另一个类(父类)的所有属性和方法。程序设计风格除了程序设计设计方法和技术之外，程序风格也是非常重要的。良好的程序设计风格概括起来包括以下及格方面：源程序文档化数据说明的方法语句的结构输入和输出详细设计：即过程设计。程序设计风格除了程序设计设计方法和技术137程序设计风格源程序文档化标识符的命名程序的注释序言性注释功能性注释程序的视觉组织数据的说明数据说明的次序应该规范化说明语句中变量的安排有序化使用注释说明复杂的数据结构程序设计风格源程序文档化138程序设计风格语句结构在一行内只写一条语句程序编写应优先考虑清晰性除非对效率有特殊要求，程序编写要做到清晰第一，效率第二首先要保证程序正确，然后才要求提高速度避免使用临时变量而使程序的可读性下降避免不必要的转移尽可能使用库函数避免使用复杂的条件语句尽量减少使用“否定”条件的条件语句数据结构要有利于程序的简化要模块化，使模块功能尽可能单一化利用信息隐蔽，确保每一个模块的独立性从数据出发构造程序不要修补不好的程序，要重写编写程序设计风格语句结构139程序设计风格输入和输出对所有输入数据检验合法性检查输入项的各种重要组合的合法性输入格式要简单，以使输入的步骤和操作尽可能简单输入数据时，应允许使用自由格式应允许缺省值输入一批数据时，最好使用输入结束标志在以交互式输入/输