[IT认证]公共基础1.ppt

《[IT认证]公共基础1.ppt》由会员分享，可在线阅读，更多相关《[IT认证]公共基础1.ppt（40页珍藏版）》请在三一办公上搜索。

1、公共基础知识,第一章 基本数据结构与算法,新航线培训中心 http:/,考点1-算法,一、算法基本概念 算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述，它是指令的有限序列，使得给定类型的问题通过有限的指令序列，在有限的时间内被求解。1.算法的基本特性 有穷性 即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。,新航线培训中心 http:/,考点1-算法,确定性 算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生

2、偏差。,新航线培训中心 http:/,考点1-算法,输入和输出（拥有足够的情报）算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。,新航线培训中心 http:/,考点1-算法,二、算法复杂度 算法的时间复杂度 算法的空间复杂度,新航线培训中心 http:/,练习,算法的时间复杂度是指 A)执行算法程序所需要的时间 B)算法程序的长度 C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数,参考答案：C【解析】算法的复杂度主要包括算法的时间复杂度和空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作

3、量,即算法执行过程中所需要的基本运算的次数;算法的空间复杂度一般是指执行这个算法所需要的内存空间。,新航线培训中心 http:/,练习,算法的空间复杂度是指 A)算法程序的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)执行算法需要的内存空间,参考答案：D【解析】算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量;算法的空间复杂度是指执行这个算法所需要的内存空间。,新航线培训中心 http:/,考点2 数据结构的基本概念,一、什么是数据结构 1 数据结构的定义 数据结构是指互相之间存在着一种或多种关系的数据元素的集合。,数

4、据元素是数据的基本单位，即数据集合中的个体。数据元素亦称节点或记录。有时一个数据元数可由若干数据项组成。数据项是数据的最小单位。,数据元素,新航线培训中心 http:/,2 数据的逻辑结构 是指反映数据元素之间的逻辑关系的数据结构。数据的逻辑结构有两个要素：数据元素的集合，记作D数据之间的前后关系，记作R则数据结构B=（D，R）,考点2 数据结构的基本概念,新航线培训中心 http:/,考点2 数据结构的基本概念,3 数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。

5、,新航线培训中心 http:/,考点2 数据结构的基本概念,二、线性结构与非线性结构,A,B,C,，X,Y,Z,学 生 成 绩 表,线性表结点间是以线性关系联结,线性结构,新航线培训中心 http:/,考点2 数据结构的基本概念,非线性结构（图形结构）,新航线培训中心 http:/,考点2 数据结构的基本概念,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),新航线培训中心 http:/,练习,数据结构作为计算机的一门学科,主要研

6、究数据的逻辑结构、对各种数据结构进行的运算,以及 _.A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储,参考答案：A【解析】数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题:数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;对各种数据结构进行的运算。,新航线培训中心 http:/,考点3 线性表及其顺序存储结构,顺序存储结构,顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点：1.作插入或删除操作时，需移动大量元数。2.长度变化较大

7、时，需按最大空间分配。3.表的容量难以扩充。,新航线培训中心 http:/,考点4 栈和队列,一、栈,进栈出栈(先进后出),栈顶,栈底,新航线培训中心 http:/,练习,栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A)ABCED B)DCBEA C)DBCEA D)CDABE,参考答案：B【解析】栈操作原则上后进先出,栈底至栈顶依次存放元素A、B、C、D,则表明这4个元素中D是最后进栈,B、C处于中间,A最早进栈,所以出栈时一定是先出D,再出C,最后出A。,新航线培训中心 http:/,考点4 栈和队列,队列定义：一种特殊的线性结构，限定只

8、能在表的一端进行插入，在表的另一端进行删除的线性表。特点：先进先出,a1，a2,a3,a4an-1,an,队 列 示 意 图,队头,队尾,新航线培训中心 http:/,考点4 栈和队列,循环队列：就是将队列存储空间最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。循环队列中实际元素个数：（Rear-Front+N）mod N，其中 Rear为队尾，Front为队头 N 为循环队列最多可以存放元素个数，mod为取余运算,设某循环列队的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_个元素,（10-45+5

9、0）%50=15,新航线培训中心 http:/,考点5 线性链表,线性表的链式存储结构称为线性链表。,链式存储结构,线性链表表示法:,新航线培训中心 http:/,考点6 树与二叉树,一、树的基本概念 由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。,新航线培训中心 http:/,考点6 树与二叉树,结点：树中的元素，包含数据项及若干指向其子树的分支。结点的度：结点拥有的子树数。叶子：度为零的结点，也称终端结点。结点的层次：从根结点开始算起，根为第一层。深度：树中结点的最大层次数。,4,新航线培训中心 http:/,考点6 树与二叉树,二、二叉树及其基本性质 二叉树

10、是另一种树型结构，它的特点是每个结点最多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。,特别要注意：二叉树不是树的特殊情况。,a,a,b,b,两棵不同的二叉树,新航线培训中心 http:/,满二叉树,特点：每一层上都含有最大结点数。,考点6 树与二叉树,新航线培训中心 http:/,完全二叉树,特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。,考点6 树与二叉树,新航线培训中心 http:/,A、二叉树的第i层上至多有2 i-1（i 1）个结点。,二叉树的基本性质,第三层上(i=3)，有23-1=4个节点。

11、第四层上(i=4)，有24-1=8个节点。,考点6 树与二叉树,新航线培训中心 http:/,A、二叉树的第i层上至多有2 i-1（i 1）个结点。B、深度为k的二叉树中至多含有2k-1个结点。,二叉树的基本性质,此树的深度k=4，共有24-1=15个节点。,考点6 树与二叉树,新航线培训中心 http:/,A、二叉树的第i层上至多有2 i-1（i 1）个结点。B、深度为k的二叉树中至多含有2k-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1,二叉树的基本性质,n0=8n2=7,考点6 树与二叉树,新航线培训中心 http:/,A、二叉树的第i层

12、上至多有2 i-1（i 1）个结点。B、深度为k的二叉树中至多含有2k-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1D、具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取log2n的整数部分。,二叉树的基本性质,考点6 树与二叉树,新航线培训中心 http:/,二叉树遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。,考点6 树与二叉树,遍历算法（1）前（先）序遍历：首选访问根结点，然后遍历左子树，最后遍历右子树。（2）中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。（3）后序遍历

13、：首选遍历左子树，然后遍历右子树，最后访问根结点。,新航线培训中心 http:/,遍历算法,先序遍历：D L R中序遍历：L D R后序遍历：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,考点6 树与二叉树,新航线培训中心 http:/,练习,若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca,参考答案：D【解析】前序遍历的第一个结点a为树的根节点;中序遍历中a的左边

14、的结点为a的左子树,a的右边的结点为a的右子树;再分别对a的左右子树进行上述两步处理,直到每个结点都找到正确的位置。,新航线培训中心 http:/,练习,已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 A)acbed B)decab C)deabc D)cedba,参考答案：D【解析】依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成,右子树为空;又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成。,新航线培训中心 http:/,考点7 查找技术,顺序查找,k=9,s,新航线培训中心 http

15、:/,考点7 查找技术,二分法查找,查找23的过程如下图：,mid=(low+high)/2取整,(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),(08,14,23,37,46,55,68,79,91),新航线培训中心 http:/,考点8 排序技术,插入排序,基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。需要n(n-1)/2次比较,新航线培训中心 http:/,考点8 排序技术,待排元素序列：53 27 36

16、 15 69 42第一次排序：27 53 36 15 69 42第二次排序：27 36 53 15 69 42第三次排序：15 27 36 53 69 42第四次排序：15 27 36 53 69 42第五次排序：15 27 36 42 53 69 插入排序示例,新航线培训中心 http:/,选择类排序法 最坏情况下需要比较 n(n-1)/2次,考点8 排序技术,2 8 10 7 5 4,2 8 10 7 5 4,2 4 10 7 5 8,2 4 5 7 10 8,2 4 5 7 10 8,2 4 5 7 8 10,待排元素序列,第一次排序,第二次排序,第三次排序,第四次排序,第五次排序,新航

17、线培训中心 http:/,练习,冒泡排序在最坏情况下的比较次数是 A)n(n+1)/2 B)nlog2n C)n(n-1)/2 D)n/2,参考答案：C【解析】冒泡排序的基本思想是对当前未排序的全部结点自上而下依次进行比较和调整,让键值较大的结点下沉,键值较小的结点往上冒。也就是说,每当两相邻结点比较后发现它们的排列与排序要求相反时,就将它们互换。对n个结点的线性表采用冒泡排序,冒泡排序的外循环最多执行n-1遍。第一遍最多执行n-1次比较,第二遍最多执行n-2次比较,依次类推,第n-1遍最多执行1次比较。因此,整个排序过程最多执行n(n-1)/2次比较,新航线培训中心 http:/,练习,对长度为n的线性表排序,在最坏情况下,比较次数不是n(n-1)/2的排序方法是 A)快速排序 B)冒泡排序 C)直接插入排序 D)堆排序,参考答案：D【解析】在最坏情况下,快速排序、冒泡排序和直接插入排序需要的比较次数都n(n-1)/2,堆排序需要比较的次数为nlog2n。,本章结束,