九院专升本第三讲.ppt

信息科学与技术学院信息科学与技术学院第三讲第三讲计算机软件基础知识计算机软件基础知识1.1 1.1 算法的基本概念及其特征算法的基本概念及其特征1 1.算法：算法：是一组有穷指令集是一组有穷指令集，是解题方案的准确而完整的描述。，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。通俗地说，算法就是计算机解题的过程。2.2.*算法的基本特征：算法的基本特征：(1)(1)可行性：算法中的操作能够用可行性：算法中的操作能够用已经已经实现的基本运算执行实现的基本运算执行有限次来实现。有限次来实现。(2)(2)确定性：算法中的每一步都有确切的含义。确定性：算法中的每一步都有确切的含义。(3)(3)有穷性：一个算法在执行有穷步骤后能够结束。有穷性：一个算法在执行有穷步骤后能够结束。(4)(4)拥有足够多情报：拥有足够多情报：算法执行过程中要尽可能考虑各种情算法执行过程中要尽可能考虑各种情况；况；一个算法一个算法至少有一至少有一个输出。个输出。第一部分第一部分 数据结构与算法数据结构与算法23.3.算法的基本要素：算法的基本要素：(1)(1)对数据对象的运算和操作对数据对象的运算和操作 (2)(2)算法的控制结构算法的控制结构 4.4.*算法设计基本方法：算法设计基本方法：(1)(1)列举法列举法 (2)(2)归纳法归纳法 (3)(3)递推递推 (4)(4)递归递归 (5)(5)减半递推减半递推 (6)(6)回溯法回溯法第一部分第一部分 数据结构与算法数据结构与算法35.5.*算法复杂度：算法复杂度：(1)(1)算法的时间复杂度：是指算法所需要的计算工作量。算法的时间复杂度：是指算法所需要的计算工作量。用用基本运算次数基本运算次数来衡量，与程序中的执行的指令条数来衡量，与程序中的执行的指令条数密切相关密切相关。(2)(2)算法的空间复杂度：是指执行这个算法所算法的空间复杂度：是指执行这个算法所需要的内存需要的内存空间空间。第一部分第一部分 数据结构与算法数据结构与算法4例题例题:(1)(1)算法的时间复杂度是指算法的时间复杂度是指()A)A)执行算法程序所需要的时间执行算法程序所需要的时间B)B)算法程序的长度算法程序的长度 C)C)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数D)D)算法程序中的指令条数算法程序中的指令条数(2)(2)算法的空间复杂度是指算法的空间复杂度是指()A)A)算法程序的长度算法程序的长度B)B)算法程序中的指令条数算法程序中的指令条数C)C)算法程序所占的存储空间算法程序所占的存储空间D)D)算法执行过程中所需要的存储空间算法执行过程中所需要的存储空间第一部分第一部分 数据结构与算法数据结构与算法5(3)(3)下列叙述中正确的是下列叙述中正确的是()()。A)A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关B)B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C)C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的D)D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关(4)(4)下列叙述中正确的是下列叙述中正确的是()()。A)A)一个算法的空间复杂度大，则其时间复杂度也必定大一个算法的空间复杂度大，则其时间复杂度也必定大B)B)一个算法的空间复杂度大，则其时间复杂度必定小一个算法的空间复杂度大，则其时间复杂度必定小C)C)一个算法的时间复杂度大，则其空间复杂度必定小一个算法的时间复杂度大，则其空间复杂度必定小D)D)上述三种说法都不对上述三种说法都不对第一部分第一部分 数据结构与算法数据结构与算法6(5)(5)问题处理方案的正确而完整的描述称为问题处理方案的正确而完整的描述称为【】。(6)(6)算法复杂度主要包括时间复杂度和算法复杂度主要包括时间复杂度和【】复杂度。复杂度。(7)(7)以下不属于算法特性的是以下不属于算法特性的是()A)A)有穷性有穷性B)B)简捷性简捷性C)C)可行性可行性D)D)确定性确定性算法算法空间空间第一部分第一部分 数据结构与算法数据结构与算法71.2 1.2 数据数据结结构的基本概念构的基本概念1、数据数据结结构是构是计计算机科学与技算机科学与技术领术领域广泛使用的一个域广泛使用的一个基本基本术语术语，用来反映数据的内部构成。，用来反映数据的内部构成。数据数据结结构研究的三个方面：构研究的三个方面：(1)数据集合中各数据元素之数据集合中各数据元素之间间所固有的所固有的逻辑逻辑关系关系,即数即数据的据的逻辑结逻辑结构构(2)在在对对数据数据进进行行处处理理时时,各元素在各元素在计计算机中的存算机中的存储储关系关系,即数据的即数据的存存储结储结构构(物理物理结结构构)(3)对对各种数据各种数据结结构构进进行的运算行的运算第一部分第一部分 数据结构与算法数据结构与算法8数据结构类型 1数据的逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。、数据的运算：检索、排序、插入、删除、修改等。A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 9数据的逻辑结构数据的逻辑结构线性结构线性结构(顺序表、链表、队列、堆栈顺序表、链表、队列、堆栈)非线性结构非线性结构(树、图树、图)数据的逻辑结构是数据的逻辑结构是反映数据元素之间逻辑关系的数反映数据元素之间逻辑关系的数据结构据结构(与所使用的计算机无关与所使用的计算机无关)。数据的逻辑结构。数据的逻辑结构包含：包含：(1 1)表示数据元素的信息；表示数据元素的信息；(2 2)表示各数据元素之间的前后件关系。表示各数据元素之间的前后件关系。第一部分第一部分 数据结构与算法数据结构与算法10线线性性结结构：必构：必须满须满足以下两个条件足以下两个条件(1)有且只有一个根有且只有一个根结结点点,(2)每个每个结结点最多有一个前件点最多有一个前件,也最多有一个后件。也最多有一个后件。线线性性结结构也称构也称线线性表。性表。图图1-11-1线性结构线性结构第一部分第一部分 数据结构与算法数据结构与算法11线性结构和非线性结构 线性结构条件线性结构条件（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。（3）首节点无前件，尾节点无后件。非线性结构：非线性结构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学学学学 生生生生 成成成成 绩绩绩绩 表表表表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号12图图1-1线线性性结结构构如果一个如果一个结结构不是构不是线线性性结结构构,则则称称为为非非线线性性结结构。构。如如图图1-2、图图1-3图图1-21-2非线性结构中的非线性结构中的“树树”形结构形结构图图1-31-3非线性结构中的非线性结构中的“图图”形结构形结构第一部分第一部分 数据结构与算法数据结构与算法13树形结构全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式非线性非线性结构结构 树树形形结结构构14树形结构ABCDEFGH树形结构树形结构树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA15图形结构 图图形形结结构构：节节点点间间的的连连接任意接任意1423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)无向图无向图213 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)有向图有向图16存储结构存储结构：也称数据的物理结构也称数据的物理结构,是指数据的逻辑结构是指数据的逻辑结构在计算机存储空间中的存放形式。在计算机存储空间中的存放形式。其形式包括顺序、其形式包括顺序、链接、索引等。链接、索引等。顺序存储：顺序存储：顺序存储：顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系元里，结点间的逻辑关系由存储单元的邻接关系(位置位置)来体来体现现 链式存储：链式存储：链式存储：链式存储：不要求逻辑上相邻的结点在物理位置上亦相邻，不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的结点间的逻辑关系是由附加的指针字段表示的第一部分第一部分 数据结构与算法数据结构与算法17顺序存储与链式存储Lo+（n-1)*m元素n.元素i.元素2元素1LoLo+mLo+(i-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+（i-1)*m每个元每个元素所占素所占用的存用的存储单元储单元个数个数 顺序存储顺序存储常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点三个弱点插入或删除操作时，需移动大量元数。长度变化较大时，需按最大空间分配。表的容量难以扩充18顺序存储与链式存储 13461346 元素元素3 3 15361536 .15361536 元素元素2 2 14001400 .元素元素4 4 13461346 14001400 元素元素1 1 13451345 指指针 存存储内内容容存存储地址地址1536元素21400元素11346元素3 元素4head1345链式链式链式链式存储存储存储存储的地的地的地的地址映址映址映址映射表射表射表射表19例题例题(1)(1)数据的存储结构是指数据的存储结构是指()A)A)存储在外存中的数据存储在外存中的数据 B)B)数据所占的存储空间数据所占的存储空间 C)C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示(2)(2)以下数据结构中不属于线性数据结构的是以下数据结构中不属于线性数据结构的是()()A)A)队列队列 B)B)线性表线性表 C)C)二叉树二叉树 D)D)栈栈第一部分第一部分 数据结构与算法数据结构与算法20(3)(3)下列叙述中正确的是下列叙述中正确的是()A)A)一个逻辑数据结构只能有一种存储结构一个逻辑数据结构只能有一种存储结构 B)B)数据的逻辑结构属于线性结构，存储结构属于非线性结构数据的逻辑结构属于线性结构，存储结构属于非线性结构 C)C)一个逻辑结构可以有多种存储结构，且各种存储结构不影响一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率数据处理的效率 D)D)一个逻辑结构可以有多种存储结构，且各种存储结构影响数一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率据处理的效率第一部分第一部分 数据结构与算法数据结构与算法211.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构1 1、线性表的基本概念：线性表是一种最简单线性表的基本概念：线性表是一种最简单,最常用的一种数据最常用的一种数据结构。它由一组数据元素构成。结构。它由一组数据元素构成。2 2、线性表的顺序存储结构：线性表的顺序存储结构：(两个特点两个特点)(1)(1)线性表中所有元素所占的存储空间是连续的线性表中所有元素所占的存储空间是连续的 (2)(2)线性表中各元素在存储空间中是按逻辑顺序依次存放的线性表中各元素在存储空间中是按逻辑顺序依次存放的3 3、元素元素a ai i的存储地址为：的存储地址为：ADR(aADR(ai i)=ADR(a)=ADR(a1 1)+(i-)+(i-1)k,1)k,，ADR(aADR(a1 1)为第一个元素的地址，为第一个元素的地址，k k代表每个元素占的字节数。代表每个元素占的字节数。4 4、线线性表的顺序存储基本操作：性表的顺序存储基本操作：插入，删除，查找插入，删除，查找第一部分第一部分 数据结构与算法数据结构与算法221.4 1.4 线性链表线性链表 概念：用一组任意的存储单元来依次存放线性表的各结点。概念：用一组任意的存储单元来依次存放线性表的各结点。这组存储单元既可以是连续的，也可以是不连续的，甚至是这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，零散分布在内存中的任意位置上的。因此，链表中结点的逻链表中结点的逻辑次序和物理次序不一定相同辑次序和物理次序不一定相同。线性链表的基本运算：插入、删除、查找线性链表的基本运算：插入、删除、查找第一部分第一部分 数据结构与算法数据结构与算法23 线性链表的结点由两部分组成：线性链表的结点由两部分组成：(1)(1)用于存储数据元素值，称为用于存储数据元素值，称为数据域数据域；(2)(2)用于存放指针，称为用于存放指针，称为指针域指针域，用于指向前一个或后，用于指向前一个或后一个结点。一个结点。在链式存储结构中，存储数据结构的空间可以不连续，各数据在链式存储结构中，存储数据结构的空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。所以，据元素之间的逻辑关系是由指针域来确定的。所以，链式存储链式存储方式即可用于表示线性结构，也可用于表示非线性结构。方式即可用于表示线性结构，也可用于表示非线性结构。第一部分第一部分 数据结构与算法数据结构与算法24几种常见的链表：几种常见的链表：(1)(1)单向链表，单向链表，HEADHEAD称为头指针，称为头指针，HEAD=NULL(HEAD=NULL(或或0)0)称为空表；称为空表；数据数据域域指针指针域域head第一部分第一部分 数据结构与算法数据结构与算法(2)(2)双向链表：左指针双向链表：左指针(LlinkLlink)指向前件结点，右指针指向前件结点，右指针(RlinkRlink)指向后件结点。指向后件结点。(3)(3)循环链表：循环链表：25线性表的顺序存储结构称为线性表的顺序存储结构称为顺序顺序表表线性表的链式存储结构称为线性链表线性表的链式存储结构称为线性链表二者的比较：二者的比较：1)1)顺顺序表存储数据时在逻辑上相连的在物理上也一定相连。序表存储数据时在逻辑上相连的在物理上也一定相连。2)2)链表存储数据时在逻辑上相连的在物理上不一定相连。链表存储数据时在逻辑上相连的在物理上不一定相连。3)3)顺序表插入和删除比较麻烦，但是访问每一个结点比较简单顺序表插入和删除比较麻烦，但是访问每一个结点比较简单4)4)链表插入和删除比较简单，但是访问每一个结点比较麻烦链表插入和删除比较简单，但是访问每一个结点比较麻烦第一部分第一部分 数据结构与算法数据结构与算法261.5 1.5 栈和队列栈和队列 栈：也叫堆栈，是指限定在一端进行插入与删除的线性表。允许栈：也叫堆栈，是指限定在一端进行插入与删除的线性表。允许插入与删除的一端称为插入与删除的一端称为栈顶栈顶；不允许插入与删除的另一端称为；不允许插入与删除的另一端称为栈栈底底。栈按照。栈按照“先进后出先进后出”(FILO)(FILO)或或“后进先出后进先出”(LIFO)(LIFO)组织数据组织数据，栈具有记忆作用。，栈具有记忆作用。栈的基本运算：栈的基本运算：(1)(1)插入元素：也称为入栈运算插入元素：也称为入栈运算 (2)(2)删除元素：也称为退栈运算删除元素：也称为退栈运算 (3)(3)读栈顶元素：将栈顶元素赋给一个指定的变量读栈顶元素：将栈顶元素赋给一个指定的变量 (此时指针无变化此时指针无变化)第一部分第一部分 数据结构与算法数据结构与算法27 队列：允许在一端队列：允许在一端(队尾队尾)进入插入，而在另一端进入插入，而在另一端(队头队头)进行删进行删除的线性表。队列按照除的线性表。队列按照“先进先出先进先出”(FIFO)(FIFO)或或“后进后出后进后出”(LI(LILO)LO)组织数据。组织数据。队列基本运算：队列基本运算：(1)(1)入队运算：从队尾插入一个元素；入队运算：从队尾插入一个元素；(2)(2)退队运算：从队头删除一个元素。退队运算：从队头删除一个元素。循环队列：是将队列的存储空间的最后一个位置绕到第一个位循环队列：是将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的形状空间，供队列循环使用置，形成逻辑上的形状空间，供队列循环使用，其实质还是顺其实质还是顺序存储结构序存储结构。第一部分第一部分 数据结构与算法数据结构与算法28例题例题(1)(1)下列关于栈叙述正确的是下列关于栈叙述正确的是()A)A)在栈中只能插入数据在栈中只能插入数据 B)B)在栈中只能删除数据在栈中只能删除数据 C)C)栈是先进先出的线性表栈是先进先出的线性表 D)D)栈是先进后出的线性表栈是先进后出的线性表(2)(2)下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是()A)A)在队列中只能插入数据在队列中只能插入数据 B)B)在队列中只能删除数据在队列中只能删除数据 C)C)队列是先进先出的线性表队列是先进先出的线性表 D)D)队列是先进后出的线性表队列是先进后出的线性表第一部分第一部分 数据结构与算法数据结构与算法29(3)(3)栈和队列的共同特点是栈和队列的共同特点是()A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点没有共同点(4)(4)设输入序列为设输入序列为1 1、2 2、3 3、4 4，则借助一个栈可以得到的输出序，则借助一个栈可以得到的输出序列是列是()A)1 A)1，3 3，4 4，2 2 B)3 B)3，1 1，4 4，2 2 C)4 C)4，3 3，1 1，2 2 D)4 D)4，1 1，2 2，3 3第一部分第一部分 数据结构与算法数据结构与算法30(5)(5)在一个容量为在一个容量为1515的循环队列中，若队头的循环队列中，若队头front=6,front=6,队尾队尾rear=9rear=9，则该循环队列中有则该循环队列中有()()个元素。个元素。答案：答案：3 3分析：如图分析：如图1-81-8与图与图1-91-9的两种循环队列存放数据的形式的两种循环队列存放数据的形式第一部分第一部分 数据结构与算法数据结构与算法在非空队列中，头指针始终指向队头元素前一个在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置位置，而尾指针始终指向队尾元素的位置31由此可以得出元素的个数为：由此可以得出元素的个数为：rear-front=3rear-front=3可是当可是当front=9,rear=6front=9,rear=6的时候，则会出现如下的存放形式的时候，则会出现如下的存放形式 图图1-91-9改改变变后的存后的存储结储结构构元素的个数元素的个数为为1212个，能个，能够查够查出，出，这这个个1212通通过计过计算也能算也能够够得出：得出：rear-front+rear-front+总总容量容量=6-9+15=12=6-9+15=12第一部分第一部分 数据结构与算法数据结构与算法32计算循环队列长度计算循环队列长度：front=rear，队列长度，队列长度0；frontrear，队列长度，队列长度rear+size-front33(6)(6)(6)(6)下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是()()()()。A)A)A)A)栈是先进先出的线性表栈是先进先出的线性表栈是先进先出的线性表栈是先进先出的线性表 B)B)B)B)队列是队列是队列是队列是 先进后出先进后出先进后出先进后出 的线性表的线性表的线性表的线性表C)C)C)C)循环队列是非线性结构循环队列是非线性结构循环队列是非线性结构循环队列是非线性结构D)D)D)D)有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构,也可以采用链式存储也可以采用链式存储也可以采用链式存储也可以采用链式存储结构结构结构结构(7)(7)(7)(7)下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是()()()()。A)A)A)A)线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构 B)B)B)B)栈与队列是非线性结构栈与队列是非线性结构栈与队列是非线性结构栈与队列是非线性结构C)C)C)C)双向链表是非线性结构双向链表是非线性结构双向链表是非线性结构双向链表是非线性结构 D)D)D)D)只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构 第一部分第一部分 数据结构与算法数据结构与算法34(8)(8)下列叙述中正确的是下列叙述中正确的是()()。A)A)顺序存储结构的存储一定是连续的，链式存储结构的存储顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的空间不一定是连续的B)B)顺序存储结构只针对线性结构，链式存储结构只针对非线顺序存储结构只针对线性结构，链式存储结构只针对非线性结构性结构C)C)顺序存储结构能存储有序表，链式存储结构不能存储有序顺序存储结构能存储有序表，链式存储结构不能存储有序表表D)D)链式存储结构比顺序存储结构节省存储空间链式存储结构比顺序存储结构节省存储空间第一部分第一部分 数据结构与算法数据结构与算法35(9)(9)数据的存储结构是指数据的存储结构是指()()。A)A)存储在外存中的数据存储在外存中的数据 B)B)数据所占的存储空间量数据所占的存储空间量C)C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示(10)(10)下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是()()A)A)存储空间不一定是连续存储空间不一定是连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的B)B)存储空间不一定是连续存储空间不一定是连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面C)C)存储空间必须连续存储空间必须连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面D)D)存储空间必须连续存储空间必须连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的 第一部分第一部分 数据结构与算法数据结构与算法36(11)(11)下列数据结构中下列数据结构中,能够按照能够按照“先进后出先进后出”原则存取数据的是原则存取数据的是()()。A)A)循环队列循环队列 B)B)栈栈 C)C)队列队列 D)D)二叉树二叉树(12)(12)对于循环队列，下列叙述中正确的是对于循环队列，下列叙述中正确的是()()。A)A)队头指针是固定不变的队头指针是固定不变的 B)B)队头指针一定大于队尾指针队头指针一定大于队尾指针C)C)队头指针一定小于队尾指针队头指针一定小于队尾指针 D)D)队头指针可以大于队尾指针队头指针可以大于队尾指针,也可以小于队尾指针也可以小于队尾指针第一部分第一部分 数据结构与算法数据结构与算法37(13)(13)假设用一个长度为假设用一个长度为5050的数组的数组(数组元素的下标从数组元素的下标从0 0到到49)49)作为作为栈的存储空间栈的存储空间,栈底指针栈底指针bottombottom指向栈底元素指向栈底元素,栈顶指针栈顶指针toptop指指向栈顶元素向栈顶元素,如果如果bottom=49,top=30(bottom=49,top=30(数组下标数组下标),),则栈中具有则栈中具有【】个元素。个元素。(14)(14)支持子程序调用的数据结构是支持子程序调用的数据结构是()()。A)A)栈栈 B)B)树树 C)C)队列队列 D)D)二叉树二叉树2020第一部分第一部分 数据结构与算法数据结构与算法38(15)(15)一个栈的初始状态为空。现将元素一个栈的初始状态为空。现将元素1 1、2 2、3 3、4 4、5 5、A A、B B、C C、D D、E E依次入栈，然后再依次出栈，则元素出栈的顺序是依次入栈，然后再依次出栈，则元素出栈的顺序是()。A)12345ABCDE A)12345ABCDE B)EDCBA54321 B)EDCBA54321 C)ABCDE12345 C)ABCDE12345 D)54321EDCBAD)54321EDCBA第一部分第一部分 数据结构与算法数据结构与算法39(16)(16)下列叙述中正确的是下列叙述中正确的是()()。A)A)循环队列有队头和队尾两个指针，因此，循环队列是非线循环队列有队头和队尾两个指针，因此，循环队列是非线性结构性结构B)B)在循环队列中，只需要队头指针就能反映队列中元素的动在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况态变化情况C)C)在循环队列中，只需要队尾指针就能反映队列中元素的动在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况态变化情况D)D)循环队列中元素的个数是由队头指针和队尾指针共同决定循环队列中元素的个数是由队头指针和队尾指针共同决定第一部分第一部分 数据结构与算法数据结构与算法40(17)(17)下列关于栈的叙述正确的是下列关于栈的叙述正确的是()()。A)A)栈按栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据C)C)只能在栈底插入数据只能在栈底插入数据 D)D)不能删除数据不能删除数据(18)(18)设某循环队列的容量为设某循环队列的容量为5050，头指针，头指针front=5(front=5(指向队头元素指向队头元素的前一位置的前一位置)，尾指针，尾指针rear=29(rear=29(指向队尾元素指向队尾元素)，则该循环队，则该循环队列中共有列中共有【】个元素。个元素。(19)(19)线性表的存储结构主要分为顺序存储结构和链式存储结构线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的。队列是一种特殊的线性表，循环队列是队列的【】存储结构存储结构。2424顺序顺序第一部分第一部分 数据结构与算法数据结构与算法41(20)(20)下列对队列的叙述正确的是下列对队列的叙述正确的是()()。A)A)队列属于非线性表队列属于非线性表 B)B)队列按队列按“先进后出先进后出”原则组织数据原则组织数据C)C)队列在队尾删除数据队列在队尾删除数据 D)D)队列按队列按“先进先出先进先出”原则组织数据原则组织数据(21)(21)数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于 【】。(23)(23)按照按照“后进先出后进先出”原则组织数据的数据结构是原则组织数据的数据结构是()()。A)A)队列队列 B)B)栈栈 C)C)双向链表双向链表 D)D)二叉树二叉树线性结构线性结构第一部分第一部分 数据结构与算法数据结构与算法421.6 1.6 树与二叉树树与二叉树 1.1.概念：树是一种简单的非线性结构，所有元素之间具有明显概念：树是一种简单的非线性结构，所有元素之间具有明显的层次特性。的层次特性。在树结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点父结点，没有前，没有前件的结点只有一个，称为件的结点只有一个，称为树的根结点，树的根结点，简称树的简称树的根根。每一个结。每一个结点可以有多个后件，称为该结点的点可以有多个后件，称为该结点的子结点子结点。没有后件的结点称。没有后件的结点称为为叶子结点叶子结点。在树结构中，一个结点所拥有的后件的个数称为在树结构中，一个结点所拥有的后件的个数称为该结点的度该结点的度，所有结点中最大的度称为树的度。树的最大层次称为所有结点中最大的度称为树的度。树的最大层次称为树的深度树的深度。第一部分第一部分 数据结构与算法数据结构与算法43 2.2.二叉树二叉树(度为度为2 2的树的树)特点：特点：(1)(1)非空二叉树只有一个根结点；非空二叉树只有一个根结点；(2)(2)每一个结点最多每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。有两棵子树，且分别称为该结点的左子树与右子树。第一部分第一部分 数据结构与算法数据结构与算法44二叉树的性质：二叉树的性质：(1)(1)在二叉树的第在二叉树的第k k层上，最多有层上，最多有2 2k-1k-1个结点，如图个结点，如图1-111-11图图1-11 1-11 性质性质1 1的理解的理解第一部分第一部分 数据结构与算法数据结构与算法45(2)(2)深度为深度为h h的二叉树最多有的二叉树最多有2 2h h-1-1个结点，如图个结点，如图1-121-12图图1-12 1-12 性质性质2 2的理解的理解第一部分第一部分 数据结构与算法数据结构与算法46(3)(3)任何一个二叉树中，度为任何一个二叉树中，度为0 0的结点的结点(即叶子结点即叶子结点N N0 0)总比度为总比度为2 2的结点的结点(N(N2 2)多一个多一个,即即 N N0 0=N=N2 2+1+1(4)(4)具有具有n n个结点的二叉树，其中深度至少为个结点的二叉树，其中深度至少为loglog2 2n+1n+1(5)(5)假设假设e e为树的边数，为树的边数，n n表示总结点数，则表示总结点数，则任何树任何树的边数一定比的边数一定比总结点数少总结点数少1 1，即，即e=n-1e=n-1第一部分第一部分 数据结构与算法数据结构与算法473 3.满二叉树：满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。除最后一层外，每一层上的所有结点都有两个子结点。4 4.完全二叉树：完全二叉树：若设二叉树的高度为若设二叉树的高度为h h，除第，除第 h h 层外，其它各层层外，其它各层 (1(1h-1)h-1)的结点数都达到最大个数，第的结点数都达到最大个数，第 h h 层所有的节点都连续集中在最左边，这就是完全二叉树。层所有的节点都连续集中在最左边，这就是完全二叉树。完全二叉树是由完全二叉树是由满二叉树满二叉树而引出来的。对于深度为而引出来的。对于深度为K K的，有的，有N N个个结点的二叉树，当且仅当其每一个结点都与深度为结点的二叉树，当且仅当其每一个结点都与深度为K K的的满二叉树满二叉树中编号从中编号从1 1至至N N的结点一一对应时称之为完全二叉树。的结点一一对应时称之为完全二叉树。完全二叉树中，度为完全二叉树中，度为1 1的结点最多只有的结点最多只有1 1个个 完全二叉树左右子树的深度之差不大于完全二叉树左右子树的深度之差不大于1 1第一部分第一部分 数据结构与算法数据结构与算法48满二叉树423167891011121314155 特点：所有分支结点都存在左右子树，且所有叶特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。子结点都在同一层上。49完全二叉树4231678910 11125 非完全二叉树非完全二叉树4231678910 11125 完全二叉树完全二叉树 特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最后一层结点都集中在该层最左边最左边的若干位置。的若干位置。50二叉树的基本性质A A、二叉树的第二叉树的第i i层上至多有层上至多有2 2i-1i-1（i i 1 1）个结点。）个结点。B B、深度为深度为h h的二叉树中至多含有的二叉树中至多含有2 2h h-1-1个结点。个结点。C C、若在任意一棵二叉树中，有若在任意一棵二叉树中，有n0n0个叶子结点（度为个叶子结点（度为0 0），有），有n2n2个度为个度为2 2的结点，则：的结点，则：n0=n2+1n0=n2+1D D、具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n+1n+1，其中，其中 loglog2 2nn表示表示loglog2 2n n 的整数部分。的整数部分。423167891011121314155第三层第三层 (i=3)(i=3)，有，有2 23-13-1=4=4个节点个节点深度深度h=4h=4，共有，共有2 24 4-1=15-1=15个节点个节点n0=8,n2=7,n0=n2+1n0=8,n2=7,n0=n2+11515个节点，深度个节点，深度=log=log2 215+1=415+1=451例题例题(1)(1)在深度为在深度为5 5的满二叉树中，叶子结点个数为的满二叉树中，叶子结点个数为()A)32 A)32 B)21 B)21 C)16 C)16 D)15 D)15第一部分第一部分 数据结构与算法数据结构与算法52(2)(2)设一棵完全二叉树上有设一棵完全二叉树上有700700个结点，则二叉树中有个结点，则二叉树中有()个叶子结点个叶子结点。根据二叉树的性质根据二叉树的性质:对于一棵非空的二叉树对于一棵非空的二叉树,如果叶子节点数为如果叶子节点数为n0,度为度为2的结点数为的结点数为n2,则则no=n2+1.根据完全二叉树的定义可得根据完全二叉树的定义可得:在完全二叉树中度为在完全二叉树中度为1的结点的结点n1只只能取两种情况能取两种情况,要么为要么为0,要么为要么为1.所以所以:n0+n1+n2=700 n0=n2+1;2n0=701-n1;因为结点数为整数，所以因为结点数为整数，所以n1=1,no=350 35035053(3)(3)设一棵完全二叉树上有设一棵完全二叉树上有801801个结点，则二叉树中有个结点，则二叉树中有()个叶子结点个叶子结点。?(4)(4)某二叉树中，度为某二叉树中，度为2 2的结点有的结点有1818个，则该二叉树中有个，则该二叉树中有()个叶子结点。个叶子结点。?(5)(5)一棵二叉树第一棵二叉树第6 6层上的结点数最多为层上的结点数最多为()个。个。40140119193232第一部分第一部分 数据结构与算法数据结构与算法54二叉树的遍历：二叉树的遍历：(1)(1)前序遍历前序遍历(DLR)(DLR)，首先访问根结点，然后遍历左子树，最后，首先访问根结点，然后遍历左子树，最后遍历右子树；遍历右子树；(树根在第一，下走不跳结点树根在第一，下走不跳结点)(2)(2)中序遍历中序遍历(LDR)(LDR)，首先遍历左子树，然后访问根结点，最后，首先遍历左子树，然后访问根结点，最后遍历右子树；遍历右子树；(有左先左，再寻根，后找右，最左边的结点最先遍历，最右有左先左，再寻根，后找右，最左边的结点最先遍历，最右边的结点最后遍历边的结点最后遍历)(3)(3)后序遍历后序遍历(LRD)(LRD)首先遍历左子树，然后访问遍历右子树，最首先遍历左子树，然后访问遍历右子树，最后访问根结点。后访问根结点。(有左先左，再找右，后寻根，到最右一路上有左先左，再找右，后寻根，到最右一路上行，树根在最后行，树根在最后)第一部分第一部分 数据结构与算法数据结构与算法55第一部分第一部分 数据结构与算法数据结构与算法56已知二叉树的前序遍历为已知二叉树的前序遍历为ABDEFCABDEFC，中序遍历为，中序遍历为DBFEACDBFEAC，则二叉，则二叉树的后序遍历结果是：树的后序遍历结果是：分析：分析：前序遍历为前序遍历为ABDEFCABDEFC中序遍历为中序遍历为DBFEACDBFEAC第一步：确定第一步：确定A A为根结点，则由中序遍历为根结点，则由中序遍历(DBFEDBFEA AC C)可以知道可以知