《计算机二级级公共基础知识课件》由会员分享，可在线阅读，更多相关《计算机二级级公共基础知识课件（61页珍藏版）》请在金锄头文库上搜索。
1、个人简介,姓名：谭夏秋 记诺教育学校二级ACCESS、二级MS-Office讲师 联系电话：13109799091 交流QQ：879150342,计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,全国计算机等级考试二级公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。 考试方式:上机考试 题型：选择题（ 注：10 道选择题，占 总分值的10%）,第一章 数据结构与算法(30%),考试大纲 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形
2、表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,算法的定义 对解题方案准确而完整的描述称为算法。,算法是程序设计的核心,算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题
3、思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,例： n个数从大到小进行排序。 有多种排序方法 ，常用的有冒泡排序、选择排序等。,算法的基本特征 一个算法应该具有以下五个重要的特征：,有穷性 确定性 输入 输出 可行性,算法的两个基本要素：,基本运算和操作 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法,算法的复杂度 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个算法所需要的计算工作量 一般可以用算
4、法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题
5、。,数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。,数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。 （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种
6、数据结构进行的运算。,1. 数据的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。,春,夏,秋,冬,数据结构的图形表示,父亲,儿子,女儿,数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。 与数据在计算机中的存储位置无关，是独立于计算机的。,常见的逻辑结构有： 线性结构、树形结构和图形结构。, 线性结构 结构中的每个元素之间存在一个 对一个的关系； 树形结构 结构中的每个元素之间存在一个 对多个的关系； 图形结构或网状结构 结构中的每个元素之间存在多个 对多个的关系。 其中，树形结构和图形结构统称为非线形结构。数据的逻辑
7、结构可以用二元关系表示，也可以直观地用图形来表示。,数据的存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。 存储结构指数据结构在计算机存储空间中的具体实现。 常见的存储结构有： 顺序存储结构 链式存储结构 索引存储结构,只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。 一种数据结构可以根据需要表示成一种或多种存储结构。,常见的数据结构：1.线性表 2.栈和队列 3.树,线性结构和非线性结构,线性结构 在数据元素的非空有限
8、集合中，线性结构的逻辑特征如下： 存在一个唯一的被称为“第一个”的数据元素 存在一个唯一的被称为“最后一个”的数据元素 除第一个之外，集合中的每个数据元素均有且只有一个直接前驱 除最后一个之外，集合中的每个数据元素均有且只有一个直接后继 非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直接前驱和直接后继，树和图都属于非线性结构。, 线性表,线性表是由n（n0）个数据元素a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男 ,记录2 02011003 李四 女 ,记录3,记录4,线性表的存储结构有两种：顺序存储结构、链式存储结构,线性表
9、的顺序存储,线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。,所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量,顺序表的插入和删除运算,线性表的顺序存储结构称为顺序表。,顺序表的插入运算 顺序表的删除运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不
10、经常变动的线性表是合适的。,线性表的链式存储结构 线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。 链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：,单链表的插入运算 单链表的删除运算,线性链表的插入和删除运算,采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。,循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。,双向链表的存储结构,HEAD,3,1,5,10,双向链表可以克服单链表的单向性的
11、缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。,线性表的存储结构有两种,顺序存储结构,注意： 数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。 一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率 。,链式存储结构,线性表 : a1，a2，a3，a4，a5 ,栈和队列,栈和队列都是特殊的线性表。 栈（Stack）及其基本运算 队列（Queue）及其基本运算 循环队列及其基本运算,栈,顺序栈的进栈和出栈运算：栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。 栈顶元素总是最后被插入的元
12、素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种先进后出（后进先出）的线性表。 通常用指针top指示栈顶位置，用指针bottom指示栈底位置。,栈的物理存储结构可以用顺序结构，也可以用链表结构。 栈的基本运算有三种：入栈、退栈和读栈顶元素,队列,队列是一种先进先出的线性表，它只允许在表的一端插入元素(队尾)，在另一端删除元素(队头)。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元素的位置。 队列是一种先进先出的数据结构。 向队尾插入一个元素的操作称为入队，从队头删除一个元素的操作称为退队。,栈的物理存储结构可以用顺序结构
13、，也可以用链表结构。 队列的基本运算有三种：入队出队读队首元素,循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，当R指向存储空间的末端后，就把它重新置于始端。 循环队列的运算,队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。,线性表 线性结构 栈 是特殊的线性表 队列 也是一种操作受限的特殊的线性表 树 （树型结构）是一种重要的非线形数据结构,常见数据结构的逻辑结构,一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结
14、点最多有一个直接后继结点。,线性结构与非线性结构 线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为非线性结构。,树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历,树与二叉树,树及其基本概念,树是一种简单的非线性结构，在树中，所有的数据元素之间具有明显的层次性关系。 树是(n0)个结点的有限集合，在任意一棵非空树中： (1)有且仅有一个特定的结点称为根结点。 (2)当n1时，其余的结点可分为m个互不相交的子集T1,T2,Tm，其中每个有限子集本身又是一棵树，并且称为根的子树。 集合为空的树简称为空树；树中的元素称为结点。,树型结构的常用术语,A
15、,B,D,F,E,C,G,H,I,J,K,M,1)度：结点拥有的子树数。 2)叶子节点(终端结点)：度为0的结点。 3)层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。 4)深度：树中结点的最大层次称为树的深度或高度。 5)结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推； 6)树的深度 树中所有结点层次的最大值；,二叉树,二叉树是n(n0)个数据元素的有限集，它或为空集,或者含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。 二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有
16、左右之分，其顺序不能任意颠倒。,定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是： 1)每个结点最多有两棵子树； 2)子树有左右之分，次序不能任意颠倒。,二叉树的基本性质,【性质1】 在二叉树的第K层上最多有2k-1个结点（k1） 【性质2】深度为h的二叉树最多有2h -1个结点（h 1） 【性质3】二叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,满二叉树和完全二叉树,满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。 完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,二叉树的
