栈只允许在表的一端举行扦插或删除操作,算法是一组严格地定义运算顺序的规则

一: 算法

1、线性表、栈和队列等数据结构所表明和拍卖的数据以线性结构为协会形式。栈是一种特其余线性表,这种线性表只可以在稳定的一端举行插队和删除操作,允许插入和删除的一端称为栈顶,另一端称为栈底。一个新因素只可以从栈顶一端进入,删除时,只好删除栈顶的元素,即刚刚被插入的因素。所以栈又称后进先出表(Last
In First
Out);队列可用作是插入在一端举行,删除在另一端举行的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。在队列中,只可以删除队头元素,队列的尾声一个要素一定是流行入队的元素。因而队列又称先进先出表(First
In First Out)。

算法:是一组周朝指令集,是解题方案的纯正而全体的讲述。通俗地说,算法就是电脑解题的长河。算法不对等程序,也不对等总结办法,程序的编排不可以有过之而无不及算法的计划性。

2、栈和队列都是一种特此外操作受限的线性表,只同目的在于端点处举行插队和删除。二者的区分是:栈只允许在表的一端举办插队或删除操作,是一种”后进先出”的线性表;而队列只允许在表的一端举办插队操作,在另一端进行删减操作,是一种”先进先出”的线性表。

算法是一组严酷地定义运算顺序的条条框框,每一个规则都是可行的,且是举世瞩目标,此顺序将在有限的次数下截至。所以其几个基本特征包括:

3、栈是一种特殊的线性表,这种线性表只可以在定点的一端举办插队和删除操作,允许插入和删除的一端称为栈顶,另一端称为栈底。一个新因素只好从栈顶一端进入,删除时,只能删除栈顶的元素,即刚刚被插入的因素。所以栈又称先进后出表(FILO-First
In Last
Out)。线性表可以顺序存储,也足以链式存储,而栈是一种线性表,也能够运用链式存储结构。

(1)确定性,算法中每一步骤都无法不有举世瞩目概念,不同意有暧昧的表明,不允许有多义性;
(2)战国性,算法必须能在点滴的日子内做完,即能在实施有限个步骤后停下;
(3)可行性,算法原则上可知精确地履行;
(4)拥有丰裕的情报。

4、栈和队列都是一种分外的操作受限的线性表,只同目的在于端点处举行扦插和删除。二者的分别是:栈只允许在表的一端举行插队或删除操作,是一种”后进先出”的线性表;而队列只同意在表的一端举办插队操作,在另一端举行删除操作,是一种”先进先出”的线性表。

算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。

5、在栈中,栈底指针不变,栈中元素随栈顶指针的变迁而动态变化

指令系统:一个处理器序列能实施的兼具指令的联谊。

top=0表示栈空,top=50表示栈满。入栈操作首先将top加1,然后将新元素插入到top指针指向的地方;退栈操作首先将top指针指向的因素赋给一个点名的变量,然后将top减1。栈顶指针top动态反映了栈中元素的浮动情状。

基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。

6、栈是一种先进后出的线性表,栈实际上也是线性表,只但是是一种特有的线性表。队列是指允许在一端进行插队、而在另一端举行删减的线性表,队列是一种”先进先出”或”后进后出”的线性表

算法的两种为主控制结构:顺序结构、采取结构、循环结构。

队列是指允许在一端举办插队、而在另一端举行删除的线性表。它又称之为”先进先出”或”后进后出”的线性表,显示了”先来先服务”的尺度。

算法基本计划方法:列举法、归结法、递推、递归、减半递推技术、回溯法。

7、带链的行列也是线性链表,在线性链表中指向线性表中的率先个结点的指针称为头指针,头指针为NULL或0时名为空表,指向队尾元素的指针称为尾指针。队列在队尾插入元素,称为入队运算;在队头删除元素,称为退队运算。带链队列在开发存储空间时,可以依据存储空间地址增大的趋向开辟,也得以听从存储空间地址缩短的倾向开辟。

算法效能的心地—算法复杂度:算法时间复杂度和算法空间复杂度。

8、所谓循环队列,就是将队列存储空间的终极一个岗位绕到第1个职务,形成逻辑上的环状空间,供队列循环使用。所以循环队列依旧属于线性结构。循环队列的头指针front指向队列的率先个要素的前一岗位,队尾指针rear指向队列的尾声一个元素,循环队列的动态变化需要头尾指针共同反映循环队列的尺寸是:(sq.rear-sq.front+maxsize)%maxsize,所以循环队列的长短是由队头和队尾指针共同决定的

算法时间复杂度:指执行算法所需要的测算工作量。即算法执行进程中所需要的着力运算次数。通常,一个算法所用的岁月包括编译时间和运行时刻。

 在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个地点。

算法空间复杂度:指执行这一个算法所急需的内存空间。包括算法程序所占的空中,输入的上马数据所占的空间,算法执行进程中所需的附加空间。

 循环队列第一有两种为主运算:入队运算与退队运算。每举办三回入队运算,队尾指针就进一。每举行五回退队运算,排头指针就进一。当rear或front的值等于队列的长短+1时,就将rear或front的值置为1。一般情状下,rear大于front,因为入队的要素肯定比出队的要素多。特殊的情事是rear到达数组的上限之后又从数组的低端开首,此时,rear是稍低于front的。

二: 数据结构的基本概念

循环队列就是将队列存储空间的最后一个岗位绕到第一个岗位,形成逻辑上的环状空间,供队列循环利用。在实际利用中,队列的顺序存储结构相似选用循环队列的款式。由此,循环队列不是队列的一种链式存储结构。循环队列是一种存储结构,因而循环队列是一种物理构造,而不是逻辑结构。循环队列是队列的顺序存储结构,因而循环队列是线性结构。

数据结构:指互相有提到的数额元素的成团。

9、循环队列不同于循环链表,循环队列是顺序存储结构,循环链表是链式存储结构。双向链表是链式存储结构,其中每个结点都有左指针和右指针,不同于二叉树结点的左子树指针和右子树指针。非线性结构和线性结构是多少的逻辑结构,顺序和链式是数据的存储结构,例如二叉树是非线性结构,也足以服从层序举办顺序存储。

数据结构切磋的六个地点:

10、非线性结构的逻辑特征是一个结点元素可能对应多少个从来前驱和三个后驱。常见的非线性结构有:树(二叉树等),图(网等)。

(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;

11、由于二叉树的储存结构中每一个囤积结点有两个指针域,由此,二叉树的链式存储结构也称之为二叉链表,二叉链表属于非线性结构。

(2)在对数码开展处理时,各数据元素在处理器中的存储关系,即数据的储存结构;

12、遍历是指不重复的走访具有结点。线性单链表每个结点只有一个指针域,由这些指针只好找到后件结点,但不可能找到前件结点。双向链表中的每个结点设置两个指针,左指针指向其前件结点,右指针指向其后件结点。循环链表中加进了一个表头结点,循环链表中的所有结点的指针构成了一个环状链。二叉链表即二叉树的链式存储结构,每个存储结点有两个指针域,左指针域指向该结点的左子结点的贮存地方,右指针域指向该结点的右子结点的积存地方。

(3)对各类数据结构举办的演算。

13、线性表的顺序存储结构有所六个为主特色:(1)线性表中装有因素所占的仓储空间是连连的;(2)线性表中各因素在存储空间中是按逻辑顺序依次存放的。

数码的逻辑结构应包含:

14、循环链表具有以下多少个特性:(1)在循环链表中扩大了一个表头结点,其数据域为擅自或者遵照需要来安装,指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不是空,而是指向表头结点。即在循环链表中,所有结点的指针构成了一个环状链。

(1)表示数据元素的信息;

15、在循环链表中,只要提议表中任何一个结点的地方,就足以从它出发访问到表中任何具备的结点,而线性单链表做不到这或多或少。

(2)表示各数据元素之间的上下件涉及(指逻辑关系,与仓储地点无关)。

16、根据二叉树的性能:二叉树第i(i≥1)层上至多有2i-1个结点。

数量的逻辑结构在电脑存储空间中的存放格局称为数据的存储结构,也称数据物理结构。

17、所谓满二叉树是指那样的一种二叉树:除最终一层外,每层上的有所结点都有多少个子结点。这就是说,在满二叉树中,每一层上的结点数都达成最大值,即在满二叉树的第K层上有2K-1个结点,且深度为m的满二叉树有2m个结点。

多少的仓储结构有各类、链接、索引等。

18、在随心所欲一颗树中,结点总数=总分支数目+1

线性结构的尺度,(一个非空数据结构):

19、二叉树的性能:在随心所欲一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。本题中度为2的结点数为n,故叶子结点数为n+1个。

(1)有且唯有一个根结点;
(2)每一个结点最多有一个前件,也最多有一个后件。

二叉树的性能:在随意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。

非线性结构:不满足线性结构条件的数据结构。

20、在用完全二叉树表示堆,树中保有非叶子结点值均不低于其左右子树的根结点值,由此,堆顶元素必为连串的n个元素中的最大项。

三:线性表及其顺序存储结构

21、作为一个算法,一般应具有以下多少个基本特征。

线性表是由一组数据元素构成,数据元素的地点只在乎自己的序号,元素之间的相对地方是线性的。

 可行性

在复杂线性表中,由若干项数据元素结合的数码元素称为记录;

 确定性

由三个记录构成的线性表称为文件。

 有穷性

非空线性表的结构特征:

拥有丰硕的消息

(1)且只有一个根结点a1,它无前件;

22、总结机算法是指解题方案的精确而完好的叙说

(2)有且只有一个极限结点an,它无后件;

算法的东周性,是指算法必须在简单的年月内做完,即算法必须能在推行有限个步骤之后终止。

(3)除根结点与极端结点外,其他具有结点有且唯有一个前件,也有且只有一个后件。

23、希尔(Hill)排序法的主导思想是:将一切无序体系分割成几何小的子系列分别展开插入排序。所以希尔(Hill)排序法属于插入类排序,但它对简易插入排序做了很大的改进。

结点个数n称为线性表的尺寸,当n=0时,称为空表。

24、快速排序的着力思想是,通过一趟排序将待排序记录分割成单身的两有些,其中有些笔录的重点字均比另一局部记录的根本字小,再分别对这两部分记录继续进行排序,以高达全部连串有序;插入排序的基本操作是指将无序系列中的各因素依次插入到已经稳步的线性表中,从而获取一个新的行列;采用排序的中央思想是:扫描整个线性表,从中选出最小的元素,将它交流来表的最前方(这是它应该的职位),然后对结余的子表采纳同一的法门,直到表空为止;归并排序是将五个或六个以上的静止表组合成一个新的有序表。

线性表的顺序存储结构有所以下六个为主特色:

25、在单链表中,扩大头结点的目的是______。

(1)线性表中所有因素所占的囤积空间是连连的;

头结点不仅标识了表中首结点的地点,而且据悉单链表(包含头结点)的协会,只要精晓了表头,就可知访问整个链表,因而扩充头结点指标是为着便利运算的实现。

(2)线性表中各数据元素在储存空间中是按逻辑顺序依次存放的。

26、算法分析是指对一个算法的运作时刻和占有空间做定量的解析,一般总计出相应的数目级,常用时间复杂度和空中复杂度表示。分析算法的目标就是要大跌算法的时光复杂度和空间复杂度,提升算法的施行效能。

元素ai的贮存地方为:ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个因素的地址,k代表每个元素占的字节数。 顺序表的演算:查找、插入、删除。

四:线性链表

数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。

结点由两片段构成:

(1) 用于储存数据元素值,称为数据域;

(2) 用于存放指针,称为指针域,用于指向前一个或后一个结点。

在链式存储结构中,存储数据结构的贮存空间可以不总是,各数据结点的积存顺序与数量元素之间的逻辑关系可以不一样,而数据元素之间的逻辑关系是由指针域来规定的。

链式存储格局即可用于表示线性结构,也可用以表示非线性结构。

线性单链表中,HEAD称为头指针,HEAD=NULL(或0)称为空表。

假诺是双项链表的两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。

线性链表的中央运算:查找、插入、删除。

五:栈和队列

栈:限定在一端举行扦插与删除的线性表。

其同意插入与删除的一端称为栈顶,用指针top表示栈顶地方。

不容许插入与删除的另一端称为栈底,用指针bottom表示栈底。

栈遵照“先进后出”(FILO)或“后进先出”(LIFO)协会数据,栈具有记忆效率。

栈的囤积模式有顺序存储和链式存储。

栈的骨干运算:

(1) 入栈运算,在栈顶地点插入元素;

(2) 退栈运算,删除元素(取出栈顶元素并赋给一个点名的变量);

(3) 读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。

队列:指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。

用rear指针指向队尾,用front指针指向队头元素的前一个职位。

队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。

队列运算包括:

(1) 入队运算:从队尾插入一个要素;

(2) 退队运算:从队头删除一个要素。

队列的顺序存储结构相似拔取队列循环的格局。

循环队列s=0表示队列空;s=1且front=rear表示队列满。

计量循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。

27、算法是指解题方案的准确而完全的描述。但算法不对等程序,也不对等总计办法。当然,程序也足以看做算法的一种描述,但顺序平常还需要考虑很多与方法和剖析无关的底细问题,这是因为在编写程序时要遭逢电脑体系运转条件的限定。平时,程序的编制不容许有过之而无不及算法的设计。作为一个算法,一般应负有可行性、确定性、有穷性、拥有充分情报五个基本特征。由此计划算法时不仅要考虑结果的可靠性,即不仅考虑算法结果的动向,还要考虑步骤的家喻户晓,时间和步子的西周性等。因而,算法是一组严刻地定义运算顺序的规则,并且每一个平整都是行之有效的,且是扎眼的,此顺序将在有限的次数下截止。

六: 树与二叉树

树是一种简单的非线性结构,其有着因素之间所有明确的层系特性。

在树结构中,每一个结点唯有一个前件,称为父结点。

不曾前件的结点唯有一个,称为树的根结点,简称树的根。

每一个结点可以有六个后件,称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中,一个结点所怀有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深浅。

二叉树的特点:

(1) 非空二叉树唯有一个根结点;
(2) 每一个结点最多有两棵子树,且分别名叫该结点的左子树与右子树。

满二叉树是指除最终一层外,每一层上的享有结点有三个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

全盘二叉树是指除最终一层外,每一层上的结点数均达标最大值,在末了一层上只贫乏左边的几何结点。

二叉树基本特性:

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;

(2)深度为m的二叉树最多有2m-1个结点;

(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;

(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]代表取log2n的平头部分

(5) 具有n个结点的一心二叉树的纵深为[log2n]+1;

(6)
设完全二叉树共有n个结点。假诺从根结点最先,按层序(每一层从左到右)用自然数1,2,…n给结点举行编号(k=1,2….n),有以下结论:

①若k=1,则该结点为根结点,它从不父结点;若k>1,则该结点的父结点编号为INT(k/2);

②若2k≤n,则k结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。

补给:扩展度为1的结点不会影响二叉树的纸牌结点数,每扩大一个度为2的结点便会扩张一个纸牌结点,没有度为2的结点时叶子结点数为1。

已知完全二叉树有x个结点,求其叶子结点数:

①   确定层数为k;

②   ②第k层的结点数y=x-(2 k-1-1);

③   第k-1层的叶子结点数n=2 (k-1)-1-y/2<若y/2有余,则要加1>;

④   ④最后y+n。

二叉树存储结构选用链式存储结构,对于满二叉树与完全二叉树可以按层序举行顺序存储。二叉树的遍历:

(1)前序遍历(DLR),首先走访根结点,然后遍历左子树,最终遍历右子树;(树根在第一,下走不跳结点)

(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最终遍历右子树;(有左先左,再寻根,后找右。最左边的结点先导遍历,最左边的结点最终遍历)

(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最终访问根结点。(有左先左,再找右,后寻根,到最右一路上行,树根在结尾)

小结:

逻辑结构可分为线性表和非线性表。

线性表包括栈、队列,其储存模式为顺序存储、链式存储均可。链式型有:线性链表,带链的栈,

带链的连串,循环链表等。

非线性表包括树(二叉树),其储存格局为链式存储。

七: 查找技术

唯其如此拔取各种查找的二种情况:

(1)线性表为无序表,不管是顺序存储依然链式存储;

(2)表选取链式存储结构,虽然是有序线性表。

二分法查找只适用于顺序存储的平稳表,对于长度为n的不变线性表,最坏情形只需相比log2n次,而一一查找需要相比较n次。

八: 排序技术

排序是指将一个无序系列整理成按值非递减顺序排列的不变系列。

沟通类排序法:

(1)冒泡排序法,需要相比的次数为n(n-1)/2;

(2 ) 神速排序法。

插入类排序法:

(1)简单插入排序法,最坏情况需要n(n-1)/2次比较;

(2) 希尔排序法,最坏情形需要O(n1.5)次相比较。

慎选类排序法:

(1)简单采用排序法, 最坏情形需要n(n-1)/2次比较;

(2)
堆排序法,最坏意况需要O(nlog2n)次相比。相相比上述两种(除Hill排序法外),堆排序法的日子复杂度最小。

28、一个算法日常由两种基本要素组成:一是对数码对象的运算和操作,二是算法的控制结构。因而计划算法时不仅需要考虑数据结构的计划性,还要考虑数据的操作和运算及各操作之间的推行各类。

29、在有向图中,若任意六个极点都联网,则称该图是强连通图,这样的有向图的模样是环状,由此至少应当n条边。

30、当数码表A中每个元素距其末了地方不远,表达数据表A按紧要性字值基本不变,在待排序体系基本板上钉钉的图景下,采取插入排序所用时间最少。

31、数据的逻辑结构在微机存储空间中的存放格局称为数据的存储结构(也称数据的情理结构)。

32、假如线性表的尺寸为n,则在最坏情状下,冒泡排序需要经过n/2遍的往日未来扫描和n/2遍的从后往前扫描,需要相比较次数为n(n-1)/2。神速排序法的最坏意况相比较次数也是n(n-1)/2

(1)冒泡排序法:是一种最简单易行的交流类排序法,它是因而邻近数据元素的互换逐渐将线性表变成有序。假如线性表的长短为n,则在最坏意况下,冒泡排序需要通过n/2遍的以前以后的围观和n/2遍的从后往前的扫描,需要相比较的次数为n(n-1)/2次。

 (2)简单插入排序法:在简要插入排序法中,每五次相比较后最多移掉一个逆序,因而,这种排序方法的频率与冒泡排序法相同。在最坏意况下,简单插入排序需要n(n-1)/2次相比较。

 (3)简单选用排序法:对于长度为n的连串,采用排序需要扫描n-1遍,每三遍扫描均从剩下的子表中选出最小的要素,然后将该最小的要素与子表中的第一个元素举办置换。简单采取排序法在最坏情状下需要相比n(n-1)/2次。

 (4)堆排序法:堆排序的方法为:①第一将一个无序连串建成堆。②然后将堆顶元素(连串中的最大项)与堆中最终一个因素交流(最大项应该在体系的末梢)。在最坏境况下,堆排序需要比较的次数为。

 假如线性表的长短为16,那么冒泡排序、直接插入排序、简单采用排序都亟待比较120次,而堆排序需要相比较64次。

33、对于长度为n的线性表,在最坏的动静下,快捷排序所急需的可比次数为n(n-1)/2;冒泡排序所需要的相比较次数为n(n-1)/2;直接插入排序所急需的相比次数为n(n-1)/2;堆排序所急需的可比次数为。

34、在举办逐项查找过程中,即便线性表中的首先个因素就是被搜寻元素,则只需做两回相比就招来成功,查找效用最高;但假使被搜寻的因素是线性表中的最终一个要素,或者被寻找的元素根本就不在线性表中,则为了探寻那一个因素需要与线性表中所有的因素举行相比较,这是各样查找的最坏情形。所以对长度为n的线性表进行逐一查找,在最坏意况下需要相比较n次。

35、二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的因素按值非递减排列(即从小到大,但允许相邻元素值相等)。

二分法检索要求线性表结点按首要性值排序且以一一格局存储。在寻找时,首先与表的中档地点上结点的第一值相比,若相等则检索成功;否则遵照相比结实确定下一步在表的前半片段或后半片段继续举行。二分法检索的功用相比较高,设线性表有n个元素,则最多的寻找次数为大于log2n(2为底数)的微乎其微整数,最少的搜索次数为1。

36、一般的话,一种多少的逻辑结构依照需要可以代表成多种仓储结构,常用的存储结构有各类、链接、索引等储存结构。而使用不同的储存结构,其数据处理的频率是不同的。

37、顺序存储结构就是用一组地点连续的存储单元依次存储该线性表中的各类要素,链式存储结构中各数据结点的积存序号是不连续的,并且各结点在蕴藏空间中的地方关系与逻辑关系也不等同。两者都得以存储线性的、有序的逻辑结构,顺序结构采纳的是接连物理空间,链式结构可以选取零散的物理空间存储,链式结构更灵活,不存在何人节约空间的说教

38、顺序存储结构中,数据元素存放在一组地方连续的存储单元中,每个数据元素地址可通过公式LOC(ai)=LOC(a1)+(i-1)L总计取得,从而实现了随机存取。对于链式存储结构,要对某结点举行存取,都得从链的头指针指向的结点起头,那是一种顺序存取的储存结构。

39、链式存储结构打败了顺序存储结构的通病:它的结点空间可以动态申请和假释;它的数据元素的逻辑次序靠结点的指针来提示,不需要活动数据元素。故链式存储结构下的线性表便于插入和删除操作。

40、线性表的顺序存储结构的蕴藏空间只用于存放结点数据,而链式存储结构的储存空间不仅要存放结点数据,还要存放数据的指针,所以线性表的链式存储结构所需要的囤积空间一般要多于顺序存储结构

41、在展开依次查找过程中,如若线性表中的第1个因素就是被搜寻元素,则只需做一遍相比就招来成功,查找功效最高;但倘若被寻找的因素是线性表中的末尾一个要素,或者被搜寻的要素根本就不在线性表中,则为了寻觅这多少个元素需要与线性表中所有的因素举行较,这是逐一查找的最坏情形。所以对长度为n的线性表举办逐一查找,在最坏意况下需要相比较n次

42、对于长度为n的不变线性表,在最坏情状下,二分查找只需要相比次,而各种查找需要相比较n次。二分法查找只适用于顺序存储的有序表,假若运用链式存储结构,也只可以用顺序查找,所以,对长度为n的平稳链表举行查找,最坏意况下需要的可比次数为n

43、遵照数据结构中各数据元素之间上下件关乎的复杂程度,一般将数据结构分为两大品类:线性结构与非线性结构。

44、如果一个非空的数据结构满意下列两个标准:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。

45、有一个上述根结点的数据结构肯定是非线性结构,循环链表、双向链表是线性结构;线性表、栈与队列、线性链表都是线性结构,而二叉树是非线性结构。

46、在链表中,假设有五个结点的同一个指针域的值异常,则该链表一定是非线性结构

47、线性表的链式存储结构称为线性链表,为了适应线性表的链式存储结构,总计机存储空间被分割为一个一个小块,每一小块占多少字节,通常称那么些小块为存储结点。每一个囤积结点分为两部分:一部分用来存储数据元素的值,称为数据域;另一有些用以存放下一个数量元素的囤积序号,即针对后件的结点,称为指针域。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的蕴藏顺序与数量元素之间的逻辑关系能够不相同。为了要在线性链表中插入一个新因素,首先要给该因素分配一个新结点,以便用于存储该因素的值,然后将存放在新元素值的结点链接到线性表中指定的职位。在线性链表的插入过程中不爆发多少无素移动的现象,只需改变有关结点的指针即可,从而提高了插入的效能。为了在线性链表中删去包含指定元素的结点,首先要在线性链表中找到这一个结点,然后就要删除结点放回到可应用栈。在线性链表中去除一个因素后,不需要移动表的多寡元素,只需改变被删元素所在结点的前一个结点的指针域即可。因此,举行扦插与删除时,不需要活动表中的元素。

48、在先左后右的尺码下,按照访问根结点的次序,二叉树的遍历可以分为3种:前序遍历、中序遍历和后序遍历。

前序遍历是指在拜访根结点、遍历左子树与遍历右子树这三者中,首先访问根结点,然后遍历左子树,最终遍历右子树;并且遍历左、右子树时,仍旧先走访根结点,然后遍历左子树,最终遍历右子树。

后序遍历指在走访根结点、遍历左子树与遍历右子树这三者中,首先遍历左子树,然后遍历右子树,最终访问根结点;并且遍历左、右子树时,依然先遍历左子树,然后遍历右子树,最终访问根结点。

二叉树的中序遍历指在拜访根结点、遍历左子树与遍历右子树这三者中,首先遍历左子树,然后访问根结点,最终遍历右子树;并且遍历左、右子树时,如故先遍历左子树,然后访问根结点,最终遍历右子树。

49、链表无线性链表,也有非线性链表。线性链表和二叉树链表的结点都有五个指针域,前者是线性结构,后者是非线性结构。线性单链表中的结点唯有一个指南针,叶子结点一般是对树结构而言,树结构是非线性结构,不是线性表。

50、算法的复杂度首要概括时间复杂度和空中复杂度:算法在运作过程中需援救存储空间的轻重缓急称为算法的长空复杂度;算法的大运复杂度是指执行算法所急需的总括工作量,即算法执行过程中所需要的骨干运算次数,为了可以相比客观地凸显出一个算法的频率,在心胸一个算法的工作量时,不仅应当与所采纳的处理器、程序设计语言以及程序编制者无关,而且还应当与算法实现过程中的许多细节无关。为此,可以用算法在执行进程中所需为主运算的履行次数来度量算法的工作量。二者没有一向关联。

51、一个算法的空中复杂度,一般是指执行那个算法所需要的内存空间。一个算法所占据的仓储空间包括程序所占的长空、输入的起初数据所占的蕴藏空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。假使额外空间相对于问题规模来说是常数,则称该算法是原地(in
place)工作的。

52、我们通常用时间复杂度和空中复杂度来衡量算法功能,算法的流年复杂度是指执行算法所需要的精打细算工作量;算法所进行的主干运算次数与问题的层面有关,而一个算法的半空中复杂度,一般是指执行那么些算法所急需的内存空间;一般的话,一种多少的逻辑结构依据需要可以表示成多种囤积结构。

所谓算法的年月复杂度,是指执行算法所需要的计量工作量。为了可以相比客观地反映出一个算法的频率,在心胸一个算法的工作量时,不仅应当与所拔取的微机、程序设计语言以及程序编制者无关,而且还应当与算法实现过程中的许多细节无关。为此,可以用算法在实施进程中所需为主运算的执行次数来度量算法的工作量。

53、子程序调用是一种层次关系,子程序调用功用模块,调用效用模块的个数也不确定,能够是一个,也足以是三个。二叉树是一种很有用的非线性结构,二叉树不同于树形结构。二叉树具有以下多少个特性:①非空二叉树唯有一个根结点;②每一个结点最多有两棵子树,且分别名叫该结点的左子树与右子树。选项D规定每个结点只好有六个后件。在子程序调用中,调用的功能模块可以是六个,可以调用超过五个效率模块。

54、结构图的深浅表示控制的层数结构图的纵深表示控制的层数

55、数据结构是指反映数据元素之间关系的数目元素集合的象征。更通俗地说,数据结构是指包含结构的数额元素的聚合。所谓结构其实就是指数据元素之间的上下件关乎。线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构依旧属于非线性结构,还要遵照具体意况来规定。如若对该数据结构的演算是按线性结构的平整来拍卖的,则属于线性结构;否则属于非线性结构。

相关文章