全国计算机等级考试二级公共基础知识讲义

全国计算机排名考试级2公共基础知识咨询讲义目录第一章数据结构和算法11.1算法11.2数据结构的基本概念11.3线性表和顺序存储结构21.4堆栈和队列21.5线性链接列表31.6树和二进制树41.7寻找技术51.8排序技术6本章要试拨6第二章编程基础72.1编程风格72.2结构化编程(面向流程的编程方法)72.3面向对象编程8本章要试拨8第三章软件工程基础93.1软件工程基本概念93.2结构分析方法103.3结构化设计方法113.4软件测试133.5程序调试15本章要试拨15第四章数据库设计基础164.1数据库系统的基本概念164.2数据模型184.3关系代数204.4数据库设计方法和步骤21本章要拍考试成绩21第一章数据结构和算法1.1算法1、算法意味着对问题解决方案的准确完整的说明。换句话说，算法是对特定故障诊断步骤的一种描述。*:算法不等于程序，不等于计算方法。编程不能比算法好，因为在编写程序时，受计算机系统操作环境的限制，程序通常需要考虑很多与方法和分析无关的细节。，即可从workspace页面中移除物件。2、算法的基本特性(1)可行性。针对实际问题设计的算法，运行后得到满意的结果。(2)确定性。各项指示的意义明确，没有异议。而且在任何条件下，算法只能通过唯一的执行路径，即相同的输入，得到相同的输出。有穷性。算法必须在有限的时间内完成。有两个含义。一种是算法中的操作步骤是有限的，另一种是每个步骤可以在有限的时间内完成。(4)有充分的信息。在算法中，每个操作始终应用于单独的操作数，这些操作数可以是初始状态，即算法运行的起点或基准。因此，一个算法运行的结果始终与输入的初始数据相关，每个输入产生不同的结果输出。如果输入不足或输入错误，算法将无法运行或出现错误。通常，此算法仅在算法包含足够的信息时有效。如果提供的信息不足，算法可能无效。*:概括地说，算法是严格定义计算顺序的规则集，每个规则都有效、明确，并且此顺序以有限的次数结束。3、算法复杂性主要包括时间复杂性和空间复杂性。(1)算法时间复杂度是运行算法所需的计算工作量，可以通过运行算法时所需的基本运算的执行次数来测量。(2)算法空间复杂性表示运行此算法所需的内存空间。1.2数据结构的基本概念1、数据结构表示相互关联的数据元素的集合。2、数据结构主要研究和讨论以下三个方面的问题：(1)数据的逻辑结构，即数据集中数据元素之间固有的逻辑关系。数据的逻辑结构如下：1)表示数据元素的信息；2)表示每个数据元素之间前后关系的前后关系。通常，在具有相同特性的数据元素集合中，每个数据元素之间的关系(即连接)反映了该集合中数据元素的唯一结构。在数据处理领域，通常将数据元素之间的这种独特关系简单地描述为前后关系，即直接前兆和直接后继关系。，即可从workspace页面中移除物件。(2)处理数据时，每个数据元素存储在计算机上的关系，即数据的存储结构。数据的存储结构包括顺序、链接、索引等。1)顺序存储。逻辑相邻节点存储在与物理位置相邻的存储设备上。节点之间的逻辑关系由存储设备的相邻关系表示。结果存储表示法称为顺序存储结构。2)链接存储。逻辑相邻节点不必在物理位置相邻，节点之间的逻辑关系显示为附加指针字段。生成的存储表示称为链存储结构。3)索引存储：除了设置存储节点信息外，还设置其他索引表以标识节点的地址。*:数据的逻辑结构反映了数据元素之间的逻辑关系，数据的存储结构(也称为数据的物理结构)是数据的逻辑结构在计算机存储空间中的存档形式。相同逻辑结构中的数据可以采用不同的存储结构，但会影响数据处理效率。(3)对各种数据结构的运算。3、数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，数据集d中的每个数据元素都由元素值标记为中间的框表示，通常称为数据节点，简称为节点。为了更详细地表示每个数据元素之间的前后关系，对于关系r中的每个二进制组，指向具有反向线段的上一个点节点。4、数据结构分为两大类型：线性结构和非线性结构。(1)具有线性结构(非空数据结构)条件：1)，数据结构中只有一个根节点，前面没有条目的节点称为根节点。2)每个节点最多有一个前后项。*:典型的线性结构包括线性表格、堆叠、伫列和线性连结表格。(2)非线性结构：不符合线性结构条件的数据结构。*:典型的非线性结构是树、二叉树和图形。1.3线性表和顺序存储结构1、线性表由一组仅取决于其序列号的数据元素组成，元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的一个有限序列，表中的每个数据元素除了第一个项目外，除了最后一个项目外，只有一个后续项目。线表格中资料元素的数目称为线表格的长度。定线表格可以是空表格。2、线性表的顺序存储结构具有两个基本特征：(1)线性表所有元素占用的存储空间是连续的。(2)线性表中的每个数据元素按逻辑顺序存储在存储空间中。*:在线性表的顺序存储结构中，可以看到前后两个元素紧挨着存储空间，前置元素一定存储在后置元素之前，通过计算机可以直接解析第一个节点的存储地址。3、插入顺序表格，删除操作(1)插入顺序表运算：通常，要在I(1In)元素之前插入新元素，请从最后一个(n)元素开始(n)元素，直到第一个元素之间的n-i 1元素总计向后移动一个元素，移动结束时，第I个位置为空，然后将新元素插入I项目。插入结束后，定线表格的长度会增加1。*:对于连续表的插入操作，需要移动元素，在相等概率下，需要移动平均n/2元素。(2)删除顺序表操作：通常，要删除I(1In)元素，请将第n个元素之间的n-i元素总计向前移动一个位置。删除结束后，定线表格的长度会减少为1。*:即使对连续表执行删除操作，也必须移动元素，同样的概率需要两个平均移动(n-1)/元素。插入、删除运算是不方便的。1.4堆栈和队列1、堆栈和基本运算堆叠是限制在一端的线性表格，用于插入和删除作业。除非堆栈允许插入和删除，否则端点称为堆栈顶部，而不允许插入和删除的其他端点称为堆栈底部。堆栈顶部元素始终是最后插入的元素，堆栈底部元素始终是第一个插入的元素。堆栈按“先进先出”或“后进先出”原则组织数据。堆栈具有内存效果。堆栈的基本运算：1)插入元素称为堆栈运算。2)删除元素称为堆栈操作。3)读取堆栈顶部元素是将堆栈顶部元素分配给指针保持不变的指定变量。堆栈以类似于线性表的方式存储，有两种类型：顺序堆栈和链堆栈。2、队列和基本运算队列是一个线表，其中一端(队列末端)允许插入，另一端(队列头)允许删除。尾部指针(Rear)指向团队尾部元素，头部指针(front)指向行头元素的先前位置(团队头)。队列是先进先出或后进先出的线性表。队列操作包括：1)入队操作：在队列末尾插入元素。2)退出计算：从小组题头中删除图元。循环队列及其运算：循环队列是将队列存储空间的最后一个位置延迟到第一个位置，从而为队列循环创建逻辑循环空间。重复队列中使用队列尾部指针rear指向队列中的页脚元素，使用行头指针front指向行头元素的前一个位置，因此从顶部指针front指向的下一个位置到队列尾部指针rear指向的位置之间的所有元素都是队列中的元素。*:重复队列是队列的链存储结构，重复队列中的元素数=rear-front。1.5定线连结清单1、线性表顺序存储的缺点：(1)插入或删除效率低下。在按顺序存储的路线表中插入或删除数据元素时，需要移动很多数据元素。(2)线性表的顺序存储结构中，线性表的存储空间不易扩展。(3)线性表的顺序存储结构不适合存储空间的动态分配。2、线性链表：线性表是顺序、链等存储结构，应特别关注考生。的链存储结构(称为线性链表)是物理存储单元中不连续和不连续的存储结构，数据元素的逻辑顺序通过链表中的指针链接实现。因此，在链存储方法中，每个节点由两部分组成。一个用于存放数据元素的值，称为数据域。另一部分用于指针，称为指针字段，指向该节点之前或之后的节点(即前面或后面)，如下图所示。线性链接列表分为三种类型：单个链接列表、双向链接列表和循环链接列表。在单个链接列表中，每个节点只有一个指针字段，只能找到下一个节点，不能找到上一个节点。因此，某些应用程序会为线性链接列表中的每个节点设置两个指针(称为左指针)，并指向第一个节点。另一个称为右指针的链接称为双向链接，如下图所示。3、线性链表的基本运算(1)在包含线性链接列表中指定元素的节点之前插入新元素。*:将元素插入联机链接表时，无需移动数据元素，只需修改相关节点指针。在为线表分配顺序存储空间后，线表的存储空间已满，但需要插入新元素时，就会出现“溢出”现象。“现象。(2)从联机链接列表中删除包含指定元素的节点。*:从联机连接的列表中删除元素时，无需移动数据元素，只需修改相关节点指针。(3)根据需要将两个路线链接表合并为一个路线链接表。(4)根据需要分解线性链接列表。(5)反转线性链接列表。(6)复制定线连结表格。(7)排序线性链接列表。(8)查找线性链接列表。*:线性链接列表不能随机访问链接列表，即使知道要访问的节点的序列号I，也不能像顺序表一样直接通过序列号I访问节点，并且可以沿着链域向下搜索，直到从连接列表的头指针中搜索到第一个节点。因此，关联列表不是随机存储结构。，即可从workspace页面中移除物件。4、循环列表和基本运算在线连接的列表中，插入和删除更方便，但是在计算过程中，将空表和第一个节点的处理分开考虑，存在空表和非空表的运算不统一的问题。要克服线性链接列表的这一缺点，可以使用另一种链接方法：循环链接列表。与前面介绍的线性链接列表相比，“循环链接”列表包含两个特性：1)链接列表中添加了一个标题循环链接表的头指针，其中数据字段是随机或根据需要设置的节点，指针字段指向线性表中的第一个元素节点，头指针指向标题节点；2)“循环链接”列表中最后一个节点的“指针”字段不是空的，而是指向“标题”节点。也就是说，“循环链接”列表中所有节点的指针构成了一个环链。下图a是非空循环链接列表，图b是空循环链接列表。回路链接的优点主要表现在两个方面。首先，通过在循环链接列表中仅指出表中某个节点的位置，可以在线性单个链接列表中访问表中所有其他节点。第二个原因是在循环链接表中设置了一个标题节点，并且在任何情况下循环链接表中至少存在一个节点，这将合并空表和非空表的运算。*:重复列表根据与单个链接列表执行相同插入和删除操作的单个链接列表添加标题节点。但是，所有节点都可以访问表中的所有其他节点，并统一空表和非空表的运算。1.6树和二进制树1、树的基本概念树是简单的非线性结构。在数据结构(如树)中，所有数据元素之间的关系具有明显的层次特征。在树状结构中，每个节点只有一个名为父节点的上一个项目。只有一个节点没有前面部分，树的根节点，简称为树的根节点。每个节点可以有多个后缀，称为该节点的子节点。没有后缀的节点称为叶节点。树结构中某个节点拥有的项目数称为该节点的度，所有节点中最大的度称为树的度数。树的最大级别称为树的深度。2，二叉树和基本特性(1)什么是二叉树二叉树是一种具有两个特征的非常有用的非线性结构。1)非空的二进制树只有一个根节点。2)每个节点最多有两个子树，分别称为该节点的左侧和右侧子树。*:根据二进制树的概念，二进制树的度可以是0(叶节点)、1(仅一个子树)或2(具有两个子树)。(2)二叉树的基本特征性质1在二进位树状结构的k层上具有最大节点。示例：二进制树第六层的节点数(根节点是第一层)最多为个。特性2深度为m的二进制树包含最大节点。示例：深度为5的二进制树包含最大节点。特性3在任意二叉树中，角度为零的节点(即叶节点)总是比度为2的节点多一个。示例：如果二进制树中有18个角度为2的节点，则该二进制树中有叶节点。属性4具有具有最小深度的n个节点的二进制树。其中表示导入的整数部分。示例：具有至少88个节点深度的二叉树。3，完整的二叉树和完整的二叉树完整二叉树：每个层次中的所有节点(最后一个层次除外)都有两个子节点。示例：在深度为7的二进制树中，叶节点数为。整个二叉树：每个层的节点数达到最大值，最后一层除外。最后一层仅缺少右侧的部分节点。*:可以根据完整二进制树的定义获得。度为1的节点数为0或1。下图a表示整个