《2022年数据结构概念名词解释大全.docx》由会员分享，可在线阅读，更多相关《2022年数据结构概念名词解释大全.docx（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 学习好资料 欢迎下载数据：是对客观事物的符号表示；数据元素：是数据的基本单位,也称节点（node）或记录（ record）；数据对象：是性质相同的数据元素的集合,是数据的一个子集；数据项：有独立含义的数据最小单位,也称域 field ；数据结构：是相互之间存在一种或多种特定关系的数据元素的集合；依据数据元素间关系的基本特性,有四种基本数据结构集合：结构中的数据元素之间除了“ 同属于一个集合” 的关系外,别无其他关系；线性结构：结构中的数据元素之间存在一个对一个的关系；树形结构：结构中的数据元素之间存在一个对多个的关系；图状结构或网状结结构：结构
2、中的数据元素之间存在多个对多个的关系；规律结构：抽象反映数据元素之间的规律关系；（算法设计）物理结构（储备结构） ：数据结构在运算机中的表示；（算法实现）储备结构分为：次序储备结构：借助元素在储备器中的相对位置来表示数据元素间的规律关系；链式储备结构：借助指示元素储备地址的指针表示数据元素间的规律关系；算法：对特定问题求解步骤的一种描述；算法的五个重要特性：有穷性,确定性,可行性,输入和输出；算法设计的原就或要求：正确性,可读性,健壮性,效率与低储备量需求；衡量算法效率的方法：事后统计法和事前分析估算法；fn 的增长率相同,就可记作：T n = Ofn ,称 T n 为算法的 渐近 时 算法执
3、行时间的增长率和 间复杂度 算法运行时间的衡量准就：以基本操作在算法中重复执行的次数；栈：限定仅在表尾进行插入或删除操作线性表；入栈：插入元素的操作； 出栈： 删除栈顶元素的操作；队列：只能在队首进行删除、队尾进行插入的线性表；答应插入的一端叫队尾,删除的一端叫队头；串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目；空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串,空格串的长度为串中空格字符的个数；储备位置： LOCi ,j=LOC0,0+b 2*i+jL结点 :包含一个数据元
4、素及如干指向其子树的分支；结点的度: 结点拥有的子树；树的度 :树中全部结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点树的深度：树中叶子结点所在的最大层次 二叉树的性质：森林： m 棵互不相交的树的集合；性质 1 ：在二叉树的第 i 层上至多有 2 i-1 个结点； i 1 性质 2 ：深度为 k 的二叉树上至多含 2 k-1 个结点；（k1）性质 3: 对任何一棵二叉树,如它含有 n0 个叶子结点、 n2 个度为 2 的结点,就必存在关系式：n0 = n 2+1；性质 4: 具有 n 个结点的完全二叉树的深度为 log 2n +1 ；满二叉树：指的是深度为 k 且含有
5、 2 k-1 个结点的二叉树；完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应；路径长度：路径上分支的数目；树的路径长度：树根到每个结点的路径长度之和；树的带权路径长度：树中全部叶子结点的带权路径长度之和,记作：WPLT =wklk带权路径长度最小的二叉树,称为最优树二叉树或赫夫曼树；关键路径：路径长度最长的路径；名师归纳总结 - - - - - - -第 1 页,共 9 页精选学习资料 - - - - - - - - - 顶点：数据元素vi 称为顶点学习好资料欢迎下载边、弧： P vi,vj表示顶点 vi 和顶点 vj 之间的直接连线,在无向图中称为边,在有向
6、图中称为弧；任 意两个顶点构成的偶对 vi,vjE是无序的,该连线称为边；是有序的,该连线称为弧；弧头、弧尾：带箭头的一端称为弧头,不带箭头的一端称为弧尾；顶点的度 TD=出度 OD+入度 ID 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础；通常有两条遍历图的路径：深度优先搜寻和广度优先搜寻；排序的分类：按待排序记录所在位置内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行拜访的排序 按排序依据原就 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 挑选排序：简洁挑选排序、堆排序 归并排序： 2-路归并排序 基数排序一、名词总结：
7、ADT：抽象数据型是一个数学模型和在该模型上定义的操作的集合线性表 ： 线性表是由 nn0 个相同类型的元素组成的有序集合；栈：线性表的一种特别形式, 是一种限定性数据结构, 也就是在对线性表的操作 加以限制后, 形成的一种新的数据结构； 是限定只在表尾进行插入和删除操作的 线性表；栈又称为后进先出的线性表；队列：将线性表的插入和删除操作分别限制在表的两端进行,和栈相反, 队列是 一种先进先出的线性表；串： 线性表的一种特别形式,表中每个元素的类型为字符型,是一个有限的字符序列；广义表： 由零个原子,或如干个原子或如干个广义表组成的有穷序列；树：1、一个结点 x 组成的集 x 是一株树 Tre
8、e ,这个结点 x 也是这株树的根；名师归纳总结 - - - - - - -第 2 页,共 9 页精选学习资料 - - - - - - - - - 学习好资料 欢迎下载2、假设 x 是一个结点, T1,T2, , Tk 是 k 株互不相交的树,我们可以构造 一株新树：令 x 为根,并有 k 条边由 x 指向树 T1,T2, , Tk；这些边也叫做分支, T1,T2, , Tk 称作根 x 的树之子树；二叉树： 有限个结点的集合,这个集合或者是空集,或者是由一个根结点和两株互不相交的二叉树组成,其中一株叫根的做左子树,另一棵叫做根的右子树；满二叉树： 深度为 k 且有 2k 1 个结点的二叉树称
9、为满二叉树；完全二叉树： 深度为 k 的,有 n 个结点的二叉树,当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应,称之为完全二叉树；线索二叉树： 如结点 p 有左孩子,就 p-lchild 指向其左孩子结点,否就令其指向其（中序）前驱；如结点 p 有右孩子,就 p-rchild 指向其右孩子结点,否就令其指向其（中序）后继；堆：假如一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（假如有的话）的元素,就称此完全二叉树为最大堆；同样,假如一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（假如有的话）的元素,就称此完
10、全二叉树为最小堆；挑选树： 一棵挑选树是一棵二叉树, 其中每一个结点都代表该结点两个儿子中的较小者；这样,树的根结点就表示树中最小元素的结点；二叉排序树： 二叉排序树或者是一棵空树,或者是具有以下性质的二叉树：1、如它的左子树非空,就左子树上的全部结点的值均小于它的根结点的值；2、如它的右子树非空,就右子树上的全部结点的值均大于或等于它的根结点的值；3、它的左右子树分别为二叉排序树；图： 一个图 G=（V,E）是一个由非空的有限集 V 和一个边集 E 所组成的；如E中的每条边都是顶点的有序对（v , w）,就说该图是有向图（ directed graph,digraph ）；如 E 中的每条边
11、是两个不同顶点无序对,就说该图是无向图,其边仍表示成（ v, w ）；开放树： 连通而无环路的无向图称作开放树；名师归纳总结 最小生成树： 设 G= V, E 是一个连通图, E中每一条边 u, v 的权为 Cu, v ,第 3 页,共 9 页也叫做边长；图 G的一株生成树 spanning tree 是连接 V 中全部结点的一株- - - - - - -精选学习资料 - - - - - - - - - 学习好资料 欢迎下载开放树；将生成树中全部边长之总和称为生成树的价 成树称为图 G的最小生成树；cost ；使这个价最小的生无向图双连通重量： 设 Vi 是 Ei 中各边所连接的点集（ 1i
12、k）, 个图 Gi = Vi , E i 叫做 G 的一个双连通重量；每双连通图： 如对 V中每个不同的三元组v,w,a ；在 v 和 w之间都存在一条不包含 a 的路,就说 G是双连通的强连通性： 设 G =（V, E）是一个有向图,称顶点 v ,wV 是等价的,要么 v = w；要么从顶点 v 到 w有一条有向路 ,并且从顶点 w到 v 也有一条有向路；拓扑排序： 给定一个无环路有向图 G=V,E , 各结点的编号为v=1,2, ,n ；要求对每一个结点 i 重新进行编号,使得如 i 是 j 的前导,就有 Label i label j ；即拓扑分类是将无环路有向图排成一个线性序列,使当从
13、结点 i 到结点 j 存在一条边,就在线性序列中,将 i 排在 j 的前面；AOE网：在带权的有向图中,用结点表示大事,用边表示活动,边上权表示活动的开销（如连续时间）,就称此有向图为边表示活动的网络 , 简称 AOE网；关键路径： 在 AOE网中,由于有些活动可以并行,所以完成工程的最短时间是从源点到汇点的最大路径长度； 因此,把从源点到汇点具有最大长度的路径称为关键路径；查找表： 由同一类型的数据元素（或纪录）构成的集合；关键字： 数据元素中某一数据项的值,用以表示一个数据元素；AVL树：AVL树或者是一颗空二叉树,或者具有如下性质的二叉查找树：其左子树和右子树都是高度平稳的二叉树,且左子
14、树和右子树高度之差的肯定值不超过 1；B-树：B-树是一种非二叉的查找树除了要满意查找树的特性,仍要满意以下结构特性：一棵 m 阶的 B- 树：（1）树的根或者是一片叶子 一个节点的树 , 或者其儿子数在 2 和 m 之间；（2）除根外,全部的非叶子结点的孩子数在 m/2 和 m之间；（3）全部的叶子结点都在相同的深度；B+树：B-树的一种变形,二者区分在于：名师归纳总结 1、有 k 个子结点的结点必定有k 个关键码；第 4 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 学习好资料 欢迎下载2、非叶子结点仅具有索引作用,与记录有关的信息均放在叶结点中
15、；地址散列法： 被查找元素的储备地址 = Hash Key ；堆分类： 把具有如下性质的数组A表示的二元树称为堆（ Heap）: A2*i+1.key; 1 如 2*i n,就 Ai.key A2*i.key ; 2 如 2*i+1 n,就 Ai.key小顶堆把具有如下性质的数组A表示的二元树称为堆（ Heap）: A2*i+1.key; 1 如 2*i n,就 Ai.key A2*i.key ; 2 如 2*i+1 n,就 Ai.key大顶堆词典排序： 设集合 S中的元素为整数元组,关系素 s1,s2, ,sp 和 t1,t2, ,tq 存 为 S的线性序,对两个元在 s1,s2, ,sp
16、t1,t2, ,tq , 当存在一个整数 j ,1jmaxp,q ,使得 sj tj ,且全部 1i j ,si ti ；或者 pq,并且 si ti ,1i p,就关系 称为词典序；归并方法： 第一将文件中的数据输入到内存,采纳内部分类方法进行分类（归并段）,然后将有序段写回外存；对多归并段进行多遍归并,最终形成一个有序序列；索引： 指的是记录的关键字值与记录驻留在外存的地址组成数对的集合；每个数对称为一个索引项；二、重要算法总结其次章： 1、模式匹配法（ KMP算法）2、串的 Substr 算法第三章： 1、二叉树的先、中、后序遍历（递归算法）2、二叉树的中序非递归遍历（帮助栈、非帮助栈）
17、3、二叉树交换左右子树；4、二叉树求深度、结点赋层号名师归纳总结 - - - - - - -第 5 页,共 9 页精选学习资料 - - - - - - - - - 学习好资料 欢迎下载5、哈夫曼树的构造 第四章： 1、DFS、BFS 2、最小生成树 3、强连通性 4、拓扑排序 5、Dijkstra 算法单源最短路径 第五章： 1、二叉排序树2、AVL树 3、地址散列法第六章：简洁排序算法及快排1数据结构是一门争论什么内容的学科？数据结构是一门争论在非数值运算的程序设计问题中, 运算机的操作对象及对象间的关系和施加于对象的操作等的学 科； 2 数据元素之间的关系在运算机中有几种表示方法？各有什么
18、特点？四种表示方法 （1）次序储备方式；数据元素次序存放,每个储备结点只含一个元素；储备位置反映数据元素间的规律关系；储备密度大,但有些操作（如插入、删除）效率较差；（2）链式储备方式；每个储备结点除包含数据元素信息外仍包含一组（至少一个）指针；指针反映数据元素间的规律关系；这种方式不要求储备空间连续,便于动态操作（如插入、删除等）,但储备空间开销大（用于指针）,另外不能折半查找等；（3）索引储备方式；除数据元素储备在一地址连续的内存空间外, 尚需建立一个索引表, 索引表中索引指示储备结点的储备位置（下标）或储备区间端点 （下标） ,兼有静态和动态特性；（4）散列储备方式；通过散列函数和解决冲
19、突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值说明成关键字所在元素的储备地址,这种储备方式称为散列存储；其特点是存取速度快,只能按关键字随机存取,不能次序存取,也不能折半存取； 3 数据类型和抽象数据类型是如何定义的；二者有何相同和不同之处,抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据 如 C语言类型是程序设计语言中的一个概念,它是一个值的集合和操作的集合；中的整型、实型、字符型等；整型值的范畴（对详细机器都应有整数范畴）,其操作有加、减、乘、除、求余等；实际上数据类型是厂家供应应用户的已实现了的数据结构；“ 抽象数据类型（ADT）” 指一个数学模型及
20、定义在该模型上的一组操作；“ 抽象” 的意义在于数据类型的数学抽象特性；抽象数据类型的定义仅名师归纳总结 取决于它的规律特性, 而与其在运算机内部如何表示和实现无关；无论其内部结第 6 页,共 9 页构如何变化, 只要它的数学特性不变就不影响它的外部使用；抽象数据类型和数- - - - - - -精选学习资料 - - - - - - - - - 学习好资料 欢迎下载据类型实质上是一个概念； 此外,抽象数据类型的范畴更广, 它已不再局限于机器已定义和实现的数据类型,仍包括用户在设计软件系统时自行定义的数据类型；使用抽象数据类型定义的软件模块含定义、表示和实现三部分, 封装在一起,对用户透亮（供应
21、接口）,而不必明白实现细节；抽象数据类型的显现使程序设计不再是“ 艺术” ,而是向“ 科学” 迈进了一步； 4 对于一个数据结构,一般包括哪三个方面：规律结构、储备结构、操作（运算）； 5 依据数据元素之间的规律关系,一般有哪几类基本的数据结构？集合、线性结构、树形结构、图形或网状结构； 6 线性表有两种储备结构： 一是次序表,二是链表；试问：（1）假如有 n 个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地转变； 在此情形下, 应选用哪种储备结构？为什么？选链式储备结构；它可动态申请内存空间,不受表长度（即表中元素个数）的影响,插入、删除时间复杂度为 O（1）；
22、 （2）如线性表的总数基本稳固,且很少进行插入和删除, 但要求以最快的速度存取线性表中的元素,那么应采纳哪种储备结构？为什么？选次序储备结构； 次序表可以随机存取, 时间复杂度为 O（1）；7线性表的次序储备结构具有三个弱点：其一,在作插入或删除操作时,需移动大量元素；其二,由于难以估量,必需预先安排较大的空间,往往使储备空间不能得到充分利用； 其三,表的容量难以扩充； 线性表的链式储备结构是否肯定都能够克服上述三个弱点,试争论之；链式储备结构一般说克服了次序储备结构的三个弱点；第一,插入、删除不需移动元素,只修改指针,时间复杂度为 O1；其次,不需要预先安排空间,可依据需要动态申请空间；其三
23、,表容量只受可用内存空间的限制；其缺点是由于指针增加了空间开销,当空间不答应时,就不能克服次序储备的缺点；8栈是只准在一端进行插入和删除操作的线性表,答应插入和删除的一端叫栈顶,另一端叫栈底；最终插入的元素最先删除,故栈也称后进先出（LIFO）表；9队列是答应在一端插入而在另一端删除的线性表,答应插入的一端叫队尾,答应删除的一端叫队头；最先插入队的元素最先离开（删除）,故队列也常称先进先出（FIFO）表；10什么是循环队列？用常规意义下次序储备结构的一维数组表示队列,由于队列的性质（队尾插入和队头删除）,简洁造成“ 假溢出” 现象,即队尾已到达一维数组的高下标,不能再插入,然而队中元素个数小于
24、队列的长度（容量）；循环队列是解决“ 假溢出” 的一种方法；通常把一维数组看成首尾相接；在循环队列下,通常采纳“ 牺牲一个存储单元” 或“ 作标记” 的方法解决“ 队满” 和“ 队空” 的判定问题；11如元素的进栈序列为：A、B、C、D、E,运用栈操作,能否得到出栈序列 B、C、A、 E、D 和 D、B、A、C、E？为什么？能得到出栈序列 B、C、 A、E、D,不能得到出栈序列 D、B、A、C、E；其理由为：如出栈序列以 D 开头,说明在 D 之前的入栈元素是 A、B 和 C,三个元素中 C是栈顶元素, B 和 A 不行能早于 C 出栈,故不可能得到 D、B、 A、C、E 出栈序列；12串？串
25、是零个至多个字符组成的有限序列；从数据结构角度讲,串属于线性结构；与线性表的特别性在于串的元素是字符；13描述以下概念的区分：空格串与空串；空格是一个字符,其 ASCII码值是 32；空格串是由空格组成的串,其长度等于空格的个数；空串是不含任何字符的串,即空串的长度是零；14数组 A1.8,-2.6,0.6以行为主序存储,设第一个元素的首地址是 78,每个元素的长度为 4,试求元素 A4,2,3 的储备首地址；958 三维数 组 以 行 为 主 序 存 储,其 元 素 地 址 公 式 为：LOCALOCALOCALOCAijkijkijkijk=LOCA=LOCA=LOCA=LOCAc1c2c
26、3c1c2c3c1c2c3c1c2c3+i+i+i+i-cccc1111VVVV2222VVVV3333+j+j+j+j-cccc2222VVVV3333+k+k+k+k-cccc3333*L+1名师归纳总结 *L+1*L+1*L+1 其中 ci,di 是各维的下界和上界,Vi=di-ci+1 是各维元素个数,L 是一个元素所占第 7 页,共 9 页的储备单元数；15数组 A 中,每个元素Ai,j 的长度均为32 个二进位 ,行下标从 -1 到 9,列下标从1 到 11,从首地址S开头连续存放主储备器中,主储备器字长为16 位；求：（1）存放该数组所需- - - - - - -精选学习资料 -
27、 - - - - - - - - 多少单元？（2）存放数组第学习好资料欢迎下载A7,44 列全部元素至少需多少单元？（3）数组按行存放时,元素的起始地址是多少？（4）数组按列存放时,元素 A4,7的起始地址是多少？答：每个元素 32 个二进制位,主存字长 16 位,故每个元素占 2 个字长, 行下标可平移至 1 到 11；（1）242 （2）22 （3）s+182 （4）s+142 16. 从概念上讲,树,森林和二叉树是三种不同的数据结构,将树,森林转化为二叉树的基本目的是什么,并指出树和二叉树的主要区分；树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是说明不同,也就是说树（树
28、是森林的特例,即森林中只有一棵树的特别情形）可用二叉树唯独表示,并可使用二叉树的一些算法去解决树和森林中的问题；树和二叉树的区分有三：一是二叉树的度至多为 2,树无此限制； 二是二叉树有左右子树之分,即使在只有一个分枝的情形下,也必需指出是左子树仍是右子树,树无此限制；三是二叉树答应为空,树一般不答应为空（个别书上答应为空）； 17请分析线性表、树、广义表的主要结构特点,以及相互的差异与关联；线性表属于约束最强的线性结构,在非空线性表中,只有一个 “ 第一个”元素, 也只有一个 “ 最终一个”元素；除第一个元素外,每个元素有唯独前驱；除最终一个元素外,每个元素有唯独后继；树是一种层次结构,有且
29、只有一个根结点,每个结点可以有多个子女,但只有一个双亲（根无双亲）,从这个意义上说存在一（双亲）对多（子女）的关系；广义表中的元素既可以是原子,也可以是子表,子表可以为它表共享；从表中套表意义上说,广义表也是层次结构；从规律上讲,树和广义表均属非线性结构；但在以下意义上,又蜕变为线性结构；如度为 表从元素之间的关系可看成前驱和后继,1 的树,以及广义表中的元素都是原子时；另外,广义 也符合线性表, 但这时元素有原子,也有子表,即元素并不属于同一 数据对象；18一棵二叉树中的结点的度或为 0 或为 2,就二叉树的枝数为 2n0-1 ,其中n0 是度为 0 的结点的个数；证明： 设二叉树度为 0
30、和 2 的结点数及总的结点数分别为 n0,n2 和 n,就 n=n0+n2 1 再设二叉树的分支数为 B, 除根结点外,每个结点都有一个分支所指,就n=B+1 2 度为零的结点是叶子,没有分支,而度为 2 的结点有两个分支,因此（2）式可写为 n=2*n2+1 3 由（1）、（3）得 n2=n0-1,代入（1）,并由（ 1）和（2）得 B=2*n0-1 ；证毕；19（1）假如 G1 是一个具有 n 个顶点的连通无向图,那么 G1 最多有多少条边？G1 最少有多少条边？（ 2）假如 G2 是一个具有 n 个顶点的强连通有向图,那么 G2 最多有多少条边？G2最少有多少条边？（3）假如 G3 是一
31、个具有 n 个顶点的弱连通有向图,那么 G3 最多有多少条边？G3 最少有多少条边？答：（1）G1 最多 nn-1/2 条边,最少 n-1 条边 2 G2 最多 nn-1条边,最少 n条边 3 G3 最多 nn-1条边,最少 n-1 条边 注：弱连通有向图指把有向图看作无向图时,仍是连通的 20n 个顶点的无向连通图最少有多少条边？n 个顶点的有向连通图最少有多少条边？n-1,n 21内部排序（名词说明）假设含 n 个记录的序列为 R1, R2, , Rn ,其相应的关键字序列为 K1, K2, , Kn ,这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系 Ks1Ks2Ksn,按
32、此固有关系将 n 个记录序列重新排列为 Rs1, Rs2, , Rsn ；如整个排序过程都在内存中完成,就称此类排序问题为内部排序；22在各种排序方法中,哪些是稳固的？哪些是不稳固的？并为每一种不稳固的排序方法举出一个不稳固的实例；排序方法 平均时间 最坏情形 帮助空间 稳固性 不稳固排序举例 直接插入排序O（n2） O（n2） O（1） 稳固 折半插入排序 O（n2） O（n2） O（1） 稳固 二路插入排序 O（n2） O（n2） O（n） 稳固 表插入排序 O（n2） O（n2） O（1） 稳固 起泡排序 O（n2） O（n2） O（1） 稳固 直接挑选排序 O（n2） O（n2） O（
33、1） 不稳固 2,2,1 希尔排序 O（n1.3）O（ n1.3） O（ 1） 不稳固 3,2,2 ,1d=2,d=1 快速排序 O（nlog2n ） O（ n2） O（log2n） 不稳固 2,2 ,1 堆排序 O（ nlog2n） O（nlog2n） O（1） 不稳固 2,1,1 极大堆 2-路归并排序 O（nlog2n） O（nlog2n）O（n） 稳固 基数排序 O d*rd+n O d*rd+n O rd 稳固 23 文件 文件是由大量性质相同的记录组成的集合,按记录类型不同可分为操作系统文件和数据库文件；24文件储备结构的基本名师归纳总结 - - - - - - -第 8 页,共
34、9 页精选学习资料 - - - - - - - - - 学习好资料 欢迎下载形式有哪些？一个文件采纳何种储备结构应考虑哪些因素？文件的基本组织方式有次序组织、索引组织、散列组织和链组织； 文件的储备结构可以采纳将基本组织结合的方法,常用的结构有次序结构、索引结构、散列结构；（1） 次序结构,相应文件为次序文件,其记录按存入文件的先后次序次序存放； 次序文件本质上就是次序表；如规律上相邻的两个记录在储备位置上相邻,就为连续文件；如记录之间以指针相链接,就称为串联文件；次序文件只能次序存取,要更新某个记录,必需复制整个文件；次序文件连续存取的速度快,主要适用于次序存取,批量修改的情形；（2） 带索
35、引的结构,相应文件为索引文件；索引文件包括索引表和数据表,索引表中的索引项包括数据表中数据的关键字和相应地址,索引表有序,其物理次序表达了文件的规律次序,实现了文件的线性结构；索引文件只能是磁盘文件,既能次序存取,又能隋机存取；（3） 散列结构,也称运算寻址结构,相应文件称为散列文件,其记录是依据关键字值经散列函数运算确定其地址,存取速度快,不需索引,节约储备空间； 不能次序存取,只能随机存取；其它文件均由以上文件派生而得；文件采纳何种储备结构应综合考虑各种因素,如：储备介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作；25索引文件 在主文件外,再建立索引表指示关键字及其物理记录的地址间一一对应关系；这种由索引表和主文件一起构成的文件称为索引文件；索引表依关键字有序；主文件如按关键字有序称为索引次序文件,否就称为索引非次序文件（通常简称索引文件）；索引次序文件因主文件有序,一般用稀疏索引, 占用空间较少； 常用索引次序文件有 ISAM 和 VSAM；ISAM 采纳静态索引结构, 而 VSAM采纳 B+树的动态索引结构；索引文件既能次序存取,也能随机存取；26索引次序文件 在索引文件中,如（数据区）主文件中关键字有序,就文件称为索引次序文件；名师归纳总结 - - - - - - -第 9 页,共 9 页