数据结构名词解释.doc

1、数据数据就是描述客观事物得符号,就是能够被计算机输入，识别，处理得各种符号，就是计算机化得信息。2、数据项数据不可分割得最小单位，一个元素由若干个数据项构成.3、数据元素它就是组成数据得基本单位,就是数据集合中得个体，在计算机程序中，通常作为一个整体进行考虑与处理。4、数据对象就是性质相同得数据元素得集合，就是数据得一个子集。、数据处理就是指对数据进行查找,插入，删除，合并，排序，统计以及简单计算等得操作过程。、数据结构就是研究数据元素之间抽象化得相互关系与这种关系在计算机中得存储表示（即数据得逻辑结构与物理结构），并对这种结构定义相适应得运算,设计出相应得算法,且确保经过这些运算后所得到得新结构仍然就是原来得结构类型。7、数据类型数据类型就是一个值得集合与定义在这个值集上得一组操作得总称。8、抽象数据类型就是指一个数学模型以及定义在该模型上得一组操作。抽象数据类型得定义取决于它得一组逻辑特性，而与其在计算机内部如何表示与实现无关.、算法解决一个问题得方法与步骤.1、时间复杂度T（N）=O(F（N），它表示随问题规模增大,算法执行时间增长率与(N)得增长率相同，F(N）算法得时间复杂性。11、原地工作算法执行时，若额外空间相对于输入数据量来说就是常数，则称此算法为原地工作.2、线性表一种数据结构,就是N(N=0)个同质元素得有限序列，除首尾元素外，每个元素有唯一得前驱与唯一得后继.13、队列就是一种受限线性表,就是先进先出得线性表14、循环队列在队列得顺序存储结构中，把存储空间得首尾逻辑上相连，构成一个环，使得存储空间上只要有空余得地址，就可以继续进行入队列操作，极大利用了物理空间.用头部与尾部两个指示器表示队列头与队列尾，插入在尾部进行，删除在头部进行。15、单链表每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点得地址（指针)，称为指针域，元素得存储空间可以连续，也可以就是不连续得。而数据元素之间得逻辑关系由指针域来确定。1、双向链表线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点得直接后继，一个指向该结点得直接前驱,这种方式构成得链表，即为双向链表。7、希尔排序就是插入排序得一种,又叫缩小增量排序,先按增量进行分组，组内插入排序，然后每次缩短增量,再进行分组与组内插入排序，直到增量为1时,进行最后一次排序止。18、完全图任何一个有N个结点得无向图，若其边数为N（N1）/2，则这个无向图就就是完全图19、有向完全图任何一个有N个结点得有向图,若其弧个数为N(N-1)个，则这个有向图就就是有向完全图。0、广度遍历按层次编历方式,从某一点V开始遍历它得所有邻接点V1,V2，再依次访问V1，V2、得所有未被访问过得邻接点，直到所有得点均遍历完成21、关键字数据元素得某个数据项得值，用它可以标识列表得一个或一组元素.22、串串就是字符线性得有限集合.23、子串串中任意个连续得字符组成得子序列称作该串得子串。24、栈就是一种受限线性表，就是插入与删除操作在同一端进行得，就是后进先出得线性表。25、树树就是n(n0)个结点得有限集。在任意一棵非空树中：（1)有且仅有一个特殊得称为根得结点； （2）当1时，其余结点可分成m(m0）个互不相交得有限集T1，T2,、，m,其中每一个集合本身又就是一棵树,并且称为根得子树。26、二叉树二叉树就是每个结点至多有两个孩子结点得一种树。其中两个孩子结点分别被称为左孩子结点与右孩子结点。2、子孙子孙结点以某结点为根得子树中得任一结点都称为该结点得子孙。8、孩子结点与双亲结点树中某个结点得子树得根结点称为该结点得孩子结点。相反，称该结点为孩子结点得双亲结点.9、结点得度树得某个结点得分支(子树)个数叫做该结点得度。30、树得度树得度就是树中所有结点得最大度数。3、平衡因子结点得左子树深度与右子树深度之差。、生成树一个连通图得生成树就是指一个极小连通子图,它含有图中得全部顶点，N1条边。33、满二叉树深度为K，且有2K -1个结点得二叉树34、物理结构（存储结构）物理结构又称为数据得存储结构,就是指数据得逻辑结构在计算机中得映像（表示），即数据结构在计算机中得存储方法.5、线索在二叉树中,利用空余得指针指向二叉树某种遍历方式得结点得前驱与后继，这种指向前驱与后继得指针,叫线索。6、线索二叉树对二叉树以某种次序进行遍历并加上线索得过程叫做线索化。线索化了得二叉树称为线索二叉树。7、广义表广义表简称表,就是零个或多个原子表所组成得有限序列.3、强连通分量有向图得极大强连通子图，称为有向图得强连通分量。39、结点得带权路径长度该结点到树根之间得路径长度与结点上权得乘积。40、插入排序在一个已排好序得记录子集得基础上，每一步将下一个待排序得记录有序地插入到已排好序记录得子集上,直到将所有待排记录全部插入为止。41、祖先一个结点得祖先就是指从根结点到该结点得路径上得所有结点。42、数据结构数据结构就是数据元素得集合以及定义在该集合上得关系。3、模式匹配子串得定位操作称作串得模式匹配.4、单循环链表就是单链表得另一种形式，它就是一个首尾相接得链表,表中最后一个结点得指针域由nul改为指向头结点或线性表得第一个结点,整个链表形成了一个环45、线索在二叉树得存储结构中，必有N+个空域，利用这些空域存放某种遍历得前驱与后继,其中指向前驱与后继得指针叫线索.6、图图就是顶点与边得集合。一般表示为一个二元组，即,图=(V，），各个顶点之间就是多对多得关系.47、折半查找对于顺序存储得有序表，先取中间位置得记录关键字与所给得关键字进行比较,若相等，则查找成功，否则,若给定得关键字比中间得关键字大，在原表得后半部分比较,反之，在原表得前半部分比较，如此反复，逐步缩小范围，直到找到为止，或找不到，最后查找范围为空.48、最小生成树在图G得所有生成树中，树权值最小得那棵生成树,称作最小生成树9、广度优先搜索（）首先访问出发点v，接着依次访问得所有邻接点w1,w2，,然后再依次访问与wl，w2，,w邻接得所有未曾访问过得顶点.依此类推,直至图中所有与源点有路径相通得顶点都已访问到为止。此时从v开始得搜索过程结束.(若G就是连通图，则遍历完成;否则，在图C中另选一个尚未访问得顶点作为新源点继续上述得搜索过程，直至中所有顶点均已被访问为止.）50、完全二叉树对满二叉树得结点从上到下，从左到右进行依次进行编号,若有一棵二叉树得每一个结点都与深度为K得满二叉树中编号都一一对应时,只就是最后一层不满，称做完全二叉树、51、前缀编码任何一个字符得编码都不就是另一个字符编码得前缀,这种编码叫做前缀编码、2、广义表就是零个或多个原子表所构成得有序序列、5、线索二叉树利用二叉树得一些空闲指针指向该结点得前驱或后继，这种指针叫线索,线索后了得二叉树,称为线索二叉树、树得高度树中所有结点得层次得最大值、5、堂兄弟同一层上不同双亲得结点，互称堂兄弟、56、叶子结点度为 0得结点，即没有后继得结点、57、森林棵互相不相交得树构成得集合，将一棵非空树得根结点删除,树就变成了森林、58、树得路径长度树中每个结点到根结点得路径长度之与、59、树得带权路径长度(WPL)树中所有叶子结点得带权路径长度之与、60、哈夫曼树设有N个权值得结点构造一棵有N个叶子结点得二叉树，其中WPL最小得那棵树，为哈夫曼树、61、哈夫曼编码一般以N种字符出现得频率做权值,构造哈付曼树，左孩子边做0，右孩子边做，那么从根到叶子结点经过得与序列,构成了哈夫曼编码、6、图中顶点得度顶点V得度就是图中与顶点相关联得边得数目。包括入度与出度两种.63、子图图G=(,）与图G1=（V，1），若1包含于,且1包含于E，则G1就是G得子图。64、连通图对于无向图,若到V有路径，称12就是连通得，若图中任意两点都就是连通得,则称该无向图就是连通图.6、网图得弧或边有与它相关得有意义得数，称作权，带有权值得图称作网。6、深度优先搜索（FS）类似树得先序遍历，在图中任选一个顶点作为出发顶点0,访问V0后,依次从0得没被访问过得邻接点出发进行深度优先搜索.直到与V0所连通得所有顶点均被访问。如果,此时图中还有顶点尚未访问，则从剩余得顶点中再任选一个顶点作为出发顶点，重复上述过程，直到图中全部顶点均被访问为止。67、简单回路除了第一个顶点与最后一个顶点之外，其余顶点均不相同得回路称为简单回路。6、简单路径在用一个顶点序列表示一条路径时，若序列中没有相同得顶点重复出现，则称其为简单路径。9、查找根据给定得关键字值,在特定得表中,确定一个其关键字与给定值相同得数据元素,并返回该数据元素在列表中得位置。这个过程叫查找。、平均查找长度（ASL）为确定数据元素在表中得位置，需与给定值进行比较得关键字个数得数学期望值，成为查找算法在查找成功得平均查找长度。71、二叉排序树它或就是一棵空树，或就是有下面性质得树:若左或右子树不空,左子树所有结点值小于根结点,而右子树所有结点值大于根结点得值,其左右子树也就是二叉排序树。2、顺序查找对于给定得关键字K,从线性表得第一个（或最后一个）元素开始，依次向后(或前)与元素得关键字比较，若某个记录得关键字与K 相等,查找成功，否则失败。73、平衡二叉树或就是一棵空树，或左右子树高度差得绝对值小于等于而且，左右子树也就是平衡二叉树。74、插入排序在一个已排好序得基础上,每一步将下一个待排序记录插到已排好记录得子集上,使之重新有序，直到所有待排记录插完为止。7、分块查找（索引查找）分块查找以前两个为基础,将待查记录分成若干块，每块得关键字无序，但每块得关键字得最大值有序，查找时，先查找到待查记录所在得块，再在块内进行顺序查找.找块时，即可以用折半查找,也可用顺序查找.76、拓扑排序由某个集合上得偏序集得到该集合上得一个全序，这个操作叫做拓扑排序。77、归并排序将两个或两个以上得有序表合并成一个新得有序表,开始将每个元素当成就是一个个单独得有序表,逐渐表个数以原来一半得速度递减,每个表得长度却就是原来长度得倍增加，不断重复,直到最后就是一个表,而表得长度就是元素个数为止。8、排序根据关键字得递减或递增得次序，把文件中得各个记录依次排列起来，可使一个无序得数据元素序列变成一个有序得序列得操作。79、sll排序它就是插入排序得一种，又叫缩小增量排序，先按增量进行分组，组内插入排序,然后每次缩短增量，再进行分组与组内插入排序， 直到增量为1时,进行最后一次排序止。80、内部排序指得就是待排序记录存放在计算机存储器中进行得排序过程;81、外部排序指得就是待排序记录得数量很大,以致内存一次不能容纳全部记录,在排序过程中对外存进行访问得排序过程。82、不稳定排序假设iK(i，1jn，），且在排序前得序列中领先于Rj（即i)。若在排序后得序列中Rj领先于R ,则称所用得排序方法就是不稳定得。3、稳定排序假设KKj(in,1jn,i),且在排序前得序列中Ri领先于R(即ij）.若在排序后得序列中i仍领先于R，则称所用得排序方法就是稳定得、直接插入排序第1遍,将初始文件中得记录R瞧作有序子文件，将R2插入这个子文件中。若2得关键字小于得关键字,则2插在R得前面，否则R插在R1得后面。第2遍，将R3插入前面得两个记录得有序子文件中，得到3个记录得有序子文件。依此类推，继续进行下去，直到将Rn插入到前面得n-1个记录得有序子文件中，最后得到个记录得有序文件。 8、气泡排序法气泡排序得过程很简单。从第一记录开始，相邻得两个记录关键字进行比较，若顺序不对,立即交换,直至1个与第N个比较为止。得到一个最大(或最小）得关键字记录得结果位置.86、选择排序选择排序就是每一趟在-+1(=，2,3-1）个记录中选择关键字最小得记录作为有序序列中第i个记录。其中最简单得就是简单选择排序87、快速排序快速排序得基本思想就是把当前待排序得记录,存放到整个表排好序后,它应当在得最终位置上.将原来得待排序表分割成两部分，其中一部分表中得关键字均比另一部分表中得关键字小。然后，分别对两部分表用同样得方式进行排序，直到整个表排好序.88、堆排序首先将根结点得记录与当前树中具有最大序号得记录交换，把交换后具有最大序号得记录输出，得到一个排序得结果。这时得树不再就是堆树，排序暂时停止。然后,必须把树重新调整成堆树,再重复上述过程,直到所有记录都排好序。89、归并排序归并排序就是把两个或两个以上得有序表合并成一个新得有序表。把含有N 个记录得无序表当成N 个有序得子表，每个子表得得长度为1,然后,利用两两归并,得到n/个长度为2或1得有序子表。再两两归并直到得到长度为N 得一个有序表。90、强连通图对于一个有向图,每两个顶点之间都有路径，称该图为强连通图.91、连通分量对于一个无向图,其极大连通子图叫做该图一个连通分量。2、基数排序基数排序就是借助“分配与“收集两种操作对单逻辑关键字进行排序得一种内排序方法.