数据结构概念名词解释大全

数据元素：是数据的基本单位，也称节点(node)或记录(record)。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据项：有独立含义的数据最小单位，也称域(field)。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。逻辑结构：抽象反映数据元素之间的逻辑关系。(算法设计)物理结构(存储结构):数据结构在计算机中的表示。(算法实现)顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。算法：对特定问题求解步骤的一种描述。算法的五个重要特性：有穷性，确定性，可行性，输入和输出。算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。衡量算法效率的方法：事后统计法和事前分析估算法。算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目；空串：零个字符的串；子串：;串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。性质1:在二叉树的第i层上至多有2-1个结点。(i≥1)性质2:深度为k的二叉树上至多含2*-1个结点。(k≥1)性质3:对任何一棵二叉树，若它含有n₀个叶子结点、n₂个度为2的结点，性质4:具有n个结点的完全二叉树的深度为[log₂n」+1。满二叉树：指的是深度为k且含有2*-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。路径长度：路径上分支的数目。树的路径长度：树根到每个结点的路径长度之和。带权路径长度最小的二叉树，称为最优树二叉树或赫夫曼树。边、弧：P(vi,vi)表示顶点vi和顶点vj之间的直接连线，在无向图中称为边，在有向图中称为弧。任意两个顶点构成的偶对(vi,vj)∈E是无序的，该连线称为边。是有序的，该连线称为弧。弧头、弧尾：带箭头的一端称为弧头，不带箭头的一端称为弧尾。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历图的路径：深度优先搜索和广度优先搜索。外部排序：排序过程中需对外存进行访问的排序插入排序：直接插入排序、折半插入排序、希尔排序选择排序：简单选择排序、堆排序ADT:抽象数据型是一个数学模型和在该模型上定义的操作的集合线性表：线性表是由n(n≥0)个相同类型的元素组成的有序集合。栈：线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。队列：将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是串：线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的广义表：由零个原子，或若干个原子或若干个广义表组成的有穷序列。树：1、一个结点x组成的集{x}是一株树(Tree),这个结点x也是这株树的根。一株新树：令x为根，并有k条边由x指向树T1,T2,…,Tk。这些边也叫做满二叉树：深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n的结点一一对线索二叉树：若结点p有左孩子，则p->lchild指向其左孩子结点，否则令其指向其(中序)前驱。若结点p有右孩子，则p->rchild指向其右孩子结点，否则令其指向其(中序)后继。和右儿子结点(如果有的话)的元素，则称此完全二叉树为最大堆。结点和右儿子结点(如果有的话)的元素，则称此完全二叉树为最小堆。仍表示成(v,w)。开放树。将生成树中所有边长之总和称为生成树的价(cost成树称为图G的最小生成树。无向图双连通分量：设Vi是Ei中各边所连接的点集(1≤i≤k),每双连通图：若对V中每个不同的三元组v,w,a;在v和w之间都存在一条不包含a的路，就说G是双连通的强连通性：设G=(V,E)是一个有向图，称顶点v,w∈V是等价的，要么v=w;要么从顶点v到w有一条有向路，并且从顶点w到v也有一条有向路。拓扑排序：给定一个无环路有向图G=(V,E),各结点的编号为v=(1,2,…,n)。要求对每一个结点i重新进行编号，使得若i是j的前导，则有Label[i]<label[j]。即拓扑分类是将无环路有向图排当从结点i到结点j存在一条边，则在线性序列中，将i排在j的前面。AOE网：在带权的有向图中，用结点表示事件，用动的开销(如持续时间),则称此有向图为边表示活动的网络，简称AOE网。关键路径：在AOE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为查找表：由同一类型的数据元素(或纪录)构成的集合。关键字：数据元素中某一数据项的值，用以表示一个数据元素。其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过1。B-树：B-树是一种非二叉的查找树除了要满足查找树的特性，还要满足以下结(1)树的根或者是一片叶子(一个节点的树),或者其儿子数在2和m之间。(2)除根外，所有的非叶子结点的孩子数在m/2和m之间。(3)所有的叶子结点都在相同的深度。1、有k个子结点的结点必然有k个关键码；地址散列法：被查找元素的存储地址=Hash(Key)。(1)若2*i≤n,则(2)若2*i+1≤n,则A[i].key≤A[2*i+1].key;小顶堆(1)若2*i≤n,则A[i].key≥A[2*i].keyA[2*i+1].key;大顶堆词典排序：设集合S中的元素为整数元组，关系≤为S的线性序，对两个元在(sl,s2,…,sp))≤(t1,t2,…,tq),当存在一个整数j≤max[p,q],使得sj≤tj,且所有1≤i<j,si=ti;或者p≤q,并且si=ti,1≤i≤p,则关系≤称为词典序。并段),然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序二、重要算法总结第三章：1、二叉树的先、中、后序遍历(递归算法)2、二叉树的中序非递归遍历(辅助栈、非辅助栈)5、Dijkstra算法单源最短路径第五章：1、二叉排序树第六章：简单排序算法及快排1.数据结构是一门研究什么内容的学科?数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。2.数据元素之间的关系在计算机中有几种表示方法?各有什么特点?四种表示方法(1)顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。(2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。(3)索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。(4)散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围(对具体机器都应有整数范围),其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型(ADT)”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类对用户透明(提供接口),而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”,而是向“科学”迈进了一步。4.对于一个数据结构，一般包括哪三个方面：逻辑结构、存储结构、操作(运算)。5.根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构?集合、线性如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为0(1)。(2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?选顺序存储结构。顺序表可以随机存取，时间复杂度为0(1)。7.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1);其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。8.栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。9.队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除),故队列也常称先进先出(FIFO)表。10.什么是循环队列?用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除),容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存B、C、D、E,运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E?为什么?能得到说明在D之前的入栈元素是A、B和C,三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。12.串?串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。13.描述以下概念的区别：空格串与空串。空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的储，设第一个元素的首地址是78,每个元素的长度为4,试求元素A[4,2,3]的存储首地址。958三维的存储单元数。15.数组A中，每个元素A[ij]的长度均为32个二进位，行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中，主存储器字长为16位。求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7,4]的起始地址是多少?(4)数组按列存放时，元素A[4,7]的起始地址是多少?答：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。(1)242(2)22(3)16.从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么,并指出树和二叉树的主要区别。树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树一是二叉树的度至多为2,树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空(个别书上允许为空)。17.请分析线性表、树、广义表的主除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲(根无双亲),从这个意义上说存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。18.一棵二叉树中的结点的度或为0或为2,则二叉树的枝数为2(n0-1),其中nO是度为0的结点的个数。证明：设二叉树度为0和2的结点数及总的结点数分别为n0,n2和n,则n=nO+n2…(1)再设二叉树的分支数为B,除根结点外，每个结点都有一个分支所指，则n=B+1………(2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此(2)式可写为n=2*n2+1…………(3)由(1)、(3)得n2=n0-1,代入(1),并由(1)和(2)得B=2*(nO-1)。证毕。19.(1).如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边?(2).如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边?(3).如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边?答：(1)G1最多n(n-1)2条边，最少n-1条边(2)G2最多n(n-1)条边，最少n条边(3)G3最多n(n-1)条边，最少n-1条边(注：弱连通有向图指把有向图看作无向图时，仍是连通的)20.n个顶点的无向连通图最少有多少条边?n个顶点的有向连通图最少有多少条边?n-1,n21.内部排序(名词解释)假设含n个记录的序列为{R1,R2……Rn},其相应的关键字序列为{K1,K2……Kn},这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ksn,按此固有关系将n个记录序列重新排列为{Rs1,Rs2……Rsn}。若整个排序过程都在内存中22.在各种排序方法中，哪些是稳定的?哪些是不稳定的?并为每一种不稳定的排序方法举出一0(n2)0(n2)O(1)稳定折半插入排序0(n2)0(n2)O(1)稳定二路插入排序O (n2)O(n2)0(n)稳定表插入排序0(n2)0(n2)O(1)稳定起泡排