《公共基础知识总结--二级考试必看》由会员分享，可在线阅读，更多相关《公共基础知识总结--二级考试必看（9页珍藏版）》请在金锄头文库上搜索。
1、1第一章数据结构与算法第一章数据结构与算法1.11.1 算法算法1 11 11 1 算法：是指解题方案的准确而完整的描述。算法：是指解题方案的准确而完整的描述。规定了解决某类问题所需的 操作语句 以及 执行顺序 使其能通过有限的指令语句，在一定时间内解决问题算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。1 1算法特征包括算法特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间
2、内做完，即能在执行有限的步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。2 2算法的基本要素算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构通常，计算机可以以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为计算机系统的指令系统。（1）计算机系统中的基本运算和操作包括：算术运算 + - * /逻辑运算 not and or 关系运算 ! =数据传输 赋值 输入与输出（2）算法的控制结构：顺序结构、选择结构、循环结构。3 3算法基本设计方法：算法基本设计方法：列举法 （列举所有解决方案）归纳法（特殊一般）递推 （已知未知）递归 （逐层分解）减
3、半递推回溯法: 找出一个解决问题的线索，然后沿着这个线索逐步多次“探、试”1 11 12 2 算法复杂度算法复杂度算法时间复杂度和算法空间复杂度。1 1算法时间复杂度算法时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。 （既算法的运算次数）含义：算法执行过程中所需要的基本运算次数2 2算法空间复杂度是指执行这个算法所需要的内存空间。算法空间复杂度是指执行这个算法所需要的内存空间。1.21.2 数据结构的基本基本概念数据结构的基本基本概念数据：数据： 在计算机科学中指所有能输入到计算机中的并被计算机程序处理的符号的总称数据元素：数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行
4、考虑和处理。数据结构数据结构：是相互之间存在一种或多种特定关系的数据元素的集合数据结构研究的三个方面：数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。1 12 22 2 数据结构的图形表示：数据结构的图形表示：春夏秋冬父亲儿子女儿D 1CAB21 12 23 3 线性结构与非线性结构线性结构与非线性结构如果一个非空的数据结构满足下列两个条件,则称该数据结构为线性结构，线性结构也称为线性表1)有且只有一个根结点2)每一个结点最多有
5、一个前件，也最多有一个后件特别需要说明的是特别需要说明的是，在一个线性结构中插入或删除任何一个结点后还应是线性结构。非线性结构：不满足线性结构条件的数据结构。1 13 3 线性表及其顺序存储结构线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。1 14 4 栈和队列栈和队列1 14 41 1 栈及其基本运算栈及其基本运算1 1什么是栈什么是栈栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈
6、按照“先进后出” （FILO）或“后进先出” （LIFO）组织数据，栈具有记忆作用。用 top 表示栈顶位置，用 bottom 表示栈底。2 2栈的顺序存储与栈的基本运算：栈的顺序存储与栈的基本运算：（1）插入元素称为入栈入栈运算；（2）删除元素称为退栈退栈运算；（3）读栈顶元素读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。1 14 42 2 队列及其基本运算队列及其基本运算1 1什么是队列什么是队列队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear 指针指向队尾，front 指针指向队头。队列是“先进先出” （FIFO）或“后进后出” （LILO）的
7、线性表。2 2循环队列运算包括循环队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0 表示队列空，s=1 且 front=rear 表示队列满1 15 5 线性链表线性链表 p24p24线性表的链式存储结构称为线性链表。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。链式存储方式的特点：链式存储方式的特点：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表
8、示线性结构，也可用于表示非线性结构。在线性链表中，用一个专门的指针 HEAD 指向线性链表中的第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）称为头指针， 头指针：在线性链表中，头指针（HEAD）很关键，不得丢失。1 16 6 树与二叉树树与二叉树 p31p311.6.11.6.1 树的基本概念树的基本概念1）树：是一种简单的非线性结构，所有元素之间具有明显的层次特性。2 2）父结点：）父结点：在树结构中，每一个结点只有一个前件，称为父结点父结点，3）根结点：没有前件的结点只有一个，称为树的根结点，简称树的根根。4）每一个结点可以有多个后件，称为该结点的子结点子结点。没有后
9、件的结点称为叶子结点叶子结点。5）结点的度：度：在树结构中，一个结点所拥有的后件的个数称为该结点的度度，6 6）树的度：）树的度：所有结点中最大的度称为树的度树的度。树的最大层次称为树的深度深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：（1）在二叉树的第 k 层上，最多有 2k-1(k1)个结点；（2）深度为 m 的二叉树最多有 2m-1 个结点；（3）度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个；3（4）具有 n 个结点的二叉树，其深度至少为log2n+1,其中log2n表示取 log2n
10、 的整数部分；（5）具有 n 个结点的完全二叉树的深度为log2n+1；完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR） ，根-左-右（2）中序遍历（LDR） ，左-根-右（3）后序遍历（LRD） ，左-右-根1 17 7 查找技术查找技术二分法查找只适用于顺序存储的有序表，对于长度为 n 的有序线性表，最坏情况只需比较 log2n次。1 18 8 排序技术排序技术交换类排序法：（1）冒泡排序法，需要比较的次数为 n(n-1)/2；
11、（2）快速排序法。插入类排序法：（1）简单插入排序法，最坏情况需要 n(n-1)/2 次比较；（2）希尔排序法，最坏情况需要 O(n1.5)次比较。选择类排序法：（1）简单选择排序法, 最坏情况需要 n(n-1)/2 次比较；（2）堆排序法，最坏情况需要 O(nlog2n)次比较。第二章程序设计基础第二章程序设计基础2 21 1 程序设计设计方法和风格程序设计设计方法和风格语句结构清晰第一、效率第二。如何形成良好的程序设计风格:1、源程序文档化；注释分序言性注释和功能性注释2、数据说明的方法；3、语句的结构； 顺序，选择，循环4、输入和输出。2 22 2 结构化程序设计结构化程序设计结构化程序
12、设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3.模块化；4.限制使用 goto 语句。结构化程序的基本结构和特点：（1）顺序结构：一种简单的程序设计，最基本、最常用的结构；（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；（3）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。2 23 3 面向对象的程序设计面向对象的程序设计1.面向对象方法的优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。2.基本概念：1）对象是面向对象方
13、法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。2）类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。3）消息：一个实例与另一个实例之间传递的信息。4）继承：是指能够直接获得已有的性质和特征。5）多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。6）封装性：是一种信息隐蔽技术。第三章软件工程基础第三章软件工程基础3 31 1 软件工程基本概念软件工程基本概念1.计算机软件是包括程序、数据及相关文档的完整集合。2.软件的特点包括：（1）软件是一种逻辑实体；（2）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行
14、、使用期间不存在磨损、老化问题；（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵；4（6）软件开发涉及诸多的社会因素。3.软件按功能分：应用软件、系统软件、支撑软件（或工具软件） 。4.软件危机是指软件在开发、运行、维护等过程中遇到的一系列问题。软件危机主要表现在成本、质量、生产率等问题软件危机主要表现在成本、质量、生产率等问题。5.软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。6.软件工程包括 3 个要素：方法、工具和过程。7.软件生命周期：软件从提出、实现、使用、维护到停止使用退役
15、的过程。8.软件生命周期三个阶段:软件定义、软件开发、运行维护9.软件生命周期主要活动阶段是：（1）可行性研究与计划制定； （2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。10.软件设计的基本原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可靠性。抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可靠性。11.软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理软件开发技术和软件工程管理。3 32 2 结构化分析方法结构化分析方法1.结构化方法的核心和基础是结构化程序设计理论。2.需求分析方法有（1）结构化需求分析方法； （
16、2）面向对象的分析的方法。3.从需求分析建立的模型的特性来分：静态分析和动态分析静态分析和动态分析。4.结构化分析的常用工具数据流图（DFD） ； 是需求理解的逻辑模型的图形表示数据流图的图符 加工 数据流存储文件源，潭建立数据流图的步骤：由外向里，自顶向下，逐层分解。数据字典（DD） ； 是结构化分析方法的核心，是对 DFD 中出现的被命名的图形元素的确切解释。判定树； 从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关 系、选择关系，根据它们构造判定树。判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。5.软件需求规格说明书的特点：（1）正确性；（2）
