第一章数据结构与算法
1
2、算法的基本特征（1）可行性（2）确定性（3）有穷性（4）拥有足够的情报。
3、算法复杂度主要包括时间复杂度和空间复杂度。
（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。
（2
1
2、数据结构主要研究和讨论以下三个方面的问题：数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算。
3、数据结构分为两大类型：线性结构和非线性结构。
（11）有且只有一个根结点；2）每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有线性表、栈、队列和线性链表等。
（2
1
由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。
*：线性表是一种存储结构，它的存储方式：顺序和链式。
2、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
3、顺序表的插入、删除运算
（1）顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。
（2）顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。
插入、删除运算不方便。
1.4 栈和队列
在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。
栈具有记忆作用。
栈的基本运算：1）插入元素称为入栈运算；2）删除元素称为退栈运算；3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
栈的存储方式和线性表类似，也有两种，即顺序栈和链式栈。
Rear）指向队尾元素，头指针（front）指向排头元素的前一个位置（队头）。
队列是“先进先出”或“后进后出”的线性表。
循环队列及其运算：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。循环队列中元素的个数=rear-front。
1.5 线性链表
1、线性链表：线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。因此，在链式存储方式中，每个结点由两部分组成：一部分用于存放数据元素的值，称为数据域；另一部分用于存放指针，称为指针域，用于指向该结点的前一个或后一个结点（即前件或后件），如下图所示：
线性链表分为单链表、双向链表和循环链表三种类型。
在线性链表中插入元素或删除元素时，不需要移动数据元素，只需要修改相关结点指针。
1.6 树与二叉树
几个概念：根结点、孩子结点、双亲结点、兄弟结点、叶子、层、度、深度
2、二叉树及其基本性质
（1）什么是二叉树
1）非空二叉树只有一个根结点；
2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
（2）二叉树的基本性质
★性质1 在二叉树的第k 层上，最多有 个结点。 ★性质2 深度为m 的二叉树最多有个 个结点。
★性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。n 0=n 2+1
★性质4 具有n 个结点的二叉树，其深度至少为 ，其中 表示取 的整数部分。
3、满二叉树与完全二叉树
满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
性质5 具有n 个结点的完全二叉树深度为 。
4、二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。
5、★二叉树的遍历 （1）前序遍历（2）中序遍历（3）后序遍历
1.7 查找技术
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
1、顺序查找
在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n 次。
下列两种情况下只能采用顺序查找：1）线性表是无序表2）采用链式存储结构的链表
2、二分法查找
特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n 次。
*：二分法查找只适用于顺序存储的线性表，且表中元素必须按关键字有序（升序）排列。
1.8 排序技术
总结：各种排序法比较：
1、交换类排序法（方法：冒泡排序n(n-1)/2，快速排序O(nlog 2n)，最坏n(n-1)/2)）。
2、插入类排序法（方法：简单插入排序n(n-1)/2，希尔排序）。
3、选择类排序法（方法：简单选择排序n(n-1)/2，堆排序O(nlog 2n)）。
本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。 数据域指针域HEAD …(a)结点结构(b)一个非空的线性链表示意图)1(21≥-k
k 12-m 1][log 2+n ][log 2n n 2log 1][log 2+n
第二章程序设计基础
2.1 程序设计风格
程序设计的风格主要强调：“清晰第一，效率第二”。
2.2 结构化程序设计（面向过程的程序设计方法）
1、结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化，限制使用goto语句。
2、结构化程序的基本结构：顺序结构，选择结构，重复结构(循环结构)。
2.3 面向对象的程序设计
客观世界中任何一个事物都可以被看成是一个对象，面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡人们在现实生活中常用的思维来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象及对象之间的关系能够如实地反映问题域中固有的事物及其关系。
面向对象方法的主要优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。
对象是客观世界中的任何实体，对象是实体的抽象。对象是属性和方法的封装体。
操作描述了对象执行的功能，操作也称为方法或服务。操作是对象的动态属性。
*：一个对象由对象名、属性和操作三部分组成。
对象的基本特点：标识惟一性，分类性，多态性，封装性，模块独立性好。
：信息隐蔽是通过对象的封装性来实现的。
类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。
许有一个父类，多重继承指一个类允许有多个父类。
本章应考点拨：本章在考试中会出现约1个题目，所占分值大约占2分，是出题量较小的一章。本章内容比较少，也很简单，掌握住基本的概念就可以轻松应对考试了，所以在这部分丢分，比较可惜。
第三章软件工程基础
3.1 软件工程基本概念
1、软件的相关概念
计算机软件是包括程序、数据及相关文档的完整集合。
软件的特点包括：1）软件是一种逻辑实体，而不是物理实体，具有抽象性；2）软件的生产与硬件不同，它没有明显的制作过程；3）软件在运行、使用期间不存在磨损、老化问题；4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；5）软件复杂性高，成本昂贵；6）软件开发涉及诸多的社会因素。
2、软件危机与软件工程
软件工程源自软件危机。所谓软件危机是泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。具体的说，在软件开发和维护过程中，软件危机主要表现在：
1）软件需求的增长得不到满足。用户对系统不满意的情况经常发生。
2）软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生。
3）软件质量难以保证。
4）软件不可维护或维护程度非常低。
5）软件的成本不断提高。
6）软件开发生产率的提高跟不上硬件的发展和应用需求的增长。
总之，可以将软件危机可以归结为成本、质量、生产率等问题。
就是要建造一个优良的软件系统，它所包含的内容概括为以下两点：
1）软件开发技术，主要有软件开发方法学、软件工具、软件工程环境。
2）软件工程管理，主要有软件管理、软件工程经济学。
软件工程的主要思想是将工程化原则运用到软件开发过程，它包括3个要素：方法、工具和过程。方法是完成软件工程项目的技术手段；工具是支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。
软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。
软件生命周期分为软件定义、软件开发及软件运行维护三个阶段：
1）软件定义阶段：包括制定计划和需求分析。
制定计划：确定总目标；可行性研究；探讨解决方案；制定开发计划。
需求分析：对待开发软件提出的需求进行分析并给出详细的定义。
2）软件开发阶段：
软件设计：分为概要设计和详细设计两个部分。
软件实现：把软件设计转换成计算机可以接受的程序代码。
软件测试：在设计测试用例的基础上检验软件的各个组成部分。
3）软件运行维护阶段：软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。
*：软件生命周期中所花费最多的阶段是软件运行维护阶段。
4、软件工程的目标和与原则
（1）软件工程目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。
（2）软件工程需要达到的基本目标应是：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；能按时完成开发，及时交付使用。
（3）软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。
件开发过程的复杂性。
2
3
块过大会使模块内部的复杂性增加，不利于模块的理解和修改，也不利于模块的调试和重用；模块太小会导致整个系统表示过于复杂，不利于控制系统的复杂性。
4
5
6
7
8
5、软件开发工具与软件开发环境
（1）软件开发工具
软件开发工具的完善和发展将促使软件开发方法的进步和完善，促进软件开发的高速度和高质量。
（2）软件开发环境
软件开发环境（或称软件工程环境）是全面支持软件开发全过程的软件工具集合。
CASE，Computer Aided Software Engineering）将各种软件工具、开发机器和一个存放开发过
程信息的中心数据库组合起来，形成软件工程环境。它将极大降低软件开发的技术难度并保证软件开发的质量。
3.2 结构化分析方法
结构化方法的核心和基础是结构化程序设计理论。
1、需求分析
需求分析方法有：1）结构化需求分析方法；2）面向对象的分析方法。
*：需求分析的任务就是导出目标系统的逻辑模型，解决“做什么”的问题。
*：需求分析一般分为需求获取、需求分析、编写需求规格说明书和需求评审四个步骤进行。
2、结构化分析方法
结构化分析方法是结构化程序设计理论在软件需求分析阶段的应用。
结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。
结构化分析的常用工具：1）数据流图（DFD）；2）数据字典（DD）；3）判定树；4）判定表。
数据流图以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。
上图是数据流图的基本图形元素：
加工（转换）：输入数据经加工变换产生输出。
数据流：沿箭头方向传送数据的通道，一般在旁边标注数据流名。
存储文件（数据源）：表示处理过程中存放各种数据的文件。
源，潭：表示系统和环境的接口，属系统之外的实体。
画数据流图的基本步骤：自外向内，自顶向下，逐层细化，完善求精。
下图是一个数据流图的示例：
数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。
*：数据字典的作用是对数据流图中出现的被命名的图形元素的确切解释。
*：数据字典是结构化分析方法的核心。
SRS）
软件需求规格说明书是需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。
3.3 结构化设计方法
1、软件设计的基础
*：需求分析主要解决“做什么”的问题，而软件设计主要解决“怎么做”的问题。
从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。
结构设计：定义软件系统各主要部件之间的关系。
数据设计：将分析时创建的模型转化为数据结构的定义。
加工数据流存储文件源、潭
接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。
过程设计：把系统结构部件转换成软件的过程性描述。
从工程角度来看，软件设计分两步完成，即概要设计和详细设计。
概要设计：又称结构设计，将软件需求转化为软件体系结构，确定系统级接口、全局数据结构或数据库模式。
详细设计：确定每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。
软件设计的基本原理包括：抽象、模块化、信息隐蔽和模块独立性。
1）抽象。抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。
2）模块化。解决一个复杂问题时自顶向下逐步把软件系统划分成一个个较小的、相对独立但又不相互关联的模块的过程。
3）信息隐蔽。每个模块的实施细节对于其他模块来说是隐蔽的。
4）模块独立性。软件系统中每个模块只涉及软件要求的具体的子功能，而和软件系统中其他模块的接口是简单的。*：模块分解的主要指导思想是信息隐蔽和模块独立性。
模块的耦合性和内聚性是衡量软件的模块独立性的两个定性指标。
内聚性：是一个模块内部各个元素间彼此结合的紧密程度的度量。
*：按内聚性由弱到强排列，内聚可以分为以下几种：偶然内聚、逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚及功能内聚。
耦合性：是模块间互相连接的紧密程度的度量。
*：按耦合性由高到低排列，耦合可以分为以下几种：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合以及非直接耦合。
一个设计良好的软件系统应具有高内聚、低耦合的特征。
在结构化程序设计中，模块划分的原则是：模块内具有高内聚度，模块间具有低耦合度。
2、总体设计（概要设计）和详细设计
（1）总体设计（概要设计）
软件概要设计的基本任务是：1）设计软件系统结构；2）数据结构及数据库设计；3）编写概要设计文档；4）概要设计文档评审。
常用的软件结构设计工具是结构图，也称程序结构图。程序结构图的例图及有关术语列举如下：
深度：表示控制的层数。宽度：整体控制跨度（最大模块数的层）的表示。扇入：调用一个给定模块的模块个数。扇出：一个模块直接调用的其他模块数。原子模块：树中位于叶子结点的模块。
面向数据流的设计方法定义了一些不同的映射方法，利用这些方法可以把数据流图变换成结构图表示软件的结构。数据流的类型：大体可以分为两种类型，变换型和事务型。
A、变换型：变换型数据处理问题的工作过程大致分为三步，即取得数据、变换数据和输出数据。变换型系统结构图由输入、中心变换、输出三部分组成。
B、事务型：事务型数据处理问题的工作机理是接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。
（2）详细设计
详细设计是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。
*：详细设计的任务是确定实现算法和局部数据结构，不同于编码或编程。
常用的详细设计工具有以下几种：图形工具、表格工具、语言工具
图形工具：程序流程图、N-S（方盒图）、PAD（问题分析图）和HIPO（层次图+输入/处理/输出图）。
表格工具：判定表。
语言工具：PDL（伪码）
3.4 软件测试
1、软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。
*：软件测试的目的：尽可能地多发现程序中的错误，不能也不可能证明程序没有错误。软件测试的关键是设计测试用例，一个好的测试用例能找到迄今为止尚未发现的错误。
、软件测试方法：静态测试和动态测试。
动态测试：是基于计算机的测试，主要包括白盒测试方法和黑盒测试方法。
（1）白盒测试
白盒测试方法也称为结构测试或逻辑驱动测试。它是根据软件产品的内部工作过程，检查内部成分，以确认每种内部操作符合设计规格要求。
白盒测试的基本原则：保证所测模块中每一独立路径至少执行一次；保证所测模块所有判断的每一分支至少执行一次；保证所测模块每一循环都在边界条件和一般条件下至少各执行一次；验证所有内部数据结构的有效性。
*：白盒测试法的测试用例是根据程序的内部逻辑来设计的，主要用软件的单元测试，主要方法有逻辑覆盖、基本路径测试等。
A、逻辑覆盖。逻辑覆盖泛指一系列以程序内部的逻辑结构为基础的测试用例设计技术。
B、基本路径测试。其思想和步骤是，根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例，对每一条独立执行路径进行测试。
（2）黑盒测试
黑盒测试方法也称为功能测试或数据驱动测试。黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。黑盒测试主要诊断功能不对或遗漏、接口错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错误。
黑盒测试不关心程序内部的逻辑，只是根据程序的功能说明来设计测试用例，主要方法有等价类划分法、边界值分析法、错误推测法等，主要用软件的确认测试。
价类），然后从每个等价类中选取数据作为测试用例。
B
C
例。
3、软件测试过程一般按4个步骤进行：单元测试、集成测试、确认测试和系统测试。
（1）单元测试
的各种错误。
*
（2）集成测试
集成测试是测试和组装软件的过程，它是把模块在按照设计要求组装起来的同时进行测试，主要目的是发现与接口有关的错误。集成测试的依据是概要设计说明书。
（3）确认测试
确认测试的任务是验证软件的有效性，即验证软件的功能和性能及其他特性是否与用户的要求一致。
确认测试的主要依据是软件需求规格说明书。确认测试主要运用黑盒测试法。
（4）系统测试
系统测试的测试用例应根据需求分析规格说明来设计，并在实际使用环境下来运行。
3.5 程序的调试
程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行，调试程序应该由编制源程序的程序员来完成。程序调试的基本步骤：（1）错误定位；（2）纠正错误；（3）回归测试。
*：软件的调试后要进行回归测试，防止引进新的错误。
软件调试可分为静态调试和动态调试。静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的调试手段，而动态调试是辅助静态调试。
对软件主要的调试方法可以采用：
（1）强行排错法。主要方法有：通过内存全部打印来排错；在程序特定部位设置打印语句；自动调试工具。
（2）回溯法。发现了错误，分析错误征兆，确定发现“症状”的位置。一般用于小程序。
（3）原因排除法。是通过演绎、归纳和二分法来实现的。
本章应考点拨：本章在笔试中一般占8分左右，约3道选择题，1道填空题，是公共基础部分比较重要的一章。从出题的深度来看，本章主要考察对基本概念的识记，有少量对基本原理的理解，没有实际运用，因此考生在复习本章时，重点应放在基本概念的记忆和基本原理的理解上。
第四章数据库设计基础
4.1 数据库系统的基本概念
1
（2
并可被各个应用程序所共享。
（3
数据服务等，是数据库的核心。
数据库管理系统功能：1）数据模式定义。2）数据存取的物理构建。3）数据操纵。4）数据的完整性、安生性定义
5）数据库的并发控制与故障恢复。6）数据的服务。（4
（5）：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。
*：数据库技术的根本目标是解决数据的共享问题。
2、数据库系统的发展
数据库管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。
下表是数据管理三个阶段的比较：
3、数据库系统的基本特点
（1）数据的高集成性。
（2*：数据库系统可以减少数据冗余，但无法避免一切冗余。
（3
序。也就是说，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。
数据独立性一般分为物理独立性与逻辑独立性两级。
1
理存储的更换、存取方式改变等都不影响数据库的逻辑结构，从而不致引起应用程序的变化。
2
相应修改应用程序，这就是数据的逻辑独立性。
（4）数据统一管理与控制。包含：
1）数据的完整性检查：检查数据库中数据的正确性以保证数据的正确。
2）数据的安全性保护：检查数据库访问者以防止非法访问。
3）并发控制：控制多个应用的并发访问所产生的相互干扰以保证其正确性。
4、数据库系统的内部结构体系
（1）数据库系统的三级模式：
1
2
出。
3
及文件级上，它还未深入到设备级上（如磁盘及磁盘操作）。内模式对一般用户是透明的，但它的设计直接影响数据库的性能。
（2）数据库系统的两级映射：
1
改相应的概念模式/内模式的映射，使得数据库的逻辑模式不变，其外模式不变，应用程序不用修改，从而保证数据2外模式/逻辑模式映射，使得用户所使用的那部分外模式不变，从而应用程序不必修改，保证数据具有较高的逻辑独立性。
4.2 数据模型
1、数据模型
（1）数据模型分为概念模型、逻辑数据模型和物理模型三类：
1）概念数据模型：主要有：E-R 模型(实体联系模型)。
2）逻辑数据模型：主要有：层次模型、网状模型、关系模型、面向对象模型等。
3）物理数据模型：又称物理模型，它是一种面向计算机物理表示的模型。
2、实体联系模型及E-R 图 （1）E-R 模型的基本概念：1）实体2）属性3）联系。有一对一、一对多、多对多的联系。
（2）E-R 模型的图示法：1）实体：用矩形表示。2）属性：用椭圆形表示。3）联系：用菱形表示。
（3）数据库管理系统常见的数据模型有层次模型、网状模型和关系模型三种。
3）关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个关系。每行数据称为元组。
主键，表中的一个属性或几个属性的组合、其值能唯一地标识表中一个元组的。例如，学生的学号。主码属性不能取空值。
外键，在一个关系中含有与另一个关系的关键字相对应的属性组称为该关系的外部关键字。
（4）关系中的数据约束：
1
2
30—100之间等。
目录 二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。 2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式 公共基础的考试方式为笔试，与C语言（V isualBASIC、V isual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。 公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 （一）算法 1．算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。 1）算法的基本特征 （1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
公共知识笔记大全（pdf豪华版） 第一部分马克思主义哲学 1、哲学、世界观、方法论 哲学，是系统化、理论化的世界观。 方法论是人们认识世界、改造世界的根本方法。 2、哲学的基本问题 哲学的基本问题，包括两个方面，两个层次。 第一方面，是关于物质和意识谁是第一性、谁是第二性的问题，是划分唯物主义和唯心主义的根本依据。 第二方面，是物质和意识是否具有同一性的问题，即人的意识能否认识和反映物质世界的问题，是划分可知识和不可知论的根本依据。 在哲学基本问题之后，还有一个世界处于什么状态的问题，并由此产生形而上学和辩证法的对立。 3、马克思主义哲学的产生 自然科学：细胞学说、能量守恒定律、达尔文生物进化论 阶级基础：英国宪章运动、法国里昂工人起义、德国西里西亚纺织工人起义 社会科学：英国古典经济学、法国空想社会主义、黑格尔辩证法、费尔巴哈唯物主义 4、马克思主义哲学的基本特征 马克思主义哲学的本质特征是它的实践性，是实践基础上的科学性和革命性的统一。 5、辩证唯物主义的物质观 （一）物质观的发展 主观唯心主义：“存在就是被感知”。 客观唯心主义：“理”、“理念”、“绝对观念” 古代朴素唯物主义:物质为一种或几种常见的具体形态。 近代形而上学唯物主义:物质是物质结构的某一层次或不可分割的最小粒子。 旧唯物主义无法对意识现象及社会历史的本质，做出唯物科学解释，旧唯物主义的物质观是形而上学的，历史观是唯心主义的。 （二）马克思主义哲学的物质观 恩格斯：“物、物质无非是各种物的总和，而这个概念就是从这一总和中抽象出来的。” 列宁：“物质是标志客观实在的哲学范畴，这种客观实在是人通过感觉感知的，它不依赖于我们的感觉而存在，为我们的感觉所复写、摄影、反映”。 物质的唯一特性：客观实在性 6、辩证唯物主义的运动观 物质是运动的物质，运动是物质的运动。运动是物质自身的固有属性和存在方式。 物质运动的具体形式是多种多样的。物质运动可分为五种基本形式：即机械运动、物理运动、化学运动、生物运动和社会运动。各种物质运动之间的区别与联系：低级运动形式是高级运动形式的基础、高级运动形式是从低级运动形式发展而来的；高级运动包含低级运动形式；各种运动形式同时并存、相互制约并在一定条件下相互转化。 静止是有条件的、暂时的和相对的，运动是无条件的和绝对的。静止是一种特殊的运动状态。 物质运动具有其自身的规律性。规律就是事物运动过程中自身所固有的本质的必然的联系。规律具有如下共同点：规律具有稳定性；规律具有普遍性；规律具有可重复性。 7、世界的物质统一性 世界的物质统一性原理，是对无限多样和永恒运动着的整个世界的根本观点和总的看法，是对整个世界的普遍本质和共同基础的科学反映，是马克思主义哲学的基础，也是我们从事一切工作的出发点。一切从实际出发，实事求是。 8、意识的起源 意识是自然界长期发展的产物：无机物的反映特性进化为低等生物的刺激感应性；低等生物的刺激感应性进化为高等动物的感觉和心理；动物心理进化为人的意识。
全国计算机等级考试二级公共基础知识要点汇总 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件；
公共基础笔记 第三部分法律 1、法的概念和本质 法是由国家制定、认可并保证实施的，反映由特定物质生活条件所决定的统治阶段意志，以权利和义务为内容，以确认、保护和发展统治阶级所期望的社会关系和社会秩序为目的行为规范体系。 共同本质：法是统治阶级意志的表现。 基本特征：（1）法是调整人的行为或社会关系的规范；（2）法是由国家制定或认可，并具有普遍约束力的社会规范；（3）法是以国家强制力保证实施的社会规范；（4）法是规定权利和义务的社会规范。 规范作用：作为由国家制定的社会规范，法具有指引、评价、预测、教育和强制等规范作用。 社会作用：维护统治阶级的阶级统治；执行社会公共事务。 2、法与其他社会现象之间的关系 （1）法与经济 法在市场经济宏观调控中的作用：引导作用；促进作用；保障作用；制约作用。 法在规范微观经济行为中的作用：确认经济活动主体的法律地位；调整经济活动中各种关系；解决经济活动中的各种纠纷；维护正常的经济秩序。 （2）法与政治、政策 法受政治制约体现在：政治关系的发展变化是影响法的发展变化的重要因素；政治体制的改革也制约法的内容及其发展的变化；政治活动的内容更制约法的内容及其变化。 党的政策指导法制建设的各个环节，社会主义法是实现党的政策的重要手段和形式，同时又对党的政策起到一定的制约作用。 3、法律制度的相关概念 法的制定：指一定的国家机关依照法定职权和法定程序制定、修改、废止法律和其他规范性法律文件的一种专门活动，一般也称为法律的立、改、废活动。 立法的指导思想：我国现阶段立法的指导思想，必须是以建设有中国特色社会主义理论和党的基本路线为指导，为实现社会主义现代化建设服务，而不能以别的思想为指导，不能离开社会主义解放生产力、发展生产力这个根本任务。 立法的基本原则：（1）立法必须以宪法为依据；（2）立法必须从实际出发；（3）总结实践经验与科学预见相结合；（4）吸收、借鉴历史和国外的经验；（5）以最大多数人的最大利益为标准，立足全局，统筹兼顾；（6）原则性和灵活性相结合；（7）保持法律的稳定性和连续性与及时立、改、废相结合。 法的渊源：（1）宪法；（2）法律；（3）行政法规；（4）地方性法规；（5）自治条例、单行条例；（6）行政规章；（7）国际条约。 法律部门：（1）宪法；（2）行政法；（3）民法；（4）婚姻法；（5）经济法；（6）劳动法；（7）环境法；（8）刑法；（9）诉讼法；（10）军事法。 4、法律实施中的相关概念 法律实施包括执法、司法和守法。 法律适用的要求：准确，指适用法律时，事实要调查清楚，证据要准确；合法，指司法机关审理案件时要合乎国家法律的规定，依法办案；及时，指司法机关办案时在正确、合法的前提下，还必须做到遵守时限。 法律适用的原则：公民在法律面前一律平等；以事实为根据，以法律为准绳；司法机关依法独立行使职权；实事求是，有错必纠。 法律关系的基本特征：法律关系是以权利义务为内容的社会关系；法律关系是由国家强制力保证的社会关系；法律关系是以现行法律存在为前提的社会关系。它不属于物质关系，而是一种思想关系。 违法的分类：刑事违法、民事违法、行政违法、违宪行为。 5、宪法的基本理论 宪法是规定国家根本制度、集中表现各种政治力量实际对比关系、规范国家权力和保障公民基本权利的国家根本法。 宪法的法律特征：内容上，宪法规定国家的根本制度、公民的基本权利和义务、国家机构的组织和活动原则等根本问题；效力上，宪法具有最高法律效力；程序上，宪法的制定和修改比其他法律更为严格。 宪法的政治特征：宪法是民主政治的法律化；宪法是对民主政治的保障；宪法集中表现各种政治力量的实际对比关系；宪法规范国家权力，保障公民基本权利。 西方宪法的基本原则：人民主权原则；基本人权原则；法治原则；权力分立与制衡原则。
第一章数据结构 一、选择题 （1）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 【答案】A 【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。选项A正确。 （2）下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 【答案】C 【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项C。 （3）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 【答案】D 【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。 (4)算法执行过程中所需要的存储空间称为算法的 A）时间复杂度B）计算工作量C）空间复杂度D）工作空间 【答案】c 【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。 (5)下列关于队列的叙述中正确的是 A）在队列中只能插入数据B）在队列中只能删除数据 C）队列是先进先出的线性表D）队列是先进后出的线性表 【答案】c 【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。 (6)设有下列二叉树： A
全国计算机二级考试公共基础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由
1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
公共基础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。
线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 1．4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满 1．5 线性链表 数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。
全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
第一部分教育学基础 第一章教育及教育学 第一节、教育概述（P3）※ 一、教育的概念 1、广义泛指凡是能够增长人的知识和技能，影响人的思想品德，提高人的认识能力，增强人的体质，完善人的个性的一切活动。 2、狭义即学校教育，是教育者根据社会发展的要求，在特定的教育场所，有目的、有计划、有组织的对受教育者的身心施加影响，以使他们的身心朝着社会期望的方向发展的过程。（组织性、计划性、目的性，专业的师资和场地，系统的教育及教学组织的规范） 3、更狭义思想品德教育活动（德育） 二、教育的要素（P3-P4）※ 构成教育活动的基本要素：教育者受教育者教育影响 1、教育者是教育实践活动的主体。 教育者的基本特征：主体性目的性社会性 2、受教育者是教育的对象，是学习的主体具有受教性（受教性是人的身心发展和动物的省心发展的本质区别）。 3、教育影响是置于教育者和受教育者之间的一切“中介”的总和。它包括作用于受教育者的影响以及运用这种影响的活动方式和方法。 4、教育要素之间的关系教育三个要素之间既相互独立，又相互制约，共同构成一个完整的实践活动系统，缺一不可。教育者按一定的目的和要求来改变受教育者，教育者及受教育者之间相互作用；教育者和受教育者之间的作用及联系是以一定的教育影响为中介的；三者之间相互联系和作用的结果使受教育者发生合乎目的的变化。 三、教育的形态 含义：由教育三要素所构成的教育系统在不同时空背景下的变化形式，也是“教育”理念的历史实现。 （一）根据教育系统自身形式化的程度：非制度化的教育及制度化的教育。 非制度化教育：没能形成相对独立的教育形式的教育——生产及生活高度一体化（人类学校教育以前的教育。 制度化教育：由专门的教育人员、机构及其运行制度所构成的教育形态——人类教育的高级形态，促进人类教育文明的发展。 （二）从教育系统所赖以运行的空间特性来看：家庭教育、学校教育、社会教育。 家庭教育：以家庭为单位进行的教育活动。 学校教育：根据一定的社会要求，按照一定的目的，选择适当的内容，利用集中的时间，有计划、系统地向学生进行各种科学文化知识的教育。 社会教育：在广泛的社会生活和生产过程中所进行的教育活动。 特点：开放性、群众性、多样性、补偿性、融合性
第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的次数下终止。特征包括：（1）可行性;（2)确定性(3）有穷性（4）拥有足够的情报。 ３、算法的基本要素:一是对数据对象的运算和操作；二是算法的控制结构。 ４、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 ６、算法的控制结构：顺序结构、选择结构、循环结构。 7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; （2）在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 ２、数据的逻辑结构包含:(1）表示数据元素的信息;(2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 ３、线性结构条件：(1）有且只有一个根结点;(２）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 线性表及其顺序存储结构 １、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1）且只有一个根结点ａ1，它无前件；(2)有且只有一个终端结点an，它无后件; （3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当ｎ=0时，称为空表。 3、线性表的顺序存储结构具有以下两个基本特点：(１）线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO)或“后进先出”(LＩFO）组织数据,栈具有记忆作用。用ｔop表示栈顶位置，用ｂottoｍ 表示栈底。 2、栈的基本运算：(1）插入元素称为入栈运算；（2)删除元素称为退栈运算;（３）读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端（队尾）进入插入,而在另一端(队头）进行删除的线性表。Ｒear指针指向队尾,frｏnt 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表
全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1、算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2、数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3、线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5、线性单链表、双向链表与循环链表的结构及其基本运算。 6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7、顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1、程序设计方法与风格。 2、结构化程序设计。 3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1、软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3、结构化设计方法，总体设计与详细设计。 4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统 测试。 5、程序的调试，静态调试与动态调试。 四、数据库设计基础 1、数据库的基本概念：数据库，数据库管理系统，数据库系统。 2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4、数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式：公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 （一）算法 1．算法的基本概念：算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且
公共基础笔记 第一部分马克思主义哲学 1、哲学、世界观、方法论 哲学，是系统化、理论化的世界观。 方法论是人们认识世界、改造世界的根本方法。 2、哲学的基本问题 哲学的基本问题，包括两个方面，两个层次。 第一方面，是关于物质和意识谁是第一性、谁是第二性的问题，是划分唯物主义和唯心主义的根本依据。 第二方面，是物质和意识是否具有同一性的问题，即人的意识能否认识和反映物质世界的问题，是划分可知识和不可知论的根本依据。 在哲学基本问题之后，还有一个世界处于什么状态的问题，并由此产生形而上学和辩证法的对立。 3、马克思主义哲学的产生 自然科学：细胞学说、能量守恒定律、达尔文生物进化论 阶级基础：英国宪章运动、法国里昂工人起义、德国西里西亚纺织工人起义 社会科学：英国古典经济学、法国空想社会主义、黑格尔辩证法、费尔巴哈唯物主义 4、马克思主义哲学的基本特征 马克思主义哲学的本质特征是它的实践性，是实践基础上的科学性和革命性的统一。 5、辩证唯物主义的物质观 （一）物质观的发展 主观唯心主义：“存在就是被感知”。 客观唯心主义：“理”、“理念”、“绝对观念” 古代朴素唯物主义:物质为一种或几种常见的具体形态。 近代形而上学唯物主义:物质是物质结构的某一层次或不可分割的最小粒子。 旧唯物主义无法对意识现象及社会历史的本质，做出唯物的科学解释，旧唯物主义的物质观是形而上学的，历史观是唯心主义的。 （二）马克思主义哲学的物质观 恩格斯：“物、物质无非是各种物的总和，而这个概念就是从这一总和中抽象出来的。” 列宁：“物质是标志客观实在的哲学范畴，这种客观实在是人通过感觉感知的，它不依赖于我们的感觉而存在，为我们的感觉所复写、摄影、反映”。 物质的唯一特性：客观实在性
2017计算机二级公共基础知识完整
第一章数据结构与算法 经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。 详细重点学习知识点： 1．算法的概念、算法时间复杂度及空间复杂度的概念 2．数据结构的定义、数据逻辑结构及物理结构的定义 3．栈的定义及其运算、线性链表的存储方式 4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历 5．二分查找法 6．冒泡排序法 1.1 算法 考点1 算法的基本概念 考试链接： 考点1在笔试考试中考核的几率为30% ，主要是以填空题的形式出现，分值为2分，此考点为识记内容，读者还应该了解算法中对数据的基本运算。 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法的基本要素：
（1）算法中对数据的运算和操作一个算法由两种基 本要素组成：一是对数据对象的运算和操作；二是算 法的控制结构。在一般的计算机系统中，基本的运算 和操作有以下4类：算术运算、逻辑运算、关系运算 和数据传输。 （2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 考点2 算法复杂度 考试链接： 考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70% ，主要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时间复杂度及空间复杂度的概念。 1.算法的时间复杂度算法的时间复杂度是指执行算 法所需要的计算 工作量。 同一个算法用不同的语言实现，或者用不同的编译 程序进行编译，或者在不同的计算机上运行，效率均不 同。这表明使用绝对的时间单位衡量算法的效率是不合 适的。撇开这些与计算机硬件、软件有关的因素，可 以认为一个特定算法" 运行工作量" 的大小，只依赖 于问题的规模（通常用整数n表 示），它是问题规模的函数。即算法的工作量=f（n） 2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存
二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A．所谓算法就是计算方法 B．程序可以作为算法的一种描述方法 C．算法设计只需考虑得到计算结果 D．算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A．算法的复杂度包括时间复杂度与空间复杂度 B．算法的复杂度是指算法控制结构的复杂程度 C．算法的复杂度是指算法程序中指令的数量 D．算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A．算法的时间复杂度与计算机的运行速度有关 B．算法的时间复杂度与运行算法时特定的输入有关 C．算法的时间复杂度与算法程序中的语句条数成正比 D．算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A．非线性结构可以为空 B．只有一个根结点和一个叶子结点的必定是线性结构 C．只有一个根结点的必定是线性结构或二叉树 D．没有根结点的一定是非线性结构 5、设数据结构B=(D，R)，其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A．线性结构 B．循环队列 C．循环链表 D．非线性结构 6、下列叙述中正确的是______。 A．矩阵是非线性结构 B．数组是长度固定的线性表 C．对线性表只能作插入与删除运算 D．线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。 A．不同，但元素的存储顺序与逻辑顺序一致 B．不同，且其元素的存储顺序可以与逻辑顺序不一致 C．相同，元素的存储顺序与逻辑顺序一致 D．相同，但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A．能采用顺序存储的必定是线性结构 B．所有的线性结构都可以采用顺序存储结构 C．具有两个以上指针的链表必定是非线性结构 D．循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A．在栈中，栈顶指针的动态变化决定栈中元素的个数
计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据，所以入栈最早的最后出栈，而队列是先进先出的线性 表。 2.循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的线性表。 在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定 树与判定表。 7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。 8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性 组，并且在结果中把重复的属性列去掉。 10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活，直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。 14.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点，则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次，而堆 排序在最坏的情况下需要比较的次数是nlog2n，即在排序方法中，最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为：应用软件，系统软件和支撑软件（或工具软件）。 19.软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误。 程序调试的基本步骤有：错误定位，修改设计和代码，以排除错误进行回归测试，防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有：所有测试都应追溯到需求，严格执行测试计划，排除测试的随 意性，充分注意测试中的群集现象，程序员应避免检查自己的程序，穷举测试不可能，
公共基础知识笔记 第一部分马克思主义哲学 1、哲学、世界观、方法论 哲学，是系统化、理论化的世界观。方法论是人们认识世界、改造世界的根本方法。 2、哲学的基本问题 哲学的基本问题，包括两个方面，两个层次。 第一方面，是关于物质和意识谁是第一性、谁是第二性的问题，是划分唯物主义和唯心主义的根本依据。 第二方面，是物质和意识是否具有同一性的问题，即人的意识能否认识和反映物质世界的问题，是划分可知识和不可知论的根本依据。 在哲学基本问题之后，还有一个世界处于什么状态的问题，并由此产生形而上学和辩证法的对立。 3、马克思主义哲学的产生 自然科学：细胞学说、能量守恒定律、达尔文生物进化论 阶级基础：英国宪章运动、法国里昂工人起义、德国西里西亚纺织工人起义 社会科学：英国古典经济学、法国空想社会主义、黑格尔辩证法、费尔巴哈唯物主义 4、马克思主义哲学的基本特征 马克思主义哲学的本质特征是它的实践性，是实践基础上的科学性和革命性的统一。
5、辩证唯物主义的物质观 （一）物质观的发展 主观唯心主义：“存在就是被感知”。 客观唯心主义：“理”、“理念”、“绝对观念” 古代朴素唯物主义:物质为一种或几种常见的具体形态。 近代形而上学唯物主义:物质是物质结构的某一层次或不可分割的最小粒子。 旧唯物主义无法对意识现象及社会历史的本质，做出唯物的科学解释，旧唯物主义的物质观是形而上学的，历史观是唯心主义的。 （二）马克思主义哲学的物质观 恩格斯：“物、物质无非是各种物的总和，而这个概念就是从这一总和中抽象出来的。” 列宁：“物质是标志客观实在的哲学范畴，这种客观实在是人通过感觉感知的，它不依赖于我们的感觉而存在，为我们的感觉所复写、摄影、反映”。 物质的唯一特性：客观实在性 6、辩证唯物主义的运动观 物质是运动的物质，运动是物质的运动。运动是物质自身的固有属性和存在方式。 物质运动的具体形式是多种多样的。物质运动可分为五种基本形式：即机械运动、物理运动、化学运动、生物运动和社会运动。各种物质运动之间的区别与联系：低级运动形式是高级运动形式的基础、