精华内容
下载资源
问答
  • 数据结构名词解释

    2011-12-26 14:52:10
    很详细的描述了数据结构的各种名词。。。对期末数据结构复习很有利。。
  • 数据结构 名词解释

    2020-10-12 16:21:54
    **抽象数据类型:**一个数据模型以及定义在该模型上的一组操作。 **外部排序:**待排序的记录储存在外存储器上,待排序的文件无法一次装入内存,需要在内存与外部存储器之间进行多次数据交换,以达到排序整个文件的...

    **共享栈:**利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底费别设置在共享空间的两端,两个栈底向共享空间的中间延伸。
    **循环队列:**将顺序队列臆造为一个环状的空间,把存储队列的元素的表从逻辑上看成一个环的队列。
    **平衡因子:**节点的左子树和右子树的高度差。
    **抽象数据类型:**一个数据模型以及定义在该模型上的一组操作。
    **外部排序:**待排序的记录储存在外存储器上,待排序的文件无法一次装入内存,需要在内存与外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

    展开全文
  • 数据结构名词解释

    数据结构名词解释

     第三章 表、栈、队列
    抽象数据类型ADT——操作的集合
    诸如表、集合、图和它们的操作一起可以看作是ADT

     第四章 树

    1. 深度:根节点->当前节点的路径长
      高度:当前节点->一片树叶的最长路径
    2. 二叉树:每个节点的儿子树<=2 (表达式树)
      二叉查找树:对每个节点X,左子树<X<右子树
      AVL树:左右子树高度差<=1的二叉查找树
      伸展树
      B-树
    3. 先序遍历:先处理当前节点,再处理儿子节点
      后序遍历:先处理儿子节点,再处理当前节点
    4. 懒惰删除:对要删除的元素只做删除记号而不将其移除
    5. 内部路径长:一棵树内所有节点的深度和

     第五章 散列表

    1. 散列函数:从关键字到地址区间的一种映射
    2. 冲突:两个关键字散列到同一个值
    3. 装填因子λ:散列表中元素个数与散列表大小的比值,即散列表的平均长度
    4. 一次聚集:散列表中的元素占据的单元聚集形成一些区块,但同时表的其他部分相对较空
    5. 二次聚集:散列到同一位置上的元素将探测相同的备选单元

     第六章 优先队列(堆)

    1. 完全二叉树:除最底层外被全部填满的二叉树
      理想二叉树:完全填满的二叉树
    2. d-堆:每个节点都有d个儿子
    3. 零路径长Npl(X):从X到一个没有两个儿子节点的最短路径的长
      Npl(NULL)=-1;
      Npl(X)比其诸儿子零路径长的最小值多1;
    4. 左式堆:对任意节点,Npl(左儿子)>=Npl(右儿子)
      左式堆节点的三种可能性:
      (1) 有2个子节点
      (2) 没有子节点
      (3) 有1个左子节点
    5. 二项树:每个节点包含数据、第一个儿子及其右兄弟
    6. 二项队列(森林):堆序树(二项树)的集合

     第九章 图论

    1. 简单路径:所有顶点互异,但第一个顶点和最后一个顶点可能相同
    2. 连通:无向图中,任意两个顶点间都存在一条路径
      强连通:有向图中,任意两个顶点间都存在一条路径
      弱连通:有向图不是强连通的,但改为无向图后连通
    3. 完全图:任意两个顶点间都存在一条边
    4. 入度:进入该节点的边的数量
      出度:从该节点出发的边的数量
    5. 广度优先搜索BFS:按层处理顶点,据开始点最近的点先被赋值,最远的点最后被赋值
      深度优先搜索DFS:访问当前节点,并递归的遍历所有与当前节点相连的节点
    6. 关键路径:一条完全由零-松弛边组成的路径
    7. 流图Gf:表示在算法任意阶段已经达到的流,当算法终止时,Gf将包含最大流
      残余图Gr:表示对于每条边还能再添加上多少流
    8. 增长通路:从发点到收点的一条路径
    9. 最小生成树:连接图中所有顶点且总价值最低的树
    10. 双连通性:一个连通的无向图中任一顶点删除后,剩下的图仍然连通
    11. 割点:在一个连通但不是双连通的图中,删除后使图不再连通的顶点是割点
    12. 欧拉回路:对图的每条边恰好访问一次的路径
    13. 哈密尔顿圈:在无向图中,通过图的每一个顶点的圈

     第十章 算法设计

    1. 贪婪算法:不断选择局部最优,最终得到全局最优
      (例如:Dijkstra算法,Prim算法,Kruskal算法)
      应用:调度问题、文件压缩(Huffman编码)、近似装箱问题
    2. 非预占调度:一旦开始一个作业,就必须把该作业运行到完成
    3. 分治算法:递归解决较小的问题,再从子问题的解中构建原问题的解
      应用:最近点问题、选择问题、整数相乘、矩阵乘法
    4. 动态规划:利用非递归算法将子问题的答案系统的记录在一个表内
      应用:矩阵乘法的顺序安排(pqr次标量法)、最优二叉查找树、求所有点对最短路径
    5. 随机化算法
    6. 回溯算法
    展开全文
  • 数据结构名词解释归纳 精品文档 精品文档 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 数据结构名词解释归纳 第一章 数据结构是相互之间...
  • 华北电力大学计算机考研844 842 数据结构 名词解释整理
  • 重要数据结构名词解释 精品文档 精品文档 收集于网络如有侵权请联系管理员删除 收集于网络如有侵权请联系管理员删除 精品文档 收集于网络如有侵权请联系管理员删除 名词解释 数据结构? 数据结构是相互之间存在一种或...
  • 数据结构名词解释.doc

    2011-05-03 09:00:37
    数据结构名词解释.doc 1.数据结构是一门研究什么内容的学科? 数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 2.数据元素之间的关系在计算机中有...
  • 数据结构名词解释以及简答

    千次阅读 多人点赞 2020-05-20 23:28:52
    名词解释数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和数据组织的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作。 数据项:是数据不可分割的最小单位...

    名词解释:

    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和数据组织的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作。

    数据项:是数据不可分割的最小单位,用它可以识别一个或一个组数据,一个数据元素可由若干数据项组成。

    数据对象:是性质相同的数据元素的集合,是数据的一个子集。

    数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称,是计算机化的信息。

    数据类型:是一个值的集合以及定义在这个值集上的一组操作,可分为原子类型和结构类型。

    抽象数据类型:是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

    逻辑结构:是数据元素之间逻辑关系的描述。

    物理结构(存储结构):是指数据的逻辑结构在计算机中的映像(又称表示),即数据结构在计算机中的存储方法。

    算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。

    时间复杂度:算法执行所需时间的量度。

    空间复杂度:算法执行所需存储空间的量度。

    存储密度:指结点数据本身所占存储量和整个结构所占存储量之比。

    填空题:

    1. 程序设计的一些基本原则:分解、抽象和信息隐蔽。

    1. 根据数据元素之间关系的不同特性,有四类基本的数据结构:集合结构,线性结构,树形结构,图形结构(网状结构)。

    1. 数据的存储结构有:顺序存储结构、链式(链接)存储结构、索引结构、散列存储结构

    1. 常用的两种存储结构:顺序存储结构和链式存储结构。

    1. 算法的五个特性:确定性、有穷性、可行性、输入和输出。(可以有零个或多个数据输入,但必须至少有一个输出数据。

    1. 算法设计的要求:正确性、可读性、稳健性、高效率低存储量。

    沃斯公式:程序=算法+数据结构。

    (算法分析)衡量算法的两个标准:时间复杂度和空间复杂度。

    一个算法的设计取决于所选的逻辑结构。

    一个算法的实现取决于所选的存储结构。

    结构化程序设计思想的要求:自顶向下、逐步细化、模块化设计、结构化编程。

    简答题:

    顺序存储结构的特点?(顺序存储和链式存储的优缺点)

    1、结点中只存放数据元素本身的信息,无附加内容。(优点)

    2、可直接存储数据元素。(优点)

    3、存储操作速度较快。(优点)

    4、插入、删除数据元素时,由于需要保持数据元素之间的逻辑关系,必须大量移动元素,因此实现起来比较慢。(缺点)

    5、顺序存储是一种静态结构、存储密度大,空间利用率低,预分配空间大小难以确定,(缺点)

    链式存储结构的特点?(顺序存储和链式存储的优缺点)

    1、结点中除存放数据元素本身的信息外,还需存放附加的指针。

    2、不能直接存取数据元素,需顺链路查找,存取速度较慢。

    3、插入、删除元素时不必移动其他元素,速度较快。(优点)

    4、链式存储是一种动态存储结构,空间利用率高,存储密度小,不存在预分配空间问题。

    线性结构与非线性结构的特点(或差异)?

    线性结构的特点:是除第一个元素和最后一个元素外,每个数据元素都有唯一的前驱和唯一的后继,第一个元素没有前驱,最后一个元素没有后继,关系是一对一的。

    非线性结构的特点是:表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系。

    逻辑结构与物理结构的区别和联系?

    1、数据的物理结构也为存储结构。

    2、数据的逻辑结构仅考虑数据之间的逻辑关系。

    3、数据的物理结构是数据的逻辑结构在计算机中的映像。

    4、数据的逻辑结构独立于数据的存储介质。

    数据结构与数据类型的区别和联系?

    数据结构是相互之间存在一种或多种特定关系的数据元素的集合,是计算机存储和数据组织的方式,它分为三个方面,即数据的逻辑结构,数据的物理结构,数据的操作,它偏向于逻辑方面,而数据类型是一个值的集合以及定义在这个值上的一组操作,可分为原子类型和结构类型,它偏向于物理方面的线性表。

    名词解释:

    线性表:是最常用,最简单的一种数据结构,一个线性表是n个数据元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继。

    顺序表:采用顺序存储结构的线性表通常称为顺序表。

    链表:采用链式存储结构的线性表通常称为顺序表。

    结点:由数据元素和指示其后继结点地址的信息组成的存储映像称为结点。

    表长:表中元素的个数称为表的表长。

    循环链表:是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

    双链表:采用链式存储结构的线性表,每个结点除一个数据域外,还有两个指针域,其一指向直接前驱,另一指向直接后继。

    静态单链表:是利用一块连续的空间,按链表的存储方式组织数据,按顺序存储结构分配空间,所构成的一种链表。

    头指针:是指向链表表头结点的指针,只要链表存在,该指针始终不会改变,单链表由头指针唯一确定,因单链表可以用头指针的名字来命名。

    头结点:在链表的开始结点之前附加的一个结点,是链表的表头,当链表不空时,其内的指针指向链表的第一个结点,当链表是空链表时,该指针为空指针。

    填空题:

    线性表的两种基本的存储结构:顺序结构和链式存储结构。

    从实现角度看,链表可分为静态链表和动态链表。

    从链接方式的角度看,链表可以分为单链表,循环链表,双链表。

    添加哨兵可以保持首指针的稳定性,方便表示空表。

    一元多项式的表示和相加可以使用链表实现。

    简答题:

    顺序表的优缺点?

    优点:1、无需为表示结点间的逻辑关系而增加额外的存储空间,存储密度大

    2.可随机存取表中的任一元素,查找方便

    缺点:1.插入,删除运算不方便,须移动大量元素,效率较低

    2.存在预分配空间问题

    链表的优缺点?

    优点:1.插入,删除操作很方便

    2.空间利用率高

    缺点:1.查找不方便,需顺链查找

    2.存储密度小

    顺序表和链表的区别和联系及适用范围?

    顺序表:内存中地址连续

    长度一般不可变更

    支持随机查找,可在O(1)内查找元素

    适用于需要大量访问元素的,而少量増删元素的程序

    链表: 内存中地址连续或非连续都可以

    长度可实时变化

    不支持随机查找,查找元素的时间复杂度为O(n)

    适用于需要大量增删元素,而对访问元素几乎无要求的程序

    头指针和头结点的作用?

    1.头指针是指向链表表头结点的指针,只要链表存在,该指针就不会变化,已知该指针便己知该链表

    2.头结点是在链表的开始结点之前夫妇家的一个结点,当链表是空链表时,该指针为空指针,因此空表和非空表的处理也就统一了

    简述在单循环链表上尾指针取代头指针的作用?

    在用头指针表示的单循环链表中,找开始结点a1的时间是O(1),然而要找终端结点an则需要从头指针开始遍历整个链表,其时间是O(n),在很多实际问题中,表的操作常常是在表尾进行的,此时头指针表示的单循环链表就显得不够方便,如果改用尾指针来表示单循环链表,则查找开始结点a1和终端结点an都很方便查找时间都是O(1)

    名词解释:

    栈:也叫后进先出表,是限定仅在表尾进行插入和删除操作的线性表,表尾端称为栈顶,表头端称为栈底,不含元素的空表称为空栈

    顺序栈:采用顺序存储结构的栈称为顺序栈

    链栈:采用链式存储结构的栈称为链栈.

    队列:是一种先进先出的线性表,它只允许在表的一段进行插入,而另一端删除元素,允许插入的一端叫做队尾,允许删除的一端称为队首

    链队列:用链表示的队列,需要两个指针分别指示队头和队尾,为了操作方便,也给链队列添加一个哨兵结点

    循环队列:队列是"先进先出表”,随着入队出队的进行,会使整个队列整体向后移动,当队尾指针移到最后,若再有元素入队就会出现“假溢出”,因为此时队头部分还有空间可用,循环队列是将队列的数据区看成头尾相接的循环结构,可解决“假溢出”

    双端队列:是限定插入,删除在表的两端进行的线性表,这两端分别称为端点。

    填空题

    栈的两种存储方式:顺序存储和链式存储

    满的判断条件:s.top= stack.size

    栈空的判断条件:s.top=0

    栈满入栈栈上溢,栈空出栈栈下溢

    链栈使用多栈共享技术时,可使用静态链表结构实现

    队列的两种存储方式:顺序存储和链式存储

    循环队列采用少用一个元素存储空间的办法下,判断队列满的条件:

    front==(rear+1)%size

    循环队列判断队列满的方法有:少用一个元素存储空间,增设一个标志量,使用计数器

    队列的应用:杨辉三角

    栈的应用:数制转换,括号匹配,表达式求值,汉诺塔(递归用栈实现)

    简答题:

    什么是多栈共享技术?

    在一个程序中经常会同时使用多个栈,使用顺序存储结构的栈.空间大小难以估计,这样使得有的栈已出,有的栈还有空闲空间,可以让多个栈共享一个足够大的连续向量空间(数组),通过利用栈的动态特性来使其存储空间互相补充,这就是多栈的共享技术,两个栈共享空间,主要利用了“栈底位置不变,栈顶位置动态变化”的特性

    顺序队列相比,循环队列有哪些优点?

    可解决假溢出现象(内容自行拓展)

    简述线性表 ,队列的区别和联系?

    相同点:都是线性结构,都是逻辑结构的概念,都可以用顺序存储或链式存储,栈和队列是两种特殊的线性表,即受限的线性表,只对插入和删除运算加以限制

    不同点:1,运算规则不同,线性表为随机存取,而栈只允许在一端进行插入、,删除运算,因而是后进先出表,队列只允许在一端进行插入,另一端删除运算,因而是先进先出表

    2.用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理,指

    令寄存及其他运算等

    名词解释:

    :是由零个或多个字符組成的有限序列.

    子串:串中任意个连续的字符组成的子序列称作该串的子串

    主串:包含子串的串相应的称为主串

    子串在主串中的位置:子串的第一个字符在主串中的位置表示

    空串:长度为零的串称为空串

    空格串:串中元素均为空格的串称为空格串.

    串相等:长度相等且对应位置字符都相等

    填空题

    在程序中,串分为串常量串变量

    串的存储结构:顺序存储结构,链式存储结构,堆存存储结构

    串的应用:文本編辑

    简答题

    串和线性表的区别?

    串的逻辑结构与线性表极为相似,区别仅在于串的数据对象约束为字符集,然而串的操作与线性表有很大的差别,在线性表基本操作中,大多以单个元素作为操作对象;而在串的基木操作中通常以“串的整体”作为操作对象

    简述静态分配的顺序串与动态分配的顺序串的区别?

    程序运行前被分配以一个给定大小的数组空间的顺序串称为静态顺序串,在程序

    运行过程中,动态分配空间能以链表形式存在的顺序串称为动态顺序串,静态申在内存一片连续的数据区中,动态串在内存堆中.

    串的链式存储与串顺序存储相比,在哪些操作上效率更高?

    插入,删除,因为无需移动其他元素(内容自行扩充)

    名词解释:

    广义表:是由零个或多个单元素或子表所构成的有限序列,是线性表的推广,也有人称其为列表

    数组:类型一致的有限个数据元素按顺序连续存储

    矩阵的压缩存储:有的矩阵中有许多值相同元素或者是零元素,为了节省存储空间对这类矩阵采用多个值相同的元素只分配一个存储空间,有时零元素不存储的存储策略,称为矩阵的压缩存储

    特殊矩阵:值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵称为特殊

    矩阵

    稀疏矩阵:非零的数据元素个数很少的矩阵称为稀疏矩阵

    对称矩阵:一个n阶方阵,若满足aij=aji,则称该矩阵为对称矩阵

    三角矩阵:主对角线上方和下方的元素(不包括对角线)均为常数或零元素的矩阵

    行表:记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表

    三元组表:若线性表顺序存储的每一个结点均是三元组,则该线性表的存储结构称为三元组表

    带状矩阵:所有非零元素均集中在以主对角线为中心的带状区域的矩阵

    填空题

    数组的两种存储方式:顺序存储和链式存储.

    数组的顺序存储有两种方式:按行存储和按列存储.

    稀疏矩阵可以采用三元组表和十字链表来存储

    简答题

    广义表和线性表的区别?

    1广义表是线性表的推广,是由零个或多个单元素或子表所构成的有限序列

    2.线性表的成分都是结构上不可分制的单个数据元素,而广义表的成分既可以是单元素,也可以是有结构的表其定义是递归的定义

    名词解释:

    树:是n个结点的有限集合,n≥0,有且只有一个称为根的结点,根结点无前驱

    有序树:树中结点的各子树看成是从左至右依次有序的,且不能交换

    森林:m(m≥1)棵互不相交的树的集合

    二叉树:是一种树型的结构,它的特点是每个结点之多有两棵子树,且有左右之分,不可任意颠倒。

    完全二又树:深度为k的有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时

    满二叉树:是一棵深度为k的,且有(2^k)-1个结点的二又树

    遍历二叉树:是按照某种搜索路径巡访二叉树中的每个结点,使得这些结点均被访问一次

    线索二叉树:由每个结点中包含左指针,左标志位,数据域,右标志位,右指针五部分组成的二叉链表,叫做线索链表,指向前驱或后继的指针叫做线索,以二又树某种遍历顺序给空指针加线索的过程叫做线索化,线索化了的二叉树称为线索二叉树

    哈夫曼树:又称最优二叉树,是一类带权路径长度最短的树.

    哈夫曼编码:在哈夫曼树中,约定左分支代表0,右分支代表1,把叶子结点到根结点的路径上的左右分支代表的码从下至上一次连接起来,组成的字符串称为该叶子结点的哈夫曼编码,这就是哈夫曼编码

    二又排序树:或者是空树,或者是符合以下性质的二叉树

    1若它的左子树不空,则左子树上所有结点均小于它的根结点值

    2.若它的右子树不空则右子树上所有结点均大于它的根结点值.

    平衡二叉排序树(AVL树):或者是空树,或者是符合一下性质的二又排序树

    1.左子树和右子树的高度之差的绝对值小于等于1

    2左子树和右子树也是平衡二叉排序树

    填空题

    在二叉树中,第i层结点最多为2^k—1个

    深度为k的二又树中,结点总数最多为(2^k)—1个

    二叉树中,n0=n2+1,n2=n0-1(no为二又树中度为0的结点的个数n2为二叉树中度为2的结点的个数)

    有n个结点的完全二叉树,深度为k,则k=[log2n]+1(log以2为底括号是向下取整不是方括号)

    k层的完全二叉树至少有2^k-2个叶子结点

    二叉树的两种存储结构:顺序存储结构和链式存储结构

    树的三种常用的存储方法:孩子表示法,双亲表示法和孩子兄弟表示法

    树的遍历方法:先根遍历和后根遍历

    简答题

    非线性结构的特点?

    表示结点间关系的前驱后继不具有唯一性,结点间是一对多或多对多的关系

    二叉树的五种基本形态?

    只有三个结点的二叉树的五种形式?

    因为二又树是有序树,所有有左右之分,这是五棵不同的二叉树,但若下列五棵是树,不是二叉树,则后面四种为同一棵树

    名词解释:

    :图G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有穷非空集合,E是由V中顶点的序偶组成的有穷集,这些序偶称为边或弧

    顶点:图中的数据元素称为顶点

    完全图:边数恰好等于n(n-1)/2的n个顶点的无向图称为完全图(无向图中任意两个顶点之间都有一条边相连,称该图为完全图)

    有向完全图:有n(n-1)条边的有向图称为有向完全图(图中每个顶点和其余n-1个顶点都有弧相连)

    入度:以顶点V为头的弧的数目称为V的入度

    出度:以顶点V为尾的弧的数目称为V的出度

    连通图:在无向图中,任意两个顶点之间都有路径相通

    强连通图:在有向图中,任意两个顶点之间都有来回路径相通

    生成树:生成树是无向连通图的一个极小连通子图,它含有图中的全部顶点和使任意顶点都连通的最少的边

    邻接矩阵:表示图中结点之间关系的矩阵称为邻接矩阵

    邻接表:由顶点数据表和表示数据关系的边(弧)构成的表

    十字链表:可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存

    储形式

    图的遍历:从某一顶点出发按序访问图中所有结点,且使每个结点仅被访问一次

    最小生成树:无向网中边上权值之和为最小的生成树

    DAG有向无环网

    拓扑排序:由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序

    关键路径:在AOE网中,从源点到汇点的最长路径称为关键路径

    AOE网:用顶点表示事件,用弧表示活动,弧的权值表示活动所需的时间,构造的有向网称为AOE网

    简单路径:一条路径上除了开始顶点和结束顶点外,其余顶点均不相同

    弧头:边的终点称为弧头

    弧尾:边的始点称为弧尾

    填空题:

    边很少的图称为稀疏图,反之称为稠密图

    有向图中,所有顶点的入度与出度的和等于边个数的2倍

    图的存储方法:邻接矩阵,邻接表,邻接多重表,十字链表和边集数组

    图的深度优先搜索类似于树的先根遍历

    图的广度优先搜索类似于树的层次遍历

    连通图→深度优先搜索遍历→深度搜索生成树

    连通图→广度优先搜索遍历→广度搜索生成树

    简答题

    邻接矩阵表示法的特点?

    1.对于无向图而言,它的邻接矩阵是对称矩阵,因此可以采用特殊矩阵的压缩存储法,但对于有向图而言,其中的弧是有方向的,因此有向图的邻接矩阵不一定是对称矩阵,对于有向图的邻接矩阵的存储则需要n*n个存储空间.

    2.采用邻接矩阵表示法,便于判断图中任意两个顶点之间是否有边相连,即根据邻接矩阵中的信息来判断,另外还便于求得各个顶点的度,对于无向图而言,其邻接矩阵第i行元素之和就是图中第i个顶点的度

    邻接表表示法的特点?

    1.n个顶点,e条边的无向图,若采取邻接表作为存储结构,需要n个顶点数据和2e个表示边的结点,显然在边很稀疏的情况下,用邻接表存储所需的空间比邻接矩阵所需的空间少

    2.无向图的度,在无向图的邻接表中,顶点Vi的度恰好就是第i个边链表上结点的

    3.有向图的度,在有向图中,第i个边链表上结点的个数就是顶点Vi的出度,只需通过表头向量表中找到第i个顶点的边链表的头指针,实现顺链查找计数即可

    DFS(深度优先搜索遍历)的基本思路?

    假设初始状态是图中所有顶点均未被访问过,则深度优先搜索可从某个顶点V出发,首先访间此顶点(称此顶点为初始点),然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历,直到图中所有与有路径相通的顶点都被访问到,若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作为初始点,重复上述步骤,直到图中所有顶点都被访问过为止

    BFS(广度优先搜索遍历)的基本思路?

    1.从图中某个顶点VO出发,首先访问VO,依次访问Vo的各个未被访间的邻接点

    2.分别从这些邻接点(端结点)出发,依次访问各个未被访问的邻接点,访问时应保证:如果Vi和Vk为当前结点,且Vi在Vk之前被访问,则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问

    3.重复步骤2,直到所有结点均没有未被访问的邻接点

    4.若此时还有顶点未被访问,则选一个未被访问的顶点作为起始点,重复上述过程,直至所有顶点均被访问过为止

    名词解释

    关键字:是数据元素中某个数据项的值,用它可以识别一个或一组数据元素

    査找:根据给定的关键字的值,检索某个与该值相等的数据元素是否在查找表中

    找到为查找成功,找不到为查找失败

    査找表:是由同一类型的数据元素或记录构成的集合

    静态査找表:査询某个特定的数据元素是否在査找表中,检素某个特定的数据元素的各种属性

    动态査找表:在查找过程中同时插入查找不存在的数据元素,或者从査找表中删除已存在的某个数据元素

    平均査找长度(ASL:为确定数据元素在査找表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度.

    冲突:两个不同的关键字,其散列函数值相同,因而被映射到同一表位置的现象称为冲突

    填空题

    哈希函数的构造方法:直接定址法,数字分析法,平方取中法,折叠法,除留余数法和随机数法

    哈希函数处理冲突的方法:开放地址法,再哈希法,链地址法和建立一个公共溢出区。

    简答题:

    各查找方法的基本思想,平均査找长度?

    顺序查找的基本思路:对于给定的关键字k,从线性表的第一个元素开始依次向后与记录的关鍵字域相比较,如果某个记录的关键字等于k,则查找成功,否则查找失败,平均查找长度ASL=3(n+1)/4.

    折半(二分)查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行此较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之,则在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败,平均查找长度 ASL=log2(n+1)-1

    分块查找(索引顺序表查找)的基本思路:先确定待査记录所在的块(子表)然后在块中顺序查找.平均查找长度ASL=1/2(n/s)+1]+s/2

    哈希查找(散列查找)的基本思路:在进行查找时,在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字k为自变量通过函数h(k)计算出该元素的存储位置,我们将h函数称为散列函数或哈希函数,这种査找方法称为散列查找或哈希查找

    名词解释:

    排序:就是按关键字值的递增或递减的次序,把文件中的各记录一次排列起来,可使一个无序文件变成有序文件的一种操作

    排序算法的稳定性:相同元素排序前后的相对位置没有发生变化,则为稳定,反之为不稳定

    内部排序:在排序过程中,所有待排序记录都放在内存中进行的排序称为内部排

    外部排序:当待排序的记录很多,排序时不仅要使用内存,而且还要使用外部存储器的排序方法称为外部排序

    简答题:

    各排序方法的基本思想,时间复杂度,空间复杂度及稳定性?

    直接插入排序的基本思想:直接插入排序是一种最简单的排序方法,基本操作是将条记录插入到已排好的有序表中,从而得到一个新的,记录数量増一的有序表

    时间复杂度O(n^2).空间复杂度O(1)直接插入排序是稳定的

    希尔排序的基本思想:先将整个待排元素序列分割成若干子序列分别进行直接插

    入排序,然后依次缩减增量再进行排序,使整个序列中的元素基本有序时,再对全体元素进行一次直接插入排序,实质就是分组直接插入排序时间复杂度O(n^2)

    空间复杂度O(1)肴尔排序是不稳定的

    冒泡排序的基本思想:先将第一个记录的关键字和第二个记录的关键字进行比较

    若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字,以此类推,直至第n-1个记录和第n个记录的关键字进行过比较为止.时间复杂度o(n^2).空间复杂度O(1)冒泡排序是稳定的

    快速排序的基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中

    部分的所有数据都比另一部分的所有数据都要小然后再按此方法对这两部分数

    据进行快速排序整个排序过程可以递归进行,以达到整个序列有序.时间复杂度

    O(nlog2n)空间复杂度O(nlog2n)快速排序是不稳定的

    直接选择排序的基本思想:对于给定的一组记录,经过第一轮比较后得到最小的

    记录,然后将该记录与第一个记录的位置交换,接着对不包括第一个记录以外的其他记录进行第二轮比较,得到最小的记录并与第二个记录的位置交换,重复该过程,直到进行比较的记录只有一个时为止.时间复杂度O(n^2).空间复杂度O(1).直接选择排序是不稳定的

    堆排序的基本思想:堆排序是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种,可以利用数组的特点快速定位索引的元素,堆分为大根堆和小根堆,是完全二叉树.时间复杂度o(nlog2n).空间复杂度O(1)堆排序是不稳定的

    归并排序的基本思想:将待排序序列看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序表再次归并,得到n/4个长度为4的有序序列;如此重复进行下去,最后得到一个长度为n的有序序列.时间复杂度O(nlog2n).空间复杂度O(n)归并排序是稳定的

    基数排序的基本思想:是借助"分配"和"收集"两种操作对单逻辑关键字进行排序的一种内排序方法.时间复杂度o(d*n).空间复杂度O(n+r).基数排序是稳定的

    展开全文
  • Data Structure 2015 hash table散列表存放记录的数组 topological sort拓扑排序将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序44 worst case 最差情况从一个n元一维数组中找...
  • 数据结构:相互之间存在一种或多种特定关系的数据元素的集合。 是研究数据元素(DataElement)之间抽象化的相互关系和这种关系在计算机中的存储表示(即数据的逻辑结构和物理结构),并对这种结构定义相适应的...
  • 1.数据 数据是描述客观事物的符号,是能够被计算机输入,识别,处理的各种符号,是计算机化的信息 2.数据数据不可分割的最小单位,一个元素由若干个数据项构成 3.数据元素 它是组成数据的基本单位,是数据集合中的个体,...
  • 多练出技巧 巧思出硕果 Data Structure 2015 hash table散列表存放记录的数组 topological sort拓扑排序将一个 DAG 中所有顶点在不违反前置依赖 条件规定的基础上排成线性序列的过程称为拓扑排序 44 worst case 最差...
  • 1、数据数据是外部信息的载体,他能够被计算机识别、存储和加工处理,是计算机程序加工的原料; 2、数据元素:数据元素是数据的基本单位,在计算机中通常被作为一个整体进行考虑和处理; 3、一个数据元素可由若干...

    顺序存储结构的特点是 :用元素在存储器中的相对位置来表示 数据元素之间的逻辑关系

    链接存储结构的特点是:用指示元素存储地址的指针表示 数据元素之间的逻辑关系

    1、数据:数据是外部信息的载体,他能够被计算机识别、存储和加工处理,是计算机程序加工的原料;

    数据(信息的载体):能输入到计算机中并被计算机处理的符号的总称。

    2、数据元素:数据元素是数据的基本单位,在计算机中通常被作为一个整体进行考虑和处理;

    3、一个数据元素可由若干个数据项组成。数据项是不可分割的、含有独立意义的最小数据单位,数据项有时也称为字段或域;

    什么是数据

    数据时事实或观察的结果,是对客观事物的逻辑归纳,是用于表示客观事物的未经过加工的原始素材
    1、**数据时信息的表示形式和载体,**可以是符号、文字、数字、语音、图像、视频等。数据和信息是不可分离,**数据时信息的表达,信息是数据的内涵。**数据本身没有意义,数据只有对实体行为产生影响时才成为信息。
    2、数据可以是连续的的值。比如声音、图像、称为模拟数据。也可以是离散的,如符号、文字、称为数字数据

    在计算机系统中,数据以二进制单元0,1的形式表示
    在计算机系统中,各种字母、数字符号的组合、语音、图形、图像等统称为数据,数据经过加工后就成为信息。

    计算机中采用二进制主要原因 :

    1)技术实现简单,计算机是由逻辑电路组成,逻辑电路通常只有两个状态,开关的接通与断开,这两种状态正好可以用"1"和 "0"表示。
    2)**简化运算规则:**两个二进制数和、积运算组合各有三种,运算规则简单,有利于简化计算机内部结构,提高运算速度
    3)适合逻辑运算:逻辑代数式逻辑运算的理论依据,二进制只有两个数码,正好与逻辑代数中的“真”和“假”相吻合
    4)易于进行转换,二进制与十进制易于互相转换

    4、算法: 是指在有限的时间范围之内为解决某一问题而采取的方法和步骤的准确完整的描述,他是一个有穷的规则序列,这些规则决定了解决某一特定问题的一系列运算;

    算法指的是对特定问题求解步骤的一种描述,是指令的有限序列。

    5、数据对象:是性质相同的数据的集合,是数据的子集。比如人都有姓名,年龄这些性质相同的数据元素。

    数据对象:是性质相同的数据元素的集合,是数据的一个子集。

    6、数据结构:不同的数据对象之前的关系并不是独立的,而是存在特定的关系,我们把这种特定的关系成为数据结构。

    数据结构:指相互之间存在一种或多种特定关系的数据元素的集合。

    7、逻辑结构:是指数据结构中,数据对象之间的相互关系,一共有4种,分别是集合结构,线性结构,树形结构,图形结构。他们分别代表的意义是:无关系,一对一关系,一对多关系,多对多关系。

    8、物理结构:是指数据的逻辑结构在计算机中的存储形式,一共有两种,一种是顺序存储结构,是指把数据元素存储在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的,还有一种是链式存储结构,是指把数据元素存储在任意的数据单元里,这些数据单元可以是连续的也可以是不连续的。

    9、数据类型:是指一些性质相同的值的集合及定义在此集合上的一些操作的总称。

    10、抽象数据类型:是指一个数学模型及定义在此模型上的一组操作。

    11、串:
    线性表的一种特殊形式,表中每个元素的类型为字符型,是一个有限的字符序列。

    12、堆:

    堆是具有下列性质的完全二叉树:每个结点的值都小于或等于其左右孩子结点的值(称为小根堆);或者每个结点的值都大于或等于其左右孩子结点的值(称为大根堆)。

    13、堆排序:

    首先将待排序的记录序列构造成一个堆(假设利用大根堆),此时,选出了堆中所有记录的最大者即堆顶记录,然后将它从堆中移走(通常将堆顶记录和堆中最后一个记录交换),并将剩余的记录再调整成堆,这样又找出了次大的记录,以此类推,直到堆中只有一个记录为止。

    14、队列:

    将线性表的插入和删除操作分别限制在表的两端进行,和栈相反,队列是一种先进先出的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。

    15、线性表:

    线性表是由n(n≥0)个相同类型的元素组成的有序集合。

    16、栈:

    线性表的一种特殊形式,是一种限定性数据结构,也就是在对线性表的操作加以限制后,形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。

    17、结构:数据元素相互之间的关系

    18、数据元素的两种不同的存储结构:顺序存储和链式存储。

    19、数据项:是对数据元素属性的描述,也称为字段或域。一个元素由若干个数据项组成,是数据不可分割的最小单位。

    20、数据元素

    它是组成数据的基本单位 , 是数据集合中的个体 , 在计算机程序中 , 通常作为一个整体进行考虑和处理

    21、数据项
    数据不可分割的最小单位 , 一个元素由若干个数据项构成。

    22、 数据处理
    是指对数据进行查找 , 插入 , 删除, 合并 , 排序, 统计以及简单计算等的操作过程。

    23、 数据对象
    是性质相同的数据元素的集合 , 是数据的一个子集。

    24、数据处理
    是指对数据进行查找 , 插入 , 删除, 合并 , 排序, 统计以及简单计算等的操作过
    程。

    25、 数据类型
    数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

    26、抽象数据类型
    是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义取决
    于它的一组逻辑特性 , 而与其在计算机内部如何表示和实现无关。

    27、算法
    解决一个问题的方法和步骤。

    28、时间复杂度
    T(N)=O(F(N)), 它表示随问题规模N增大 , 算法执行时间增长率与 F(N)的增长
    率相同 ,F(N) 算法的时间复杂性。

    29、原地工作
    算法执行时 , 若额外空间相对于输入数据量来说是常数 , 则称此算法为原地工
    作。

    30、 队列
    是一种受限线性表 , 是先进先出的线性表

    31、循环队列
    在队列的顺序存储结构中 , 把存储空间的首尾逻辑上相连 , 构成一个环 , 使得存储空间上只要有空余的地址 , 就可以继续进行入队列操作 , 极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾 , 插入在尾部进行 , 删除在头部进行。

    32、单链表
    每一个数据元素 , 都需用两部分来存储: 一部分用于存放数据元素值 , 称为数据域;另一部分用于存放直接后继结点的地址 ( 指针), 称为指针域 , 元素的存储空间可以连续 , 也可以是不连续的。 而数据元素之间的逻辑关系由指针域来确定。

    33、双向链表
    线性表采用链式存储时 , 每个结点除一个数据域外 , 包含两个指针域 , 一个指向该结点的直接后继 , 一个指向该结点的直接前驱 , 这种方式构成的链表 , 即为双向链表。

    34、希尔排序
    是插入排序的一种 , 又叫缩小增量排序 , 先按增量进行分组 , 组内插入排序 , 然后每次缩短增量 , 再进行分组和组内插入排序 , 直到增量为 1 时, 进行最后一次排序止。

    35、完全图
    任何一个有 N 个结点的无向图 , 若其边数为 N(N-1)/2, 则这个无向图就是完全

    36、有向完全图
    任何一个有 N 个结点的有向图 , 若其弧个数为 N(N-1) 个, 则这个有向图就是有
    向完全图。

    37、广度遍历
    按层次编历方式 , 从某一点 V0 开始遍历它的所有邻接点 V1,V2⋯⋯, 再依次访
    问 V1,V2… 的所有未被访问过的邻接点 , 直到所有的点均遍历完成

    38、关键字
    数据元素的某个数据项的值 , 用它可以标识列表的一个或一组元素。

    39、 子串
    串中任意个连续的字符组成的子序列称作该串的子串。

    40、栈
    是一种受限线性表 , 是插入和删除操作在同一端进行的 , 是后进先出的线性表。

    41、树
    树是 n(n>=0) 个结点的有限集。在任意一棵非空树中:
    (1) 有且仅有一个特殊的称为根的结点 ;
    (2) 当 n>1时, 其余结点可分成 m(m>0) 个互不相交的有限集 T1,T2,…,Tm, 其中每一个集合本身又是一棵树 , 并且称为根的子树。

    42、二叉树
    二叉树是每个结点至多有两个孩子结点的一种树。 其中两个孩子结点分别被称
    为左孩子结点和右孩子结点。

    43、子孙
    子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。

    44、孩子结点与双亲结点
    树中某个结点的子树的根结点称为该结点的孩子结点。相反 , 称该结点为孩子
    结点的双亲结点。

    45、结点的度
    树的某个结点的分支 ( 子树) 个数叫做该结点的度。

    46、树的度
    树的度是树中所有结点的最大度数。

    47、平衡因子
    结点的左子树深度与右子树深度之差。

    48、 生成树
    一个连通图的生成树是指一个极小连通子图 , 它含有图中的全部顶点 ,N-1 条
    边。

    49、满二叉树
    深度为 K,且有 2K -1 个结点的二叉树

    50、物理结构 (存储结构 )
    物理结构又称为数据的存储结构 , 是指数据的逻辑结构在计算机中的映像 (表
    示), 即数据结构在计算机中的存储方法。

    51、线索
    在二叉树中 , 利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继 ,
    这种指向前驱和后继的指针 , 叫线索。

    52、线索二叉树
    对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。 线索化了的二叉
    树称为线索二叉树。

    53、广义表
    广义表简称表 , 是零个或多个原子表所组成的有限序

    54、强连通分量
    有向图的极大强连通子图 , 称为有向图的强连通分量。

    55、结点的带权路径长度
    该结点到树根之间的路径长度与结点上权的乘积。

    56、 插入排序
    在一个已排好序的记录子集的基础上 , 每一步将下一个待排序的记录有序地插
    入到已排好序记录的子集上 , 直到将所有待排记录全部插入为止。

    57、祖先
    一个结点的祖先是指从根结点到该结点的路径上的所有结点。

    58、数据结构
    数据结构是数据元素的集合以及定义在该集合上的关系。

    59、模式匹配
    子串的定位操作称作串的模式匹配。

    60、单循环链表
    是单链表的另一种形式 , 它是一个首尾相接的链表 , 表中最后一个结点的指针
    域由 null 改为指向头结点或线性表的第一个结点 , 整个链表形成了一个环.

    61、线索
    在二叉树的存储结构中 , 必有N+1个空域 , 利用这些空域存放某种遍历的前
    驱和后继 , 其中指向前驱和后继的指针叫线索.

    62、 图
    图是顶点与边的集合。一般表示为一个二元组 , 即, 图 G=(V,E), 各个顶点之间
    是多对多的关系。

    63、 折半查找
    对于顺序存储的有序表 , 先取中间位置的记录关键字与所给的关键字进行比较 ,若相等 , 则查找成功 , 否则, 若给定的关键字比中间的关键字大 , 在原表的后半部分比较 , 反之, 在原表的前半部分比较 , 如此反复 , 逐步缩小范围 , 直到找到为止, 或找不到 , 最后查找范围为空.

    64、最小生成树
    在图 G的所有生成树中 , 树权值最小的那棵生成树 , 称作最小生成树.

    65、完全二叉树
    对满二叉树的结点从上到下 , 从左到右进行依次进行编号 , 若有一棵二叉树的每一个结点都与深度为 K 的满二叉树中编号都一一对应时 , 只是最后一层不满,称做完全二叉树 .

    66、前缀编码
    任何一个字符的编码都不是另一个字符编码的前缀 , 这种编码叫做前缀编码

    67、 广义表
    是零个或多个原子表所构成的有序序列 .

    68、线索二叉树
    利用二叉树的一些空闲指针指向该结点的前驱或后继 , 这种指针叫线索 , 线索后了的二叉树 , 称为线索二叉树 .

    69、树的高度
    树中所有结点的层次的最大值 .

    70、堂兄弟
    同一层上不同双亲的结点 , 互称堂兄弟 .

    71、 叶子结点
    度为 0 的结点 , 即没有后继的结点 .

    72、森林
    M 棵互相不相交的树构成的集合 , 将一棵非空树的根结点删除 , 树就变成了森林.

    73、 树的路径长度
    树中每个结点到根结点的路径长度之和

    74、树的带权路径长度 (WPL)
    树中所有叶子结点的带权路径长度之和 .

    75、哈夫曼树
    设有 N个权值的结点构造一棵有 N个叶子结点的二叉树 , 其中 WPL最小的那棵树, 为哈夫曼树 .

    76、哈夫曼编码
    一般以 N 种字符出现的频率做权值 , 构造哈付曼树 , 左孩子边做 0, 右孩子边做1, 那么从根到叶子结点经过的 0 和 1 序列, 构成了哈夫曼编码 .

    77、图中顶点的度
    顶点 V的度是图中和顶点 V相关联的边的数目。包括入度和出度两种。

    78、子图
    图 G=(V,E)与图 G1=(V1,E1), 若 V1包含于 V,且 E1包含于 E,则 G1是 G的子图。

    79、连通图
    对于无向图 , 若 V1到 V2有路径 , 称 V1V2是连通的 , 若图中任意两点都是连通的 ,则称该无向图是连通图。

    80、网
    图的弧或边有与它相关的有意义的数 , 称作权 , 带有权值的图称作网。

    81、简单回路
    除了第一个顶点和最后一个顶点之外 , 其余顶点均不相同的回路称为简单回路。

    82、 简单路径
    在用一个顶点序列表示一条路径时 , 若序列中没有相同的顶点重复出现 , 则称其为简单路径。

    83、查找
    根据给定的关键字值 , 在特定的表中 , 确定一个其关键字与给定值相同的数据
    元素, 并返回该数据元素在列表中的位置。这个过程叫查找。

    84、平均查找长度 (ASL)
    为确定数据元素在表中的位置 , 需和给定值进行比较的关键字个数的数学期望值, 成为查找算法在查找成功的平均查找长度。

    85、 二叉排序树
    它或是一棵空树 , 或是有下面性质的树: 若左或右子树不空 , 左子树所有结点值小于根结点 , 而右子树所有结点值大于根结点的值 , 其左右子树也是二叉排序树。

    86、 顺序查找
    对于给定的关键字 K,从线性表的第一个 (或最后一个 ) 元素开始 , 依次向后 (或前)与元素的关键字比较 , 若某个记录的关键字与 K 相等, 查找成功 , 否则失败。

    87、平衡二叉树
    或是一棵空树 , 或左右子树高度差的绝对值小于等于 1 而且, 左右子树也是平衡二叉树。

    88、插入排序
    在一个已排好序的基础上 , 每一步将下一个待排序记录插到已排好记录的子集
    上, 使之重新有序 , 直到所有待排记录插完为止。

    89、分块查找 (索引查找 )
    分块查找以前两个为基础 , 将待查记录分成若干块 , 每块的关键字无序 , 但每块的关键字的最大值有序 , 查找时 , 先查找到待查记录所在的块 , 再在块内进行顺序查找。找块时 , 即可以用折半查找 , 也可用顺序查找。

    90、拓扑排序
    由某个集合上的偏序集得到该集合上的一个全序 , 这个操作叫做拓扑排序。

    91、shell 排序
    它是插入排序的一种 , 又叫缩小增量排序 , 先按增量进行分组 , 组内插入排序 ,然后每次缩短增量 , 再进行分组和组内插入排序 , 直到增量为 1 时, 进行最后一次排序止。

    92、内部排序

    指的是待排序记录存放在计算机存储器中进行的排序过程;

    93、外部排序

    指的是待排序记录的数量很大 , 以致内存一次不能容纳全部记录 , 在排序过程中对外存进行访问的排序过程。

    94、气泡排序法
    气泡排序的过程很简单。从第一记录开始 , 相邻的两个记录关键字进行比较 ,若顺序不对 , 立即交换 , 直至 N-1 个与第 N个比较为止。 得到一个最大 ( 或最小 )的关键字记录的结果位置。

    95、选择排序
    选择排序是每一趟在 n-i+1(i= 1,2,3 ⋯n-1) 个记录中选择关键字最小的记录作为有序序列中第 i 个记录。其中最简单的是简单选择排序

    96、快速排序
    快速排序的基本思想是把当前待排序的记录 , 存放到整个表排好序后 , 它应当在的最终位置上。将原来的待排序表分割成两部分 , 其中一部分表中的关键字均比另一部分表中的关键字小。 然后, 分别对两部分表用同样的方式进行排序 ,直到整个表排好序。

    97、堆排序

    首先将根结点的记录与当前树中具有最大序号的记录交换 , 把交换后具有最大序号的记录输出 , 得到一个排序的结果。这时的树不再是堆树 , 排序暂时停止。然后, 必须把树重新调整成堆树 , 再重复上述过程 , 直到所有记录都排好序。

    98、 强连通图
    对于一个有向图 , 每两个顶点之间都有路径 , 称该图为强连通图。

    99、 连通分量
    对于一个无向图 , 其极大连通子图叫做该图一个连通分量。

    100、原子类型 :其值不可在分的数据类型

    101、数据的存储结构 :指数据结构在计算机中的表示, 也成物理结构。主要有顺序存储、 连接存储、索引存储、散列存储。

    102、数据的逻辑结构 :指数据元素之间的逻辑关系。包括集合、线性结构、树形结构、图状结构或网状结构。

    103、算法 :对特定问题求解步骤的一种描述, 是指令的有限序列, 其中每一条指令表示一个或多个操作。有 5 个重要特性(有穷性、确定性、可行性、输入、输出)

    104、算法设计的要求 :正确性、可读性、健壮性、效率与低存储量需求。

    105、数据的存储结构 :指数据结构在计算机中的表示, 也成物理结构。主要有顺序存储、 连接存储、索引存储、散列存储。

    106、线性表 :具有相同数据类型的 n(n>=0)个数据元素的有限序列。

    107、线性表的顺序存储又称 顺序表 ;链式存储又称 单链表

    108、静态链表 :借助数组来描述线性表的链式存储结构, 结点也有数据域和指针域。 但指针是结点的相对地址(数组下标) 。需要预先分配连续的内存空间。

    109、静态链表 :借助数组来描述线性表的链式存储结构, 结点也有数据域和指针域。 但指针是结点的相对地址(数组下标) 。需要预先分配连续的内存空间。

    110、树的高度或深度 :树中结点的最大层数。

    111、有序树和无序树 :树中结点的子树从左到右是有次序的,不能交换,叫做有序树。反之为无序树。

    112、路径和路径长度 :树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。

    113、路径长度是路径上经过的边的个数。

    114、树的路径长度 :树根到每一个结点的路径长度之和

    115、树的带权路径长度( WPL):树中所有叶子结点的带权路径长度之和。

    116、满二叉树 :一棵高度为 h,并且含有 2^h -1 个结点的二叉树称为满二叉树。即每层都有最多的结点,叶子集中在二叉树的最下一层且除叶子之外的每个结点度为 2.

    117、平衡二叉树 :树上任一结点的左子树和右子树的深度之差不超过 1.

    118、平衡因子 :该结点的左子树深度减去它的右子树深度。

    119、二叉树的遍历 :指按某条搜索路径访问树中的每个结点, 使得每个结点均被访问一次且仅被访问一次。

    120、判定树 :树中每个结点表示表中的一个记录, 结点里的值为该记录在表中的位置, 通常称这个查找过程的二叉树为判定树。

    121、树的先根遍历 :若树非空, 则先访问根结点, 再按从左到右的顺序遍历根节点的每一颗子树。

    122、图的遍历 :从图中某一顶点出发, 按照某种搜索方法沿着图中的边对图中所有顶点访问一次且仅访问一次。

    123、查找表 (查找结构) :用于查找的数据集合称为查找表。

    124、查找 :在数据集合中寻找满足某种条件的数据元素的过程称为查找。

    125、静态查找表 :如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中和检索满足条件的某个特定的数据元素的各种属性,则称为静态查找表。

    126、动态查找表 :需要动态的插入或删除的查找表称为动态查找表。

    127、关键字 :数据元素中唯一标识该元素的某个数据项的值, 使用基于关键字的查找, 查找结果应该是唯一的。

    128、平均查找长度( ASL):在查找的过程中,一次查找的长度指需要比较的关键字次数, 而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

    129、折半查找 :仅适用于有序的顺序表。 将给定的值 key 与表中间位置元素的关键字比较, 相等则查找成功返回位置。 若不等则缩小查找范围, 重复查找直到找到或者确定表中没有需查找的元素。

    130、散列函数 :一个把查找表中的关键字映射成该关键字对应的地址的函数,

    131、冲突 :散列函数可能会把两个或以上的不同关键字映射到同一地址,这种情况为冲突

    132、开放定址法 :指的是可存放新表项的空闲地址既向它的同义词表项开放, 又向它的非同义词表项开放。

    133、拉链法(链地址法) :把所有的同义词存储在一个线性链表中,这个线性链表由其散列地址唯一标识。

    134、二次聚集 :指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。

    135、插入排序 :每次将一个待排序的记录, 按关键字大小插入到前面已经排好序的子序列中, 直至全部记录插入完成。

    136、希尔排序 :又称缩小增量排序, 先将整个记录序列分割成若干子序列分别进行直接插入排序,待整个序列中记录基本有序时,再对全体进行一次直接插入排序。

    137、冒泡排序: 从前往后(或从后往前)两两比较相邻元素的值,若为逆序则交换,知道序列比较完, 既完成一趟冒泡排序。 这一趟确定的最小元素不再参与比较, 重复上述过程直到一趟排序没有记录交换。

    138、基数排序 :采用多关键字排序思想,借助“分配 /收集”两种操作对但逻辑关键字进行排序。

    139、查找表: 由同一类型的数据元素(或纪录)构成的集合。

    140、关键字: 数据元素中某一数据项的值,用以表示一个数据元素。

    141、 基数排序

    基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种
    内排序方法。

    142、原地工作

    算法执行时 , 若额外空间相对于输入数据量来说是常数 , 则称此算法为原地工
    作。

    143、希尔排序

    是插入排序的一种 , 又叫缩小增量排序 , 先按增量进行分组 , 组内插入排序 , 然后每次缩短增量 , 再进行分组和组内插入排序 , 直到增量为 1 时, 进行最后一次排序止。

    144、线索

    在二叉树中 , 利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继 ,这种指向前驱和后继的指针 , 叫线索。

    145、强连通分量
    有向图的极大强连通子图 , 称为有向图的强连通分量。

    146、结点的带权路径长度
    该结点到树根之间的路径长度与结点上权的乘积。

    147、祖先
    一个结点的祖先是指从根结点到该结点的路径上的所有结点。

    148、模式匹配
    子串的定位操作称作串的模式匹配。

    149、连通分量

    对于一个无向图 , 其极大连通子图叫做该图一个连通分量。

    150、强连通图
    对于一个有向图 , 每两个顶点之间都有路径 , 称该图为强连通图。

    151、气泡排序法

    气泡排序的过程很简单。从第一记录开始 , 相邻的两个记录关键字进行比较 ,若顺序不对 , 立即交换 , 直至 N-1 个与第 N个比较为止。 得到一个最大 ( 或最小 )的关键字记录的结果位置。

    152、80. 内部排序

    指的是待排序记录存放在计算机存储器中进行的排序过程;
    81. 外部排序
    指的是待排序记录的数量很大 , 以致内存一次不能容纳全部记录 , 在排序过程
    中对外存进行访问的排序过程。

    153、 《数据结构》中的英语名词

    data 数据
    data element 数据元素
    data item 数据项
    data object 数据对象
    data structure 数据结构
    ADT (Abstruct Date Type) 抽象数据类型
    alogrithm 算法
    correctness 正确性
    readability 可读性
    robustness 健壮性
    frequency count 频度
    asymptotic time complexity 渐进时间复杂度
    space complexity 空间复杂度
    storage density 存储密度
    storage structure 存储结构
    linear list 线性表
    node 结点
    record 记录
    file 文件
    circular linked list 循环链表
    double linked list 双向链表
    stack 栈
    bottom 栈底
    top 栈顶
    LIFO (Last In First Out) 后进先出
    FILO (First In Last Out) 先进后出
    operand 操作数
    operator 运算符
    delimiter 界限符
    queue 队列
    front 队头
    rear 队尾
    circular Queue 循环队列
    string 串
    null string 空串
    blank string 空格串
    lists 广义表
    head 表头
    tail 表尾
    array 数组
    Divide and Conquer 分治法
    tree 树
    Sub Tree 子树
    root 树根
    degree 度
    leaf 叶子结点
    branch 分支结点
    parent 双亲结点
    child 孩子结点
    sibling 兄弟结点
    path 路径
    path length 路径长度
    level 层数
    depth 深度
    ancestor 祖先
    descendant 子孙
    forest 森林
    Preorder 先序遍历
    Inorder 中序遍历
    Postorder 后序遍历
    threaded binary tree 线索化二叉树
    Huffman tree 哈夫曼树
    weight 权
    graph 图
    vertex 顶点
    undirecte edge 无向边
    direct edge 有向边
    undirect graph 无向图
    direct graph 有向图
    undirect complete graph 无向完全图
    direct complete graph 有向完全图
    network 网
    subgraph 子图
    adjacent 邻接点
    incident 依附
    connected graph 连通图
    connected component 连通分量
    adjacency matrix 邻接矩阵
    adjacency list 邻接表
    orthogonal list 十字链表
    adjacency multilist 邻接多重表
    firstarc 链域
    vertex 顶点域
    nextarc 数据域
    info 数据域
    traversing graph 图的遍历
    DFS (depth first search) 深度优先搜素
    BFS (breadth firsi search) 广度优先搜索
    MST (Minimum cost Spanning Tree) 最小代价生成树
    Direct Acycline Graph 有向无环图
    project 工程
    activity 活动
    AOV (Activity On Vertex) AOV网
    topological sort 拓扑排序
    topological order 拓扑序列
    AOE (Activity On Edge network) AOE网
    critical path 关键路径
    critical activity 关键活动
    sourse 源点
    destination 终点
    search table 查找表
    static search table 静态查找表
    dynamic search table 动态查找表
    keyword 关键字
    primary keyword 主关键字
    secondary keyword 次关键字
    binary saerch 折半查找
    blocking search 分块查找
    open addressing 开放定址
    ASL (Average Search Length) 平均查找长度
    binary sort tree 二叉排序树
    balanced binary tree 平衡二叉树
    BF (Balance Factor) 平衡因子
    load factor 装填因子
    Digital Search Tree 数字查找树/键树
    Hash table 哈希表
    Hashing 哈希法
    sorting 排序
    internal sorting 内部排序
    external sorting 外部排序
    straight insertion sort 直接插入排序
    Shell sort 希尔排序
    bubble sort 冒泡排序
    quick sort 快速排序
    merge sort 归并排序
    simple selection sort 简单选择排序
    heap sort 堆排序
    merging sort 归并排序
    radix sort 基数排序
    pointer 指针
    backtracking 回溯

    参考链接 :

    https://blog.csdn.net/u014469254/article/details/49467713?utm_medium=distribute.pc_relevant.none-task-blog-searchFromBaidu-6.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-searchFromBaidu-6.channel_param

    https://blog.csdn.net/durendong/article/details/7727542?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-3.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-3.channel_param

    展开全文
  • 数据结构概念名词解释大全
  • 精品文档 栅格数据与矢量数据 栅格数据结构 基于栅格模型的数据结构简称栅格数据结构是指将空间分割成有规则的网格称为栅格单 元在各个栅格单元上给出出相应的属性值来表示地理实体的一种数据组织形式 栅格数据结构...
  • 自己从书上整理的 妈妈再也不用担心我的考试了
  • 数据结构----名词解释

    2018-10-17 00:20:12
    数据结构----名词解释
  • 初学者简单总结的名词解释
  • 数据 答案: 对客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据结构 答案: 指的是数据之间的相互关系即数据的组织形式 数据元素 答案: 是数据的基本单位在计算机程序...
  • 数据结构名词术语解释 数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的科学 数据结构:是指相互之间存在着一种或多种关系的 数据元素的集合和该集合中数据元素之间的...
  • 一些简单的数据结构名词解释

    千次阅读 2015-10-28 13:44:01
    线性表的一种特殊形式,是一种限定性数据结构,也就是在对线性表的操作加以限制后,形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何...
  • 一、概念数据结构就像是一个催化剂,如果没有原料是无用的,单是有了算法就能帮算法更快的实现任务...二、名词解释数据是一个最广泛的概念,数据中可以有多个数据对象,数据对象中可以有多个数据元素,数据元素中可...
  • 考研题型里有一个题型叫做名词解释,这道题或多或少的咋试卷中占着一定的分量,但是分数又不是太多,用大量的大块时间来搞这个有点不太值当,所以抽些时间做个总结文档,用于空闲时间查看。 本文中概念不全,仅总结...
  • 基础名词解释 数据:程序的操作对象,用于描述客观事物,有以下两个特点 可以输入到计算机 可以被计算机处理 数据元素:组成数据对象的基本单元 数据项:一个数据元素由若干数据项组成 数据对象:性质...
  • (一)数据结构的起源,常见的名词解释,数据元素之间的关系 何为数据结构? 待处理的数据以及数据之间的关系 数据元素之间一种或多种特定关系的集合 数据结构的起源 一开始计算机是计算数值用的,...
  • 华中科技大学887考研名词解释,数据结构名词解释,,,
  • 辅助数据结构 Bellman-Ford算法 Floyd算法 SPFA算法 最小生成树 问题定义 Prim算法 Kruscal算法 拓扑排序 问题定义 算法 二分图的最大匹配 问题定义 匈牙利算法 最大流 问题定义 增广算法 压入重标,KM算法 ...
  • 绪论 数据:数据是信息的载体,信息是数据的内涵。...数据结构:相互之间存在一种或多种特定关系的数据元素的集合。数据结构=数据元素+数据关系。 数据结构三要素:逻辑结构、物理结构、数据运算。
  • 简答题很有帮助的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 745
精华内容 298
关键字:

数据结构名词解释

数据结构 订阅