《计算机基础课件ppt-计算机公共基础基础.ppt》由会员分享，可在线阅读，更多相关《计算机基础课件ppt-计算机公共基础基础.ppt（128页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)A)执行算法程序所需要的时间执行算法程序所需要的时间B)B)算法程序的长度算法程序的长度 C)C)算法执行过程中所需
4、要的基本运算次数算法执行过程中所需要的基本运算次数D)D)算法程序中的指令条数算法程序中的指令条数(2)(2)算法的空间复杂度是指算法的空间复杂度是指()A)A)算法程序的长度算法程序的长度B)B)算法程序中的指令条数算法程序中的指令条数C)C)算法程序所占的存储空间算法程序所占的存储空间D)D)算法执行过程中所需要的存储空间算法执行过程中所需要的存储空间第一部分第一部分 数据结构与算法数据结构与算法(3)(3)下列叙述中正确的是下列叙述中正确的是()()。A)A)算法的效率只与问题的规模有关，而与数据的存储结构无关算法的效率只与问题的规模有关，而与数据的存储结构无关B)B)算法的时间复杂度是
5、指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量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)确定性确定性算法算法空间空间第一部分第一部分 数据结构与算法数据结构与算法1.2 1.2 数据结构的基本概念数据结构的基本概念1 1、数据结构是计算机科学与技术领域广泛使用的一个数据结构是计算机科学与技术领域广泛使用的一
7、个基本术语，用来反映数据的内部构成。基本术语，用来反映数据的内部构成。数据结构研究的三个方面：数据结构研究的三个方面：(1)(1)数据集合中各数据元素之间所固有的逻辑关系数据集合中各数据元素之间所固有的逻辑关系,即数即数据的据的逻辑结构逻辑结构(2)(2)在对数据进行处理时在对数据进行处理时,各元素在计算机中的存储关系各元素在计算机中的存储关系,即数据的即数据的存储结构存储结构(物理结构物理结构)(3)(3)对各种数据结构进行的运算对各种数据结构进行的运算第一部分第一部分 数据结构与算法数据结构与算法数据的逻辑结构数据的逻辑结构线性结构线性结构(顺序表、链表、队列、堆栈顺序表、链表、队列、堆栈
8、)非线性结构非线性结构(树、图树、图)数据的逻辑结构是数据的逻辑结构是反映数据元素之间逻辑关系的数反映数据元素之间逻辑关系的数据结构据结构(与所使用的计算机无关与所使用的计算机无关)。数据的逻辑结构。数据的逻辑结构包含：包含：(1 1)表示数据元素的信息；表示数据元素的信息；(2 2)表示各数据元素之间的前后件关系。表示各数据元素之间的前后件关系。第一部分第一部分 数据结构与算法数据结构与算法线性结构：必须满足以下两个条件线性结构：必须满足以下两个条件(1)(1)有且只有一个根结点有且只有一个根结点,(2)(2)每个结点最多有一个前件每个结点最多有一个前件,也最多有一个后件。也最多有一个后件。
9、线性结构也称线性表。线性结构也称线性表。图图1-11-1线性结构线性结构第一部分第一部分 数据结构与算法数据结构与算法图图1-11-1线性结构线性结构如果一个结构不是线性结构如果一个结构不是线性结构,则称为非线性结构。则称为非线性结构。如图如图1-21-2、图、图1-31-3图图1-21-2非线性结构中的非线性结构中的“树树”形结构形结构图图1-31-3非线性结构中的非线性结构中的“图图”形结构形结构第一部分第一部分 数据结构与算法数据结构与算法存储结构存储结构：也称数据的物理结构也称数据的物理结构,是指数据的逻辑结构是指数据的逻辑结构在计算机存储空间中的存放形式。在计算机存储空间中的存放形式
10、。其形式包括顺序、其形式包括顺序、链接、索引等。链接、索引等。顺序存储：顺序存储：顺序存储：顺序存储：逻辑上相邻的结点存储在物理位置相邻的存储单逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系元里，结点间的逻辑关系由存储单元的邻接关系(位置位置)来体来体现现 链式存储：链式存储：链式存储：链式存储：不要求逻辑上相邻的结点在物理位置上亦相邻，不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的结点间的逻辑关系是由附加的指针字段表示的第一部分第一部分 数据结构与算法数据结构与算法例题例题(1)(1)数据的存储结构是指数据的存储结构是
11、指()A)A)存储在外存中的数据存储在外存中的数据 B)B)数据所占的存储空间数据所占的存储空间 C)C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示(2)(2)以下数据结构中不属于线性数据结构的是以下数据结构中不属于线性数据结构的是()()A)A)队列队列 B)B)线性表线性表 C)C)二叉树二叉树 D)D)栈栈第一部分第一部分 数据结构与算法数据结构与算法(3)(3)下列叙述中正确的是下列叙述中正确的是()A)A)一个逻辑数据结构只能有一种存储结构一个逻辑数据结构只能有一种存储结构 B)B)数据的逻辑结构属于
12、线性结构，存储结构属于非线性结构数据的逻辑结构属于线性结构，存储结构属于非线性结构 C)C)一个逻辑结构可以有多种存储结构，且各种存储结构不影响一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率数据处理的效率 D)D)一个逻辑结构可以有多种存储结构，且各种存储结构影响数一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率据处理的效率第一部分第一部分 数据结构与算法数据结构与算法1.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构1 1、线性表的基本概念：线性表是一种最简单线性表的基本概念：线性表是一种最简单,最常用的一种数据最常用的一种数据结构。它由一组数据
13、元素构成。结构。它由一组数据元素构成。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、线线性表
14、的顺序存储基本操作：性表的顺序存储基本操作：插入，删除，查找插入，删除，查找第一部分第一部分 数据结构与算法数据结构与算法1.4 1.4 线性链表线性链表 概念：用一组任意的存储单元来依次存放线性表的各结点。概念：用一组任意的存储单元来依次存放线性表的各结点。这组存储单元既可以是连续的，也可以是不连续的，甚至是这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，零散分布在内存中的任意位置上的。因此，链表中结点的逻链表中结点的逻辑次序和物理次序不一定相同辑次序和物理次序不一定相同。线性链表的基本运算：插入、删除、查找线性链表的基本运算：插入、删除、查找第一部
15、分第一部分 数据结构与算法数据结构与算法 线性链表的结点由两部分组成：线性链表的结点由两部分组成：(1)(1)用于存储数据元素值，称为用于存储数据元素值，称为数据域数据域；(2)(2)用于存放指针，称为用于存放指针，称为指针域指针域，用于指向前一个或后，用于指向前一个或后一个结点。一个结点。在链式存储结构中，存储数据结构的空间可以不连续，各数据在链式存储结构中，存储数据结构的空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。所以，据元素之间的逻辑关系是由指针域来确定的。所以，
16、链式存储链式存储方式即可用于表示线性结构，也可用于表示非线性结构。方式即可用于表示线性结构，也可用于表示非线性结构。第一部分第一部分 数据结构与算法数据结构与算法几种常见的链表：几种常见的链表：(1)(1)单向链表，单向链表，HEADHEAD称为头指针，称为头指针，HEAD=NULL(HEAD=NULL(或或0)0)称为空表；称为空表；数据数据域域指针指针域域head第一部分第一部分 数据结构与算法数据结构与算法(2)(2)双向链表：左指针双向链表：左指针(LlinkLlink)指向前件结点，右指针指向前件结点，右指针(RlinkRlink)指向后件结点。指向后件结点。(3)(3)循环链表：循
17、环链表：线性表的顺序存储结构称为线性表的顺序存储结构称为顺序顺序表表线性表的链式存储结构称为线性链表线性表的链式存储结构称为线性链表二者的比较：二者的比较：1)1)顺顺序表存储数据时在逻辑上相连的在物理上也一定相连。序表存储数据时在逻辑上相连的在物理上也一定相连。2)2)链表存储数据时在逻辑上相连的在物理上不一定相连。链表存储数据时在逻辑上相连的在物理上不一定相连。3)3)顺序表插入和删除比较麻烦，但是访问每一个结点比较简单顺序表插入和删除比较麻烦，但是访问每一个结点比较简单4)4)链表插入和删除比较简单，但是访问每一个结点比较麻烦链表插入和删除比较简单，但是访问每一个结点比较麻烦第一部分第一
18、部分 数据结构与算法数据结构与算法1.5 1.5 栈和队列栈和队列 栈：也叫堆栈，是指限定在一端进行插入与删除的线性表。允许栈：也叫堆栈，是指限定在一端进行插入与删除的线性表。允许插入与删除的一端称为插入与删除的一端称为栈顶栈顶；不允许插入与删除的另一端称为；不允许插入与删除的另一端称为栈栈底底。栈按照。栈按照“先进后出先进后出”(FILO)(FILO)或或“后进先出后进先出”(LIFO)(LIFO)组织数据组织数据，栈具有记忆作用。，栈具有记忆作用。栈的基本运算：栈的基本运算：(1)(1)插入元素：也称为入栈运算插入元素：也称为入栈运算 (2)(2)删除元素：也称为退栈运算删除元素：也称为退
19、栈运算 (3)(3)读栈顶元素：将栈顶元素赋给一个指定的变量读栈顶元素：将栈顶元素赋给一个指定的变量 (此时指针无变化此时指针无变化)第一部分第一部分 数据结构与算法数据结构与算法 队列：允许在一端队列：允许在一端(队尾队尾)进入插入，而在另一端进入插入，而在另一端(队头队头)进行删进行删除的线性表。队列按照除的线性表。队列按照“先进先出先进先出”(FIFO)(FIFO)或或“后进后出后进后出”(LI(LILO)LO)组织数据。组织数据。队列基本运算：队列基本运算：(1)(1)入队运算：从队尾插入一个元素；入队运算：从队尾插入一个元素；(2)(2)退队运算：从队头删除一个元素。退队运算：从队头
20、删除一个元素。循环队列：是将队列的存储空间的最后一个位置绕到第一个位循环队列：是将队列的存储空间的最后一个位置绕到第一个位置，形成逻辑上的形状空间，供队列循环使用置，形成逻辑上的形状空间，供队列循环使用，其实质还是顺其实质还是顺序存储结构序存储结构。第一部分第一部分 数据结构与算法数据结构与算法例题例题(1)(1)下列关于栈叙述正确的是下列关于栈叙述正确的是()A)A)在栈中只能插入数据在栈中只能插入数据 B)B)在栈中只能删除数据在栈中只能删除数据 C)C)栈是先进先出的线性表栈是先进先出的线性表 D)D)栈是先进后出的线性表栈是先进后出的线性表(2)(2)下列关于队列的叙述中正确的是下列关
21、于队列的叙述中正确的是()A)A)在队列中只能插入数据在队列中只能插入数据 B)B)在队列中只能删除数据在队列中只能删除数据 C)C)队列是先进先出的线性表队列是先进先出的线性表 D)D)队列是先进后出的线性表队列是先进后出的线性表第一部分第一部分 数据结构与算法数据结构与算法(3)(3)栈和队列的共同特点是栈和队列的共同特点是()A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点没有共同点(4)(4)设输入序列为设输入序列为1 1、2 2、3 3、4 4，则借助一个栈可以得到的输出序，则借助
22、一个栈可以得到的输出序列是列是()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，则该循环队列中有则该循环队列中有()()个元素。个元素。答案：答案：3 3分析：如图分析：如图1-81-8与图与图1-91-9的两种循环队列存放数据的形式的两种循环队列存放数据的形式第一部分第一部分 数据结构与算
23、法数据结构与算法由此可以得出元素的个数为：由此可以得出元素的个数为：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第一部分第一部分 数据结构与算法数据结构与算法(6)(6)(6)(6)下列叙述中正确的是下列叙
24、述中正确的是下列叙述中正确的是下列叙述中正确的是()()()()。A)A)A)A)栈是先进先出的线性表栈是先进先出的线性表栈是先进先出的线性表栈是先进先出的线性表 B)B)B)B)队列是队列是队列是队列是 先进后出先进后出先进后出先进后出 的线性表的线性表的线性表的线性表C)C)C)C)循环队列是非线性结构循环队列是非线性结构循环队列是非线性结构循环队列是非线性结构D)D)D)D)有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构有序线性表即可以采用顺序存储结构,也可以采用链式存储也可以采用链式存储也可以采用链式存储也可以采用链式存储结构结构结构结
25、构(7)(7)(7)(7)下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是下列叙述中正确的是()()()()。A)A)A)A)线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构线性链表是线性表的链式存储结构 B)B)B)B)栈与队列是非线性结构栈与队列是非线性结构栈与队列是非线性结构栈与队列是非线性结构C)C)C)C)双向链表是非线性结构双向链表是非线性结构双向链表是非线性结构双向链表是非线性结构 D)D)D)D)只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构只有根结点的二叉树是线性结构 第一部分第一部分 数据
26、结构与算法数据结构与算法(8)(8)下列叙述中正确的是下列叙述中正确的是()()。A)A)顺序存储结构的存储一定是连续的，链式存储结构的存储顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的空间不一定是连续的B)B)顺序存储结构只针对线性结构，链式存储结构只针对非线顺序存储结构只针对线性结构，链式存储结构只针对非线性结构性结构C)C)顺序存储结构能存储有序表，链式存储结构不能存储有序顺序存储结构能存储有序表，链式存储结构不能存储有序表表D)D)链式存储结构比顺序存储结构节省存储空间链式存储结构比顺序存储结构节省存储空间第一部分第一部分 数据结构与算法数据结构与算法(9)(9)
27、数据的存储结构是指数据的存储结构是指()()。A)A)存储在外存中的数据存储在外存中的数据 B)B)数据所占的存储空间量数据所占的存储空间量C)C)数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示(10)(10)下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是()()A)A)存储空间不一定是连续存储空间不一定是连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的B)B)存储空间不一定是连续存储空间不一定是连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面C)C)存储空间必
28、须连续存储空间必须连续,且前件元素一定存储在后件元素的前面且前件元素一定存储在后件元素的前面D)D)存储空间必须连续存储空间必须连续,且各元素的存储顺序是任意的且各元素的存储顺序是任意的 第一部分第一部分 数据结构与算法数据结构与算法(11)(11)下列数据结构中下列数据结构中,能够按照能够按照“先进后出先进后出”原则存取数据的是原则存取数据的是()()。A)A)循环队列循环队列 B)B)栈栈 C)C)队列队列 D)D)二叉树二叉树(12)(12)对于循环队列，下列叙述中正确的是对于循环队列，下列叙述中正确的是()()。A)A)队头指针是固定不变的队头指针是固定不变的 B)B)队头指针一定大于
29、队尾指针队头指针一定大于队尾指针C)C)队头指针一定小于队尾指针队头指针一定小于队尾指针 D)D)队头指针可以大于队尾指针队头指针可以大于队尾指针,也可以小于队尾指针也可以小于队尾指针第一部分第一部分 数据结构与算法数据结构与算法(13)(13)假设用一个长度为假设用一个长度为5050的数组的数组(数组元素的下标从数组元素的下标从0 0到到49)49)作为作为栈的存储空间栈的存储空间,栈底指针栈底指针bottombottom指向栈底元素指向栈底元素,栈顶指针栈顶指针toptop指指向栈顶元素向栈顶元素,如果如果bottom=49,top=30(bottom=49,top=30(数组下标数组下标
30、),),则栈中具有则栈中具有【】个元素。个元素。(14)(14)支持子程序调用的数据结构是支持子程序调用的数据结构是()()。A)A)栈栈 B)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
31、)ABCDE12345 C)ABCDE12345 D)54321EDCBAD)54321EDCBA第一部分第一部分 数据结构与算法数据结构与算法(16)(16)下列叙述中正确的是下列叙述中正确的是()()。A)A)循环队列有队头和队尾两个指针，因此，循环队列是非线循环队列有队头和队尾两个指针，因此，循环队列是非线性结构性结构B)B)在循环队列中，只需要队头指针就能反映队列中元素的动在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况态变化情况C)C)在循环队列中，只需要队尾指针就能反映队列中元素的动在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况态变化情况D)D)循环队列中
32、元素的个数是由队头指针和队尾指针共同决定循环队列中元素的个数是由队头指针和队尾指针共同决定第一部分第一部分 数据结构与算法数据结构与算法(17)(17)下列关于栈的叙述正确的是下列关于栈的叙述正确的是()()。A)A)栈按栈按“先进先出先进先出”组织数据组织数据 B)B)栈按栈按“先进后出先进后出”组织数据组织数据C)C)只能在栈底插入数据只能在栈底插入数据 D)D)不能删除数据不能删除数据(18)(18)设某循环队列的容量为设某循环队列的容量为5050，头指针，头指针front=5(front=5(指向队头元素指向队头元素的前一位置的前一位置)，尾指针，尾指针rear=29(rear=29(
33、指向队尾元素指向队尾元素)，则该循环队，则该循环队列中共有列中共有【】个元素。个元素。(19)(19)线性表的存储结构主要分为顺序存储结构和链式存储结构线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的。队列是一种特殊的线性表，循环队列是队列的【】存储结构存储结构。2424顺序顺序第一部分第一部分 数据结构与算法数据结构与算法(20)(20)下列对队列的叙述正确的是下列对队列的叙述正确的是()()。A)A)队列属于非线性表队列属于非线性表 B)B)队列按队列按“先进后出先进后出”原则组织数据原则组织数据C)C)队列在队尾删除数据队列在队尾删除数据 D)
34、D)队列按队列按“先进先出先进先出”原则组织数据原则组织数据(21)(21)数据结构分为线性结构和非线性结构，带链的队列属于数据结构分为线性结构和非线性结构，带链的队列属于 【】。(23)(23)按照按照“后进先出后进先出”原则组织数据的数据结构是原则组织数据的数据结构是()()。A)A)队列队列 B)B)栈栈 C)C)双向链表双向链表 D)D)二叉树二叉树线性结构线性结构第一部分第一部分 数据结构与算法数据结构与算法1.6 1.6 树与二叉树树与二叉树 1.1.概念：树是一种简单的非线性结构，所有元素之间具有明显概念：树是一种简单的非线性结构，所有元素之间具有明显的层次特性。的层次特性。在树
35、结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点父结点，没有前，没有前件的结点只有一个，称为件的结点只有一个，称为树的根结点，树的根结点，简称树的简称树的根根。每一个结。每一个结点可以有多个后件，称为该结点的点可以有多个后件，称为该结点的子结点子结点。没有后件的结点称。没有后件的结点称为为叶子结点叶子结点。在树结构中，一个结点所拥有的后件的个数称为在树结构中，一个结点所拥有的后件的个数称为该结点的度该结点的度，所有结点中最大的度称为树的度。树的最大层次称为所有结点中最大的度称为树的度。树的最大层次称为树的深度树的深度。第一部分第一部分 数据结构与算法数据结构与
36、算法 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的理解的理解第一部分第一部分 数据结构与算法数据结构与算法(2)(2)深度为深度为h h的二叉树最多有的
37、二叉树最多有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+1n+1(5)(5)假设假设e e为树的边数，为树的边数，n n表示总结点数，则表示总结点数，则任何树任何树的
38、边数一定比的边数一定比总结点数少总结点数少1 1，即，即e=n-1e=n-1第一部分第一部分 数据结构与算法数据结构与算法3 3.满二叉树：满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。除最后一层外，每一层上的所有结点都有两个子结点。4 4.完全二叉树：完全二叉树：若设二叉树的高度为若设二叉树的高度为h h，除第，除第 h h 层外，其它各层层外，其它各层 (1(1h-1)h-1)的结点数都达到最大个数，第的结点数都达到最大个数，第 h h 层所有的节点都连续集中在最左边，这就是完全二叉树。层所有的节点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度
39、为完全二叉树是由满二叉树而引出来的。对于深度为K K的，有的，有N N个个结点的二叉树，当且仅当其每一个结点都与深度为结点的二叉树，当且仅当其每一个结点都与深度为K K的满二叉树的满二叉树中编号从中编号从1 1至至N N的结点一一对应时称之为完全二叉树。的结点一一对应时称之为完全二叉树。完全二叉树中，度为完全二叉树中，度为1 1的结点最多只有的结点最多只有1 1个个 完全二叉树左右子树的深度之差不大于完全二叉树左右子树的深度之差不大于1 1第一部分第一部分 数据结构与算法数据结构与算法例题例题(1)(1)在深度为在深度为5 5的满二叉树中，叶子结点个数为的满二叉树中，叶子结点个数为()A)32
40、 A)32 B)21 B)21 C)16 C)16 D)15 D)15(2)(2)设一棵完全二叉树上有设一棵完全二叉树上有700700个结点，则二叉树中有个结点，则二叉树中有()个叶子结点个叶子结点。350350第一部分第一部分 数据结构与算法数据结构与算法(3)(3)设一棵完全二叉树上有设一棵完全二叉树上有801801个结点，则二叉树中有个结点，则二叉树中有()个叶子结点个叶子结点。(4)(4)某二叉树中，度为某二叉树中，度为2 2的结点有的结点有1818个，则该二叉树中有个，则该二叉树中有()个叶子结点。个叶子结点。(5)(5)一棵二叉树第一棵二叉树第6 6层上的结点数最多为层上的结点数最
41、多为()个。个。40140119193232第一部分第一部分 数据结构与算法数据结构与算法二叉树的遍历：二叉树的遍历：(1)(1)前序遍历前序遍历(DLR)(DLR)，首先访问根结点，然后遍历左子树，最后，首先访问根结点，然后遍历左子树，最后遍历右子树；遍历右子树；(树根在第一，下走不跳结点树根在第一，下走不跳结点)(2)(2)中序遍历中序遍历(LDR)(LDR)，首先遍历左子树，然后访问根结点，最后，首先遍历左子树，然后访问根结点，最后遍历右子树；遍历右子树；(有左先左，再寻根，后找右，最左边的结点最先遍历，最右有左先左，再寻根，后找右，最左边的结点最先遍历，最右边的结点最后遍历边的结点最后
42、遍历)(3)(3)后序遍历后序遍历(LRD)(LRD)首先遍历左子树，然后访问遍历右子树，最首先遍历左子树，然后访问遍历右子树，最后访问根结点。后访问根结点。(有左先左，再找右，后寻根，到最右一路上有左先左，再找右，后寻根，到最右一路上行，树根在最后行，树根在最后)第一部分第一部分 数据结构与算法数据结构与算法第一部分第一部分 数据结构与算法数据结构与算法已知二叉树的前序遍历为已知二叉树的前序遍历为ABDEFCABDEFC，中序遍历为，中序遍历为DBFEACDBFEAC，则二叉，则二叉树的后序遍历结果是：树的后序遍历结果是：分析：分析：前序遍历为前序遍历为ABDEFCABDEFC中序遍历为中序
43、遍历为DBFEACDBFEAC第一步：确定第一步：确定A A为根结点，则由中序遍历为根结点，则由中序遍历(DBFEDBFEA AC C)可以知道可以知道DBFEDBFE为为A A的左子树部分，的左子树部分，C C为为A A的右子树部分。的右子树部分。第一部分第一部分 数据结构与算法数据结构与算法第二步：对于中序中的第二步：对于中序中的DBFEDBFE，在前序中的结果为，在前序中的结果为BDEFBDEF，所，所以可以得出这四个结点中以可以得出这四个结点中B B为为“小根小根”结点，即结点，即B B直接和直接和A A相相连，接着在中序中连，接着在中序中(D DB BFEFE)可以知道可以知道D D
44、在在B B的左边，的左边，FEFE在在B B的右的右面。面。第一部分第一部分 数据结构与算法数据结构与算法第三步：对于中序中的第三步：对于中序中的FEFE，在前序中为，在前序中为EFEF，则可以知道，则可以知道E E直直接和接和B B相连，在中序中，相连，在中序中，F F在在E E的左面，即可以得出二叉树图的左面，即可以得出二叉树图形形。第四步：根据第四步：根据二叉树图形二叉树图形写出写出后序遍历为后序遍历为DFEBCADFEBCA。第一部分第一部分 数据结构与算法数据结构与算法例题例题(1)(1)对于如图的二叉树，进行后序遍历的结果为对于如图的二叉树，进行后序遍历的结果为()A)ABCDEF
45、 A)ABCDEF B)DBEAFC B)DBEAFC C)ABDECF C)ABDECF D)DEBFCA D)DEBFCA第一部分第一部分 数据结构与算法数据结构与算法(2)(2)在深度为在深度为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)一棵二叉树中共有一棵
46、二叉树中共有7070个叶子结点与个叶子结点与8080个度为个度为1 1的结点，则该二的结点，则该二叉树中的总结点数为叉树中的总结点数为()()A)219 A)219 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
47、，1 1，1 1。则。则T T的叶子结点数为的叶子结点数为()A)8 A)8 B)7 B)7 C)6 C)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总总
48、=16=16马上马上可以得到可以得到 n n0 0=n=n总总-n n1 1-n-n2 2-n-n3 3-n-n4 4=8=8第一部分第一部分 数据结构与算法数据结构与算法1.7 1.7 查找与排序技术查找与排序技术1.1.顺序查找顺序查找：从表中的最后一个从表中的最后一个(或第一个或第一个)记录开始，逐个进行记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到了所有查找的记录；反之，若直至第较相等，则查找成功，找到了所有查找的记录；反之，若直至第一个记录，其关键字和给定值比较不等，则表明表中
49、没有所查找一个记录，其关键字和给定值比较不等，则表明表中没有所查找的记录，查找不成功。的记录，查找不成功。若有若有n n个记录，顺序查找的平均查找长度为个记录，顺序查找的平均查找长度为(n+1n+1)/2/2，最坏情况下的比较次数为，最坏情况下的比较次数为n n。二分查找：适用于顺序存储的有序表二分查找：适用于顺序存储的有序表。第一部分第一部分 数据结构与算法数据结构与算法2.2.二分查找二分查找：要求线性表中的结点必须是按关键字值的递增或要求线性表中的结点必须是按关键字值的递增或递减顺序排列。它首先把要查找的关键字递减顺序排列。它首先把要查找的关键字k k与中间位置的关键字与中间位置的关键字
50、相比较，若相等，则查找成功；若不相等，则缩小范围。根据相比较，若相等，则查找成功；若不相等，则缩小范围。根据关键字与中间结点关键字的比较大小确定下一步查找那个子表关键字与中间结点关键字的比较大小确定下一步查找那个子表，这样一直查找下去，直到满足条件的结点或者确认表中没有，这样一直查找下去，直到满足条件的结点或者确认表中没有这样的结点为止。所以这样的结点为止。所以在有序表中，二分查找为首选，二分查在有序表中，二分查找为首选，二分查找的比较次数为找的比较次数为loglog2 2n n。第一部分第一部分 数据结构与算法数据结构与算法顺序查找适用于两种情况：顺序查找适用于两种情况：1)1)线性表为无序