二级公共基础知识考点总结

二级公共基础知识考点总结

第一章 数据结构与算法

考点1：算法的概念和基本特征

算法是指解题方案的准确而完整的描述。 算法的基本特征包括：

（1）可行性：针对实际问题设计的算法，总是在某个特定计算工具上执行，往往要受到计算工具的限制，使执行结果产生偏差。

（2）确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性。

（3）有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。

（4）拥有足够的情报：拥有足够的输入。

考点2：算法复杂度

算法的复杂度主要包括时间复杂度和空间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量(即算法执行过程中所需基本运算的执行次数)。

算法的空间复杂度是指执行这个算法所需要的内存空间。

特别注意：时间复杂度与空间复杂度没有必然的正比或反比的关系。

考点3：数据的逻辑结构与存储结构

数据的逻辑结构是反映数据元素之间逻辑关系的数据结构，与它们在计算机中的存储位置无关。

数据的存储结构（也称物理结构）是指数据的逻辑结构在计算机存储空间中的存放形式。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等（包括线性结构和非线性结构）。而采用不同的存储结构，其数据处理的效率是不同的。

考点4：线性表的顺序存储结构

线性表的顺序存储结构具有以下两个基本特点： 1) 线性表中所有元素所占的存储空间是连续的

2) 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间

1

考点5：栈与队列(属于线性结构) 1、栈

栈是限定在一端进行插入与删除的线性表。

在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。通常用指针top指示栈顶的位置，用指针bottom指向栈底。

top-bottom的绝对值加1即为当前栈中元素的个数。

栈是按照“先进后出”或“后进先出”的原则组织数据的，用栈顶指针top动态反映了栈中元素的变化情况，而不须改变指针bottom的位置。 栈具有记忆作用。

2、队列

队列是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个尾指针rear指向队尾元素，允许删除的一端称为排头（也称队头），通常用一个排头指针front指向排头元素的前一个位置。

队列按照“先进先出”或“后进后出”的原则组织数据，队尾指针rear和排头指针front共同反映了队列中元素动态变化情况。 在实际应用中，队列的顺序存储结构一般采用循环队列的形式，循环队列是逻辑上的环状空间，但物理上仍然是线性结构。从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

在普通队列中，rear指针位置减去front指针位置的差值即为队列中元素的个数。但在循环队列中，rear指针的位置可能大于front指针的位置，也可能小于front指针的位置，所以循环队列的元素个数计算方法如下： 设循环队列总容量为m

如果rear>front，则循环队列的元素个数为rear-front

如果rear

栈与队列的共同点：皆为线性结构，只允许在端点处插入与删除，而且不须移动其他元素。

2

考点6：线性链表

线性表的链式存储结构称为线性链表 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。

链式存储结构即可用于表示线性结构，也可用于表示非线性结构，栈与队列也可以采用链式存储结构。

★ 考点7：二叉树的基本性质

树是典型的非线性结构，在树中，每个结点的前件称为父结点，没有父结点的只有一个，称为根结点（有且仅有一个）。

每个结点拥有的后件称为子结点，没有子结点的称为叶子结点。一个结点所拥有的子结点的个数称为该结点的度，叶子结点的度为0。 树的最大层次称为树的深度。

二叉树：每个结点最大的度为2，如下图所示

性质1：在二叉树的第k层上，最多有2性质2：深度为m的二叉树最多有2

m

k-1

个结点

-1个结点

性质3：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。

3

满二叉树：每一层上的结点数都达到最大值，即第k层上有二叉树有2

m

2k-1个结点，且深度为m的满

-1个结点

完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。当完全二叉树有n个结点，若n为偶数，则有n/2个叶子结点；若n为奇数，则有[n/2]+1个叶子结点（[ ]表示只取整数部分）。

★考点8：二叉树的遍历 （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。

考点9：查找技术

对于长度为n的线性表：

顺序查找在最坏情况下，需要比较n次。

二分法查找只适用于顺序存储的有序表，在最坏情况下只需要比较log2n次。 考点10：排序技术

在最坏情况下，对于长度为n的线性表，冒泡排序法、快速排序法、简单插入排序法、简单选择排序法都需要比较n(n-1)/2次；希尔排序法需要比较O(n1.5)次；堆排序法需要比较O(nlog2n)次。

在各种排序法中，冒泡排序法最简单，比较次数最少（通常少于n(n-1)/2次）。

4

查找技术顺序查找n最坏情况下的次数（时间复杂度）log2n二分法查找排序技术交换类排序冒泡排序法n(n-1)/2快速排序法插入类排序简单插入排序法希尔排序法O(n1.5)选择类排序简单选择排序法堆排序法O(nlog2n)

第二章 程序设计基础

考点1：程序设计风格

主要风格：清晰第一，效率第二

形成良好的程序设计风格应注重的因素： 1. 源程序的文档化：要包含必要的程序注释 2. 数据说明的方法：数据说明的次序规范化 3. 语句的结构 4. 输入与输出

考点2：结构化程序设计的原则 1. 自顶向下 2. 逐步求精 3. 模块化

4. 限制使用goto语句

结构化程序设计的基本结构包括顺序结构、选择结构和循环结构。 考点3：面向对象的基本概念

1、 对象的特点：标识唯一性、分类性、多态性、封装性（实现信息隐蔽）、模块独立性 2、 类是具有共同属性、共同方法的对象的集合，类具有继承性

3、类与对象的关系：类是对象的抽象，对象则是其对应类的一个实例

第三章 软件工程基础

考点1：软件的定义及特点

计算机软件是包括程序、数据及相关文档的完整集合。 软件的特点包括：

（1）软件是一种逻辑实体，而不是物理实体。

（2）软件的生产与硬件不同，它没有明显的制作过程； （3）软件在运行、使用期间不存在磨损、老化问题；

（4）软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移

5

设有关系R与S:

R S A 1 1 2 1 B 2 5 4 1 C 3 8 2 4 D 4 3 6 7 D 5 6 7 6 E 1 4 3 8 R | × | S（自然联接） A 2 2 1 B 4 4 1 C 2 2 4 D 6 6 7 E 4 8 3 设有关系R，经过投影运算得到S

R

A B A B C 1 4 7 2 5 8 3 6 9 1 4 7 2 5 8

设有关系R，经过选择运算得到S R A 1 4 7 B 2 5 8 C 3 6 9 A 1 4 B 2 5 C 3 6

考点8：数据库设计

数据库设计分四个阶段：需求分析、概念设计、逻辑设计、物理设计

数据库逻辑设计的主要工作是将E-R图转换成指定RDBMS中的关系模式 E-R模型 属性 实体 关系 属性 元组 E-R模型 实体集 联系 关系 关系 关系 11

本文来源：https://www.bwwdw.com/article/dcig.html