计算机基础课件ppt-计算机软件.pdf

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

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

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

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

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

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

8、一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法9数据结构类型 1数数据据的的逻逻辑辑结结构构 2、数数据据的的存存储储结结构构 3、数数据据的的运运算算：检检索索、排排序序、插插入入、删删除除、修修改改等等。A线线性性结结构构 B非非线线性性结结构构A 顺顺序序存存储储 B 链链式式存存储储 线线性性表表栈栈队队树树形形结结构构图图形形结结构构数数据据结结构构的的三三个个方方面面 10数数据据的的逻逻辑辑结结构构线线性性结结构构(顺顺序序表表、链链表表、队队列列、堆堆栈栈)非非线线性性结结构构(树树、图图)数数据据的的逻逻辑辑结结构构是是反反映映数数据据元元素素之之间间

9、逻逻辑辑关关系系的的数数据据结结构构(与与所所使使用用的的计计算算机机无无关关)。数数据据的的逻逻辑辑结结构构包包含含：(1 1)表表示示数数据据元元素素的的信信息息；(2 2)表表示示各各数数据据元元素素之之间间的的前前后后件件关关系系。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法线线性性结结构构：必必须须满满足足以以下下两两个个条条件件(1)有有且且只只有有一一个个根根结结点点,(2)每每个个结结点点最最多多有有一一个个前前件件,也也最最多多有有一一个个后后件件。线线性性结结构构也也称称线线性性表表。图图1-11-1线线性性结结构构第第一一部部分分 数数数数据

10、据据据结结结结构构构构与与与与算算算算法法法法12线性结构和非线性结构 线线性性结结构构条条件件（1 1）有有且且只只有有一一个个根根结结点点；（2 2）每每一一个个结结点点最最多多有有一一个个前前件件，也也最最多多有有一一个个后后件件。（3 3）首首节节点点无无前前件件，尾尾节节点点无无后后件件。非非线线性性结结构构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学学学学 生生生生 成成成成 绩绩绩绩 表表表表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号13图图1-1线线性性结结构构如

11、如果果一一个个结结构构不不是是线线性性结结构构,则则称称为为非非线线性性结结构构。如如图图1-2、图图1-3图图1-21-2非非线线性性结结构构中中的的“树树”形形结结构构图图1-31-3非非线线性性结结构构中中的的“图图”形形结结构构第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法14树形结构全全全全校校校校学学学学生生生生档档档档案案案案管管管管理理理理的的的的树树树树形形形形结结结结构构构构的的的的组组组组织织织织方方方方式式式式非非线线性性结结构构 树树形形结结构构15树形结构树树树树形形形形结结结结构构构构 结结结结点点点点间间间间具具具具有有有有分分分分层

12、层层层次次次次的的的的连连连连接接接接关关关关系系系系HBCDEFGA16图形结构 图图形形结结构构：节节点点间间的的连连接接任任意意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)有有向向图图存存储储结结构构：也也称称数数据据的的物物理理结结构构,是是指指数数据据的的逻逻辑辑结结构构在在计计算算机机存存储储空空间间中中的的存存放放形形式式。其其形形式式包包括括顺顺序序、链链接接、索索引引等等。顺顺顺顺序序序序存存存存储储储储：逻逻辑辑上上相相邻邻的的结结

13、点点存存储储在在物物理理位位置置相相邻邻的的存存储储单单元元里里，结结点点间间的的逻逻辑辑关关系系由由存存储储单单元元的的邻邻接接关关系系(位位置置)来来体体现现 链链链链式式式式存存存存储储储储：不不要要求求逻逻辑辑上上相相邻邻的的结结点点在在物物理理位位置置上上亦亦相相邻邻，结结点点间间的的逻逻辑辑关关系系是是由由附附加加的的指指针针字字段段表表示示的的第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法18顺序存储与链式存储Lo+（n-1)*m元素n.元素i.元素2元素1LoLo+mLo+(i-1)*m存存储储地地址址存存储储内内容容Loc(a)=Lo+（i-1)*

14、m每每个个元元素素所所占占用用的的存存储储单单元元个个数数 顺顺序序存存储储常常用用于于线线性性数数据据结结构构，将将逻逻辑辑上上相相邻邻的的数数据据元元素素存存储储在在物物理理上上相相邻邻的的存存储储单单元元里里。三三个个弱弱点点插插入入或或删删除除操操作作时时，需需移移动动大大量量元元数数。长长度度变变化化较较大大时时，需需按按最最大大空空间间分分配配。表表的的容容量量难难以以扩扩充充19顺序存储与链式存储 13461346 元元素素3 3 15361536 .15361536 元元素素2 2 14001400 .元元素素4 4 13461346 14001400 元元素素1 1 1345

15、1345 指指针针 存存储储内内容容存存储储地地址址1536元素21400元素11346元素3 元素4head1345链链链链式式式式存存存存储储储储的的的的地地地地址址址址映映映映射射射射表表表表例例题题(1)(1)数数据据的的存存储储结结构构是是指指()A)A)存存储储在在外外存存中中的的数数据据 B)B)数数据据所所占占的的存存储储空空间间 C)C)数数据据在在计计算算机机中中的的顺顺序序存存储储方方式式 D)D)数数据据的的逻逻辑辑结结构构在在计计算算机机中中的的表表示示(2)(2)以以下下数数据据结结构构中中不不属属于于线线性性数数据据结结构构的的是是()()A)A)队队列列 B)B

16、)线线性性表表 C)C)二二叉叉树树 D)D)栈栈第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法21(3)(3)下下列列叙叙述述中中正正确确的的是是()A)A)一一个个逻逻辑辑数数据据结结构构只只能能有有一一种种存存储储结结构构 B)B)数数据据的的逻逻辑辑结结构构属属于于线线性性结结构构，存存储储结结构构属属于于非非线线性性结结构构 C)C)一一个个逻逻辑辑结结构构可可以以有有多多种种存存储储结结构构，且且各各种种存存储储结结构构不不影影响响数数据据处处理理的的效效率率 D)D)一一个个逻逻辑辑结结构构可可以以有有多多种种存存储储结结构构，且且各各种种存存储储结结

17、构构影影响响数数据据处处理理的的效效率率第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.3 1.3 线线性性表表及及其其顺顺序序存存储储结结构构1 1、线线性性表表的的基基本本概概念念：线线性性表表是是一一种种最最简简单单,最最常常用用的的一一种种数数据据结结构构。它它由由一一组组数数据据元元素素构构成成。2 2、线线性性表表的的顺顺序序存存储储结结构构：(两两个个特特点点)(1)(1)线线性性表表中中所所有有元元素素所所占占的的存存储储空空间间是是连连续续的的 (2)(2)线线性性表表中中各各元元素素在在存存储储空空间间中中是是按按逻逻辑辑顺顺序序依依次次存存放

18、放的的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、线线性性表表的的顺顺序序存存储储基基本本操操作作：插插入入，删删除除，查查找找第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.4 1.4 线线性性链链表表 概概念念：用用一一组组任任意意的的存存储储单单元元来来依依次次存存放放线线性性表表的的各各结结点点。这这组组存存储储单单元元既既可

19、可以以是是连连续续的的，也也可可以以是是不不连连续续的的，甚甚至至是是零零散散分分布布在在内内存存中中的的任任意意位位置置上上的的。因因此此，链链表表中中结结点点的的逻逻辑辑次次序序和和物物理理次次序序不不一一定定相相同同。线线性性链链表表的的基基本本运运算算：插插入入、删删除除、查查找找第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法 线线性性链链表表的的结结点点由由两两部部分分组组成成：(1)(1)用用于于存存储储数数据据元元素素值值，称称为为数数据据域域；(2)(2)用用于于存存放放指指针针，称称为为指指针针域域，用用于于指指向向前前一一个个或或后后一一个个结结

20、点点。在在链链式式存存储储结结构构中中，存存储储数数据据结结构构的的空空间间可可以以不不连连续续，各各数数据据结结点点的的存存储储顺顺序序与与数数据据元元素素之之间间的的逻逻辑辑关关系系可可以以不不一一致致，而而数数据据元元素素之之间间的的逻逻辑辑关关系系是是由由指指针针域域来来确确定定的的。所所以以，链链式式存存储储方方式式即即可可用用于于表表示示线线性性结结构构，也也可可用用于于表表示示非非线线性性结结构构。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法几几种种常常见见的的链链表表：(1)(1)单单向向链链表表，HEADHEAD称称为为头头指指针针，HEAD=N

21、ULL(HEAD=NULL(或或0)0)称称为为空空表表；数数据据域域指指针针域域head第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(2)(2)双双向向链链表表：左左指指针针(LlinkLlink)指指向向前前件件结结点点，右右指指针针(RlinkRlink)指指向向后后件件结结点点。(3)(3)循循环环链链表表：线线性性表表的的顺顺序序存存储储结结构构称称为为顺顺序序表表线线性性表表的的链链式式存存储储结结构构称称为为线线性性链链表表二二者者的的比比较较：1)1)顺顺序序表表存存储储数数据据时时在在逻逻辑辑上上相相连连的的在在物物理理上上也也一一定定相相连连。

22、2)2)链链表表存存储储数数据据时时在在逻逻辑辑上上相相连连的的在在物物理理上上不不一一定定相相连连。3)3)顺顺序序表表插插入入和和删删除除比比较较麻麻烦烦，但但是是访访问问每每一一个个结结点点比比较较简简单单4)4)链链表表插插入入和和删删除除比比较较简简单单，但但是是访访问问每每一一个个结结点点比比较较麻麻烦烦第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.5 1.5 栈栈和和队队列列 栈栈：也也叫叫堆堆栈栈，是是指指限限定定在在一一端端进进行行插插入入与与删删除除的的线线性性表表。允允许许插插入入与与删删除除的的一一端端称称为为栈栈顶顶；不不允允许许插插入

23、入与与删删除除的的另另一一端端称称为为栈栈底底。栈栈按按照照“先先进进后后出出”(FILO)(FILO)或或“后后进进先先出出”(LIFO)(LIFO)组组织织数数据据，栈栈具具有有记记忆忆作作用用。栈栈的的基基本本运运算算：(1)(1)插插入入元元素素：也也称称为为入入栈栈运运算算 (2)(2)删删除除元元素素：也也称称为为退退栈栈运运算算 (3)(3)读读栈栈顶顶元元素素：将将栈栈顶顶元元素素赋赋给给一一个个指指定定的的变变量量 (此此时时指指针针无无变变化化)第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法 队队列列：允允许许在在一一端端(队队尾尾)进进入入插插

24、入入，而而在在另另一一端端(队队头头)进进行行删删除除的的线线性性表表。队队列列按按照照“先先进进先先出出”(FIFO)(FIFO)或或“后后进进后后出出”(LILO)(LILO)组组织织数数据据。队队列列基基本本运运算算：(1)(1)入入队队运运算算：从从队队尾尾插插入入一一个个元元素素；(2)(2)退退队队运运算算：从从队队头头删删除除一一个个元元素素。循循环环队队列列：是是将将队队列列的的存存储储空空间间的的最最后后一一个个位位置置绕绕到到第第一一个个位位置置，形形成成逻逻辑辑上上的的形形状状空空间间，供供队队列列循循环环使使用用，其其实实质质还还是是顺顺序序存存储储结结构构。第第一一部

25、部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法例例题题(1)(1)下下列列关关于于栈栈叙叙述述正正确确的的是是()A)A)在在栈栈中中只只能能插插入入数数据据 B)B)在在栈栈中中只只能能删删除除数数据据 C)C)栈栈是是先先进进先先出出的的线线性性表表 D)D)栈栈是是先先进进后后出出的的线线性性表表(2)(2)下下列列关关于于队队列列的的叙叙述述中中正正确确的的是是()A)A)在在队队列列中中只只能能插插入入数数据据 B)B)在在队队列列中中只只能能删删除除数数据据 C)C)队队列列是是先先进进先先出出的的线线性性表表 D)D)队队列列是是先先进进后后出出的的线线性性表表

26、第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法30(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第第一一部

27、部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(5)(5)在在一一个个容容量量为为1515的的循循环环队队列列中中，若若队队头头front=6,front=6,队队尾尾rear=9rear=9，则则该该循循环环队队列列中中有有()()个个元元素素。答答案案：3 3分分析析：如如图图1-81-8与与图图1-91-9的的两两种种循循环环队队列列存存放放数数据据的的形形式式第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法在在非非空空队队列列中中，头头指指针针始始终终指指向向队队头头元元素素前前一一个个位位置置，而而尾尾指指针针始始终终指指向向队队尾尾元元素

28、素的的位位置置由由此此可可以以得得出出元元素素的的个个数数为为：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第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法33计计算算循循环环队队列列长长

29、度度：front=rear，队队列列长长度度0；frontrear，队队列列长长度度rear+size-front34(6)(6)(6)(6)下下下下列列列列叙叙叙叙述述述述中中中中正正正正确确确确的的的的是是是是()()()()。A)A)A)A)栈栈栈栈是是是是先先先先进进进进先先先先出出出出的的的的线线线线性性性性表表表表 B)B)B)B)队队队队列列列列是是是是 先先先先进进进进后后后后出出出出 的的的的线线线线性性性性表表表表C)C)C)C)循循循循环环环环队队队队列列列列是是是是非非非非线线线线性性性性结结结结构构构构D)D)D)D)有有有有序序序序线线线线性性性性表表表表即即即即可

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

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

32、链式式存存储储结结构构不不能能存存储储有有序序表表D)D)链链式式存存储储结结构构比比顺顺序序存存储储结结构构节节省省存存储储空空间间第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法36(9)(9)数数据据的的存存储储结结构构是是指指()()。A)A)存存储储在在外外存存中中的的数数据据 B)B)数数据据所所占占的的存存储储空空间间量量C)C)数数据据在在计计算算机机中中的的顺顺序序存存储储方方式式 D)D)数数据据的的逻逻辑辑结结构构在在计计算算机机中中的的表表示示(10)(10)下下列列对对于于线线性性链链表表的的描描述述中中正正确确的的是是()()A)A)存存储

33、储空空间间不不一一定定是是连连续续,且且各各元元素素的的存存储储顺顺序序是是任任意意的的B)B)存存储储空空间间不不一一定定是是连连续续,且且前前件件元元素素一一定定存存储储在在后后件件元元素素的的前前面面C)C)存存储储空空间间必必须须连连续续,且且前前件件元元素素一一定定存存储储在在后后件件元元素素的的前前面面D)D)存存储储空空间间必必须须连连续续,且且各各元元素素的的存存储储顺顺序序是是任任意意的的 第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法37(11)(11)下下列列数数据据结结构构中中,能能够够按按照照“先先进进后后出出”原原则则存存取取数数据据的的

34、是是()()。A)A)循循环环队队列列 B)B)栈栈 C)C)队队列列 D)D)二二叉叉树树(12)(12)对对于于循循环环队队列列，下下列列叙叙述述中中正正确确的的是是()()。A)A)队队头头指指针针是是固固定定不不变变的的 B)B)队队头头指指针针一一定定大大于于队队尾尾指指针针C)C)队队头头指指针针一一定定小小于于队队尾尾指指针针 D)D)队队头头指指针针可可以以大大于于队队尾尾指指针针,也也可可以以小小于于队队尾尾指指针针第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法38(13)(13)假假设设用用一一个个长长度度为为5050的的数数组组(数数组组元元素

35、素的的下下标标从从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第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法39(15)(15)一一个个栈栈的的初初始

36、始状状态态为为空空。现现将将元元素素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第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法40(16)(16)下下列列叙叙述述中中正正确确的的是是()()。A)A)循循环环队队列列有有队队头头和和队队尾尾

37、两两个个指指针针，因因此此，循循环环队队列列是是非非线线性性结结构构B)B)在在循循环环队队列列中中，只只需需要要队队头头指指针针就就能能反反映映队队列列中中元元素素的的动动态态变变化化情情况况C)C)在在循循环环队队列列中中，只只需需要要队队尾尾指指针针就就能能反反映映队队列列中中元元素素的的动动态态变变化化情情况况D)D)循循环环队队列列中中元元素素的的个个数数是是由由队队头头指指针针和和队队尾尾指指针针共共同同决决定定第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法41(17)(17)下下列列关关于于栈栈的的叙叙述述正正确确的的是是()()。A)A)栈栈按按“先

38、先进进先先出出”组组织织数数据据 B)B)栈栈按按“先先进进后后出出”组组织织数数据据C)C)只只能能在在栈栈底底插插入入数数据据 D)D)不不能能删删除除数数据据(18)(18)设设某某循循环环队队列列的的容容量量为为5050，头头指指针针front=5(front=5(指指向向队队头头元元素素的的前前一一位位置置)，尾尾指指针针rear=29(rear=29(指指向向队队尾尾元元素素)，则则该该循循环环队队列列中中共共有有【】个个元元素素。(19)(19)线线性性表表的的存存储储结结构构主主要要分分为为顺顺序序存存储储结结构构和和链链式式存存储储结结构构。队队列列是是一一种种特特殊殊的的线

39、线性性表表，循循环环队队列列是是队队列列的的【】存存储储结结构构。2424顺顺序序第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法42(20)(20)下下列列对对队队列列的的叙叙述述正正确确的的是是()()。A)A)队队列列属属于于非非线线性性表表 B)B)队队列列按按“先先进进后后出出”原原则则组组织织数数据据C)C)队队列列在在队队尾尾删删除除数数据据 D)D)队队列列按按“先先进进先先出出”原原则则组组织织数数据据(21)(21)数数据据结结构构分分为为线线性性结结构构和和非非线线性性结结构构，带带链链的的队队列列属属于于 【】。(23)(23)按按照照“后后进

40、进先先出出”原原则则组组织织数数据据的的数数据据结结构构是是()()。A)A)队队列列 B)B)栈栈 C)C)双双向向链链表表 D)D)二二叉叉树树线线性性结结构构第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法1.6 1.6 树树与与二二叉叉树树 1.1.概概念念：树树是是一一种种简简单单的的非非线线性性结结构构，所所有有元元素素之之间间具具有有明明显显的的层层次次特特性性。在在树树结结构构中中，每每一一个个结结点点只只有有一一个个前前件件，称称为为父父结结点点，没没有有前前件件的的结结点点只只有有一一个个，称称为为树树的的根根结结点点，简简称称树树的的根根。每每一

41、一个个结结点点可可以以有有多多个个后后件件，称称为为该该结结点点的的子子结结点点。没没有有后后件件的的结结点点称称为为叶叶子子结结点点。在在树树结结构构中中，一一个个结结点点所所拥拥有有的的后后件件的的个个数数称称为为该该结结点点的的度度，所所有有结结点点中中最最大大的的度度称称为为树树的的度度。树树的的最最大大层层次次称称为为树树的的深深度度。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法 2.2.二二叉叉树树(度度为为2 2的的树树)特特点点：(1)(1)非非空空二二叉叉树树只只有有一一个个根根结结点点；(2)(2)每每一一个个结结点点最最多多有有两两棵棵子子树

42、树，且且分分别别称称为为该该结结点点的的左左子子树树与与右右子子树树。第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法二二叉叉树树的的性性质质：(1)(1)在在二二叉叉树树的的第第k k层层上上，最最多多有有2 2k-1k-1个个结结点点，如如图图1-111-11图图1-11 1-11 性性质质1 1的的理理解解第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法(2)(2)深深度度为为h h的的二二叉叉树树最最多多有有2 2h h-1-1个个结结点点，如如图图1-121-12图图1-12 1-12 性性质质2 2的的理理解解第第一一部部分分 数

43、数数数据据据据结结结结构构构构与与与与算算算算法法法法(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第第一一部部分分 数数数数据据据据结结结结构构构

44、构与与与与算算算算法法法法3 3.满满二二叉叉树树：除除最最后后一一层层外外，每每一一层层上上的的所所有有结结点点都都有有两两个个子子结结点点。4 4.完完全全二二叉叉树树：若若设设二二叉叉树树的的高高度度为为h h，除除第第 h h 层层外外，其其它它各各层层 (1(1h-1)h-1)的的结结点点数数都都达达到到最最大大个个数数，第第 h h 层层所所有有的的节节点点都都连连续续集集中中在在最最左左边边，这这就就是是完完全全二二叉叉树树。完完全全二二叉叉树树是是由由满满二二叉叉树树而而引引出出来来的的。对对于于深深度度为为K K的的，有有N N个个结结点点的的二二叉叉树树，当当且且仅仅当当其

45、其每每一一个个结结点点都都与与深深度度为为K K的的满满二二叉叉树树中中编编号号从从1 1至至N N的的结结点点一一一一对对应应时时称称之之为为完完全全二二叉叉树树。完完全全二二叉叉树树中中，度度为为1 1的的结结点点最最多多只只有有1 1个个 完完全全二二叉叉树树左左右右子子树树的的深深度度之之差差不不大大于于1 1第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法49满二叉树423167891011121314155 特特点点：所所有有分分支支结结点点都都存存在在左左右右子子树树，且且所所有有叶叶子子结结点点都都在在同同一一层层上上。50完全二叉树423167891

46、0 11125 非非完完全全二二叉叉树树4231678910 11125 完完全全二二叉叉树树 特特点点：除除最最后后一一层层外外，每每一一层层都都取取最最大大结结点点数数，最最后后一一层层结结点点都都集集中中在在该该层层最最左左边边的的若若干干位位置置。51二叉树的基本性质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个个度度为

47、为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=4例例题题(1

48、)(1)在在深深度度为为5 5的的满满二二叉叉树树中中，叶叶子子结结点点个个数数为为()A)32 A)32 B)21 B)21 C)16 C)16 D)15 D)15第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法53(2)(2)设设一一棵棵完完全全二二叉叉树树上上有有700700个个结结点点，则则二二叉叉树树中中有有()个个叶叶子子结结点点。根根据据二二叉叉树树的的性性质质:对对于于一一棵棵非非空空的的二二叉叉树树,如如果果叶叶子子节节点点数数为为n0,度度为为2的的结结点点数数为为n2,则则no=n2+1.根根据据完完全全二二叉叉树树的的定定义义可可得得:在在完完

49、全全二二叉叉树树中中度度为为1的的结结点点n1只只能能取取两两种种情情况况,要要么么为为0,要要么么为为1.所所以以:n0+n1+n2=700 n0=n2+1;2n0=701-n1;因因为为结结点点数数为为整整数数，所所以以n1=1,no=350 35035054(3)(3)设设一一棵棵完完全全二二叉叉树树上上有有801801个个结结点点，则则二二叉叉树树中中有有()个个叶叶子子结结点点。?(4)(4)某某二二叉叉树树中中，度度为为2 2的的结结点点有有1818个个，则则该该二二叉叉树树中中有有()个个叶叶子子结结点点。?(5)(5)一一棵棵二二叉叉树树第第6 6层层上上的的结结点点数数最最多

50、多为为()个个。40140119193232第第一一部部分分 数数数数据据据据结结结结构构构构与与与与算算算算法法法法二二叉叉树树的的遍遍历历：(1)(1)前前序序遍遍历历(DLR)(DLR)，首首先先访访问问根根结结点点，然然后后遍遍历历左左子子树树，最最后后遍遍历历右右子子树树；(树树根根在在第第一一，下下走走不不跳跳结结点点)(2)(2)中中序序遍遍历历(LDR)(LDR)，首首先先遍遍历历左左子子树树，然然后后访访问问根根结结点点，最最后后遍遍历历右右子子树树；(有有左左先先左左，再再寻寻根根，后后找找右右，最最左左边边的的结结点点最最先先遍遍历历，最最右右边边的的结结点点最最后后遍遍