全国计算机等级考试二级教程公共基础知识第一章 数据结.ppt

1、全国计算机等级考试二级教程公共基础知识,2020/8/13,2,第一章 数据结构与算法,2020/8/13,3,1.1 算法,1.1.1 算法的基本概念 算法是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算方法。 一般说来，程序的编制不可能优于算法的设计。,2020/8/13,4,1.1 算法,1.算法的基本特征 可行性（effectiveness） 确定性（definiteness） 有穷性（finiteness） 拥有足够的情报,2020/8/13,5,1.1 算法,算法的定义： 是一组严禁地定义的运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下中

2、止。,2020/8/13,6,1.1 算法,2.算法的基本要素 (1) 算法中对数据的运算和操作 算术运算 逻辑运算 关系运算 数据传输,2020/8/13,7,1.1 算法,(2) 算法的控制结构 算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。 算法的基本控制结构：顺序、选择、循环,2020/8/13,8,1.1 算法,3.算法设计基本方法 列举法 归纳法 递推 递归 减半递推技术 回溯法,2020/8/13,9,1.1 算法,例题1 设方程 f ( x ) = 0 在 a , b 上有实根，且 f(a) 与 f(b) 异号，

3、利用二分法来该方程在区间 a , b 上的一个实根。,b,2020/8/13,10,1.1 算法,1.1.2 算法复杂度 算法的复杂度包括时间复杂度和空间复杂度。 1.算法的时间复杂度 算法的时间复杂度是指算法所需要的计算工作量。 与问题有关 与问题的规模有关 与输入有关,2020/8/13,11,课后习题选择1,算法的时间复杂度是指 执行算法程序所需要的时间 算法程序的长度 算法执行过程中所需要的基本运算次数 算法程序中的指令条数,2020/8/13,12,2005年9月试题填空,算法复杂度主要包括时间复杂度和 【2】 复杂度。,2020/8/13,13,1.1 算法,算法工作量f（n） n

4、是问题的规模,2020/8/13,14,1.1 算法,分析算法的工作量 平均性态 最坏情况复杂性,2020/8/13,15,1.1 算法,例题2 采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较，基本运算为x与数组元素的比较。,2020/8/13,16,1.1 算法,平均性态分析 设被查项x在数组中出现的概率为q，则查找次数ti ti =i 1in时 ti =n,i=n+1时 假设x在每个位置上出现的概率一样，则在每个位置上出现的概率为q/n，不出现的概率为1-q，则平均查找次数为 A(n)=1q/n+2 q/n+3 q/n+n q/n+

5、n (1-q) 最坏情况为n,2020/8/13,17,1.1 算法,2.算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。 算法程序所占用的空间 输入的初始数据所占的空间 算法执行过程中所需的额外空间 压缩存储技术,2020/8/13,18,课后习题选择,算法的空间复杂度是指 算法程序的长度 算法程序中的指令条数 算法程序所占的存储空间 算法执行过程中所需要的存储空间,2020/8/13,19,2006年9月试题选择,下列叙述中正确的是_。 A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其

6、空间可复杂度必定小 D）上述三种说法都不对,2020/8/13,20,1.2 数据结构的基本概念,数据结构所研究的问题 数据的逻辑结构数据集合中各数据元素之间所固有的逻辑关系 数据的存储结构在对数据进行处理时，各数据元素在计算机中存储关系 对各种数据结构进行的运算,2020/8/13,21,1.2 数据结构的基本概念,1.2.1 什么是数据结构 数据结构是指相互有关联的数据元素的集合。 数据元素：现实世界中客观存在的一切个体都可以是数据元素。,2020/8/13,22,1.2 数据结构的基本概念,例题3 无序表的顺序查找与有序表的对分查找,35,16,78,85,43,29,33,21,54,

7、46,16,21,29,33,35,43,46,54,78,85,2020/8/13,23,1.2 数据结构的基本概念,例题4 查看学生情况登记表中的学生成绩 总表 分类表 分等次表,2020/8/13,24,1.2 数据结构的基本概念,数据的逻辑结构 数据元素的集合，记为D D上关系的集合，记为R 数据结构表示为 B=(D,R) 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构,2020/8/13,25,1.2 数据结构的基本概念,例题5 一年四季的数据结构可以表示为 B= (D,R) D=春，夏，秋，冬 R= (春，夏) ，(夏，秋)， (秋，冬),2020/8/13,26,1.2 数

8、据结构的基本概念,例题6 家庭成员数据结构表示为 B= (D,R) D=父亲，儿子，女儿 R= (父亲，儿子) ，(父亲，女儿),2020/8/13,27,1.2 数据结构的基本概念,例题7 n维向量的数据结构 X= (X1,X2,X3, ,Xn) D= X1,X2,X3, ,Xn R= (X1,X2 ),( X2,X3 ), , (Xn-1,Xn ) ,2020/8/13,28,1.2 数据结构的基本概念,2. 数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。 不仅要存储数据的信息，还要存储数据元素关系的信息。 常用存储结构：顺序、链接、索引,2020/8/13

9、,29,课后习题选择,数据的存储结构是指 数据所占的存储空间量 数据的逻辑结构在计算机中的表示 数据在计算机中的顺序存储方式 存储在外存中的数据,2020/8/13,30,2007年9月试题选择6,下列叙述中正确的是 A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构 D）以上三种说法都不对,2020/8/13,31,2007年4月试题选择1,下列叙述中正确的是 。 A） 算法的效率只与问题的规模有关,而与数据的存储结构无关. B）算法的时间复杂度

10、是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的. D）算法的时间复杂度与空间复杂度一定相关.,2020/8/13,32,2005年4月试题选择4,下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率,2020/8/13,33,1.2 数据结构的基本概念,1.2.2 数据的图形表示 例题8 用图形表示数据结构B=(D,R) D=di|1i7=d1,d2,d3,d

11、4,d5,d6,d7 R=(d1,d3),(d1,d7 ),(d2,d4 ),(d4,d5),(d3,d6),d1,d3,d7,d6,d2,d4,d5,2020/8/13,34,1.2 数据结构的基本概念,1.2.2 数据的图形表示 根结点 终端结点 数据结构的运算： 插入、删除、查找、分类、合并、分解、复制、修改,2020/8/13,35,1.2 数据结构的基本概念,1.2.3 线性结构与非线性结构 分类依据 数据结构中各数据元素之间前后件关系的复杂程度 线性结构的特点： 有且只有一个根结点 每一个结点最多只有一个前件，也最多只有一个后件。 在一个线性结构中插入或删除任何一个结点后还应是线性

12、结构。,2020/8/13,36,课后习题选择,下列叙述中正确的是 线性表是线性结构 栈和队列是非线性结构 线性链表是非线性结构 二叉树是线性结构,2020/8/13,37,1.3 线性表及其顺序存储结构,1.3.1 线性表的基本概念 线性表是由n（n0）个数据元素a1，a2，a3，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件，即线性表或是一个空表，或可以表示为 （ a1，a2，ai，an ）,2020/8/13,38,1.3 线性表及其顺序存储结构,非空线性表的结构特征 有且只有一个根结点，它无前件 有且只有一个终端结点，它无

13、后件 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件 线性表的长度n0时为空表,2020/8/13,39,1.3 线性表及其顺序存储结构,1.3.2 线性表的顺序存储结构 线性表的顺序存储结构的特点： 线性表中所有元素所占的存储空间时连续的。 线性表中各数据元素在存储空间中是按照逻辑顺序依次存放的。,2020/8/13,40,1.3 线性表及其顺序存储结构,线性表中元素地址 ADR(ai)=ADR(a1)+(i-1)k ADR(a1)：第一个数据元素的存储地址 每个元素占k个字节,2020/8/13,41,1.3 线性表及其顺序存储结构,线性表的主要运算 线性表的插入

14、线性表的删除 线性表的查找 线性表的排序 线性表的分解 线性表的合并 线性表的复制 线性表的逆转,2020/8/13,42,1.3 线性表及其顺序存储结构,1.3.3 顺序表的插入运算 例题9 一个长度为8的线性表顺序存储在长度为10的存储空间中，现在要求在第二个元素18之前插入一个新元素87,2020/8/13,43,1.3 线性表及其顺序存储结构,例题9,V(1:10),87,V(1:10),87,47,31,24,35,63,56,18,29,2020/8/13,44,1.3 线性表及其顺序存储结构,例题9,2020/8/13,45,1.3 线性表及其顺序存储结构,线性表（ a1，a2，

15、ai，an ） 在第i个元素ai前插入一个新元素b，得 （ a1，a2 ，aj ， aj+1 ，an ， an+1 ） 则插入前后两线性表的关系 aj 1j i-1 aj b j=i aj-1 i+1 j n+1,2020/8/13,46,1.3 线性表及其顺序存储结构,1.3.4 顺序表的删除运算 例题10 长度为8的线性表顺序存储在长度为10的存储空间中，要求删除第一个元素。,2020/8/13,47,1.3 线性表及其顺序存储结构,例题10,V(1:10),29,18,56,63,35,24,31,47,V(1:10),2020/8/13,48,1.3 线性表及其顺序存储结构,例题10

16、aj 1j i1 aj aj1 i j n1 线性表插入与删除的效率很低,2020/8/13,49,1.4 栈和队列,1.4.1 栈及其基本运算 1.什么是栈 栈（stack）是限定在一端进行插入与删除的线性表。 栈顶 栈底 先进后出（FILO）后进先出 Topbottom,2020/8/13,50,课后习题选择,下列关于栈的叙述中正确的是 在栈中只能插入数据 在栈中只能删除数据 栈是先进先出的线性表 栈是先进后出的线性表,2020/8/13,51,2006年9月试题填空4,按“先进后出”原则组织数据的数据结构是 【4】 。,2020/8/13,52,2006年4月试题选择4,按照“后进先出”

17、原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 D）二叉树,2020/8/13,53,1.4 栈和队列,2. 栈的顺序存储及其运算 入栈操作,A,B,C,2020/8/13,54,1.4 栈和队列,2. 栈的顺序存储及其运算 退栈操作,A,B,C,X,2020/8/13,55,1.4 栈和队列,思考题：入栈顺序为A、B、C，出栈顺序有哪些？,CBA ABC ACB BAC BCA,不可能有的顺序：CAB,2020/8/13,56,1.4 栈和队列,思考题：入栈顺序为A、B、C、D，出栈顺序有哪些？ ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCD

18、A BDCA CBAD CBDA CDBA DCBA 不可能有的情况 DABC DACB DBCA DBAC DCAB CABD CDAB CADB BDAC ADBC,2020/8/13,57,1.4 栈和队列,2. 栈的顺序存储及其运算 读栈顶操作,A,B,C,X,C,2020/8/13,58,2005年9月试题选择3,下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素,2020/8/13,59,2005年4月试题选择3,下列关于栈

19、的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素,2020/8/13,60,1.4 栈和队列,1.4.2 队列及其基本运算 1.什么是队列 队列（queue）是指允许在一端进行插入、而在另一端进行删除的线性表。 尾指针（rear）排头指针（front） 先进先出（FIFO）,2020/8/13,61,课后习题选择,下列关于队列的叙述中正确的是 在队列中只能插入数据 在队列中只能删除数据 队列是先进先出的线性表 队列是先进后出的线性表,2020/

20、8/13,62,1.4 栈和队列,1.4.2 队列及其基本运算 1.什么是队列 入队,A,B,C,D,2020/8/13,63,1.4 栈和队列,1.4.2 队列及其基本运算 1.什么是队列 退队,A,B,C,D,X,2020/8/13,64,1.4 栈和队列,2. 循环队列及其运算 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,A,B,C,D,2020/8/13,65,1.4 栈和队列,2. 循环队列及其运算,A,B,C,D,E,F,2020/8/13,66,1.4 栈和队列,2. 循环队列及其运算,A,B,C,D,2020/8/13,67,1.4 栈和

21、队列,2. 循环队列及其运算 队列空的条件,rear=front=m,S,0,2020/8/13,68,1.4 栈和队列,2. 循环队列及其运算 队列满的条件,A,B,C,D,E,F,H,I,J,K,L,G,rear=front=m,S,1,2020/8/13,69,课后习题填空,在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列共有_个元素。,个数=rear-front,2020/8/13,70,A,B,C,D,I,J,K,L,1,2,3,4,5,6,8,9,10,11,0,7,个数=rear +m -front,个数=(rear +m front) mo

22、d m,对应记忆：表盘,2020/8/13,71,2005年9月试题填空5,数据结构分为逻辑结构和存储结构，循环队列属于 【5】 结构。,2020/8/13,72,1.4 栈和队列,2. 循环队列及其运算 入队操作,A,B,C,D,E,非满才能入队,2020/8/13,73,1.4 栈和队列,2. 循环队列及其运算 退队操作,A,B,C,D,非空才能退队,X,2020/8/13,74,2007年9月试题填空3,线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_【3】_存储结构。,线性表、队列、栈不提链式存储即默认顺序存储结构,2020/8/13,75

23、,2007年4月试题选择5,下列对列的叙述正确的是 。 A）队列属于非线性表 B）队列按”先进后出”的原则组织数据 C）队列在队尾删除数据 D）队列按先进先出原则组织数据,2020/8/13,76,2006年4月试题选择5,下列叙述中正确的是 A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构,2020/8/13,77,1.5 线性链表,1.5.1 线性链表的基本概念 线性表的顺序存储结构存在的缺点 插入或删除过程需移动大量的元素 存储空间不便于扩充 计算机存储空间得不到充分利用，不便于对存储空间的动态分配 链式存储的结点的

24、结构 数据域 指针域,2020/8/13,78,1.5 线性链表,1. 线式链表,存储序号,数据域,指针域,2020/8/13,79,1.5 线性链表,2020/8/13,80,1.5 线性链表,V(i),NEXT(i),1,2,3,4,5,6,7,8,9,10,a1,3,HEAD,a2,a4,a3,a5,1,9,10,5,0,HEAD,a2,a1,a3,a4,a5,0,2020/8/13,81,1.5 线性链表,双向链表,a1,a2,an,0,0,2020/8/13,82,1.5 线性链表,2. 带链的栈 用来收集计算机存储空间所有空闲的存储结点,a1,a2,a3,0,2020/8/13,8

25、3,1.5 线性链表,3.带链的队列,a1,a2,a3,2020/8/13,84,2006年9月试题填空5,数据结构分为线性结构和非线性结构，带链的队列属于 【5】,2020/8/13,85,1.5 线性链表,1.5.2 线性链表的基本运算 线性链表的插入 线性链表的删除 线性链表的合并 线性链表的分解 线性链表的逆转 线性链表的复制 线性链表的排序 线性链表的查找,2020/8/13,86,1.5 线性链表,1.5.2 线性链表的基本运算 1. 在线性链表中查找指定元素,2020/8/13,87,1.5 线性链表,1.5.2 线性链表的基本运算 插入,a1,a3,a2,a4,2020/8/1

26、3,88,1.5 线性链表,1.5.2 线性链表的基本运算 删除,a1,a3,a2,2020/8/13,89,1.5 线性链表,1.5.3 循环链表及其基本运算 循环链表的两个特点 表头结点、指针域、头指针 最后一个结点,2020/8/13,90,1.6 树与二叉树,1.6.1 树的基本概念,2020/8/13,91,课后习题选择10,设树的度为，其中度为，的结点个数分别为，则中的叶子结点数为 A) 8 B) 7 C) 6 D) 5,2020/8/13,92,2020/8/13,93,2020/8/13,94,2020/8/13,95,2020/8/13,96,度个数叶子 1 4 0 2 2

27、1 3 1 2 4 1 3 1 共个,2020/8/13,97,1.6 树与二叉树,有关名词 根结点 父结点 子结点 叶子结点 度 树的深度,2020/8/13,98,1.6 树与二叉树,运算符 单目运算符 双目运算符 三目运算符 多目运算符 用树表示运算表达式的原则,2020/8/13,99,1.6 树与二叉树,1.6.2 二叉树及其基本性质 1.什么是二叉树 非空二叉树只有一个根结点 每一个结点最多有两棵子树，且分别被称为该结点的左子树和右子树。,2020/8/13,100,1.6 树与二叉树,1.6.2 二叉树及其基本性质 1.什么是二叉树,2020/8/13,101,1.6 树与二叉树

28、,2. 二叉树的基本性质 性质1 在二叉树的第k层上，最多有2 k-1(k=1)个结点。,2020/8/13,102,2005年9月试题填空4,一棵二叉树第六层（根结点为第一层）的结点数最多为 【4】 个。,2020/8/13,103,1.6 树与二叉树,2. 二叉树的基本性质 性质2 深度为m的二叉树最多有2 m-1个结点。,2020/8/13,104,1.6 树与二叉树,2. 二叉树的基本性质 性质3 在任意一棵二叉树中，度为0的结点（即子结点）总是比度为2的结点多一个。 n0+n1+n2=n n1+2*n2=n-1,n0=n2+1,2020/8/13,105,2007年9月试题选择8,一

29、棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A）219 B）221 C）229 D）231,2020/8/13,106,2007年4月试题选择7,某二叉树中有n个度为2的结点则该二叉树中的叶子结点数为 A）n+1 B ）n-1 C）2n D）n/2,2020/8/13,107,1.6 树与二叉树,2. 二叉树的基本性质 性质4 具有n个结点的二叉树，其深度至少为log2n1，其中log2n表示取log2n的整数部分。,2020/8/13,108,1.6 树与二叉树,3. 满二叉树与完全二叉树 满二叉树,2020/8/13,109,课后习题选择8,在深度为的满二叉

30、树中，叶子结点的个数为 A) 32 B) 31 C) 16 D) 15,2020/8/13,110,2007年4月试题填空,在深度为7的满二叉树中，度为2的结点个数为 【1】 。,2020/8/13,111,2006年4月试题选择7,在深度为7的满二叉树中，叶子结点的个数为 A）32 B）31 C）64 D）63,2020/8/13,112,1.6 树与二叉树,3. 满二叉树与完全二叉树 完全二叉树,A,2020/8/13,113,课后习题填空2,设一棵完全二叉树共有700个结点，则在该二叉树中有_个叶子结点。 n0=n2+1 结点数：n0+n1+n2=700 n1=0 或 n1=1 n0、n

31、1、n2 都是整数,2020/8/13,114,1.6 树与二叉树,3. 满二叉树与完全二叉树 性质5 具有n个结点的完全二叉树的深度为log2n1,2020/8/13,115,1.6 树与二叉树,3. 满二叉树与完全二叉树 性质6,2020/8/13,116,1.6 树与二叉树,1.6.3 二叉树的存储结构 链式存储 1.6.4 二叉树的遍历 前序遍历,TBZ,A,XCPY,T,BZ,A,CY,X,P,T,Z,B,A,C,Y,X,P,2020/8/13,117,1.6 树与二叉树,1.6.4 二叉树的遍历 中序遍历,TBZ,A,XCPY,T,BZ,A,CY,X,P,T,Z,B,A,C,Y,X

32、,P,2020/8/13,118,2007年9月试题填空4,对下列二叉树进行中序遍历的结果为_【4】_。,2020/8/13,119,1.6 树与二叉树,1.6.4 二叉树的遍历 后序遍历,TBZ,A,XCPY,T,BZ,A,CY,X,P,T,Z,B,A,C,Y,X,P,2020/8/13,120,课后习题选择,设有下列二叉树，对此二叉树中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,2020/8/13,121,课后习题填空,设一棵二叉树的中序遍历为DBEAFC，前序遍历结果为ABDECF，则其后序遍历结果为,A,D,E,B,F,C,A,BDE

33、,CF,2020/8/13,122,2007年4月试题选择6,对下列二叉树 进行前序遍历的结果为 A）DYBEAFCZX B）YDEBFZXCA C）ABDYECFXZ D）ABCDEFXYZ,2020/8/13,123,2006年9月试题选择10,对下列二叉树进行中序遍历的结果是_。 A）ACBDFEG B）ACBDFGE C）ABDCGEF D）FCADBEG,2020/8/13,124,2006年4月试题选择6,对如下二叉树行后序遍历的结果为 A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA,2020/8/13,125,1.7 查找技术,1.7.1 顺序查找 只能使

34、用顺序查找的情况 无序表 有序表链式存储 1 、 n/2、n 1.7.2 二分法查找 只能在有序的顺序存储时使用 1、log2n,2020/8/13,126,课后习题选择9,对长度为的线性表进行顺序查找，在最坏的情况下所需要的比较次数为 A) n+1 B) n C) (n+1)/2 D) n/2,2020/8/13,127,课后习题填空,在长度为的有序线性表中进行二分查找，需要的比较次数为 log2n +1 log2n,2020/8/13,128,2006年9月试题选择,在长度为64 的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。 A）63 B）64 C）6 D）7,2020/8/

35、13,129,2005年9月试题选择2,下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表,2020/8/13,130,2005年4月试题选择,下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表,2020/8/13,131,1.8 排序技术,1.8.1 交换类排序法 冒泡排序法 从前向后扫描，同时逐次比较相邻两元素大小，若前大后小则互换位置，最大数到最后。 从后向前扫描，逐次比较相邻两元素大小，若后小前大则互换，最小数到最前。 重复过程至有序。,5,1,7,3,1,6,9,4,2,8,6,2020/8/13,132,1.8 排序技术,1.8.1 交换类排序法 冒泡排序法,5,1,7,3,1,6,9,4,2,8,6,1,3,1,6,7,4,2,6,9,1,1,5,3,2,6,7,4,6,8,9,1,1,3,2,5,6,4,6,7,8,9,8,5