李春葆数据结构习题与解析(修订版)知识分享

第1章绪论教材中练习题及参考答案1. 简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据元素与数据之间的关系是元素与集合之间的关系。

2. 采用二元组表示的数据逻辑结构S=<D，R>，其中D={a，b，…，i}，R={r}，r={<a，b>，<a，c>，<c，d>，<c，f>，<f，h>，<d，e>，<f，g>，<h，i>}，问关系r是什么类型的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？答：该逻辑结构为树形结构，其中a结点没有前驱结点，它是开始结点，b、e、i和g、结点没有后继结点，它们都是终端结点。

3. 简述数据逻辑结构与存储结构的关系。

答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在计算机中的表示。

存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还要在内存中存储各数据元素间的逻辑关系。

通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。

4. 简述数据结构中运算描述和运算实现的异同。

答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。

它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。

不同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设计处理步骤。

5. 数据结构和数据类型有什么区别？答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767（16位机）的整数和+、-、*、/、%等运算符构成。

李春葆《数据结构教程》（第4版）笔记和课后习题详解第8章图8.1复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。

采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。

抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。

（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。

②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。

③出度以顶点i为起点的出边的数目，称为该顶点的出度。

一个顶点的入度与出度的和为该顶点的度。

（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。

（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。

②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。

（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。

（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。

②路径长度路径长度是指一条路径上经过的边的数目。

（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。

第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。

数据元素是数据的基本单位。

有时候，一个数据元素可以由若干个数据项组成。

② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。

李春葆《数据结构教程》（C++语⾔描述）模拟试题及详解（⼀）李春葆《数据结构教程》（C++语⾔描述）模拟试题及详解（⼀）⼀、单项选择题（每⼩题2分，共20分）1．队列的特点是（）。

A．先进后出B．先进先出C．任意位置进出D．前⾯都不正确【答案】B2．有n个记录的⽂件，如关键字位数为d，基数为r，则基数排序共要进⾏（）遍分配与收集。

A．nB．dC．rD．n-d【答案】B【解析】基数排序是按组成关键字的各位值进⾏分配收集⽽完成的。

3．在⼆叉树节点的先序序列、中序序列和后序序列中，所有叶⼦节点的先后顺序（）。

A．都不相同B．完全相同C．先序和中序相同，⽽与后序不同D．中序和后序相同，⽽与先序不同【答案】B【解析】⽆论是哪种遍历⽅式，遍历叶⼦节点时，都是先访问左⼦树，后访问右⼦树。

4．限定在⼀端加⼊和删除元素的线性表称为（）。

A．双向链表B．单向链表C．栈D．队列【答案】C【解析】根据栈后进先出的特性，可见栈都在⼀端对元素进⾏操作。

5．设内存⼯作区可容纳8个记录，初始⽂件共有64个关键字不同的记录，且已按关键字递减排列，如⽤置换．选择排序产⽣初始归并段，最长初始归并段所含记录数是（）。

A．6B．7C．8D．9【答案】C【解析】对于置换选择排序，输⼊的⽂件是以关键字降序排列时，所得的初始归并段的最⼤长度为⼯作区的⼤⼩。

当输⼊的⽂件以关键字的升序排序时，只能得到⼀个长度为⽂件长度的初始归并段。

6．设森林F对应的⼆叉树为B，它有m个节点，B的根为p，p的右⼦树上的节点个数为n，森林F中第⼀棵树的节点个数是（）。

A．m-n-1B．n+lC．m-n+1D．m-n【答案】D7．设有198个初始归并段，如采⽤K-路平衡归并三遍完成排序，则K值最⼤为（）。

A．12B．13C．14D．15【答案】C【解析】k⼀路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。

要三遍完成遍历，那就看两遍完成排序的需遍历的最⼩数。

李春葆《数据结构教程》（第4版）笔记和课后习题详解第11章外排序11.1复习笔记一、外排序概述文件存储在外存上，因此外排序方法与各种外存设备的特征有关。

外排序的基本方法是归并排序法。

它分为以下两个步骤：1．生成若干初始归并段（顺串）将一个文件（含待排序的数据）中的数据分段读入内存，在内存中对其进行内排序，并将经过排序的数据段（有序段）写到多个外存文件上。

2．多路归并对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。

二、磁盘排序1．磁盘排序概述磁盘是直接存取设备，读／写一个数据块的时间与当前读／写头所处的位置关系不大，存放在磁盘中的文件的排序属典型的外排序。

磁盘排序过程如图11-1所示.图11-1磁盘排序过程磁盘中的F in文件包括待排序的数据，通过相关算法将F in文件中数据一部分一部分地调入内存（每个记录被读一次）处理，产生若干个文件F1～F n（每个记录被写一次），它们都是有序的，称为顺串。

然后再次将F1～F n文件中的记录调入内存（每个记录被读一次），通过相关归并算法产生一个有序的F out文件（每个记录被写一次），从而达到数据排序的目的。

可见，提高排序速度很重要的一个方面是减少对数据的扫描遍数。

2．生成初始归并段使用置换—选择的排序算法用于生成较长的初始归并段。

采用置换—选择排序算法生成初始归并段时，内排序基于选择排序，即从若干个记录中通过关键字比较选择一个最小的记录，同时在此过程中进行记录的输入和输出，最后生成若干个长度可能各不相同的有序文件。

基本步骤如下：（1）从待排序文件F in中按内存工作区WA的容量（设为w）读入w个记录，设归并段编号i=1；（2）从WA中选出关键字最小的记录R min；（3）将R min 记录输出到文件F i 中，作为当前归并段的一个成员；（4）若F in 不空，则从F in 中读入下一个记录到WA 中替代刚输出的记录；（5）从WA 工作区中所有大于或等于R min 的记录中选择出最小记录作为新的R min ，转（3），直到选不出这样的R min ；（6）置i=i+1，开始一个新的归并段；（7）若WA 工作区已空，则初始归并段已全部产生，否则转（2）。

数据结构(李春葆)习题与解析编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构(李春葆)习题与解析）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为数据结构(李春葆)习题与解析的全部内容。

数据结构（C语言篇）―习题与解析（修订版）清华大学出版社一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科.1 A.数据元素 B。

计算方法C。

逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2。

数据结构被形式地定义为（K， R)，其中K是的有限集，R是K 上的有限集。

1A。

算法 B。

数据元素C。

数据操作 D.逻辑结构2A。

操作 B。

映像C。

存储D。

关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C。

线性结构和非线性结构 D。

内部结构和外部结构4.线性结构的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种B的存储结构。

A.随机存取 B。

顺序存取 C.索引存取 D.散列存取5。

算法分析的目的是C，算法分析的两个主要方面是AB。

1 A.找出数据结构的合理性 B。

研究算法中的输入和输出的关系C。

分析算法的效率以求改进 D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C。

可读性和文档性 D.数据复杂性和程序复杂性6.计算机算法指的是C，它必须具备输入、输出和B等5个特性。

1 A.计算方法 B。

排序方法C。

解决问题的有限运算序列D.调度方法2 A.可执行性、可移植性和可扩充性B。

可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法B。

春葆编著：数据结构（C语言篇）――习题与解析（修订版）清华大学一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的两个主要方面是2。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的两个主要方面是2。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。

第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。

（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。

数据元素是数据的基本单位。

有时候，一个数据元素可以由若干个数据项组成。

② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。

（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。

第10章内排序10.1 复习笔记一、排序的基本概念1．定义排序，就是整理表中的元素，使之按关键字递增或递减的顺序排列，本章仅讨论递增排序的情况。

其确切定义如下：输入：n个元素，R0，R1，…，R n-1，相应的关键字分别为k0，k1，…，k n-1。

输出：R i0，R i1，…，R in-1，使得k i0≤k i1≤…≤k in-1。

因此，排序算法就是要确定0，1，…，n-1的一种排列i0，i1，…，i n-1，使表中的元素依此排列整理后按关键字有序。

2．排序的稳定性（1）稳定如果待排序的表中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。

（2）不稳定若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。

注意：排序算法的稳定性是针对所有输入实例而言的。

在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

3．内排序和外排序（1）内排序在排序过程中，若整个表都是放在内存中处理，排序时不涉及内、外存数据的交换，则称之为内排序。

内排序适用于元素个数不很多的小表。

（2）外排序若排序过程中要进行内、外存数据的交换，则称之为外排序。

外排序则适用于元素个数很多，不能一次将全部元素放入内存的大表。

内排序是外排序的基础。

（3）排序方法的其他分类①需要关键字比较的排序需要关键字比较的排序方法有插入排序、选择排序、交换排序和归并排序等。

②不需关键字比较的排序不需要关键字比较的排序方法有基数排序。

4．排序数据的组织在本章中，以顺序表作为排序数据的存储结构，假设关键字类型为整型。

待排序的顺序表中数据元素的类型定义如下：二、插入排序1．插入排序的思想及方法基本思想是：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止。

主要有两种插入排序方法，即直接插入排序和希尔排序。

第1章绪论1.1复习笔记一、数据结构1．概述（1）计算机对具体问题的处理在用计算机解决一个具体的问题时，大致需要经过以下几个步骤：①分析问题，确定数据模型。

②设计相应的算法。

③编写程序，运行并调试程序，直至得到正确的结果。

（2）数据的含义①数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。

从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。

它是计算机操作的对象的总称，也是计算机所处理信息的某种特定的符号表示形式。

②数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，有些情况下数据元素也称为元素、结点、记录等。

一个数据元素可以由若干个数据项组成。

数据项是具有独立含义的数据的最小单位，也称为域。

③数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。

默认情况下，数据结构中的数据指的都是数据对象。

（3）数据结构的定义数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在特定关系的数据元素的集合，因此，可时把数据结构看成是带结构的数据元素的集合。

数据结构包括以下几个方面：①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

数据的逻辑结构是从逻辑关系（主要指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（也称为映像），也是指逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。

一般情况下，只在高级语言（如C、C++、Java语言）的层次上讨论存储结构。

③施加在该数据上的操作，即数据的运算。

数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。

第12章文件12.1 复习笔记一、文件的基本概念1．文件概述（1）定义文件是性质相同的记录的集合。

（2）按关键字划分①单关键字文件若文件中的记录只有一个惟一标识记录的主关键字，则称之为单关键字文件；②多关键字文件若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称之为多关键字文件。

（3）按是否定长划分①定长文件若文件中各记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称作定长文件；②不定长文件若文件中各记录含有的信息长度不等，则称作不定长文件。

2．文件的逻辑结构及操作（1）文件的逻辑结构文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时，各记录之间就自然地形成了一种线性关系。

在这种次序下，文件中每个记录最多只有一个直接后继记录和一个直接前驱记录，而文件的第一个记录只有直接后继没有直接前驱，文件的最后一个记录只有直接前驱而没有直接后继。

此时，文件可看成是一种线性结构。

（2）文件操作①检索文件检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号（即记录存入文件时的顺序编号）查找，也可以按关键字查找。

②维护文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。

此外，为提高文件的效率，还要进行再组织操作、文件被破坏后的恢复操作以及文件中数据的安全保护等。

3．文件的存储结构（1）概念文件的存储结构是指文件在外存上的组织方式。

采用不同的组织方式就得到不同的存储结构。

（2）基本的组织方式①顺序组织；②索引组织；③哈希组织；④链组织。

文件组织的各种方式往往是这四种基本方式的结合。

二、顺序文件1．定义顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。

若顺序文件中的记录按其主关键字有序，则称此顺序文件为顺序有序文件；否则称为顺序无序文件。

2．优点顺序文件的主要优点是连续存取的速度较快，即若文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。

第8章图8.1 复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。

采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。

抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。

（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。

②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。

③出度以顶点i为起点的出边的数目，称为该顶点的出度。

一个顶点的入度与出度的和为该顶点的度。

（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。

（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。

②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。

（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。

（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。

②路径长度路径长度是指一条路径上经过的边的数目。

（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。