计算机基础课件ppt-计算机公共基础基础.pdf

《计算机基础课件ppt-计算机公共基础基础.pdf》由会员分享，可在线阅读，更多相关《计算机基础课件ppt-计算机公共基础基础.pdf（128页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.1 1.1 算算法法的的基基本本概概念念及及其其特特征征1 1. . 算算法法：是是一一组组有有穷穷指指令令集集，是是解解题题方方案案的的准准确确而而完完整整的的描描述述。通通俗俗地地说说，算算法法就就是是计计算算机机解解题题的的过过程程。2.2. * *算算法法的的基基本本特特征征： (1) (1)可可行行性性：算算法法中中的的操操作作能能够够用用已已经经实实现现的的基基本本运运算算执执行行有有限限次次来来实实现现。 (2) (2)确确定定性性：算算法法中中的的每每一一步步都都有有确确切切的的含含义义。 (3) (3)有有穷穷性性：一一个个算算法法在在执执行行有有穷穷步步骤骤后后能能够够

2、结结束束。 (4) (4)拥拥有有足足够够多多情情报报：算算法法执执行行过过程程中中要要尽尽可可能能给给考考虑虑各各种种情情况况；一一个个算算法法至至少少有有一一个个输输出出。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法3.3.算算法法的的基基本本要要素素： (1) (1)对对数数据据对对象象的的运运算算和和操操作作 (2) (2)算算法法的的控控制制结结构构 4.4.* *算算法法设设计计基基本本方方法法： (1) (1)列列举举法法 (2) (2)归归纳纳法法 (3) (3)递递推推 (4) (4)递递归归 (5) (5)减减半半递递推推 (6) (6)回回溯

3、溯法法第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法5.5.* *算算法法复复杂杂度度： (1) (1)算算法法的的时时间间复复杂杂度度：是是指指算算法法所所需需要要的的计计算算工工作作量量。用用基基本本运运算算次次数数来来衡衡量量，与与程程序序中中的的执执行行的的指指令令条条数数密密切切相相关关。 (2) (2)算算法法的的空空间间复复杂杂度度：是是指指执执行行这这个个算算法法所所需需要要的的内内存存空空间间。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法例例题题: :(1)(1)算算法法的的时时间间复复杂杂度度是是指指( ( ) )A

4、)A)执执行行算算法法程程序序所所需需要要的的时时间间B)B)算算法法程程序序的的长长度度 C)C)算算法法执执行行过过程程中中所所需需要要的的基基本本运运算算次次数数D)D)算算法法程程序序中中的的指指令令条条数数(2)(2)算算法法的的空空间间复复杂杂度度是是指指( ( ) )A)A)算算法法程程序序的的长长度度B)B)算算法法程程序序中中的的指指令令条条数数C)C)算算法法程程序序所所占占的的存存储储空空间间D)D)算算法法执执行行过过程程中中所所需需要要的的存存储储空空间间第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(3)(3)下下列列叙叙述述中中正正确确

5、的的是是( )( )。A)A)算算法法的的效效率率只只与与问问题题的的规规模模有有关关，而而与与数数据据的的存存储储结结构构无无关关B)B)算算法法的的时时间间复复杂杂度度是是指指执执行行算算法法所所需需要要的的计计算算工工作作量量C)C)数数据据的的逻逻辑辑结结构构与与存存储储结结构构是是一一一一对对应应的的D)D)算算法法的的时时间间复复杂杂度度与与空空间间复复杂杂度度一一定定相相关关(4)(4)下下列列叙叙述述中中正正确确的的是是( )( )。A)A)一一个个算算法法的的空空间间复复杂杂度度大大，则则其其时时间间复复杂杂度度也也必必定定大大B)B)一一个个算算法法的的空空间间复复杂杂度度

6、大大，则则其其时时间间复复杂杂度度必必定定小小C)C)一一个个算算法法的的时时间间复复杂杂度度大大，则则其其空空间间复复杂杂度度必必定定小小D)D)上上述述三三种种说说法法都都不不对对第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(5)(5)问问题题处处理理方方案案的的正正确确而而完完整整的的描描述述称称为为【 】。(6)(6)算算法法复复杂杂度度主主要要包包括括时时间间复复杂杂度度和和【 】复复杂杂度度。(7)(7)以以下下不不属属于于算算法法特特性性的的是是( ( ) )A)A)有有穷穷性性B)B)简简捷捷性性C)C)可可行行性性D)D)确确定定性性算算法法空空

7、间间第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.2 1.2 数数据据结结构构的的基基本本概概念念1 1、数数据据结结构构是是计计算算机机科科学学与与技技术术领领域域广广泛泛使使用用的的一一个个基基本本术术语语，用用来来反反映映数数据据的的内内部部构构成成。数数据据结结构构研研究究的的三三个个方方面面：(1)(1)数数据据集集合合中中各各数数据据元元素素之之间间所所固固有有的的逻逻辑辑关关系系, ,即即数数据据的的逻逻辑辑结结构构(2)(2)在在对对数数据据进进行行处处理理时时, ,各各元元素素在在计计算算机机中中的的存存储储关关系系, ,即即数数据据的的存存储

8、储结结构构( (物物理理结结构构) )(3)(3)对对各各种种数数据据结结构构进进行行的的运运算算第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法数数据据的的逻逻辑辑结结构构线线性性结结构构( (顺顺序序表表、链链表表、队队列列、堆堆栈栈) )非非线线性性结结构构( (树树、图图) )数数据据的的逻逻辑辑结结构构是是反反映映数数据据元元素素之之间间逻逻辑辑关关系系的的数数据据结结构构( (与与所所使使用用的的计计算算机机无无关关) )。数数据据的的逻逻辑辑结结构构包包含含：( (1 1) )表表示示数数据据元元素素的的信信息息；( (2 2) )表表示示各各数数据据元

9、元素素之之间间的的前前后后件件关关系系。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法线线性性结结构构：必必须须满满足足以以下下两两个个条条件件(1)(1)有有且且只只有有一一个个根根结结点点, ,(2)(2)每每个个结结点点最最多多有有一一个个前前件件, ,也也最最多多有有一一个个后后件件。线线性性结结构构也也称称线线性性表表。图图1-11-1线线性性结结构构第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法图图1-11-1线线性性结结构构如如果果一一个个结结构构不不是是线线性性结结构构, ,则则称称为为非非线线性性结结构构。如如图图1-2

10、1-2、图图1-31-3图图1-21-2非非线线性性结结构构中中的的“树树”形形结结构构图图1-31-3非非线线性性结结构构中中的的“图图”形形结结构构第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法存存储储结结构构：也也称称数数据据的的物物理理结结构构, ,是是指指数数据据的的逻逻辑辑结结构构在在计计算算机机存存储储空空间间中中的的存存放放形形式式。其其形形式式包包括括顺顺序序、链链接接、索索引引等等。顺顺顺顺序序序序存存存存储储储储：逻逻辑辑上上相相邻邻的的结结点点存存储储在在物物理理位位置置相相邻邻的的存存储储单单元元里里，结结点点间间的的逻逻辑辑关关系系由由存

11、存储储单单元元的的邻邻接接关关系系( (位位置置) )来来体体现现 链链链链式式式式存存存存储储储储：不不要要求求逻逻辑辑上上相相邻邻的的结结点点在在物物理理位位置置上上亦亦相相邻邻，结结点点间间的的逻逻辑辑关关系系是是由由附附加加的的指指针针字字段段表表示示的的第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法例例题题(1)(1)数数据据的的存存储储结结构构是是指指( ( ) ) A)A)存存储储在在外外存存中中的的数数据据 B) B)数数据据所所占占的的存存储储空空间间 C) C)数数据据在在计计算算机机中中的的顺顺序序存存储储方方式式 D) D)数数据据的的逻逻辑

12、辑结结构构在在计计算算机机中中的的表表示示(2)(2)以以下下数数据据结结构构中中不不属属于于线线性性数数据据结结构构的的是是 ( ) ( ) A)A)队队列列 B) B)线线性性表表 C) C)二二叉叉树树 D) D) 栈栈第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(3)(3)下下列列叙叙述述中中正正确确的的是是( ( ) ) A) A)一一个个逻逻辑辑数数据据结结构构只只能能有有一一种种存存储储结结构构 B) B)数数据据的的逻逻辑辑结结构构属属于于线线性性结结构构，存存储储结结构构属属于于非非线线性性结结构构 C) C)一一个个逻逻辑辑结结构构可可以以有有

13、多多种种存存储储结结构构，且且各各种种存存储储结结构构不不影影响响数数据据处处理理的的效效率率 D) D)一一个个逻逻辑辑结结构构可可以以有有多多种种存存储储结结构构，且且各各种种存存储储结结构构影影响响数数据据处处理理的的效效率率第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.3 1.3 线线性性表表及及其其顺顺序序存存储储结结构构1 1、线线性性表表的的基基本本概概念念：线线性性表表是是一一种种最最简简单单, ,最最常常用用的的一一种种数数据据结结构构。它它由由一一组组数数据据元元素素构构成成。2 2、线线性性表表的的顺顺序序存存储储结结构构：( (两两个个特

14、特点点) ) (1) (1)线线性性表表中中所所有有元元素素所所占占的的存存储储空空间间是是连连续续的的 (2) (2)线线性性表表中中各各元元素素在在存存储储空空间间中中是是按按逻逻辑辑顺顺序序依依次次存存放放的的3 3、元元素素a ai i的的存存储储地地址址为为：ADR(aADR(ai i)=ADR(a)=ADR(a1 1)+(i-1)k,)+(i-1)k,，ADR(aADR(a1 1) )为为第第一一个个元元素素的的地地址址，k k代代表表每每个个元元素素占占的的字字节节数数。4 4、线线性性表表的的顺顺序序存存储储基基本本操操作作：插插入入，删删除除，查查找找第第一一部部分分 数数数

15、数据据据据结结结结构构构构与与与与算算算算法法法法1.4 1.4 线线性性链链表表 概概念念：用用一一组组任任意意的的存存储储单单元元来来依依次次存存放放线线性性表表的的各各结结点点。 这这组组存存储储单单元元既既可可以以是是连连续续的的，也也可可以以是是不不连连续续的的，甚甚至至是是零零散散分分布布在在内内存存中中的的任任意意位位置置上上的的。因因此此，链链表表中中结结点点的的逻逻辑辑次次序序和和物物理理次次序序不不一一定定相相同同。线线性性链链表表的的基基本本运运算算：插插入入、删删除除、查查找找第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法 线线性性链链表表的

16、的结结点点由由两两部部分分组组成成：(1)(1)用用于于存存储储数数据据元元素素值值，称称为为数数据据域域；(2)(2)用用于于存存放放指指针针，称称为为指指针针域域，用用于于指指向向前前一一个个或或后后一一个个结结点点。 在在链链式式存存储储结结构构中中，存存储储数数据据结结构构的的空空间间可可以以不不连连续续，各各数数据据结结点点的的存存储储顺顺序序与与数数据据元元素素之之间间的的逻逻辑辑关关系系可可以以不不一一致致，而而数数据据元元素素之之间间的的逻逻辑辑关关系系是是由由指指针针域域来来确确定定的的。所所以以，链链式式存存储储方方式式即即可可用用于于表表示示线线性性结结构构，也也可可用用

17、于于表表示示非非线线性性结结构构。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法几几种种常常见见的的链链表表：(1)(1)单单向向链链表表，HEADHEAD称称为为头头指指针针，HEAD=NULL(HEAD=NULL(或或0)0)称称为为空空表表；数数据据域域指指针针域域head第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(2)(2)双双向向链链表表：左左指指针针( (LlinkLlink) )指指向向前前件件结结点点，右右指指针针( (RlinkRlink) )指指向向后后件件结结点点。(3)(3)循循环环链链表表：线线性性表表的的顺

18、顺序序存存储储结结构构称称为为顺顺序序表表线线性性表表的的链链式式存存储储结结构构称称为为线线性性链链表表二二者者的的比比较较：1)1)顺顺序序表表存存储储数数据据时时在在逻逻辑辑上上相相连连的的在在物物理理上上也也一一定定相相连连。2)2)链链表表存存储储数数据据时时在在逻逻辑辑上上相相连连的的在在物物理理上上不不一一定定相相连连。3)3)顺顺序序表表插插入入和和删删除除比比较较麻麻烦烦，但但是是访访问问每每一一个个结结点点比比较较简简单单4)4)链链表表插插入入和和删删除除比比较较简简单单，但但是是访访问问每每一一个个结结点点比比较较麻麻烦烦第第一一部部分分 数数数数据据据据结结结结构构构

19、构与与与与算算算算法法法法1.5 1.5 栈栈和和队队列列 栈栈：也也叫叫堆堆栈栈，是是指指限限定定在在一一端端进进行行插插入入与与删删除除的的线线性性表表。允允许许插插入入与与删删除除的的一一端端称称为为栈栈顶顶；不不允允许许插插入入与与删删除除的的另另一一端端称称为为栈栈底底。栈栈按按照照“先先进进后后出出”(FILO)(FILO)或或“后后进进先先出出”(LIFO)(LIFO)组组织织数数据据，栈栈具具有有记记忆忆作作用用。 栈栈的的基基本本运运算算： (1)(1)插插入入元元素素：也也称称为为入入栈栈运运算算 (2)(2)删删除除元元素素：也也称称为为退退栈栈运运算算 (3)(3)读读

20、栈栈顶顶元元素素：将将栈栈顶顶元元素素赋赋给给一一个个指指定定的的变变量量 ( (此此时时指指针针无无变变化化) )第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法 队队列列：允允许许在在一一端端( (队队尾尾) )进进入入插插入入，而而在在另另一一端端( (队队头头) )进进行行删删除除的的线线性性表表。队队列列按按照照“先先进进先先出出”(FIFO)(FIFO)或或“后后进进后后出出”(LILO)(LILO)组组织织数数据据。 队队列列基基本本运运算算： (1)(1)入入队队运运算算：从从队队尾尾插插入入一一个个元元素素； (2)(2)退退队队运运算算：从从队队头

21、头删删除除一一个个元元素素。 循循环环队队列列：是是将将队队列列的的存存储储空空间间的的最最后后一一个个位位置置绕绕到到第第一一个个位位置置，形形成成逻逻辑辑上上的的形形状状空空间间，供供队队列列循循环环使使用用，其其实实质质还还是是顺顺序序存存储储结结构构。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法例例题题(1)(1)下下列列关关于于栈栈叙叙述述正正确确的的是是( ( ) ) A) A) 在在栈栈中中只只能能插插入入数数据据 B) B) 在在栈栈中中只只能能删删除除数数据据 C) C) 栈栈是是先先进进先先出出的的线线性性表表 D) D) 栈栈是是先先进进后后

22、出出的的线线性性表表(2)(2)下下列列关关于于队队列列的的叙叙述述中中正正确确的的是是( ( ) ) A) A) 在在队队列列中中只只能能插插入入数数据据 B) B) 在在队队列列中中只只能能删删除除数数据据 C) C) 队队列列是是先先进进先先出出的的线线性性表表 D) D) 队队列列是是先先进进后后出出的的线线性性表表第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(3)(3)栈栈和和队队列列的的共共同同特特点点是是( ( ) ) A) A) 都都是是先先进进先先出出 B) B) 都都是是先先进进后后出出 C) C) 只只允允许许在在端端点点处处插插入入和和删删

23、除除元元素素 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第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(5)(5)在在一一个个容容量量为为1515的的循循环环队队列列中中，若若队队头头front=6,front=6,队队尾尾rear=9rear=9，则则该该循

24、循环环队队列列中中有有( )( )个个元元素素。答答案案：3 3分分析析：如如图图1-81-8与与图图1-91-9的的两两种种循循环环队队列列存存放放数数据据的的形形式式第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法由由此此可可以以得得出出元元素素的的个个数数为为：rear-front=3rear-front=3可可是是当当front=9,rear=6front=9,rear=6的的时时候候，则则会会出出现现如如下下的的存存放放形形式式 图图1-91-9改改变变后后的的存存储储结结构构元元素素的的个个数数为为1212个个，能能够够查查出出，这这个个1212通通过过计

25、计算算也也能能够够得得出出： rear-front+ rear-front+总总容容量量=6-9+15=12=6-9+15=12第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(6)(6)(6)(6)下下下下列列列列叙叙叙叙述述述述中中中中正正正正确确确确的的的的是是是是( )( )( )( )。 A)A)A)A)栈栈栈栈是是是是先先先先进进进进先先先先出出出出的的的的线线线线性性性性表表表表 B)B)B)B)队队队队列列列列是是是是 先先先先进进进进后后后后出出出出 的的的的线线线线性性性性表表表表C)C)C)C)循循循循环环环环队队队队列列列列是是是是非非非非线线

26、线线性性性性结结结结构构构构D)D)D)D)有有有有序序序序线线线线性性性性表表表表即即即即可可可可以以以以采采采采用用用用顺顺顺顺序序序序存存存存储储储储结结结结构构构构, , , ,也也也也可可可可以以以以采采采采用用用用链链链链式式式式存存存存储储储储结结结结构构构构(7)(7)(7)(7)下下下下列列列列叙叙叙叙述述述述中中中中正正正正确确确确的的的的是是是是( )( )( )( )。A)A)A)A)线线线线性性性性链链链链表表表表是是是是线线线线性性性性表表表表的的的的链链链链式式式式存存存存储储储储结结结结构构构构 B)B)B)B)栈栈栈栈与与与与队队队队列列列列是是是是非非非非线

27、线线线性性性性结结结结构构构构C)C)C)C)双双双双向向向向链链链链表表表表是是是是非非非非线线线线性性性性结结结结构构构构 D)D)D)D)只只只只有有有有根根根根结结结结点点点点的的的的二二二二叉叉叉叉树树树树是是是是线线线线性性性性结结结结构构构构 第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(8)(8)下下列列叙叙述述中中正正确确的的是是( )( )。A)A)顺顺序序存存储储结结构构的的存存储储一一定定是是连连续续的的，链链式式存存储储结结构构的的存存储储空空间间不不一一定定是是连连续续的的B)B)顺顺序序存存储储结结构构只只针针对对线线性性结结构构，链

28、链式式存存储储结结构构只只针针对对非非线线性性结结构构C)C)顺顺序序存存储储结结构构能能存存储储有有序序表表，链链式式存存储储结结构构不不能能存存储储有有序序表表D)D)链链式式存存储储结结构构比比顺顺序序存存储储结结构构节节省省存存储储空空间间第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(9)(9)数数据据的的存存储储结结构构是是指指( )( )。A)A)存存储储在在外外存存中中的的数数据据 B)B)数数据据所所占占的的存存储储空空间间量量C)C)数数据据在在计计算算机机中中的的顺顺序序存存储储方方式式 D)D)数数据据的的逻逻辑辑结结构构在在计计算算机机中中

29、的的表表示示(10)(10)下下列列对对于于线线性性链链表表的的描描述述中中正正确确的的是是( )( )A)A)存存储储空空间间不不一一定定是是连连续续, , 且且各各元元素素的的存存储储顺顺序序是是任任意意的的B)B)存存储储空空间间不不一一定定是是连连续续, , 且且前前件件元元素素一一定定存存储储在在后后件件元元素素的的前前面面C)C)存存储储空空间间必必须须连连续续, , 且且前前件件元元素素一一定定存存储储在在后后件件元元素素的的前前面面D)D)存存储储空空间间必必须须连连续续, , 且且各各元元素素的的存存储储顺顺序序是是任任意意的的 第第一一部部分分 数数数数据据据据结结结结构构

30、构构与与与与算算算算法法法法(11)(11)下下列列数数据据结结构构中中, ,能能够够按按照照“先先进进后后出出”原原则则存存取取数数据据的的是是( )( )。A)A)循循环环队队列列 B)B)栈栈 C)C)队队列列 D)D)二二叉叉树树(12)(12)对对于于循循环环队队列列，下下列列叙叙述述中中正正确确的的是是( )( )。A)A)队队头头指指针针是是固固定定不不变变的的 B)B)队队头头指指针针一一定定大大于于队队尾尾指指针针C)C)队队头头指指针针一一定定小小于于队队尾尾指指针针 D)D)队队头头指指针针可可以以大大于于队队尾尾指指针针, ,也也可可以以小小于于队队尾尾指指针针第第一一

31、部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(13)(13)假假设设用用一一个个长长度度为为5050的的数数组组( (数数组组元元素素的的下下标标从从0 0到到49)49)作作为为栈栈的的存存储储空空间间, ,栈栈底底指指针针bottombottom指指向向栈栈底底元元素素, ,栈栈顶顶指指针针toptop指指向向栈栈顶顶元元素素, ,如如果果bottom=49,top=30(bottom=49,top=30(数数组组下下标标),),则则栈栈中中具具有有【 】个个元元素素。(14)(14)支支持持子子程程序序调调用用的的数数据据结结构构是是( )( )。A)A)栈栈 B)

32、B)树树 C)C)队队列列 D)D)二二叉叉树树2020第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(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第第一一部部分分

33、 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(16)(16)下下列列叙叙述述中中正正确确的的是是( )( )。A)A)循循环环队队列列有有队队头头和和队队尾尾两两个个指指针针，因因此此，循循环环队队列列是是非非线线性性结结构构B)B)在在循循环环队队列列中中，只只需需要要队队头头指指针针就就能能反反映映队队列列中中元元素素的的动动态态变变化化情情况况C)C)在在循循环环队队列列中中，只只需需要要队队尾尾指指针针就就能能反反映映队队列列中中元元素素的的动动态态变变化化情情况况D)D)循循环环队队列列中中元元素素的的个个数数是是由由队队头头指指针针和和队队尾尾指指针针共共同同决决定定

34、第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(17)(17)下下列列关关于于栈栈的的叙叙述述正正确确的的是是( )( )。A)A)栈栈按按“先先进进先先出出”组组织织数数据据 B)B)栈栈按按“先先进进后后出出”组组织织数数据据C)C)只只能能在在栈栈底底插插入入数数据据 D)D)不不能能删删除除数数据据(18)(18)设设某某循循环环队队列列的的容容量量为为5050，头头指指针针front=5(front=5(指指向向队队头头元元素素的的前前一一位位置置) )，尾尾指指针针rear=29(rear=29(指指向向队队尾尾元元素素) )，则则该该循循环环队队列列中

35、中共共有有【 】个个元元素素。(19)(19)线线性性表表的的存存储储结结构构主主要要分分为为顺顺序序存存储储结结构构和和链链式式存存储储结结构构。队队列列是是一一种种特特殊殊的的线线性性表表，循循环环队队列列是是队队列列的的【 】存存储储结结构构。2424顺顺序序第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(20)(20)下下列列对对队队列列的的叙叙述述正正确确的的是是( )( )。A)A)队队列列属属于于非非线线性性表表 B)B)队队列列按按“先先进进后后出出”原原则则组组织织数数据据C)C)队队列列在在队队尾尾删删除除数数据据 D)D)队队列列按按“先先进进

36、先先出出”原原则则组组织织数数据据(21)(21)数数据据结结构构分分为为线线性性结结构构和和非非线线性性结结构构，带带链链的的队队列列属属于于 【 】。(23)(23)按按照照“后后进进先先出出”原原则则组组织织数数据据的的数数据据结结构构是是( )( )。A)A)队队列列 B)B)栈栈 C)C)双双向向链链表表 D)D)二二叉叉树树线线性性结结构构第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.6 1.6 树树与与二二叉叉树树 1.1.概概念念：树树是是一一种种简简单单的的非非线线性性结结构构，所所有有元元素素之之间间具具有有明明显显的的层层次次特特性性。在在

37、树树结结构构中中，每每一一个个结结点点只只有有一一个个前前件件，称称为为父父结结点点，没没有有前前件件的的结结点点只只有有一一个个，称称为为树树的的根根结结点点，简简称称树树的的根根。每每一一个个结结点点可可以以有有多多个个后后件件，称称为为该该结结点点的的子子结结点点。没没有有后后件件的的结结点点称称为为叶叶子子结结点点。在在树树结结构构中中，一一个个结结点点所所拥拥有有的的后后件件的的个个数数称称为为该该结结点点的的度度，所所有有结结点点中中最最大大的的度度称称为为树树的的度度。树树的的最最大大层层次次称称为为树树的的深深度度。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算

38、算算法法法法 2.2.二二叉叉树树( (度度为为2 2的的树树) ) 特特点点：(1)(1)非非空空二二叉叉树树只只有有一一个个根根结结点点；(2)(2)每每一一个个结结点点最最多多有有两两棵棵子子树树，且且分分别别称称为为该该结结点点的的左左子子树树与与右右子子树树。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法二二叉叉树树的的性性质质：(1)(1)在在二二叉叉树树的的第第k k层层上上，最最多多有有2 2k-1k-1个个结结点点，如如图图1-111-11图图1-11 1-11 性性质质1 1的的理理解解第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算

39、算算算法法法法(2)(2)深深度度为为h h的的二二叉叉树树最最多多有有2 2h h-1-1个个结结点点，如如图图1-121-12图图1-12 1-12 性性质质2 2的的理理解解第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(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+1

40、n+1(5)(5)假假设设e e为为树树的的边边数数，n n表表示示总总结结点点数数，则则任任何何树树的的边边数数一一定定比比总总结结点点数数少少1 1，即即e=n-1e=n-1第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法3 3. .满满二二叉叉树树： 除除最最后后一一层层外外，每每一一层层上上的的所所有有结结点点都都有有两两个个子子结结点点。4 4. .完完全全二二叉叉树树： 若若设设二二叉叉树树的的高高度度为为h h，除除第第 h h 层层外外，其其它它各各层层 (1(1h-1) h-1) 的的结结点点数数都都达达到到最最大大个个数数，第第 h h 层层所所有

41、有的的节节点点都都连连续续集集中中在在最最左左边边，这这就就是是完完全全二二叉叉树树。 完完全全二二叉叉树树是是由由满满二二叉叉树树而而引引出出来来的的。对对于于深深度度为为K K的的，有有N N个个结结点点的的二二叉叉树树，当当且且仅仅当当其其每每一一个个结结点点都都与与深深度度为为K K的的满满二二叉叉树树中中编编号号从从1 1至至N N的的结结点点一一一一对对应应时时称称之之为为完完全全二二叉叉树树。 完完全全二二叉叉树树中中，度度为为1 1的的结结点点最最多多只只有有1 1个个 完完全全二二叉叉树树左左右右子子树树的的深深度度之之差差不不大大于于1 1第第一一部部分分 数数数数据据据据

42、结结结结构构构构与与与与算算算算法法法法例例题题(1)(1)在在深深度度为为5 5的的满满二二叉叉树树中中，叶叶子子结结点点个个数数为为( ( ) ) A) 32 A) 32 B) 21 B) 21 C) 16 C) 16 D) 15 D) 15(2)(2)设设一一棵棵完完全全二二叉叉树树上上有有700700个个结结点点，则则二二叉叉树树中中有有( ( ) )个个叶叶子子结结点点。350350第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(3) (3) 设设一一棵棵完完全全二二叉叉树树上上有有801801个个结结点点，则则二二叉叉树树中中有有( ( ) )个个叶叶子

43、子结结点点。(4)(4)某某二二叉叉树树中中，度度为为2 2的的结结点点有有1818个个，则则该该二二叉叉树树中中有有( ( ) )个个叶叶子子结结点点。(5)(5)一一棵棵二二叉叉树树第第6 6层层上上的的结结点点数数最最多多为为( ( ) )个个。40140119193232第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法二二叉叉树树的的遍遍历历：(1)(1)前前序序遍遍历历(DLR)(DLR)，首首先先访访问问根根结结点点，然然后后遍遍历历左左子子树树，最最后后遍遍历历右右子子树树；( (树树根根在在第第一一，下下走走不不跳跳结结点点) )(2)(2)中中序序遍

44、遍历历(LDR)(LDR)，首首先先遍遍历历左左子子树树，然然后后访访问问根根结结点点，最最后后遍遍历历右右子子树树； ( (有有左左先先左左，再再寻寻根根，后后找找右右，最最左左边边的的结结点点最最先先遍遍历历，最最右右边边的的结结点点最最后后遍遍历历) )(3)(3)后后序序遍遍历历(LRD)(LRD)首首先先遍遍历历左左子子树树，然然后后访访问问遍遍历历右右子子树树，最最后后访访问问根根结结点点。( (有有左左先先左左，再再找找右右，后后寻寻根根，到到最最右右一一路路上上行行，树树根根在在最最后后) )第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法第第一一部部

45、分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法已已知知二二叉叉树树的的前前序序遍遍历历为为ABDEFCABDEFC，中中序序遍遍历历为为DBFEACDBFEAC，则则二二叉叉树树的的后后序序遍遍历历结结果果是是：分分析析：前前序序遍遍历历为为ABDEFCABDEFC中中序序遍遍历历为为DBFEACDBFEAC第第一一步步：确确定定A A为为根根结结点点，则则由由中中序序遍遍历历( (DBFEDBFEA AC C) )可可以以知知道道DBFEDBFE为为A A的的左左子子树树部部分分，C C为为A A的的右右子子树树部部分分。第第一一部部分分 数数数数据据据据结结结结构构构构与与

46、与与算算算算法法法法第第二二步步：对对于于中中序序中中的的DBFEDBFE，在在前前序序中中的的结结果果为为BDEFBDEF，所所以以可可以以得得出出这这四四个个结结点点中中B B为为“小小根根”结结点点，即即B B直直接接和和A A相相连连，接接着着在在中中序序中中( (D DB BFEFE) )可可以以知知道道D D在在B B的的左左边边，FEFE在在B B的的右右面面。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法第第三三步步：对对于于中中序序中中的的FEFE，在在前前序序中中为为EFEF，则则可可以以知知道道E E直直接接和和B B相相连连，在在中中序序中中

47、，F F在在E E的的左左面面，即即可可以以得得出出二二叉叉树树图图形形。第第四四步步：根根据据二二叉叉树树图图形形写写出出后后序序遍遍历历为为DFEBCADFEBCA。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法例例题题(1) (1) 对对于于如如图图的的二二叉叉树树，进进行行后后序序遍遍历历的的结结果果为为( ( ) ) A)ABCDEF A)ABCDEF B)DBEAFC B)DBEAFC C)ABDECF C)ABDECF D)DEBFCA D)DEBFCA第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(2)(2)在在深深度度为

48、为7 7的的满满二二叉叉树树中中，叶叶子子结结点点的的个个数数为为( )( )。 A)32 A)32 B)31 B)31 C)64 C)64 D)63 D)63第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(3)(3)某某二二叉叉树树有有5 5个个度度为为2 2的的结结点点以以及及3 3个个度度为为1 1的的结结点点，则则该该二二叉叉树树中中共共有有【 】个个结结点点。(4)(4)一一棵棵二二叉叉树树中中共共有有7070个个叶叶子子结结点点与与8080个个度度为为1 1的的结结点点，则则该该二二叉叉树树中中的的总总结结点点数数为为( )( )A)219 A)219

49、B)221 B)221 C)229 C)229 D)231D)2311414第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(5) (5) 设设一一棵棵二二叉叉树树的的中中序序遍遍历历为为DBEAFC,DBEAFC,前前序序遍遍历历为为ABDECFABDECF，则则后后序序遍遍历历结结果果为为( ( ) )(6) (6) 设设树树T T的的度度为为4 4，其其中中度度为为1 1，2 2，3 3，4 4的的结结点点个个数数分分别别为为4 4，2 2，1 1，1 1。则则T T的的叶叶子子结结点点数数为为( ( ) ) A) 8 A) 8 B) 7 B) 7 C) 6 C

50、) 6 D) 5 D) 5 DEBFCADEBFCA分分析析：由由e e( (边边数数) )=n=n( (总总结结点点数数) )-1-1入入手手，假假设设n n0 0、n n1 1、n n2 2、n n3 3、n n4 4分分别别为为度度是是0 0、1 1、2 2、3 3、4 4结结点点的的个个数数。那那么么，e = 4*ne = 4*n1 1+3*n+3*n2 2+2*n+2*n3 3+1*n+1*n4 4 = 4*1+3*1+2*2+1*4 = 4*1+3*1+2*2+1*4 = 15 = 15所所以以， n n总总 = 16= 16马马上上可可以以得得到到 n n0 0 = n= n总总