计算机等级二级公共基础知识

1、共同基本知识，第一，基本数据结构和算法。第二，编程基础。第三，软件工程的基础。第四，数据库设计基础。数据结构和算法的第一部分5-7问题(10-14分)，测试概述： 1。基本要求： 1。掌握算法的基本概念2。了解基本数据结构及其操作3。确定基本排序和查找算法2。考试内容： 1。算法的基本概念；算法复杂性的概念和意义(时间复杂性和空间复杂性)2。数据结构的定义；数据的逻辑结构和存储结构数据结构的图形表示；线性结构和非线性结构的概念3。定线表格的定义；线性表的顺序存储结构和插入和删除操作4。堆栈和队列定义；堆栈和队列顺序存储结构以及基本运算5。线性单列表、双向列表和循环列表结构以及基本运算6。树的基

2、本概念；二叉树的定义和存储结构；二叉树的前导、中间和结尾遍历。顺序搜索和二分法搜索算法；默认排序算法(交换类排序、选择类排序、插入类排序)、测试点1、算法(P1)、1。算法的基本概念，即算法，意味着问题解决方案的准确、完整的说明。1.算法基本特性的可行性：是否可行。确定性：算法的每个阶段都必须有明确的定义，意味着不允许模糊的解释或多元性。有穷：意味着算法必须在有限的时间内完成。这意味着在执行有限的步骤后，算法必须能够终止。足够的信息：收集的输入信息等。2 .算法的基本要素一个算法通常由两个要素组成。一种是对数据对象的运算和运算，另一种是算法的控制结构。(1)算法中数据的运算和运算(指令)(P2

3、)算术运算：加、减、乘、除逻辑运算：and，or；非相关运算：大于，小于，等于；不等于数据传输：分配，不等于描述算法的工具包括现有流程图、N-S结构化流程图、算法描述语言等。现有流程图，N-S结构化流程图，算法说明语言。a=0？yes、no、no、yes、3。算法设计的基本方法枚举方法归纳递归方法，2。算法的复杂性(P5)算法的复杂性主要是：小时复杂性和空间复杂性。1.算法的时间复杂度：表示执行算法所需的计算工作量。工作量可以通过算法执行的基本计算次数来测量。算法执行的基本操作数为算法的工作量=f(n)。其中n是问题的大小。可以通过两种方式使用平均和最坏的复杂性。2 .算法的空间复杂性：表示运

4、行此算法所需的内存空间。这包括算法占用的空间、输入的初始数据占用的存储空间以及运行算法所需的其他空间。这些额外空间包括运行算法程序时工作单元和基本种类的数据结构所需的额外存储空间(例如，链结构需要存储链接信息，而不仅仅是数据本身)。，测试点ii，数据结构的基本概念(P7)，数据结构领域主要研究：数据集合中数据元素之间固有的逻辑关系，即数据的逻辑结构。处理数据时，计算机上存储每个数据元素的关系，即数据的存储结构。各种数据结构的运算。数据结构领域的研究目的：提高数据处理的效率。主要包括：数据处理速度。最大限度地节省数据处理过程中使用的计算机存储空间。I .数据结构的定义：是指相互关联的数据元素的集

5、合。1 .数据处理：是指以不同方式操作数据集的各种元素。(插入、删除、查找、更改等)2。数据元素：在数据处理领域中，需要处理的每个对象可以抽象为数据元素3。数据结构：是反映数据元素之间关系的数据元素集合的表示。数据结构应包括信息：两种形式。一种是表示数据元素的信息，另一种是表示数据元素之间前后关系的信息。数据的逻辑结构(P11):表示反映数据元素之间逻辑关系的数据结构。此结构包含两个元素：一个是数据元素的集合，一个通常是D，另一个是D的关系，另一个反映D的数据元素之间的前后关系，另一个写为R，另一个写为：B=(D，R)。其中b表示数据结构，以反映d的数据元素之间的前后关系。通常表示为二进制组。

6、例如，假设a和b是d中的两个数据，则二进制组(a，b)意味着a是b的前面，b是a的后面。因此，d的两个元素之间的关系可以用这个二进制组来表示。示例：的一年第四季度数据结构为： B=(D，R) D=春天、夏天、秋天、冬天R=(春天、夏天)、(夏天、秋天)、(秋天、冬天也称为物理结构。通常，数据的逻辑结构根据需要以多种存储结构表示，常见存储结构包括顺序、链接和索引等。在计算机存储空间中，每个数据元素的位置关系可以与逻辑关系不同。此外，通常不完全相同。(P13)、ii。数据结构的图形表示除了二进制关系外，还可以图形方式表示数据结构。图形表示方法：对于数据集d中的每个数据元素，元素值显示为中间的框，通

7、常称为数据节点，简称为节点。对于关系r中的每个二进制组，使用垂直段前节点表示数据元素之间的前后关系。示例：用图形表示数据结构B=(D，R)。其中d=di | 1 i6=D1，D2，D3，D4，D5，D6 r=(D1，D2)，(D1，D3)，(D5，D4)，(线性结构和非线性结构(概念)(P14)数据结构通常分为两类：线性结构和非线性结构。非空线性结构满足以下条件：并且只有一个根节点：每个节点最多有一个前后项目。在线性结构中插入或删除节点后，称为线性结构。如果数据结构不是线性结构，则称为非线性结构。线性结构包括：堆栈、队列和双向链接表。非线性结构：树，二叉树，1。定线表格的基本概念定线表格定义：

8、定线表格由n(n=0)个资料元素a1、a2、an组成的有限序列，表格中的每个资料元素，除了第一个项目外只有一个前面，除了最后一个项目外，还有一个后面项目。也就是说，它可以表示为路线表或空表，或表示为： (a1，a2，an)。其中ai(i=1，2，n)是属于数据对象的元素，通常也称为线表中的一个节点。非空线条表的基本特性：具有一个根节点a1，其前面没有条目。只有终端节点，没有后者。除了根节点和终端节点外，所有其他节点都有一个前面的项目和一个后面的项目。定线表格中的长度：定线表格中节点数的n称为定线表格中的长度。N=0时称为空表。、测试点3，行表及其顺序存储结构，2。线路表的顺序存储结构(P16)

9、具有两个基本特征，即线路表的所有元素占用的存储空间都是顺序的。线性表中的每个数据元素按逻辑顺序存储在存储空间中。也就是说，在线性表的顺序存储结构中，前后两个元素紧挨着存储空间，前置任务一定存储在后置元素之前。线表格的随机存取位址的计算公式：ADR (ai)=ADR (a1) (I-1) k参考每个元素占用的位元组，线表格的预设动作：插入、删除、寻找、排序、分解、合并、合并直线表格的插入操作计算长度为n的直线表格，要在i(1in)元素之前插入新元素，请从最后一个(即第n个)元素向后移动一个位置，直到第一个元素之间的n-i 1元素向后移动一个位置，移动结束后，第I个位置为空，然后将新元素插入I项。

10、插入结束后，定线表格的长度将增加1，变为n 1。时间复杂度是平均元素的一半，最差的情况下，必须移动所有元素。线造型表格顺序存储结构适用时：对于较小的线造型表格或元素不经常更改的线造型表格，插入和删除效率不高。4 .删除定线表格作业要删除i(1in)元素，请先从I 1元素开始，一次向前移动一个位置，直到最后一个(n)元素之间的n-1元素为止。删除结束后，定线表格的长度会减少1。N-1。删除操作的时间复杂性：平均情况下，必须移动表中的一半元素，最差情况下，必须移动表中的所有元素。测试点4、堆栈和队列(焦点)(P19)、1、堆栈及其基本运算(1)堆栈的定义：堆栈是限定一侧的插入和删除操作的线表。这将

11、根据“后进先出”(或“先进先出”)的原则组织数据。(2)堆栈顺序将：作为堆栈顺序存储在编程语言中，通常是一维数据S(13360m)。其中m是堆栈的最大容量。(3)堆栈的基本运算输入：首先将堆栈顶部指针(top)加1，然后在堆栈顶部指针指向的位置插入新元素。当堆栈顶部指针指向存储空间中的最后一个位置时，堆栈空间已满，无法再执行堆栈操作。堆栈操作：首先将堆栈顶部元素分配给指定变量。然后从堆栈顶部的指针(top)中减去1。堆栈顶部的指针为0时，堆栈为空，不能再执行堆栈操作。堆栈顶部元素读取：将堆栈顶部元素指定给指定变量，堆栈指针(top)保持不变。如果堆栈顶部指针为零，则堆栈为空，并且堆栈顶部元素读

12、取操作将失败。堆栈、堆栈、2、队列和基本运算(P21) (1)队列是线性表，可以插入一端，也可以删除另一端。根据“先进先出”原则组织数据。(2)循环队列：将队列存储空间的最后一个位置延迟到第一个位置，从而形成用于队列循环的逻辑循环空间。(3)将重复队列的基本运算排入队列运算：首先在队列尾部指针中添加1(real=real 1)，如果real=m 1，则放置real=1，然后在指针指向的位置插入新元素。后退操作：首先向行头指针添加1(front=front 1)，在front=m 1时放置front=1，然后将行头指针指向的元素分配给指定变量。a、b、c、d、e、f、8、7、6、5、4、3、2、

13、1、real、front，测试点5，线性链表(P24)，1，线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链接表的存储结构：线性链接表中每个节点的数据域存储数据元素的值，指针域存储后节点的存储地址。双向关联列表的存储结构：双向关联列表的存储结构比线性关联列表的存储结构多一个指针字段，用于存储前一个节点的存储地址。带链的堆栈，带链的队列，2，线性链表的基本操作(P27):插入、删除、合并、分解、反转、复制、对齐、查找。插入线性链接表：首先为堆栈中的新元素指定新节点q，然后指定值。然后，使用“线性链接”列表中的查询算法查找指向要插入位置的上一个节点的指针p。将q指向p的背面，将q放在p

14、节点后面。删除、x、p、q、x、p、q、线性链接表：首先查找要删除的元素的前一个节点p，然后使用其他指针q查找p的后一个节点(最后返回q节点分配的堆栈空间。3、循环链接列表(P30):循环链接的一些特征：向循环链接表中添加标题节点，使循环链接表对于空表和非空表统一。循环链接列表中最后一个节点的指针字段不是空的，而是指向标题节点。确定循环链接是否为空的方法不是检查标题指针是否为空，而是检查标题节点的后续节点是否为标题节点。在循环链接列表中，可以从所有节点访问表中的所有其他节点。测试点6，树和二进制树(焦点)(P31)，1，树的基本概念树是具有层次特征的非线性结构，所有数据元素之间的关系很明显。父

15、节点：树结构中的每个节点只有一个名为父节点的前一个节点。根节点：只有一个节点，称为树的根节点。子节点：每个节点可以有多个后缀，这些后缀称为该节点的子节点。叶节点：没有背面项目的节点称为叶节点。节点的度：一个节点包围后的数量称为该节点的度。树的度：树中所有节点中最大的度称为树的度。树的深度：树的最大级别称为树的深度，树的深度也称为树的高度，根节点位于层1中。子树：将树中一个节点的子节点组织为根节点的树称为该节点的子树。叶节点没有子树。2、二进制树和基本特征(P34)二进制树的两个特征：非空二进制树只有一个根节点。每个节点最多包含两个子树，分别称为节点的左侧和右侧子树。二叉树的基本特性：二叉树的k

16、层包含最多2k-1 (k=1)个节点。深度为m的二进制树最多包含2m-1个节点。在两个二叉树中，度为0的节点(即叶节点)总是比度为2的节点多一个。具有至少2n 1深度的n个节点的二叉树。3、完整二进制树和完整二进制树(P35)完整二进制树：每个层次结构(最后一个层次结构除外)中的所有节点都有两个子节点。整个二叉树：除了最后一层，每个层的节点数达到最大值，最后一层仅缺少右侧的部分节点。基本特性：整个二进制树的级别k具有2k-1 (k=1)节点，深度m的二进制树具有2m-1节点。具有n个节点的完整二进制树的深度为2n 1。如果设置整个二进制树的共n个节点，从根节点开始，按顺序(第一层从左到右)按自

17、然数1、2、n对节点编号，则编号为k的节点将得出以下结论：如果k=1，则节点是根节点，没有父节点。如果是K1，则节点的父节点编号为INT(K/2)。2k=n时，编号为k的节点的左侧子节点编号为2k。否则，节点没有左子节点(显然没有右子节点)。如果2k 1=n，则编号为k的节点的右侧子节点编号为2k 1。否则，节点没有右侧的子节点。4，二进制树的存储结构(P36) L(i):指向左侧指针域，此节点的左侧子节点(存储左侧子节点的存储地址)。R(i):右侧指针字段，指向右侧子节点的右侧子节点(存储右侧子节点的地址)。V(i):储存节点的值。，5，遍历二叉树(P38):首先访问根节点，前后遍历左侧子树，然后遍历右侧子树，依此类推。按中间顺序遍历：按中间顺序遍历左侧子树