全国计算机等级考试培训教材（二级C）课件 ch01 公共基础知识.pptx

计算机等级考试第一章公共基础知识高等院校公共课系列精品教材

数据结构与算法01ONE

1.1数据结构与算法01考点1算法1.算法定义算法是指对解题方案准确而完整的描述。算法不等于数学上的计算方法，也不等于程序。2.算法的特征算法的特征有4个：可行性、确定性、有穷性、拥有足够的情报。（1）可行性：在算法的执行过程中，每一个步骤都要可行、可通。经过执行能够得到一个结果。（2）确定性：算法中的每一个步骤都要有确切的含义，不能有二义性，对于相同的输入必须能得出相同的执行结果。（3）有穷性：一个算法包含的操优步骤是有限的。也就是说，在执行若干个操作步骤之后算法结束，而且每一个步骤都要在合理的时间内完成。（4）拥有足够的情报：即拥有足够的输入数据。通过大量的算法输入数据来验证算法输出的结果是否有误。

1.1数据结构与算法3.算法复杂度（1）算法的复杂度是指运行该算法所需要的计算机资源的多少，所需的资源越多，该算法的复杂度越高：反之，所需资源越少，复东度越低。也就是说，算法的复杂度是对算法中的各种方法进行衡量的标准。（2）算法的复杂度有两种：算法的时间复杂度和算法的空问复杂度。①算法的时间复杂度：执行算法所需要的（计算工作量）基本运算次数。②算法的空间复杂度：执行算法所需要的内存空问。【注意】算法时间复杂度的好与坏不会影响空问复杂度的好与坏。01考点1算法

1.1数据结构与算法01考点2数据结构1.数据的逻辑结构(1）数据结构定义数据结构主要研充和讨论了个方面的内容：逻辑结构、存储结构和运算。逻辑结构讨论的是现实世界中数据与数据之间的关系：存储结构也称物理结构，指的是逻辑结构在计算机存储空问的存放形式。(2）数据的逻辑结构满足逻辑结构的的条件：①表示数据元素的信息；②表示各数据元素之问的前后件关系。逻辑结构的分类：线性结构、非线性结构。①线性结构：有且只有一个根节点：每一个节点最多有一个前件，也最多有一个后件。在二级公共基础中，线性结构主要讲到的有：线性表、栈、队列。②非线性结构：不满足线性结构条件的就属于非线性结构。在二级公共基础中，非线性结构主要讲到的有：树、二叉树。

1.1数据结构与算法01考点2数据结构2．数据的存储结构(1）概念：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。(2）数据的逻辑结构在计算机存储空间中的存储形式通常有两种：顺序存储结构、链式存储结构。①顺序存储结构：数据在存储空间中必须连续，且元素之问一定要有前后件的关系。②链式存储结构：数据在存储空问中不一定连续，且各元素的存储顺序是任意的。(3）两种存储结构的优缺点如下。①顺序存储结构：优点是查找方便；缺点是插入、刪除不方便。②链式存储结构：优点是插入、删除方便；缺点是查找不方便。

1.1数据结构与算法01考点3线性表及顺序存储结构(1）一个非空的数据结构如果满足以下两个条件：有且只有一个根节点；每一个节点最多有一个前件，也最多有一个后件，那么该数据结构称为线性结构，也称为线性表。(2）线性表往计算机中进行存放，不仅可以采用顺序存储结构存放，还可以采用链式存储结构存放。①顺序表：线性表采用顺序存储结构存放。②线性链表：线性表采用链式存储结构存放。(3）顺序表和线性链表的特点如下。①顺序表：随机（访问〉存取、查找方便，插入、删除不方便，事先估计存储空间。②线性链表：顺序（访问）存取、插入、刪除方便，查找不方便，不必事先估计存储空间。

1.1数据结构与算法01考点4栈和队列1.栈(1）栈是一种特殊的线性表，其特殊性是插入与删除运算都只在线性表的一端进行。即栈的一个考点：入栈和退栈都是在一端（栈顶）进行的。(2）栈在计算机中进行存储时通常采用的存储方式有顺序存储结构、链式存储结构。(3）栈的原则是先进后出、后进先出。2.队列(1）队列是一个允许在一端进行插入，而在另一端进行删除的线性表。即队列的一个考点：队列的入队运算是在队尾进行的，而退队运算是在队头进行的。(2）队列在计算机中进行存储时通常买用的存储方式有顺序存储结构、链式存储结构。(3）队列的原则是先进先出、后进后出。(4）循环队列是队列在计算机存储空间中采用顺序存储结构进行存储的一种形式。

1.1数据结构与算法01考点4栈和队列3.循环队列循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

1.1数据结构与算法01考点5树与二叉树(1）树是一种简单的非线性结构。在树中，所有数据元素之间的关系具有明显的层次特性。树的根书点可以没有或有一个。(2）二叉树的性质如下。性质1：在二叉树的第上层上至多有2k-1个节点(k≥1）