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

    千次阅读 多人点赞 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).基数排序是稳定的

    展开全文
  • 初学者简单总结的名词解释

    第一章:绪论

    1. 数据与数据结构

      • 数据:信息的载体。
      • 数据元素:数据中的一个“个体”,是数据的基本组织单位。
      • 数据项:
        • 简单数据项(例如:姓名,年龄)
        • 组合数据项(例如:出生年月日,包含年,月,日三个简单数据项)
      • 数据对象:属性相同的数据元素的集合。
      • 数据结构:相互之间存在一种或多种特定关系的数据元素的集合。
    2. 逻辑结构

      • 开始结点:第一个数据元素。
      • 终端结点:最后一个数据元素。
      • 前驱:与当前数据相邻的前面一个元素。
      • 后继:与当前数据元素相邻的后一个元素。
      • 集合:集合众数据元素之间除了“同属一个集合”之后数据元素之间无其他关系,他们之间的关系称为是松散的。
      • 线性结构:有且仅有一个开始结点和终端结点,数据元素之间存在“一对一”的关系,开始结点没有前驱,但只有一个后继,终端结点没有后继,但只有一个前驱,其余结点只有一个前驱,一个后继。
      • 树形结构:数据元素之间存在“一对多”的关系,有一个称为根节点,此结点无前驱结点,其余结点有且仅有一个前驱,所有节点都可以有多个后继。
      • 图形结构:数据元素之间存在“多对多”的关系,任何结点都可以有多个前驱和后继。
    3. 存储结构

      • 顺序存储:将所有数据元素存放在一片连续的存储空间中,并使逻辑上相邻的数据元素在对应的物理位置也相邻。
      • 链式存储:不要求将逻辑上相邻的数据元素存储在物理上相邻的位置,即数据元素可以存储在任意的物理位置上,每个数据元素包含两部分,一部分用来存放数据元素值本身,另一部分用来存放表示逻辑关系的指针。
      • 索引存储:在存储数据元素的同时,还增设了一个索引表,索引表中的每一项包含关键字和地址,关键字是能唯一标识一个数据元素的数据项,地址是指示数据元素的存储地址或存储区域的首地址。
      • 散列存储(哈希存储):将数据元素存储在一片连续的区域内,每一个数据元素的具体存储地址是根据该数据元素的关键字值,通过哈希函数直接计算出来的。
    4. 算法与算法分析

      • 算法的性质:
        1. 有穷性:一个算法都必须在执行有限步骤后结束;
        2. 确定性:一方面指每一条指令都有确切的含义,另一方面指算法输出结果确定;
        3. 有效性:算法中每一条语句都可以被计算机正确执行;
        4. 输入:一个算法具有零个或多个输入;
        5. 输出:一个算法必须有零个或多个输出。这些输出是与输入有着某种特定关系的量,是经过处理后的信息;
      • 设计算法应该考虑的目标:
        1. 正确性:满足具体问题的功能和性能要求;
        2. 可读性:便于阅读,以便后续对算法的理解和修改;
        3. 健壮性:具有检查错误和对某些错误进行适当处理的功能;
        4. 高效率:效率高低是通过算法运行所需资源的多少来反映的,这里的资源包括时间和空间需求;
    5. 算法的描述

      • 自然语言:俗称人话。。。通俗易懂,但是不严谨;
      • 程序设计语言:可以直接运行,但是不直观;
      • 伪代码:介于自然语言和程序设计语言之间,忽略语法要求,容易理解;
    6. 算法分析

      • 时间复杂度:尝试通过计算出依据算法编制的程序中每条语句频度之和的值来估算一个算法的执行时间。语句频度是语句重复执行的次数;
      • 空间复杂度:包括算法本身的代码,常量等占用的资源(固定空间需求)和临时工作单元和递归运算时的资源占用(可变空间需求);
      • 注意:算法编写时if else 的大括号以防万一,不要省略。递归中尽量不要递归的产生变量或对象或是数组什么的;

    第二章:线性表

    1. 方法

      • void clear:置空
      • boolean isEmpty:判断是否为空
      • int length:求线性表长度
      • Object get(int i):返回下标为i的对象
      • int get(Object x):返回对象值为 x 的下标
      • void insert(int i,Object x):在第i个数据元素之前插入一个值为x的对象
      • Object remove(int i):删除下标为i的元素,并且返回该元素对象
      • display():顺序输出所有元素
    2. 顺序表相关概念

      • 存储密度 = 数据元素本身之所需的存储空间 / 该数据元素实际所占用的空间
      • 循环链表:也称环形链表,将单链表的首尾相连,构成一个环形结构。再这个链表中,每一个元素都有后继;
      • 双向链表:在单链表中不仅包含指向后继的指针,还包含指向前驱的指针。
    3. 特点

      • 顺序表:因为本质是数组,因此便于随机存取,但不利于插删操作,不容易扩充,只能被动的改变空间大小,访问第i个元素的时间复杂度是O(1)
      • 链表:本质是对.next 的指向来确定链,在空间上较为灵活,便于插删,但不利于查找,访问第i个元素的时间复杂度为O(n)

    第三章:栈与队列

    1. 相关概念

      • 栈:类似于一个大坑,先扔进去的东西要后取出来。有顺序栈(以顺序表为本质的栈)和链栈(以链表为核心的栈)
      • 队列:相当于食堂排队买饭,先排队的先买饭。有顺序队列和链队列;
      • 循环队列:在循环链表的基础上建立循环队列
    2. 方法

      • void clear:置空
      • boolean isEmpty:判断是否为空
      • int length:返回长度
      • (栈)Object peek:读取栈顶元素
      • (栈)void push(Object x):将对象x入栈(压倒栈顶)
      • (栈)Object pop:删除并返回栈顶元素,如果栈为空,返回null
      • (队列)Object peek:读取队列首元素
      • (队列)void offer(Object x):将数据元素x加入队列
      • (队列)Object poll:删除队列中的首元素并且返回该对象,若队列为空,返回null
    3. 算法

      • 栈:大数问题,后缀表达式,汉诺塔
      • 队列:素数环,优先队列
    4. 栈与队列的比较

      • 都是线性结构,“一对一”的对应关系
      • 插入操作都限制在表尾进行
      • 都可使用顺序存储和链式存储实现
      • 在增加和方法的时间复杂度上都是常数阶

    第四章:串与数组

    1. 相关概念

      • 串:字符串,本质是字符数组
      • 串相等:两个串的长度与对应位置上的字符相同
      • 主串:模式匹配中等待匹配的通常比较长的字符串
      • 模式串:模式匹配中主动匹配的通常比较短的字符串
    2. 方法

      • void clear:置空
      • boolean isEmpty:判断是否为空
      • int length:返回长度
      • char charAt(int index):读取并返回串中的第index个字符
      • String substring(int begin,int end):返回 [begin,end)的子串
      • String insert(int offset,String str):在当前串的第offset个字符前插入str,并且返回一个新的字符串
      • String delete(int begin,int end):删除当前串中[begin,end)的字符串,并且返回新字符串
      • String concat(str):连接两个新的字符串
      • int compareTo(str):将当前串与str比较,若当前串大于str,返回大于0的值,若相等,返回0,若小于,返回小于0的值
    3. 串的模式匹配

      • Brute-Force 模式匹配算法:模式串与主串一个字符一个字符的匹配,不成功,就从主串的下一个字符开始让子串从头开始匹配
      • KMP 模式匹配算法:匹配失败后,不直接从主串的下一个字符开始,而是扫描子串,跳过已经匹配过的正确的串,从主串与子串不匹配的地方开始。
    4. 数组

      • 数组是n(n>=1)个具有相同类型的数据元素构成的有序序列
      • 行优先顺序:在将多维数组存在一维数组中时以行序为主序列的存储方式
      • 列优先顺序:在将多维数组存在一维数组中时以列序为主序列的存储方式
    5. 矩阵的压缩存储

      • 目的:节省存储空间
      • 三角矩阵的压缩存储
      • 稀疏矩阵的压缩存储:
        1. 三元组表存储
        2. 十字链表存储

    第五章:树与二叉树

    1. 相关概念

      • 树的结点:由一个数据元素及关联其子树
      • 结点的路径:从根节点到该节点所经历的结点和分支的顺序排列
      • 路径的长度:结点路径中所包含的分支数
      • 结点的度:指该节点拥有的子树的数目
      • 树的度:树中所有结点的度的最大值
      • 叶结点(终端结点):树中度为0的结点,也称终端结点
      • 分支结点(非终端结点):树中度不为0的结点,也称非终端结点
      • 孩子结点(子结点):一个结点的孩子结点指这个结点的子树的根结点
      • 双亲结点(父结点):若树中某个结点有孩子结点,那么这个结点就称为孩子结点的双亲结点
      • 子孙结点:一个节点的子孙结点是指这个结点的所有子树中的任意结点
      • 祖先结点:指该结点的路径中除此结点之外的所有结点
      • 兄弟结点:指具有同一双亲的结点
      • 结点的层次:若规定根结点的层次为0,那么其他结点的层次是其双亲结点的层次数加1;
      • 树的深度:指数中所有结点的层次数的最大值加1
      • 有序树:指树中各结点的所有子树之间从左到右有严格的次序关系,不能互换(如二叉树)
      • 无序树:树中各结点的所有子树之间从左到右没有严格的次序关系
      • 森林:由n(n>=0)棵互不相交的树所构成的集合
    2. 二叉树的延伸概念

      • 满二叉树:所有结点或者是叶结点,或者是左右子树都非空,并且所有叶结点都在同一层上的二叉树称为满二叉树
      • 完全二叉树:相当于满二叉树结点的前n个结点的集合
      • 单分支树:所有结点都没有左子树或是右子树的二叉树
    3. 二叉树的性质

      • 二叉树中第i层上的结点数最多为 2的i次方 个
      • 深度为h的二叉树中最多有 2的h次方-1 个结点(因为深度 = 层数-1,所以其实与上一条本质相同)
      • 若叶结点的个数为 a 个,度为2的结点个数是 b 个,则有 a = b + 1;
      • 对于具有 n 个结点的二叉树,在从左向右的基础上从上到下从0开始编号,那么编号为i的结点有:
        1. i = 0 时为根节点
        2. 2i 为该结点的左子树的根节点(如果有),2i + 1 为该结点的右子树的根节点
        3. 若 2i + 1 >= n ,则该结点无左孩子
        4. 若 2i + 2 >= n ,则该结点无右孩子
    4. 二叉树的存储结构

      • 顺序存储:存在数组中
      • 链式存储:在结点类中有链接左结点和右结点的属性
    5. 二叉树的遍历

      • DLR先根遍历或先序遍历:先查找根节点,在一直查找左子树的左结点,然后翻上来找右结点
      • LDR中根遍历或中序遍历
      • LRD后根遍历或后序遍历:先处理左子树,再处理右子树,最后访问根结点
      • 层次遍历:将二叉数在从左到右的基础上逐层的访问

    第六章:图

    1. 相关概念

      • 无向图:全部由无向边构成的图
      • 有向图:全部由有向边构成的图
      • 权:图中的每条边上都有的表示特定意义的值
      • 网:边上标有权的图
      • 完全图:具有n个顶点,n*(n+1)/2 条边的图,即每两个顶点都有连接
      • 稠密图和稀疏图
      • 子图:一个图的边或点的子集所构成的图
      • 邻接点
      • 顶点的度:图中与该顶点相关联边的数目
      • 路径与回路:路径长度是该路径上边的数目
      • 连通图:若任意两个顶点均是连通的,则该图是连通图
      • 连通分量:无向图中的极大连通子图称为连通分量
      • 强连通图和强连通分量:在有向图中,若任意两个顶点均连通,则称为强连通图;有向图中的极大强连通子图称为强连通分量
    2. 图的存储结构

      • 图的类型有四种:无向图(UDG),有向图(DG),无向网(UDN),有向网(DN)
      • 邻接矩阵:
        1. 图:在二维数组中,如果图中两个顶点连接,那么二维数组的对应坐标的位置就是1,其余位置是0
        2. 网:在二维数组中,如果两个顶点链接,那么二维数组中的对应坐标的位置就是他们的权值,其余的位置为无穷大
      • 邻接表:一种链式存储结构
    3. 算法

      • BFS,DFS:广度优先搜索与深度优先搜索
      • 克鲁斯卡尔算法
      • 普里姆算法
      • 最短路径
      • 拓扑排序
      • 关键路径(带权搜索)

    第七章:内排序

    1. 相关概念

      • 内部排序:内部排序指待排序列完全存放在内存中进行的排序过程,适合数量不太大的数据
      • 外部排序:外部排序指待排序列借助外部存储器进行的排序,适合数量大的数据
      • 稳定排序与不稳定排序:关键字的前后位置关系在排序前与排序后是否一致,一致则是稳定排序,不一致就是不稳定排序
    2. 内排序方法

      • 插入类:
        1. 直接插入排序:空间复杂度O(1),时间复杂度O(n2)
        2. 希尔排序:空间复杂度O(1),时间复杂度与增量序列的选择有关
      • 交换类:
        1. 冒泡排序:空间复杂度O(1),时间复杂度O(n2)
        2. 快速排序:空间复杂度O(logn),时间复杂度O(nlogn)
      • 选择类:
        1. 直接选择排序:空间复杂度O(1),时间复杂度O(n2)
        2. 树形选择排序:时间复杂度O(nlogn)
        3. 堆排序:空间复杂度O(1),时间复杂度O(nlogn)
      • 归并类:归并排序:空间复杂度O(n),时间复杂度O(nlogn)
      • 基数排序:多关键字排序与链式奇数排序

    第八章:外排序

    1. 相关概念

      • 外排序:与外部存储设备的特征有关
    2. 磁盘排序

      • 磁盘信息的存取
      • 多路归并排序
      • 最优归并树

    第九章:查找

    1. 相关概念

      • 平均查找长度:ASL
    2. 静态表的查找(线性表,链表等)

      • 顺序查找:从第一个开始查找
      • 二分查找:在有序后,从中间开始,确定区间后再从区间的中部开始找
      • 分块查找(索引顺序查找):通过一个索引,使查找更加方便
    3. 动态表的查找(表本身就是动态生成的)

      • 二叉排序树
      • 平衡二叉树
      • B- 与 B+ 树
      • 红黑树(对称二叉B树)
    4. 哈希表的查找

      • 概念:以关键字的值作为自变量,进行哈希函数的运算后得到一个函数值,将该值作为数据元素的地址进行存储
      • 常用的哈希函数:
        1. 除留余数法:用自变量除一个值后取余,将余数作为函数值
        2. 直接地址法:例如自变量与函数值呈线性关系,可以根据自变量的值直接求出函数值
        3. 数字分析法
        4. 平方取中法
        5. 折叠法:将自变量进行分割,并且进行累加之类的方法,得到函数值
        6. 随机数法
    5. 处理冲突的方法

      • 一旦数据元素较多时,可能会出现两个不同的值有相同的函数值,因此需要处理这种冲突的情况
      • 开放地址法:如果发现冲突,就沿着发生冲突的地方继续寻找空位,遇到空位就填进去
      • 链地址法(拉链法):将所有具有相同哈希地址的不同关键字的数据元素通过链表保存起来
      • 公共溢出区法:另建一个公共溢出区(称为溢出表),如果发生冲突,就存放在这里
      • 再哈希法:发生冲突后就用另一个哈希函数进行运算,重新求得函数值

    展开全文
  • 考研题型里有一个题型叫做名词解释,这道题或多或少的咋试卷中占着一定的分量,但是分数又不是太多,用大量的大块时间来搞这个有点不太值当,所以抽些时间做个总结文档,用于空闲时间查看。 本文中概念不全,仅总结...

    考研题型里有一个题型叫做名词解释,这道题或多或少的咋试卷中占着一定的分量,但是分数又不是太多,用大量的大块时间来搞这个有点不太值当,所以抽些时间做个总结文档,用于空闲时间查看。

    本文中概念不全,仅总结了个人易混淆及常考的概念。

     

    名词解释

    数据:是对客观事物的符号表示。

    数据元素:是数据的基本单位,也称节点(node)或记录(record)。

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

    数据项:有独立含义的数据最小单位,也称域(field)。

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

    逻辑结构:抽象反映数据元素之间的逻辑关系。

    物理结构:数据结构在计算机中的表示。(存储结构)

    算法:对特定问题求解步骤的一种描述。

    算法设计原则:正确性,可读性,健壮性,效率与低存储量需求。

    空串:零个字符的串;

     

    树的度:树中所有结点的度的最大值;

    分支结点: 度大于零的结点

    树的深度:树中叶子结点所在的最大层次

    森林:m棵互不相交的树的集合。

    满二叉树:指的是深度为k且含有2k-1个结点的二叉树。

    完全二叉树:树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。

    路径长度:路径上分支的数目。树的路径长度:树根到每个结点的路径长度之和。

    树的带权路径长度:树中所有叶子结点的带权路径长度之和,记作:WPL(T) = Swklk

    带权路径长度最小的二叉树,称为最优树二叉树或赫夫曼树

    关键路径:路径长度最长的路径。

     

    顶点:数据元素vi称为顶点

    边、弧:P (vi,vj)表示顶点vi和顶点vj之间的直接连线,在无向图中称为边,在有向图中称为弧。任意两个顶点构成的偶对(vi,vj)∈E是无序的,该连线称为边。是有序的,该连线称为弧。

    弧头、弧尾:带箭头的一端称为弧头,不带箭头的一端称为弧尾。

    顶点的度(TD)=出度(OD)+入度(ID)

    图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

    通常有两条遍历图的路径:深度优先搜索和广度优先搜索。

    排序的分类:

    按待排序记录所在位置

        内部排序:待排序记录存放在内存

    外部排序:排序过程中需对外存进行访问的排序

     

    ADT抽象数据型是一个数学模型和在该模型上定义的操作的集合

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

    栈:线性表的一种特殊形式,是一种限定性数据结构,也就是在对线性表的操作加以限制后,形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。

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

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

    字符序列。

    广义表:由零个原子,或若干个原子或若干个广义表组成的有穷序列。

    树:1、一个结点x组成的集{x}是一株树(Tree),这个结点x也是这株树的根。

    2、假设x是一个结点,T1,T2,…,Tk是 k 株互不相交的树,我们可以构造一株新树:令x为根,并有k条边由x指向树T1,T2,…,Tk。这些边也叫做分支,T1,T2,…,Tk称作根x的树之子树。

    二叉树:有限个结点的集合,这个集合或者是空集,或者是由一个根结点和两株互不相交的二叉树组成,其中一株叫根的做左子树,另一棵叫做根的右子树。

    满二叉树:深度为k且有2k -1个结点的二叉树称为满二叉树。

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

    线索二叉树:若结点p有左孩子,则p->lchild指向其左孩子结点,否则令其指向其(中序)前驱。若结点p有右孩子,则p->rchild指向其右孩子结点,否则令其指向其(中序)后继。

    堆:如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点(如果有的话)的元素,则称此完全二叉树为最大堆。

            同样,如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点(如果有的话)的元素,则称此完全二叉树为最小堆。

    选择树:一棵选择树是一棵二叉树,其中每一个结点都代表该结点两个儿子中的较小者。这样,树的根结点就表示树中最小元素的结点。

     二叉排序树:二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

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

    2、若它的右子树非空,则右子树上的所有结点的值均大于或等于它的根结点的值。

    3、它的左右子树分别为二叉排序树。

    图:一个图G=(V,E)是一个由非空的有限集 V和一个边集E所组成的。若E中的每条边都是顶点的有序对(v , w),就说该图是有向图(directed graph,digraph)。若E中的每条边是两个不同顶点无序对,就说该图是无向图,其边仍表示成(v, w)。

    开放树:连通而无环路的无向图称作开放树。

    最小生成树:设G=( V, E )是一个连通图,E中每一条边(u, v)的权为C(u, v),也叫做边长。图G的一株生成树(spanning  tree)是连接V中所有结点的一株开放树。将生成树中所有边长之总和称为生成树的价(cost)。使这个价最小的生成树称为图G的最小生成树。

    无向图双连通分量:设Vi 是 Ei 中各边所连接的点集(1≤i≤k),  每个图Gi = ( Vi   ,  E i)叫做 G 的一个双连通分量。

    双连通图:若对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网中,由于有些活动可以并行,所以完成工程的最短时间是从源点到汇点的最大路径长度。因此,把从源点到汇点具有最大长度的路径称为关键路径。

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

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

    AVL树:AVL树或者是一颗空二叉树,或者具有如下性质的二叉查找树:

                其左子树和右子树都是高度平衡的二叉树,且左子树和右子树高度之差的绝对值不超过1。

        B-树:B-树是一种非二叉的查找树除了要满足查找树的特性,还要满足以下结构特性:一棵m 阶的 B- 树:

    (1)树的根或者是一片叶子(一个节点的树),或者其儿子数在 2 和 m 之间。

    (2)除根外,所有的非叶子结点的孩子数在m/2 和m 之间。

    (3)所有的叶子结点都在相同的深度。

    B+树:B-树的一种变形,二者区别在于:

               1、有k个子结点的结点必然有k个关键码;

               2、非叶子结点仅具有索引作用,与记录有关的信息均放在叶结点中。

    地址散列法:被查找元素的存储地址 = Hash ( Key )。

    堆分类:把具有如下性质的数组A表示的二元树称为堆(Heap):

                (1) 若2*i≤n,则A[i].key ≤ A[2*i].key ;

                (2) 若2*i+1≤n,则A[i].key≤A[2*i+1].key;       小顶堆

                把具有如下性质的数组A表示的二元树称为堆(Heap):

                (1) 若2*i≤n,则A[i].key ≥ A[2*i].key ;

                (2) 若2*i+1≤n,则A[i].key≥ A[2*i+1].key;      大顶堆

    词典排序:设集合S 中的元素为整数元组,关系 ≤ 为S 的线性序,对两个元素( s1,s2,…,sp )  和  ( t1,t2,…,tq )   存在   ( s1,s2,…,sp )  ≤  ( t1,t2,…,tq ) , 当存在一个整数j,1≤j≤max[p,q],使得sj≤tj,且所有1≤i<j,si=ti;或者p≤q,并且si=ti,1≤i≤p,则关系≤  称为词典序。

    归并方法:首先将文件中的数据输入到内存,采用内部分类方法进行分类(归并段),然后将有序段写回外存;对多归并段进行多遍归并,最后形成一个有序序列。

    索引: 指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。

     

    数据结构学科? 数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象及对象间的关系和施加于对象的操作等的学科。

    数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处,抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么? 数据类型是程序设计语言中的一个概念,它是一个值的集合和操作的集合。

     

    对于一个数据结构,一般包括哪三个方面:逻辑结构、存储结构、操作(运算)。

     

    循环队列 用常规意义下顺序存储结构的一维数组表示队列,由于队列的性质(队尾插入和队头删除),容易造成“假溢出”现象,即队尾已到达一维数组的高下标,不能再插入,然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下,通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。

     

    从数据结构角度讲,串属于线性结构。与线性表的特殊性在于串的元素是字符。

    从逻辑上讲,树和广义表均属非线性结构。但在以下意义上,又蜕变为线性结构。如度为1的树,以及广义表中的元素都是原子时。

     

    内部排序  若整个排序过程都在内存中完成,则称此类排序问题为内部排序。

    文件 文件是由大量性质相同的记录组成的集合,按记录类型不同可分为操作系统文件和数据库文件。

    文件存储结构的基本形式有哪些?一个文件采用何种存储结构应考虑哪些因素? 文件的基本组织方式有顺序组织、索引组织、散列组织和链组织。文件的存储结构可以采用将基本组织结合的方法,常用的结构有顺序结构、索引结构、散列结构。

    索引文件 在主文件外,再建立索引表指示关键字及其物理记录的地址间一一对应关系。这种由索引表和主文件一起构成的文件称为索引文件。索引表依关键字有序。

     

    参考书籍及网址

    1. 严蔚敏,吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社,2013.

    2. https://wenku.baidu.com/view/74033056f01dc281e53af0e7.html

    3. https://wenku.baidu.com/view/c5c24b1ed15abe23492f4d0d.html

     

    展开全文
  • 计算机体系结构——名词解释 文章目录计算机体系结构——名词解释一、第一章1.计算机系统结构,计算机组成,计算机实现2.计算机系统结构分类法①Flynn分类法②冯氏分类法③Handler分类法3.定量分析技术①Amdahl定律...

    计算机体系结构——名词解释

    文章目录

    一、第一章

    1.计算机系统结构,计算机组成,计算机实现

    计算机系统结构:
    经典定义:传统机器程序员所看到的计算机属性,即概念性结构与功能特性,是计算机系统的软、硬件的界面。
    广义定义:指令系统结构、组成、硬件

    计算机组成:计算机系统结构的逻辑实现

    计算机实现:计算机组成的物理实现

    2.计算机系统结构分类法

    ①Flynn分类法

    按照指令流和数据流的多倍性进行分类。
    指令流:计算机执行的指令序列。
    数据流:由指令流调用的数据序列。
    多倍性:在系统最受限的部件上,同时处于同一执行阶段的指令或数据的最大数目。
    Flynn分类法将计算机系统结构分为4类:
    单指令流单数据流(SISD)
    单指令流多数据流(SIMD)
    多指令流单数据流(MISD)
    多指令流多数据流(MIMD)

    ②冯氏分类法

    用系统的最大并行度对计算机进行分类。
    4类不同最大并行度的计算机系统结构
    最大并行度:计算机系统在单位时间内能够处理的最大的二进制位数。
    字宽(n位),一次能同时处理的字数(m字)。m×n就表示了其最大并行度。
    字串位串:n=1,m=1。(第一代计算机发展初期的纯串行计算机)
    字串位并:n>1,m=1。这是传统的单处理机,同时处理单个字的多个位,如16位、32位等。
    字并位串:n=1,m>1。同时处理多个字的同一位(位片)。
    字并位并:n>1,m>1。同时处理多个字的多个位。

    ③Handler分类法

    根据并行度和流水线对计算机进行分类。
    把计算机的硬件结构分成3个层次
    程序控制部件(PCU)的个数k
    算术逻辑部件(ALU)或处理部件(PE)的个数d
    每个算术逻辑部件包含基本逻辑线路(ELC)的套数w
    用公式表示:t(系统型号)=(k,d,w)

    进一步改进:t(系统型号)=(k×k’,d×d’,w×w’)
    k’:宏流水线中程序控制部件的个数
    d’:指令流水线中算术逻辑部件的个数
    w’:操作流水线中基本逻辑线路的套数

    3.定量分析技术

    ①Amdahl定律

    加快某部件执行速度所能获得的系统性能加速比,受限于该部件的执行时间占系统中总执行时间的百分比。

    ②CPU性能公式

    ③程序的局部性原理

    程序执行时所访问的存储器地址分布不是随机的,而是相对地簇聚。
    程序执行时间的90%都是在执行程序中10%的代码。
    1、程序的时间局部性:程序即将用到的信息很可能就是目前正在使用的信息。
    2、程序的空间局部性:程序即将用到的信息很可能与目前正在使用的信息
    在空间上相邻或者临近。

    4.实现可移植性的方法

    ①统一高级语言: 各个机器使用相同的高级语言以实现软件移植,不过较难实现。
    ②采用系列机:由同一厂家生产的具有相同的系统结构,但具有不同组成和实现的一系列不同型号的机器。
    ③模拟与仿真:
    模拟:用软件的方法在一台现有的机器(称为宿主机)上实现另一台机器(称为虚拟机)的指令集。
    仿真:用一台现有机器(宿主机)上的微程序去解释实现另一台机器(目标机)的指令集。

    5.提高并行性的三种技术途径

    时间重叠、资源重复、资源共享
    ①时间重叠:引入时间因素,让多个处理过程在时间上相互错开,轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度。
    ②资源重复:引入空间因素,以数量取胜。通过重复设置硬件资源,大幅度地提高计算机系统的性能
    ③资源共享:这是一种软件方法,它使多个任务按一定时间顺序轮流使用同一套硬件设备。

    二、第二章 指令系统的设计

    1.CISC指令集结构的功能设计

    ①面向目标程序优化:
    对大量的目标程序及其执行情况进行统计分析,找出那些使用频度高、执行时间长的指令或指令串。对于使用频度高的指令,用硬件加快其执行;对于使用频度高的指令串,用一条新的指令来替代。既能减少目标程序的执行时间,也能有效地缩短程序的长度。
    ②面向高级语言优化:
    缩小高级语言与机器语言的语义差距
    ③面向操作系统优化:
    操作系统和计算机系统结构是紧密联系的,操作系统的实现在很大程度上取决于系统结构的支持。
    指令系统对操作系统的支持主要有:
    处理机工作状态和访问方式的切换;
    进程的管理和切换;
    存储管理和信息保护;
    进程的同步与互斥,信号灯的管理等。

    2.RISC设计原则

    ①指令条数少、指令功能简单。只选取使用频度很高的指令,在此基础上补充一些最有用的指令;
    ②采用简单而又统一的指令格式,并减少寻址方式;指令字长都为32位或64位;
    ③指令的执行在单个机器周期内完成;(采用流水线机制)
    ④只有load和store指令才能访问存储器,其它指令的操作都是在寄存器之间进行;(即采用load-store结构)
    ⑤大多数指令都采用硬连逻辑来实现;
    ⑥强调优化编译器的作用,为高级语言程序生成优化的代码;
    ⑦充分利用流水技术来提高性能。

    3.指令系统的设计与优化

    三、第三章 流水线技术

    1.流水线概念和特点

    流水线的概念:把一个重复的过程分解为若干个子过程,每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开,依次通过各功能段,这样,每个子过程就可以与其它的子过程并行进行。

    流水线特点:
    1.流水线将一个任务分解成若干段,每段由一个专门对应的部件来处理
    2.流水线中各个段的时间应该尽可能相等,否则会引起流水线堵塞或断流
    3.流水线每个段后面要有一个缓冲寄存器,称为流水线寄存器(作用是在相邻的两段之间传送数据,以保证后面要用到的信息,把各个段处理工作相互隔离)
    4.流水技术适用于大量重复的的时序过程,只有在输入端不断地提供任务,才能充分发挥流水线的效率。
    5.流水线需要有通过时间和排空时间。
    (1)通过时间:第一个任务从进入流水线到流出结果所需的时间。
    (2)排空时间:最后一个任务从进入流水线到流出结果所需的时间。

    2.流水线的分类

    从不同的角度和观点,把流水线分成多种不同的种类。

    ①部件级、处理机级及处理机间流水线

    划分标准:按照流水技术用于计算机系统的等级不同

    部件级流水线(运算操作流水线):把处理机中的部件分段,再把这些分段相互连接起来,使得各种类型的运算操作能够按流水方式进行。

    处理机级流水线(指令流水线):把指令的执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程,每个子过程在独立的功能部件中执行。

    系统级流水线(宏流水线):把多台处理机串行连接起来,对同一数据流进行处理,每个处理机完成整个任务中的一部分。

    ②单功能流水线与多功能流水线

    划分标准:按照流水线所完成的功能来分类

    单功能流水线:只能完成一种固定功能的流水线。

    多功能流水线:流水线的各段可以进行不同的连接,以实现不同的功能。

    ③静态流水线与动态流水线

    划分标准:按照同一时间内各段之间的连接方式对多功能流水线作进一步的分类

    静态流水线:在同一时间内,多功能流水线中的各段只能按同一种功能的连接方式工作。(对于静态流水线来说,只有当输入的是一串相同的运算任务时,流水的效率才能得到充分的发挥)

    动态流水线:在同一时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能。(优点:灵活,能够提高流水线各段的使用率,从而
    提高处理速度。缺点:控制复杂。)

    ④线性流水线与非线性流水线

    划分标准:按照流水线中是否有反馈回路来进行分类

    线性流水线:流水线的各段串行连接,没有反馈回路。数据通过流水线中的各段时,每一个段最多只流过一次。

    非线性流水线:流水线中除了有串行的连接外,还有反馈回路。

    ⑤顺序流水线与乱序流水线

    划分标准:根据任务流入和流出的顺序是否相同来进行分类

    顺序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的。

    乱序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同,允许后进入流水线的任务先完成(从输出端流出)。(也称为无序流水线、错序流水线、异步流水线)

    ⑥标量处理机与向量流水处理机

    把指令执行部件中采用了流水线的处理机称为流水线处理机。

    标量处理机:处理机不具有向量数据表示和向量指令,仅对标量数据进行流水处理。

    向量流水处理机:具有向量数据表示和向量指令的处理机。向量数据表示和流水技术的结合。

    3.流水线的性能指标

    4.流水线的三种相关

    相关:两条指令之间存在某种依赖关系。如果两条指令相关,则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。

    对于两条指令i(在前)和j(在后)

    ①数据相关

    如果下述条件之一成立,则称指令j与指令i数据相关。
    (1)指令j使用指令i产生的结果;
    (2)指令j与指令k数据相关,而指令k又与指令i数据相关。

    数据相关具有传递性。

    ②名相关

    名:指令所访问的寄存器或存储器单元的名称。

    名相关:如果两条指令使用相同的名,但是它们之间并没有数据流动,则称这两条指令存在名相关。

    名相关又可以分为:

    反相关:如果指令j写的名与指令i读的名相同,则称指令 i 和 j 发生了反相关。
    ——指令 j 写的名=指令 i 读的名

    输出相关:如果指令j和指令i写相同的名,则称指令 i 和 j 发生了输出相关。
    ——指令 j 写的名=指令 i 写的名

    名相关的解决方案:

    换名技术:通过改变指令中操作数的名来消除名相关。
    对于寄存器操作数进行换名称为寄存器换名。

    ③控制相关

    控制相关:由分支指令引起的相关。

    5.流水线的三种类型冲突

    ①结构冲突

    结构冲突:如果某种指令组合因为资源冲突而不能正常执行,则称该处理机有结构冲突。

    解决方案:
    1.插入暂停周期
    2.设置相互独立的IR(指令寄存器),和DR(数据寄存器)或设置相互独立的指令cache和数据cache

    ②数据冲突

    数据冲突:当相关的指令靠得足够近时,它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序,使之不同于它们串行执行时的顺序,则发生了数据冲突。

    三种数据冲突:WAR,WAW,RAW

    解决方案:
    1.通过定向技术减少数据冲突引起的停顿
    定向技术的关键思想:在计算结果尚未出来之前,后面等待使用该结果的指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方,那么就可以避免停顿。
    2.增加流水线互锁机制,插入“暂停”。
    3.依靠编译器解决数据冲突:让编译器重新组织指令顺序来消除冲突,这种技术称为指令调度或流水线调度。

    ③控制冲突

    控制冲突:

    解决方案:
    1.处理分支指令最简单的方法:“冻结”或者“排空”流水线,但是这样处理会带来较长的分支延迟。

    可采取两种措施来减少分支延迟:
    在流水线中尽早判断出分支转移是否成功;
    尽早计算出分支目标地址。

    3种通过软件(编译器)来减少分支延迟的方法

    3种通过软件(编译器)来减少分支延迟的方法
    共同点:
    ——对分支的处理方法在程序的执行过程中始终是不变的,是静态的。
    ——要么总是预测分支成功,要么总是预测分支失败。
    (1)预测分支失败
    允许分支指令后的指令继续在流水线中流动,就好象什么都没发生似的;
    若确定分支失败,将分支指令看作是一条普通指令,流水线正常流动;
    若确定分支成功,流水线就把在分支指令之后取出的所有指令转化为空操作,并按分支目地重新取指令执行。
    (2)预测分支成功
    假设分支转移成功,并从分支目标地址处取指令执行。起作用的前题:先知道分支目标地址,后知道分支是否成功。
    (3)延迟分支
    从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成,不管分支是否成功,都要按顺序执行延迟槽中的指令。

    分支延迟指令的调度

    任务:在延迟槽中放入有用的指令
    三种调度方法:从前调度,从目标处调度,从失败处调度

    6.向量处理机

    ①向量处理机的概念

    在流水线处理机中,设置向量数据表示和相应的向量指令,称为向量处理机。

    ②向量处理方式

    横向(水平)处理方式
    纵向(垂直)处理方式
    纵横(分组)处理方式

    ③提高向量处理机性能的常用技术

    设置多个功能部件,使它们并行工作;
    采用链接技术,加快一串向量指令的执行;
    采用循环开采技术,加快循环的处理;
    采用多处理机系统,进一步提高性能。

    四、第四章 指令级并行

    1.指令级并行(ILP)

    指令级并行(ILP):指令之间存在的一种并行性,利用它,计算机可以并行执行两条或两条以上的指令。

    2.IPC(Instructions Per Cycle)

    IPC:每个时钟周期完成的指令条数)

    3.循环级并行(LLP)

    循环级并行(LLP):使一个循环中的不同循环体并行执行。

    4.动态分支预测技术

    ①动态分支预测技术

    在程序运行时,根据分支指令过去的表现来预测其将来的行为。
    ——如果分支行为发生了变化,预测结果也跟着改变。
    ——有更好的预测准确度和适应性。

    ②采用动态分支预测技术的目的

    ——预测分支是否成功
    ——尽快找到分支目标地址(或指令)(避免控制相关造成流水线停顿)

    ③动态分支预测需要解决的两个关键问题

    ——如何记录分支的历史信息,要记录哪些信息?
    ——如何根据这些信息来预测分支的去向,甚至提前取出分支目标处的指令?

    ④分支历史表(BHT)

    第四章 p81

    ⑤分支目标缓冲器(BTB)

    第四章 p85

    ⑥基于硬件的前瞻执行

    第四章 p92

    5.多指令流出技术

    ①超标量

    在每个时钟周期流出的指令条数不固定,依代码的具体情况而定。(有个上限)可以通过编译器进行静态调度,也可以基于Tomasulo算法进行动态调度。

    ②超长指令字(VLIW)

    在每个时钟周期流出的指令条数是固定的,这些指令构成一条长指令或者一个指令包。指令包中,指令之间的并行性是通过指令显式地表示出来的。指令调度是由编译器静态完成的。

    ③n-流出

    在每个时钟周期流出的指令条数的上限为n,就称该处理机为n-流出。

    6.循环展开和指令调度

    ①基本指令调度及循环展开

    指令调度:找出不相关的指令序列,让它们在流水线上重叠并行执行。

    循环展开:把循环体的代码复制多次并按顺序排放, 然后相应调整循环的结束条件。开发循环级并行的有效方法

    ②超块调度

    用尾复制技术来构造超块,且超块为只能拥有一个入口,但可以拥有多个出口的结构,这样可以简化补偿代码的生成过程,并降低了指令调度的复杂度。

    ③VLIW

    在VLIW处理器中,相关检测和指令调度工作全部由编译器完成,它需要更“智能”的编译器。

    ④显示并行指令计算EPIC

    见:第四章 p168

    ⑤循环携带相关

    循环携带相关:一个循环的某个叠代中的指令与其他叠代中的指令之间的数据相关。

    展开全文
  • 基础名词解释 数据:程序的操作对象,用于描述客观事物,有以下两个特点 可以输入到计算机 可以被计算机处理 数据元素:组成数据对象的基本单元 数据项:一个数据元素由若干数据项组成 数据对象:性质...
  • 1、数据数据是外部信息的载体,他能够被计算机识别、存储和加工处理,是计算机程序加工的原料; 2、数据元素:数据元素是数据的基本单位,在计算机中通常被作为一个整体进行考虑和处理; 3、一个数据元素可由若干...
  • 数据分析常用名词解释

    千次阅读 2020-01-09 09:13:32
    3、数据分析名词解释 一、互联网常用名词解释 1、PV(Page View)页面浏览量 指某段时间内访问网站或某一页面的用户的总数量,通常用来衡量一篇文章或一次活动带来的流量效果,也是评价网站日常流量数据的重要指标...
  • 绪论 数据数据是信息的载体,信息是数据的内涵。 数据元素:数据的基本单位。 数据项:构成数据元素不可分割的最小单位。 数据对象:性质相同的数据元素的集合,...数据结构三要素:逻辑结构、物理结构数据运算。
  • 名词解释:构件、架构、 4GL   1.构件:面向软件体系架构的可复用软件模块。 构件(component )是可复用的软件组成成份,可被用来构造其他软件。它可以是被封装的对象类、类树、一些功能模块、软件...
  • 计算机系统结构名词解释

    千次阅读 2020-08-08 21:15:42
    1、计算机体系结构 计算机系统结构就是计算机的机器语言程序员或编译程序编写者所看到的外特 性,是硬件子系统的概念结构及其功能特性 2、地址映象 把虚拟地址空间映象到主存地址空间,具体地说,就是把用户用虚拟...
  • 数据仓库之名词解释

    千次阅读 2019-06-08 21:23:22
    On-Line Transaction Processing联机事务处理过程(OLTP),也称为面向交易的处理过程,其基本特征是前台接收的用户数据可以立即传送到计算中心进行处理,并在很短的时间内给出处理结果,是对用户操作快速响应的方式之...
  • 一、名词解释 1.虚拟机:指由软件实现的机器,以区别于由固件/硬件实现的物理机器。 2. 系统加速比:总执行时间改进前/总执行时间改进后 3. Amdahl定律:加快某部件执行速度所获得的系统性能加速比,受限于该...
  • 数据结构专有名词&常见术语(中英双语)

    千次阅读 多人点赞 2019-01-01 15:28:16
    数据结构的一些常见术语的中英文双语对照,很多场合都可以用到, 比如编程命名,我觉得挺有用的,就收集在这里了 --_-- 目录 一. 常见术语 数据 Data 指针 Pointer 正确性 Correctness 线性表 Linear list 栈 ...
  • 几个名词解释:大数据、Hadoop、云计算、机器学习、NLP、数据挖掘 大数据: 大数据是相对于传统"小数据"的, 传统由于数据处理的成本很高,所以只能处理部分信息系统中产生的非常规范的数据,而对于文本、...
  • 软件工程名词解释

    万次阅读 2019-11-06 16:01:00
     软件是计算机系统中与硬件相互依存的部分,它是包括程序、数据及相关文档的完整集合。 软件危机  软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题。 软件工程  软件工程是研究和应用如何...
  • 电子商务之部分名词解释

    千次阅读 2020-01-03 17:47:25
    电子商务——部分名词解释 目录 电子商务——部分名词解释 (1)电子商务 (2)企业资源计划ERP (3)管理信息系统 (4)人力资源管理 (5)客户关系管理 (6)供应链管理 (7)认证机构 (8)数字证书 ...
  • GIS名词解释大全

    万次阅读 2012-02-21 11:26:52
    地理信息系统专业考研 GIS专业考研 名词解释大全  地理信息系统专业考研 GIS专业考研 名词解释大全(自己考研时候搜集的。。晒出来) 1. 地理信息系统(南大95、南大96、南大03、中科院03、中科院04、华东师00、...
  • 计算机名词解释——1

    千次阅读 2013-10-17 09:27:43
    能够把这些名词脱口而出,不仅是是对学习的检验,也是学好专业知识的自信表现,现在我打算花几天时间,总结关于计算机的一些名词解释。在这里,我打算就几门学科的一些名词进行解释,比如数据结构,计算机网络,操作...
  • C++名词解释

    千次阅读 2017-07-12 11:35:44
    C++名词解释 1. 保留字reserved word  C++中,保留字也称关键字,它是预先定义好的标识符。见关键字的解释。2.关键字key word  C++中已经被系统定义为特殊含义的一类标识符。C++中的关键字有: auto double ...
  • 数据库名词解释

    千次阅读 2017-09-11 18:00:24
    DB能为各种用户共享,具有最小冗余度,数据间联系密切,而又有较高的数据独立性。  ◆ DBMS:数据库管理系统(Database Management System),DBMS是位于用户与操作系统之间的一层数据管理软件,为用户或应用程序提供...
  • 电信技术名词解释:什么是SDHhttp://www.sina.com.cn 2004年07月15日 18:40 新浪科技 信息高速公路近来已成为人们的热门话题。到21世纪,人们借助与信息高速公路,可以在家中完成各种日常活动。而构成信息高速公路...
  • 数据库常用名词解释

    万次阅读 2008-10-22 18:39:00
    ◆ DB:数据库(Database),DB是统一管理的相关数据的集合。DB能为各种用户共享,具有最小冗余度,数据间联系密切,而又有较高的数据独立性。◆ DBMS:数据库管理系统(Database Management System),DBMS是位于用户...
  • 名词解释

    千次阅读 2007-06-22 07:33:00
    采用点一点的拓扑结构,用户可独享高带宽;  5. 可广泛用于视频业务及高速INTERNET等数据的接入。  目前,由于普通的INTERNET用户接入网络的方式采用拨号MODEM的方式,因此,INTERNET用户的剧增可能会造成网络的...
  • 区块链相关名词解释汇总

    千次阅读 2018-05-22 10:22:51
    转载自:《node.js开发加密货币》密码...散列:一个散列函数(或散列算法)是一个处理,依靠这个处理,一个文档(比如一个数据块或文件)被加工成看起来完全是随机的小片数据(通常为32个字节),从中没有意义的数据...
  • 互联网数据中心(Internet Data Center)简称IDC,就是电信部门利用已有的互联网通信线路、带宽资源,建立标准化的电信专业级机房环境,为企业、政府提供服务器托管、租用以及相关增值等方面的全方位服务。...
  • os名词解释

    千次阅读 2016-06-16 01:36:44
    (或)作业调度是高级调度,它位于操作系统的作业管理层次。进程调度是低级调度,它位于操作系统分层结构的最内层。 (2)作业调度是选符合条件的收容态作业装入内存。进程调度是从就绪态进程中选一个占用处理机。...
  • SAP 名词解释

    千次阅读 2014-09-03 08:31:06
    企业资源计划(Enterprise Resources Planning,ERP),可以从三个层次进行定义: 管理思想:ERP是由美国著名的计算机技术咨询和评估集团Gartner Group Inc.提出了一整套企业管理系统体系标准,其实质是在MRPII...
  • 1、 DB:即数据库( Database), 是统一管理的相关数据的集合 . DB 能为各种用户共享,具有最小冗余度,... DBMS总是基于某种数据模型,可以分为层次型、网状型、关系型、面向对象型 DBMS. 3、DBS:即数据库系统( Datab
  • FI 名词解释

    千次阅读 2012-02-15 23:05:30
    1. 总帐科目主数据 general ledger account master data: 业务交易需要通过帐户进行记录和管理。R/3中需要为每一个帐户创建主记录,它包括控制业务交易的输入和数据处理的信息。 2.会计科目表 chart of accounts...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,601
精华内容 7,040
关键字:

层次结构数据名词解释