公共基础知识总结
第一章数据结构与算法
1.1 算法
1.2 数据结构的基本基本概念
（1
（2
线性结构条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素的所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
1．4 栈和队列
1、先进后出 FILO;
1、支持子程序调用;
2、具有记忆功能；
3、可以不用顺序存放数据；
4、只能够在top首部进行操作，bottom是绝对不动的；
5、栈的存放数据的个数为 num = （bottom – top）+1；
1、Rear指针指向队尾，front指针指向队头。
3、先进先出FIFO,或者是后进后出LILO
2、循环队列里面的个数计算方法：
A、rear > front 的时候， num = rear – front；
B、rear < front 的时候， num = rear + n – front；
1．5 线性链表
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性结构，也可用于表示非线性结构。
1．6 树与二叉树
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
子树。
二叉树的基本性质：必考的题目
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；
（2）深度为m的二叉树最多有2m-1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）二叉树中 n = n0 +n1 +n2
每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
二叉树的遍历：（一般画个图要你把顺序写出来）
1．7 查找技术
顺序查找的使用情况：
长度为n的线性表，找出一个数据，最差的情况为比较n 次。
长度为n的线性表，找出一个最大数据，最差的情况为比较n-1 次。
二分查找：对于长度为n的有序线性表，最坏情况只需比较
1．8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法：（1
（2。
插入类排序法：（1
（2
选择类排序法：（1）简单选择排序法,
（2）堆排序法，最坏情况需要
第二章程序设计基础
2．1 程序设计设计方法和风格
程序设计方法有两种，结构化程序设计和面向对象程序设计。
2．2 结构化程序设计
结构化程序设计方法的四条原则是：考试重点都要背下来
1.自顶向下；
2. 逐步求精；
3.模块化；
4.限制使用goto语句。
注意，这四个特点中，最重要的是模块化。
结构化程序的基本结构和特点：顺序结构\选择结构\循环结构
2．3 面向对象的程序设计
面向对象的程序设计：以对象为核心。
面向对象具备哪些基本概念：
对象、类和实例、消息、继承、多态性、
面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。
对象的基本特点：
（1）标识惟一性；
（2）分类性；
（3）多态性；重点
（4）封装性；重点
（5）模块独立性好。
消息的组成包括：
（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。
继承分单继承和多重继承。对象也可以没有继承。
1、单继承指一个类只允许有一个父类，
2、多重继承指一个类允许有多个父类。
第三章软件工程基础
3．1 软件工程基本概念
软件的特点包括：
（1）软件是一种逻辑实体；
（2）软件的生产与硬件不同，它没有明显的制作过程；
（3）软件在运行、使用期间不存在磨损、老化问题；
（4）软件的开发、运行对计算机系统具有依赖性，
（5）软件复杂性高，成本昂贵；
（6）软件开发涉及诸多的社会因素。
1、数据库管理系统是系统软件。
2、教务处管理系统是应用软件。
软件危机主要表现在成本、质量、生产率等问题。
软件工程包括3个要素：方法、工具、过程。
方法：完成软件工程项目的技术手段。
工具：支持软件的开发、管理、文档生成。
过程：支持软件开发的各个环节的控制、管理。
主要活动阶段是：
需求分析,详细设计和概要设计是开发阶段。
3．2 结构化分析方法
需求分析方法有（1
需求分析阶段工作4个方面：
结构化分析的常用工具：
（1（2（3（4
数据流图：描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统功能
建模。
数据字典：对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得
用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。
软件需求规格说明书的特点：（核心的是无歧义性）
（1）正确性；（2）无岐义性；（3）完整性；（4）可验证性；
（5）一致性；（6）可理解性；（7）可追踪性。
3．3 结构化设计方法
软件设计的基本目标是用比较抽象概括的方式确定目标系统如何完成预定的任务，
。
软件设计的一般过程：软件设计是一个迭代的过程；先进行高层次的结构设计；后进行低层次的过程设计；穿插进行数据设计和接口设计。
耦合性：对一个软件结构中不同模块之间互连程度的度量。
内聚性：一个模块内部各个元素间彼此结合的紧密程度的度量。
软件概要设计的基本任务是：
（1）设计软件系统结构；（2）数据结构及数据库设计；
（3）编写概要设计文档；（4）概要设计文档评审。
常见的过程设计工具有：考试重点
程序流程图是考试重点，其中->箭头表示控制流，<>菱形表示逻辑条件。
3．4 软件测试
软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。
软件测试的目的：发现错误而执行程序的过程。
静态测试：包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。
动态测试：是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。
白盒测试：在程序内部进行，主要用于完成软件内部CAO作的验证。主要方法有逻辑覆盖、基
本基路径测试。
黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、
初始化和终止条件错，用于软件确认。
软件测试过程一般按4个步骤进行（要背先后顺序）：
3．5 程序的调试
程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。
软件调试可分表静态调试和动态调试。
静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段，
动态调试是辅助静态调试。
第四章数据库设计基础
4．1 数据库系统的基本概念
数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。
的具有集成与共享的特点。
护和数据服务等，是数据库的核心。
数据库管理系统提供以下的数据语言：
（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；
（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；
（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。
、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬
件）、软件平台（软件）五个部分构成的运行实体。DBS是最大的包括其他所有的。
数据库发展的三个阶段：人工管理阶段、文件系统阶段、数据库管理阶段。
数据库系统阶段的基本特点：
1、数据的集成性、
2、数据的高共享性与低冗余性、
3、数据独立性（物理独立性与逻辑独立性）、数据统一管理与控制。
数据库系统的三级模式：
（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；
（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；
（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。
一个数据库只有一个内模式，可以有多个外模式。
数据库系统的两级映射：
（1）概念模式到内模式的映射；
（2）外模式到概念模式的映射。
4.2 数据模型
数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。
E-R模型的基本概念
（1
（2
（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。
E-R模型的图示法：（1）实体集表示法；（2）属性表法；（3）联系表示法。
1
2
3、元组就是二维表中一行，属性就是二维表表中一列。
4
5、表A中的某属性是某表B的键，则称该属性集为A
6、分量是不可以再分的。
以上六点非常重要。
关系中的数据约束：
（1）实体完整性约束：约束关系的主键中属性值不能为空值；
（2）参照完全性约束：是关系之间的基本约束；
（3）用户定义的完整性约束：它反映了具体应用中数据的语义要求。
4.3关系代数
关系模型的基本运算：
（1（2（4
两个表的运算一般会考到：投影、链接、选择、笛卡尔积、交、并当中的一个。
4.4 数据库设计与管理
进一步修改阶段。
SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。
5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。
公共基础补充知识点
1、一个数据结构的逻辑结构根据需要可以有多个存储结构。存储结构的不同，会造成处理的效率不同。
2、程序设计方法和技术的发展经过了结构化程序设计和面向对象设计两个阶段。
3、当今程序设计的风格是“清晰第一，效率第二”。
4、程序可以没有输入，但是一定要有输出。
5、结构化程序设计遵循：自顶向下，逐步求精，模块化，限制使用goto语句（常考）。
6、面向对象的基本特点：标志唯一性，分类性，多态性，封装性，模块独立性。尤其重要的是多态性和封装性。没有类比性。
7、多态性：统一操作可以是不同对象的行为。同样的消息被不同的对象接收时可导致不同的动作的现象。
8、封装性：从外面看不到对象的内部，只能看到对象的外部特性。
9、类：是具有共同属性、共同方法的对象的集合。描述了属于该对象类型的所有对象的性质，而一个对象则是对应类的一个实例。（常考）
10、消息：是指对象间的相互合作的协作机制，是一个对象与另一个对象之间的传递的消息。
11、继承：是指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。
12、面向对象中，类的实例叫做对象。
13、源程序文档化要求程序应该加上注释。注释一般为序言性注释和功能性注释。
14
软件工程基础
1、软件工程的核心思想是把软件当作一个工程产品来处理。
这个表请大家抽时间背下。软件开发的三个阶段，每个阶段的工程。
2、软件开发方法包括分析方法，设计方法，程序设计方法。
3、结构化方法包括结构化分析方法，结构化设计方法，结构化编程方法。
4、结构化分析方法在软件需求分析阶段的应用。
5、表示加工，表示数据流，
表示数据存储（数据源）表示源和潭。
6、软件规格说明书（SRS）是需求分析阶段的最后结果，是软件开发文档重要的文档之一。
7、软件设计要求高耦合性和低内聚性是考试的重点,要知道什么是耦合,什么是内聚。
8、软件测试和程序调试的区别。软件测试的过程涵盖了整个软件生命周期。目的是为了发现错误而执行程序的过程。
10
11
12、白盒测试是检查内部成分，方法有：逻辑覆盖测试方法，基本路径测试。
13、黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。方法有：等价类划分法，边界值划分法，错误推测法。
14、
15、软件调试方法：强制排错法，回朔法，原因排除法。
16、软件维护不属于软件生命周期开发阶段的任务。
17、软件进行了程序调试后还要进行测试。
18、软件工程的主要思想是：强调在软件开发过程中需要应用工程化的原则。
19、软件设计中，不属于过程设计工具的是：DFD图。
20、结构化分析常见的工具：DFD图，DD（数据字典），判定树，判定表。
21、
22、软件的开发、运行对计算机系统具有依赖性。
23、软件工程的三要素：工具、过程、方法。
24、
25、数据流图只含有数据流，不含有控制流。数据流图用于抽象描述一个软件的逻辑模型。
26、数据流的类型有两种：事务型和变换型。在很多软件应用中，存在某种作业数据流，它可以引发一个或多个
处理，这些处理能够完成该作业要求的功能，这种数据流叫做事务型数据流。
27、程序流程图中的箭头代表的是：控制流。
28、在结构化方法中，软件功能分解属于总体设计阶段。
29、内聚型中内聚性最强的是：功能内聚。
30、检查软件产品是否符合需求定义的过程是：确认测试。
31、软件危机：泛指在计算机软件的开发和维护过程中遇到的一系列严重的问题。
32、Jackson 方法是一种面向数据结构的结构化方法。
33、软件开发环境是全面支持软件开发全过程的软件开发工具集合。
34、软件需求是指用户对目标软件系统在功能、行为、性能设计约束等方面的期望。
35、
数据库设计基础
1、关系运算是考试的重点，考的多的是并和笛卡尔积。不改变属性但减少元组个数的是并。投影也是比较喜欢考的，
一般的意思是从4、5个列中选出2、3个。笛卡尔积则是会增加元组的个数。
2、E-R图中，矩形、菱形、椭圆形等代表的意思是考试的重点。
3、数据库系统中，数据的物理结构不一定要和逻辑结构一致。
4、
5、数据库系统中，用户所见的数据模式为：外模式。
6、
7、两个实体间的关系是：一对一，多对多，一对多等，这种题目根据具体的题目分析。（常考题目）
8、数据库DB，数据库系统DBS，数据库管理系统DBMS之间的关系：DBS包含DB和DBMS。
9、
10、数据独立性：是指数据与程序的互不依赖性。他包括数据的物理独立性和逻辑独立性。物理独立性是数据的物理
结构（包括存储结构、存取方式）的改变，不影响数据库的逻辑结构。
11、数据的逻辑独立性是指数据库总体逻辑结构的改变，不需要相应修改应用程序。
12、用树形结构表示实体之间联系的模型是：层次模型。
13
14、不涉及具体的硬件环境和平台，也与具体的软件环境无关的模式是：概念模型。
15
16、给出数据的全局逻辑结构到数据的物理存储结构间的对应关系的映射是：概念模式到内模式的映射。
17、网状模型：不加任何的限制的无向图。
18、不准关系应用不存在的元组的约束是：参照完整性约束。
19、数据库设计包括两个方面的设计内容，它们是：概念设计和逻辑设计。
20、数据库设计中的主流方法是：面向数据的设计方法。
21、数据库概念设计过程分三个步骤进行：首先选择局部应用，在局部视图设计，最后进行视图集成。
22
23
24
25
26
27
28
29
30
31
32
目录 二级公共基础知识考纲 (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）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
计算机二级C语言公共基础知识手册 1.算法的时间复杂度是指执行算法所需要的计算工作量.算法的工作量由算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数. 2.算法的空间复杂度是指算法执行过程中所需要的存储空间,存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间. 3.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作;而是算法的控制结构. 4算法设计基本方法主要包括有列举法、归纳法、递推、递归和减半递推技术. 5.数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构).、 6.数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析. 7.数据元素是指相互有关联的数据元素的集合. 8.前驱和后继关系是数据元素之间的一个基本关系,但前驱个后继关系所表示的实际意义随具体对象的不同而不同.一般说来,数据元素之间的任何关系都可以用前驱和后继关系来描述. 9.常用的存储结构有顺序链接、索引等存储结构.而采用不同的存储结构,其数据处理的效率是不同的.
10.在数据结构中,没有前驱的结点称为根结点;没有后继的结点称为终端结点(叶子结点);数据结构中除了根结点与终端结点外的其他结点一般称为内部结点. 11.在数据结构中,结点几结点的相互关系有线性结构和非线性结构. 12.线性结构(线性表):非空数据结构满足(1)有且只有一个根结点;(2)每个结点最多有一个前驱,也最多有一个后继. 在一个线性结构中插入或删除任何一个结点后还应该是线性结构,若删除或插入后不是线性结构,则该数据结构不能称为线性结构. 13.线性表是最简单、最常用的一种数据结构.有一组数据元素组成.在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成,在这种情况下,常把数据元素称为记录,含有大量记录的线性表就称作文件. 14.非空线性表如与如下结构特征(1)有且只有一个根结点A1,它无前驱;(2)有且只有一个终端结点AI,它无后继;(3)除根结点与终端结点外,其他所有结点有且只有一个前驱,也只有一个后继.线性表中结点的个数N称为线性表的长度.当 N=0时,称其为空表. 15.在计算机中存放线性表,一种最简单的方法是顺序存储,也称顺序分配. 16.线性表的顺序存储结构具有以下两种基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的. 在线性表的存储结构中,其前后继两个元素在存 储空间中是紧邻的,且前驱元素一定存储在后继元素的前面. 17.假设线性表中第一个数据元素的存储地址是ADR(AI),每一个数据元素占K 个字节,则线性表中第I个元素AI在计算机存储空间中的存储地址是 ADR(AI)=ADR(A1)+(I-1)K.
公共基础知识笔记 第五部分公文写作与处理 1、写作基础知识 主题是文章的统帅和纲领，是文章的核心；主题源于材料，主题不能先行，必须从实际出发，从材料中引出主题。实用文体主题的表现表式主要有：①直接阐述；②单一集中；③以意役法；④片言居要；⑤善用标题。 文章结构安排的环节主要包括：选择角度；设置线索；安排层次；划分段落；设计开头与结尾；处理过渡和照应等。文章的结构应达到严谨（严密精细，无懈可击）、自然（顺理成章，开阖自如）、完整（匀称饱满，首尾圆合）、统一（和谐一致，通篇一贯，决不相互抵触，自相矛盾）文章常用的表达方法有叙述、描写、议论、说明，其中议论的方法又可具体分为：①例证法；②喻证法；③类比法；④对比法；⑤反驳法；⑥归谬法。 语言运用的基本要求：合体、得体，准确、顺达，简洁、明快，生动、有力。 2、公文的特点和种类 公文，也称公务文件，是在社会活动中直接形成和使用的具有规范体式和法定效用的信息记录，其区别于图书、情报、资料等事物的个性点主要有：①由法定作者制发；②具有法定的现实执行效用；③具有规范的体式；④履行法定的程序。 根据不同的标准，公文可从不同角度进行如下分类： （1）根据形成和作用的公务活动领域，公文可分为通用公文和专用公文两类。
（2）根据内容涉及国家秘密的程度，公文可分为对外公开、限国内公开、内部使用、秘密、机密、绝密六类 （3）根据行文方向，公文可分为上行文、下行文、平行文三类。 （4）根据内容的性质，公文可分为规范性、领导指导性、公布性、陈述呈请性、商洽性、证明性公文。 （5）根据处理时限的要求，公文可分为平件、急件、特急件三类。 （6）根据来源，在一个机关内部可将公文分为收文、发文两类。 3、政府系统的通用公文文种 （1）规范性文件 条例。用于对某一方面的行政工作作全面、系统的规定，国务院各部门和地方人民政府的规章不得称“条例”。 规定。用于对某一方面的行政工作作部分的规定。 办法。用于对某一项行政工作作比较具体的规定。 （2）领导指导性文件 命令（令）。用于依照有关法律规定发布行政法规和规章；宣布旅行重大强制性行政措施；奖惩有关人员；撤销下级机关不适当的决定。 决定。用于对重要事项或重大行动作出安排。 指示。用于对下级机关布置工作，阐明工作活动的指导原则。 批复。用于答复下级机关的请示事项。 通知。用于批转下级机关的公文，转发上级机关和不相隶属机关的公文；发布规章；传达要求下级机关办理和有关单位需要周知或者共同执行的事项；任免和聘用干部。 通报。用于表彰先进，批评错误，传达重要精神或情况。
全国计算机二级考试公共基础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：（1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由
二级公共基础知识总结 第一章数据结构与算法 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代表每个元素占的字节数。顺序表的运算：插入、删除。 （4）1．4 栈和队列栈是限定在一端进行插入与删除的线性表，允许
公共知识笔记大全（pdf豪华版） 第一部分马克思主义哲学 1、哲学、世界观、方法论 哲学，是系统化、理论化的世界观。 方法论是人们认识世界、改造世界的根本方法。 2、哲学的基本问题 哲学的基本问题，包括两个方面，两个层次。 第一方面，是关于物质和意识谁是第一性、谁是第二性的问题，是划分唯物主义和唯心主义的根本依据。 第二方面，是物质和意识是否具有同一性的问题，即人的意识能否认识和反映物质世界的问题，是划分可知识和不可知论的根本依据。 在哲学基本问题之后，还有一个世界处于什么状态的问题，并由此产生形而上学和辩证法的对立。 3、马克思主义哲学的产生 自然科学：细胞学说、能量守恒定律、达尔文生物进化论 阶级基础：英国宪章运动、法国里昂工人起义、德国西里西亚纺织工人起义 社会科学：英国古典经济学、法国空想社会主义、黑格尔辩证法、费尔巴哈唯物主义 4、马克思主义哲学的基本特征 马克思主义哲学的本质特征是它的实践性，是实践基础上的科学性和革命性的统一。 5、辩证唯物主义的物质观 （一）物质观的发展 主观唯心主义：“存在就是被感知”。 客观唯心主义：“理”、“理念”、“绝对观念” 古代朴素唯物主义:物质为一种或几种常见的具体形态。 近代形而上学唯物主义:物质是物质结构的某一层次或不可分割的最小粒子。 旧唯物主义无法对意识现象及社会历史的本质，做出唯物科学解释，旧唯物主义的物质观是形而上学的，历史观是唯心主义的。 （二）马克思主义哲学的物质观 恩格斯：“物、物质无非是各种物的总和，而这个概念就是从这一总和中抽象出来的。” 列宁：“物质是标志客观实在的哲学范畴，这种客观实在是人通过感觉感知的，它不依赖于我们的感觉而存在，为我们的感觉所复写、摄影、反映”。 物质的唯一特性：客观实在性 6、辩证唯物主义的运动观 物质是运动的物质，运动是物质的运动。运动是物质自身的固有属性和存在方式。 物质运动的具体形式是多种多样的。物质运动可分为五种基本形式：即机械运动、物理运动、化学运动、生物运动和社会运动。各种物质运动之间的区别与联系：低级运动形式是高级运动形式的基础、高级运动形式是从低级运动形式发展而来的；高级运动包含低级运动形式；各种运动形式同时并存、相互制约并在一定条件下相互转化。 静止是有条件的、暂时的和相对的，运动是无条件的和绝对的。静止是一种特殊的运动状态。 物质运动具有其自身的规律性。规律就是事物运动过程中自身所固有的本质的必然的联系。规律具有如下共同点：规律具有稳定性；规律具有普遍性；规律具有可重复性。 7、世界的物质统一性 世界的物质统一性原理，是对无限多样和永恒运动着的整个世界的根本观点和总的看法，是对整个世界的普遍本质和共同基础的科学反映，是马克思主义哲学的基础，也是我们从事一切工作的出发点。一切从实际出发，实事求是。 8、意识的起源 意识是自然界长期发展的产物：无机物的反映特性进化为低等生物的刺激感应性；低等生物的刺激感应性进化为高等动物的感觉和心理；动物心理进化为人的意识。
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 算法的基本概念 1．算法的概念(必记)： 算法是指解题方案的准确而完整的描述。 分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方 案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。 结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 2．算法的基本特征(必记)： a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。 b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 d.拥有足够的情报：算法有相应的初始数据。 3．算法的基本要素： 一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。 基本运算和操作分为四类： a. 算术运算: (加、减、乘、除等运算) b. 逻辑运算: (与、或、非等运算) c. 关系运算: (大于、小于、等于、不等于等运算) d. 数据传输: (赋值、输入、输出等操作) 算法的控制结构： 算法中各操作之间的执行顺序称之为算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控 制结构组合而成。 注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。 4．算法设计基本方法： 列举法、归纳法、递推、递归、减半递推技术、回溯法。 1.2 算法的复杂度 (必记) 算法的复杂度主要包括时间复杂度和空间复杂度。 1．算法的时间复杂度： 是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。 可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运算次数的加权平 均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。 2．算法的空间复杂度： 一个算法的空间复杂度，是指执行这个算法所需要的内存空间。包含有三部分所组成：算法程序所占的空间 +输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。 历届的考题： 1、算法具有五个特性，以下选项中不属于算法特性的是(______) [2005.4] A)有穷性B)简洁性C)可行性D)确定性 2、问题处理方案的正确而完整的描述称为______。[2005.4] 3、下列叙述中正确的是________。[2006.9] A）一个算法的空间复杂度大，则其时间复杂度也必定大
公共基础笔记 第三部分法律 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.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 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．算法的基本概念：算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且
计算机二级C语言的二级共公基础知识教程 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念
数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位臵只取决于自己的序号，元素之间的相对位臵是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件；
第一章数据结构与算法 算法 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)的线性表。 线性链表
计算机公共基础部分知识归纳 第一章数据结构与算法 算法---是一组严谨地定义运算顺序的规则 算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构 算法设计基本方法---列举法、归纳法、递推、递归、减半递推 算法的复杂度---包括时间复杂度和空间复杂度 时间复杂度---执行算法所需的计算工作量 空间复杂度---执行算法所需的内存空间 数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。； 父亲、儿子、女儿等都是数据元素。 前件---数据元素之间的关系，如父亲是儿子和女儿的前件 后件---如儿子是父亲的后件 结构---指数据元素之间的前后件关系 数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素 在计算机存储空间的位置关系可能与逻辑关系不同。 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与 非线性结构 线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有 一个前件和后件。则称该数据结构为线性结构，否则为非线 性结构。 线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方 式为顺序存储的，如数组 栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进 后出”，栈的运算有入栈、退栈、读栈顶元素 队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操 作规则是“先进先出”，其运算有入队和退队。 树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结 点、叶子结点。根结点在第一层，一个结点所拥有的后件的 个数称为该结点的度，所有结点中最大的度称为树的度， 树的最大层次称为树的深度。 二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子 树），其存储结构为链式。 二叉树性质---（1）K层上最多有2（K-1）个结点（2）深度为m的二叉树最多有2m-1个结点（3）度为0的结点（叶子结点）比度为2的结点多一个（4）具有n个结点的 二叉树，其深度至少为[Log2n]+1，其中[Log2n]表示对Log2n 取整 满二叉树---除最后一层外，其余层的结点都有两个子结点 完全二叉树---除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的 若干结点，叶子结点只可能在层次最大的两层上出现。满二 叉树是完全二叉树，而完全二叉树不是满二叉树。完全二叉 树有两个性质：（1）具有n个结点的完全二叉树的深度为
二级公共基础知识分类模拟题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．在栈中，栈顶指针的动态变化决定栈中元素的个数
C语言公共基础知识标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-
第一部分公共基础部分知识归纳 数据结构与算法 算法---是一组严谨地定义运算顺序的规则 算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构 算法设计基本方法---列举法、归纳法、递推、递归、减半递推 算法的复杂度---包括时间复杂度和空间复杂度 时间复杂度---执行算法所需的计算工作量 空间复杂度---执行算法所需的内存空间 数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父亲、儿子、女儿等都是数据元素。 前件---数据元素之间的关系，如父亲是儿子和女儿的前件 后件---如儿子是父亲的后件 结构---指数据元素之间的前后件关系 数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关 数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与非线性结构 线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件和后件。则称该数据结构为线性结构，否则为非线性结构。 线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组 栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈的运算有入栈、退栈、读栈顶元素 队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操作规则是“先进先出”，其运算有入队和退队。 树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结点、叶子结点。根结点在第一层，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度，树的最大层次称为树的深度。 二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式。
公共基础笔记 第一部分马克思主义哲学 1、哲学、世界观、方法论 哲学，是系统化、理论化的世界观。 方法论是人们认识世界、改造世界的根本方法。 2、哲学的基本问题 哲学的基本问题，包括两个方面，两个层次。 第一方面，是关于物质和意识谁是第一性、谁是第二性的问题，是划分唯物主义和唯心主义的根本依据。 第二方面，是物质和意识是否具有同一性的问题，即人的意识能否认识和反映物质世界的问题，是划分可知识和不可知论的根本依据。 在哲学基本问题之后，还有一个世界处于什么状态的问题，并由此产生形而上学和辩证法的对立。 3、马克思主义哲学的产生 自然科学：细胞学说、能量守恒定律、达尔文生物进化论 阶级基础：英国宪章运动、法国里昂工人起义、德国西里西亚纺织工人起义 社会科学：英国古典经济学、法国空想社会主义、黑格尔辩证法、费尔巴哈唯物主义 4、马克思主义哲学的基本特征 马克思主义哲学的本质特征是它的实践性，是实践基础上的科学性和革命性的统一。 5、辩证唯物主义的物质观 （一）物质观的发展 主观唯心主义：“存在就是被感知”。 客观唯心主义：“理”、“理念”、“绝对观念” 古代朴素唯物主义:物质为一种或几种常见的具体形态。 近代形而上学唯物主义:物质是物质结构的某一层次或不可分割的最小粒子。 旧唯物主义无法对意识现象及社会历史的本质，做出唯物的科学解释，旧唯物主义的物质观是形而上学的，历史观是唯心主义的。 （二）马克思主义哲学的物质观 恩格斯：“物、物质无非是各种物的总和，而这个概念就是从这一总和中抽象出来的。” 列宁：“物质是标志客观实在的哲学范畴，这种客观实在是人通过感觉感知的，它不依赖于我们的感觉而存在，为我们的感觉所复写、摄影、反映”。 物质的唯一特性：客观实在性