计算机⼆级关于选择题⼆叉树的知识点，计算机⼆级Office知识
点：数据结构与算法整理...
计算机⼆级Office知识点：数据结构与算法整理
计算机⼆级Office知识点有哪些？下⾯是⼩编为⼤家搜集整理的计算机⼆级Office知识点：数据结构与算法整理，希望能对⼤家有所帮助！
1.1算法
1.算法的基本概念
(1)概念：算法是指⼀系列解决问题的清晰指令。
(2)4个基本特征：可⾏性、确定性、有穷性、拥有⾜够的情报。
(3)两种基本要素：对数据对象的运算和操作、算法的控制结构(运算和操作时问的顺序)。
(4)设计的基本⽅法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
2.算法的复杂度
二叉树的基本性质
(1)算法的时间复杂度：执⾏算法所需要的计算⼯作量。
(2)算法的空间复杂度：执⾏算法所需的内存空间。
1.2数据结构的基本概念
数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间逻辑关系；存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种⽅式。
数据结构按各元素之间前后件关系的复杂度可划分为：
(1)线性结构：有且只有⼀个根节点，且每个节点最多有⼀个直接前驱和⼀个直接后继的⾮空数据结构。
(2)⾮线性结构：不满⾜线性结构的数据结构。
1.3线性表及其顺序存储结构
1.线性表的基本概念
线性结构⼜称线性表，线性表是最简单也是最常⽤的⼀种数据结构。
2.线性表的顺序存储结构
元素所占的存储空间必须连续。
元素在存储空间的位置是按逻辑顺序存放的。
3.线性表的插⼊运算
在第i个元素之前插⼊⼀个新元素的步骤如下：
步骤⼀：把原来第n个节点⾄第i个节点依次往后移⼀个元素位置。
步骤⼆：把新节点放在第i个位置上。
步骤三：修正线性表的节点个数。
在最坏情况下，即插⼊元素在第⼀个位置，线性表中所有元素均需要移动。
4.线性表的删除运算
删除第i个位置的元素的步骤如下：
步骤⼀：把第i个元素之后不包括第i个元素的n—i个元素依次前移⼀个位置；
步骤⼆：修正线性表的结点个数。
1.4栈和队列
1.栈及其基本运算
(1)基本概念：栈是⼀种特殊的线性表，其插⼊运算与删除运算都只在线性表的⼀端进⾏，也被称为“先进后出”表或“后进先出”表。
栈顶：允许插⼊与删除的⼀端。
栈底：栈顶的另⼀端。
空栈：栈中没有元素的栈。
(2)特点。
栈顶元素是最后被 插⼊和最早被删除的元素。
栈底元素是最早被 插⼊和最后被删除的元素。
栈有记忆作⽤。
在顺序存储结构下，栈的插⼊和删除运算不需移动表中其他数据元素。
栈顶指针top动态反映了栈中元素的变化情况
(3)顺序存储和运算：⼊栈运算、退栈运算和读栈顶运算。
2.队列及其基本运算
(1)基本概念：队列是指允许在⼀端进⾏插⼊，在另⼀端进⾏删除的'线性表，⼜称“先进先出”的线性表。
队尾：允许插⼊的⼀端，⽤尾指针指向队尾元素。
排头：允许删除的⼀端，⽤头指针指向头元素的前⼀位置。
(2)循环队列及其运算。
所谓循环队列，就是将队列存储空间的最后⼀个位置绕到第⼀个位置，形成逻辑上的环状空间。
⼊队运算是指在循环队列的队尾加⼊⼀个新元素。
当循环队列⾮空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进⾏⼈队运算，这种情况称为“上溢”。
退队运算是指在循环队列的队头位置退出⼀个元素并赋给指定的变量。⾸先将队头指针进⼀，然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s=0)时，不能进⾏退队运算，这种情况称为“下溢”。
1.5线性链表
在定义的链表中，若只含有⼀个指针域来存放下⼀个元素地址，称这样的链表为单链表或线性链表。
在链式存储⽅式中，要求每个结点由两部分组成：⼀部分⽤于存放数据元素值，称为数据域；另⼀部分⽤于存放指针，称为指针域。其中指针⽤于指向该结点的前⼀个或后⼀个结点(即前件或后件)。
1.6树和⼆叉树
1.树的基本概念
树是简单的⾮线性结构，树中有且仅有⼀个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1，T2，…，T}mm，每个集合⼜是⼀棵树，称T1，T2，…，T}mm为根结点的⼦树。
⽗节点：每⼀个节点只有⼀个前件，⽆前件的节点只有⼀个，称为树的根结点(简称树的根)。
⼦节点：每～个节点可以后多个后件，⽆后件的节点称为叶⼦节点。
树的度：所有节点最⼤的度。
树的深度：树的最⼤层次。
2.⼆叉树的定义及其基本性质
(1)⼆叉树的定义：⼆叉树是⼀种⾮线性结构，是有限的节点集合，该集合为空(空⼆叉树)或由⼀个根节点及两棵互不相交的左右⼆叉⼦树组成。可分为满⼆叉树和完全⼆叉树，其中满⼆叉树⼀定是完全⼆叉树，但完全⼆叉树不⼀定是满⼆叉树。⼆叉树具有如下两个特点：
⼆叉树可为空，空的⼆叉树⽆节点，⾮空⼆叉树有且只有⼀个根结点；
每个节点最多可有两棵⼦树，称为左⼦树和右⼦树。
(2)⼆叉树的基本性质。
性质1：在⼆叉树的第k层上⾄多有2k—1个结点(k≥1)。
性质2：深度为m的⼆叉树⾄多有2m—1个结点。
性质3：对任何⼀棵⼆叉树，度为0的结点(即叶⼦结点)总是⽐度为2的结点多⼀个。
性质4：具有n个结点的完全⼆叉树的深度⾄少为[log2n]+1，其中[log2n]表⽰log2n的整数部分。
3.满⼆叉树与完全⼆叉树
(1)满⼆叉树：满⼆叉树是指这样的⼀种⼆叉树：除最后⼀层外，每⼀层上的所有结点都有两个⼦结点。满⼆叉树在其第i层上有2i—1个结点。
从上⾯满⼆叉树定义可知，⼆叉树的每⼀层上的结点数必须都达到最⼤，否则就不是满⼆叉树。深度为m的满⼆叉树有2m—1个结点。
(2)完全⼆叉树：完全⼆叉树是指这样的⼆叉树：除最后⼀层外，每⼀层上的结点数均达到最⼤值；在最后⼀层上只缺少右边的若⼲结点。
如果—棵具有n个结点的深度为k的⼆叉树，它的每—个结点都与深度为k的满⼆叉树中编号为1～n的结点——对应。
4.⼆叉树的存储结构
⼆叉树通常采⽤链式存储结构，存储节点由数据域和指针域(左指针域和右指针域)组成。⼆叉树的链式存储结构也称⼆叉链表，对满⼆叉树和完全⼆叉树可按层次进⾏顺序存储。
5.⼆叉树的遍历
⼆叉树的遍历是指不重复地访问⼆叉树中所有节点，主要指⾮空⼆叉树，对于空⼆叉树则结束返回。⼆叉树的遍历包括前序遍历、中序遍历和后序遍历。
(1)前序遍历。
前序遍历是指在访问根结点、遍历左⼦树与遍历右⼦树这三者中，⾸先访问根结点，然后遍历左⼦树，最后遍历右⼦树；并且，在遍历左右⼦树时，仍然先访问根结点，然后遍历左⼦树，最后遍历右⼦树。前序遍历描述为：若⼆叉树为空，则执⾏空操作；否则①访问根结点；②前序遍历左⼦树；③前序遍历右⼦树。
(2)中序遍历。
中序遍历是指在访问根结点、遍历左⼦树与遍历右⼦树这三者中，⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树；并且，在遍历左、右⼦树时，仍然先遍历左⼦树，然后访问根结点，最后遍历右⼦树。中序遍历描述为：若⼆叉树为空，则执⾏空操作；否则①中序遍历左⼦树；②访问根结点；③中序
遍历右⼦树。
(3)后序遍历。
后序遍历是指在访问根结点、遍历左⼦树与遍历右⼦树这三者中，⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点，并且，在遍历左、右⼦树时，仍然先遍历左⼦树，然后遍历右⼦树，最后访问根结点。后序遍历描述为：若⼆叉树为空，则执⾏空操作；否则①后序遍历左⼦树；②后序遍历右⼦树；③访问根结点。
1.7查技术
(1)顺序查：在线性表中查指定的元素。
(2)最坏情况下，最后⼀个元素才是要的元素，则需要与线性表中所有元素⽐较，⽐较次数为n。
(2)⼆分查：⼆分查也称折半查，它是⼀种⾼效率的查⽅法。但⼆分查有条件限制，它要求表必须⽤顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)排列。对长度为n的有序线性表，在最坏情况下，⼆分查法只需⽐较log2n次。
1.8排序技术
(1)交换类排序法。
冒泡排序：通过对待排序序列从后向前或从前向后，依次⽐较相邻元素的排序码，若发现逆序则交换，使较⼤的元素逐渐从前部移向后部或较⼩的元素逐渐从后部移向前部，直到所有元素有序为⽌。在最坏情况下，对长度为n的线性表排序，冒泡排序需要⽐较的次数为n(n—
1)/2。
快速排序：是迄今为⽌所有内排序算法中速度最快的⼀种。它的基本思想是：任取待排序序列中的某个元素作为基准(⼀般取第⼀个元素)，通过⼀趟排序，将待排元素分为左右两个⼦序列，左⼦序列元索的排序码均⼩于或等于基准元素的排序码，右⼦序列的排序码则⼤于基准元素的排序码，然后分别对两个⼦序列继续进⾏排序，直⾄整个序列有序。最坏情况下，即每次划分，只得到⼀个序列，时间效率为O(n2)。
(2)插⼈类排序法。
简单插⼊排序法：把n个待排序的元素看成为⼀个有序表和⼀个⽆序表，开始时有序表中只包含⼀个元素，⽆序表中包含有n—1个元素，排序过程中每次从⽆序表中取出第⼀个元素，把它的排序码依次与有序表元素的排序码进⾏⽐较，将它插⼊到有序表中的适当位置，使之成为新的有序表。在最坏情况下，即初始排序序列是逆序的情况下，⽐较次数为n(n—1)/2，移动次数为n(n—1)/2。
希尔排序法：先将整个待排元素序列分割成若⼲个⼦序列(由相隔某个“增量”的元素组成的)分别进⾏直接插⼊排序。待整个序列中的元素基本有序(增量⾜够⼩)时，再对全体元素进⾏⼀次直接插⼊排序。
(3)选择类排序法。
简单选择排序法：扫描整个线性表。从中选出最⼩的元素。将它交换到表的最前⾯；然后对剩下的⼦表采⽤同样的⽅法，直到⼦表空为⽌。最坏情况下需要⽐较n(n—1)/2次。
堆排序的⽅法：⾸先将⼀个⽆序序列建成堆；然后将堆顶元素(序列中的最⼤项)与堆中最后⼀个元素交换(最⼤项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n—1个元素构成的⼦序列，将该⼦序列调整为堆。反复做步骤②，直到剩下的⼦序列空为⽌。在最坏情况下，堆排序法需要⽐较的次数为0(nlog2n)
【计算机⼆级Office知识点：数据结构与算法整理】相关⽂章：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。