伯乐大典之计算机二级二级公共基础

《伯乐大典之计算机二级二级公共基础》由会员分享，可在线阅读，更多相关《伯乐大典之计算机二级二级公共基础（189页珍藏版）》请在金锄头文库上搜索。

1、1,计算机等级考试二级,公共基础,2,主要内容,算法与数据结构 程序设计基础 软件工程基础 数据库设计基础,比例：10道选择题，共10分,3,第1章 算法和数据结构,1.1 算法的基本内容 算法的基本概念 算法的描述方法 算法的基本特征 算法的基本运算和操作 算法的控制结构 算法的基本设计方法 算法的复杂度,4,1. 算法的基本概念,算法是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法； 程序可以作为算法的一种描述。 对于一个问题，如果通过一个计算机程序，在有限的存储空间内、运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。,5,自然语言来描述：用人们日常使用的语

2、言来表述算法，可以是汉语、英语或其它语言，直接将算法步骤表述出来。 专门的描述语言（伪码）：一种接近于计算机编程语言的算法描述方法，便于向计算机程序语言过渡。由一些英文单词构成伪码的符号系统。 传统流程图：采用一些图形框和带箭头的线条来描述算法中的各种操作。 N-S结构化图：去掉流程图中的流程线和开始结束的圆角矩形，其余的部分都表示在一个矩形框内。,2. 算法的描述方法,6,流程图,N-S图,7,练习,为了避免流程图在描述程序逻辑时的灵活性,提出了用方框图来代替传统的程序流程图,通常也把这种图称为 A) PAD图 B) N-S图 C) 结构图 D) 数据流图,8,3. 算法的基本特征,可行性：

3、针对实际问题而设计的算法，执行后能够得到满意的结果。 确定性：算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性。 有穷性：算法必须能在有限的时间内做完，即能在执行有限个步骤后终止。 拥有足够的情报：要使算法有效必需为算法提供足够的情报（基础数据）。当算法拥有足够的情报时，此算法才是最有效的；而当提供的情报不够时，算法可能无效。,9,4. 算法的基本运算和操作,算术运算：加、减、乘、除 逻辑运算：与、或、非 关系运算：大于、小于、等于、不等于 数据传输：赋值、输入、输出,10,5. 算法的控制结构,顺序结构 选择结构 循环结构,11,列举法：根据提出的问题，列举所有可能的情

4、况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。例如，鸡兔同笼问题 归纳法：通过观察一些简单而特殊的情况，最后总结出一般性的结论，需要证明。例如，自然数求和,6. 算法的基本设计方法,12,递推：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。例如：裴波那契数列，是采用递推的方法解决问题的。 递归：分为直接递归（算法调用本身）与间接递归（算法调用其他算法，而其他算法又调用该算法）例如：求阶乘,13,减半递推技术：“减半” 是指将问题的规模减半，而问题的性质不变；“递推”是指重复减半的过程。 例如：二分法查找 回溯法一种有效的方法是“试”。通过对问题的分析，找出一个解决问题

5、的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，否则，就逐步回退，换别的路线再逐步试探。例如：走迷宫,14,7. 算法的复杂度,算法的时间复杂度 指执行算法所需要的计算工作量，用算法所执行的基本运算的次数来计算，被称为问题规模。 算法的空间复杂度 指执行这个算法所需要的内存空间 ，包括： 算法对应的源程序存储占用的空间 输入数据占用空间 运行过程中所需要的额外的空间,分析算法的目的：分析算法的效率，以求改进,15,1.2 数据结构的主要内容,数据结构的概念 数据结构研究的内容 数据逻辑结构的分类 数据存储结构的分类 数据的存储结构与逻辑结构的关系,16,1. 什么是数据结构,数据

6、结构是指相互有关联的数据元素的集合。它包括以下两个方面： 表示数据元素的信息 表示各数据之间的前后件关系,17,2. 数据结构研究的内容,数据结构研究和讨论以下三个方面 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; 在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构; 对各种数据结构进行的运算：插入、删除、修改数据元素。,18,3.逻辑结构的分类,线性结构 有且只有一个结点没有前件，称为根结点； 每个结点最多有一个前件，最多只有一个后件，没有后件的结点称为叶子结点 常见的线性结构：线性表、栈、队列,19,非线性结构 集合：元素无顺序 树形结构：结构中的数据

7、元素之间存在着“一对多”的关系。 图形结构：数据元素之间存在“多对多”的关系，每个结点都可以有多个直接前件和多个直接后件。,20,空数据结构 空数据结构是线性结构和非线性结构的一种特殊情况。 空数据结构如果按照线性结构的规则去处理则属于线性结构 如果按照非线性结构的规则去处理则属于非线性结构。,21,4. 数据的存储结构及分类,数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。 数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。 常见的存储结构有：顺序、链式、索引,22,5.数据的存储结构与逻辑结构的关系,一种数据的逻辑结构根据需要可

8、以表示成多种存储结构 一种存储结构可以表示多种逻辑结构。,线性表 栈 队列 树,顺序存储 链式存储,23,1.3 线性表的顺序存储结构,1. 线性表的基本概念 线性表是由n个数据元素构成的有限序列（a1, a2, an），具有下面的特征： (1) 有且只有一个根结点a1，它无前件; (2) 有且只有一个终端结点an，它无后件; (3) 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 结点个数n称为线性表的长度。 当n=0时，称为空线性表。,24,2.线性表的顺序存储结构,用一组地址连续的存储单元依次存储线性表的数据元素 线性表第1个元素的地址为adr(a1) 每个元素

9、占的字节数为k 第i个元素ai的存储地址为： adr(ai)=adr(a1)+(i-1)k 线性表的顺序存储，称为顺序表,adr(a1),adr(an),adr(a1),adr(an),adr(a1),adr(an),25,3.顺序表的特点,顺序表中所有元素的所占的存储空间是连续的; 线性表中逻辑上相邻的数据元素在存储空间中是相邻的，即按顺序依次存放的； 可以随机访问元素； 对于元素很多的线性表进行插入和删除运算不方便。,adr(a1),adr(an),26,查找：从头查找，最坏情况下比较n次 插入：长度为n的顺序表 在第i（1in+1)个位置插入一个新结点x，将结点an，ai各后移一位，腾出

10、第i个位置， 将x插入该空位，表长加1 删除：长度为n指将顺序表删除第i个结点， ai+1，an依次向前移动一个位置，表长减1,4. 线性表顺序存储后的运算,27,顺序表的插入运算举例：,28,在线性表中删除元素举例,29,1.4 栈,栈是一种线性结构，是一种特殊的线性表 栈是限定在一端进行插入与删除操作。允许插入与删除的一端称为栈顶（用top表示），不允许插入与删除的另一端称为栈底（用bottom表示）。 栈的特点 “先进后出”(FILO)或“后进先出”(LIFO) 栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才能被删除的元素。,30,栈的示意图

11、,31,1.5 队列,队列是一种线性结构，是一种特殊的线性表 。 队列允许在一端进行插入，称为队尾；在另一端进行删除 ，称为队头。 队列有两个指针：rear指针指向队尾元素的后一个位置，front指针指向队头元素。 队列的特点是“先进先出”(FIFO)或“后进后出”(LILO),rear,front,32,1.6 栈和队列的顺序存储,栈的顺序存储,33,队列的顺序存储,这种队列存在的问题：假溢出,34,循环队列,将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。 即：当rear=m，下一次入队rear=1 入队：在队尾插入一个元素，rear=rear+1。当rear=m+1时，

12、rear=1。 退队：从队头删除，front=front+1。当front=m+1时，front=1,35,队列，在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列共有（）个元素。 评析：循环队列中元素的数目： rearfront，为rear-front rearfront, m-(front-rear) 本例中9-6=3 答案：3,36,设某循环队列的容量为50，如果头指针front=45,（指向队头元素的前一位置），尾指针rear=10（指向对尾元素），则该循环队列中共有_个元素 M=50 M-(front-rear)=50-(45-10)=15 答案：

13、15,37,1.7 链式存储,数据元素随机存储在计算机中。存储数据的存储空间可以连续也可以不连续。 为了表达数据之间的逻辑关系，存储一个数据由两部分组成： 一部分用于存放数据元素，称为数据域； 另一部分用于存放指向该结点的前一个或后一个结点的指针，称为指针域。,38,1.7.1 线性表的链式存储,定义：线性表的链式存储称为线性链表 线性链表中元素由两部分组成： 存储数据元素本身的数据域 存储后件或前件地址的指针域。 头结点：数据域为空，指针域指向第一个结点的数据域. 设置头结点的目的：使空表的运算和非空表的运算统一。,234,101,500,206,头指针,数据域,指针域,39,根据结点的指针

14、域的个数和尾结点是否指向头结点分为以下几类：,1. 线性链表的分类,单链表,双向链表,40,单循环链表,双循环链表,41,2. 单链表的基本运算,1）查找 在线性单链表中，查找元素x，只能从链表的头指针出发，顺着指针域next逐个结点往下查找是否有结点值等于给定值x，若有的话，则返回首次找到的结点的存储位置；否则返回null。,42,在线性单链表中第i个结点的位置上插入一个新元素X。生成一个新结点*q，数据域为x，新结点的指针域指向结点ai，ai-1指向新结点,2）插入,43,3）删除,44,链表的头指针就是链栈的栈顶指针 插入和删除操作只能在栈顶进行.,1.7.2 栈的链式存储（链栈）,45

15、,带链的队列实际上是一个同时带有头指针和尾指针的带头结点的单链表 头指针front指向链队列的头结点，尾指针rear指向链队列的尾结点。 链队列一般不会出现队满的情况,front,rear,1.7.3 队列的链式存储,46,树是一种简单的的非线性结构，所有元素之间的关系具有明显的层次特性。,1.8 树和二叉树,A,只有一个结点的树,有多个结点的树,47,1.8.1 树的定义,有一个根（root）结点，它没有直接前件，只有后件 除根结点以外的其它结点有且仅有一个直接前件，但可以有0个或多个直接后件。 没有后件的结点称为叶子结点 同一父结点下的子结点称为兄弟结点；,48,一个结点所拥有的后件的个数

16、（子结点的数目）称为该结点的度； 叶子结点的度为0 所有结点中最大的度称为树的度； 层数：根结点的层数为1，其余结点的层数等于它父结点的层数加1 树的最大层次称为树的深度。,49,1. 二叉树的特点 非空二叉树只有一个根结点； 根可以有空的左子树或空的右子树。且其次序不能任意颠倒 左右子树都是二叉树。 每个结点至多有二棵子树，即二叉树中不存在度大于2的结点,1.8.2 二叉树,50,2. 二叉树基本形态,A,空二叉树； 只有一个根结点的二叉树； 可以只有左子树或只有右子树的二叉树； 既有左子树又有右子树的二叉树。,51,3. 二叉树的基本性质,在二叉树的第k层上，最多有2（k-1）(k1)个结点;最少有1个结点 深度为k的二叉树最多有2k-1个结点; 度为0的结点n0(即叶子结点) 比度为2的结点n2多一个，则n0=n2+1,52,练习,深度为9的二叉树中至少有 个结点。 )9 )8 ) )91,53,1.8.3 满二叉树和完全二叉树,若二叉树中的结点，或者度为2，或者度为0，并且度