数据结构必背名词解释&&简答题汇总
数据结构必背名词解释&&简答题汇总
数据结构-名词合集
第一章：绪论
1.数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3.数据项：数据项是数据结构中讨论的最小单位。是数据记录中基本的，不可分的数据单位。
4.数据对象：数据对象是性质相同的数据元素的集合，是数据的一个子集。
5.数据结构：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括3个方面的内容：逻辑结构、存储结构和对数据的运算。
6.数据的逻辑结构：数据的逻辑结构是对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。归纳起来数据的逻辑结构主要有四大类：集合、线性结构、树形结构、图状结构或网状结构。
7.数据的存储结构：数据的物理结构又称为存储结构，是数据的逻辑结构在计算机中的表示(又称映像)。它包括数据元素的表示和关系的表示。当数据元素是由若干数据项构成的时候，数据项的表示称为数据域；比如一个链表节点，节点包含值域和指针域，这里节点可以看做一个数据元素，其中的值域和指针域都是这个数据元素的数据域。主要有顺序存储、链式存储、索引存储、散列存储。
8.数据的运算：施加在数据上的运算包括运算的定义和实现。定义是针对逻辑结构，指出运算的功能。实现是针对存储结构的，指出运算的具体操作步骤。
9.算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。有5个重要特性(有穷性、确定性、可行性、输入、输出)。
(1)有穷性：一个算法必须保证执行有限步之后结束。
(2)确定性：算法的每一步骤必须有确定的定义。
(3)输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身确定了初始条件。
(4)输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
(5)可行性：算法中的所有操作都必须可以通过已经实现的基本操作进行运算，并在有限次内实现，而且人们用笔和纸做有限次运算后也可完成。
10.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。
(1)正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是重要也是基本的标准。
(2)可读性：要求算法易于人的理解。
(3)健壮性：要求算法有很好的容错性，能够对不合理的数据进行检查。
(4)高效率与低存储量需求：算法的效率主要是指算法的执行时间。对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法的存储量指的是算法执行过程中所需要的大存储空间。高效率和低存储量这两者都与问题的规模有关。
11.时间复杂度：算法的时间复杂度，也就是算法的时间量度，记作：T(n)=0(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
12.空间复杂度：算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小(和时间复杂度一样，以数量级的形式给出)。
13.就地算法：就地( In-place)算法指的是直接修改输入数据而不是将输入数据复制一份处理之后再覆盖回去，这个名称和时间复杂度没什么关系，纯粹是指算法处理数据的方式。比如一个冒泡排序就是就地算法。
第二章：线性表
1.线性表的逻辑特性：线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，每个元素最多只能有一个前驱和一个后继。
2.线性表的存储结构：线性表的存储结构有顺序存储结构和链式存储结构两种，前者称为顺序表，后者称为链表，其中顺序表是保存在一片连续的存储空间中的，而链表则是通过指针来与其他数据进行联系，每个数据元素除了存储元素本身信息，还要存储与其他数据之间的关系。
3.单链表：包含数据域和指针域，指针域有一个指针，指针指向下一节点的地址。
4.双链表：包含数据域和指针域，指针域有两个指针，一个指针指向下一节点的地址，另一个指针指向上一节点的地址。
5.循环单链表：在单链表基础上，最后一个节点的后继指向第一个节点
6.循环双链表：在双链表基础上，最后一个节点的后继指向第一个节点，第一个节点的前驱指向最后一个节点。
7.静态链表：借助数组来描述线性表的链式存储结构，节点也有数据域和指针域。但指针是节点的相对地址(数组下标)，需要预先分配连续的内存空间。
第三章：栈与队列
1.栈：栈是一个特殊的线性表，它在操作上有一些特殊的要求和限制：栈的元素必须“后进先出”，栈的操作只能在这个线性表的表尾进行。
2.队列：队列是一个特殊的线性表，它在操作上有一些特殊的要求和限制：队列的元素必须“先进先出”，队列的入队操作只能在这个线性表的一端进行，出队操作只能在这个线性表的另一端进行。进行删除操作的一端称为队头，进行插入操作的一端称为队尾。
3.假溢出：系统作为队列用的存储区还没有满，但队列却发生了溢出，我们把这种现象称为"假溢出”。
解决办法：
一是将队列元素向前“平移”(占用0至rear-front-1);
二是将队列看成 首尾相连，即循环队列(0..m-1)。
另一种解法是“设标记”方法，如设标记tag， tag等于0情况下，若删除时导致front=rear 为队空;tag=1情况下,若因插入导致front=rear则为队满。
4.循环队列:为了克服顺序队列中假溢出,通常将一维数组Queue[0]到Queue [MAXSIZE-1]看成是一个首尾相连接的圆环,即Queue[0]与Queue[MAXSIZE-1]相连接在一起,将这样形式的队列成为循环队列。
5.递归函数：对于某一函数f(x)，其定义域是集合A，若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定,那么就称f(x)为递归函数。
第四章：串
1.串；由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。
2.串的存储方式：可大致分为三种，定长顺序存储方式、动态分配的堆分配存储方式以及链式存储方式。
所谓堆，即为一块内存。当程序运行时，系统自动为程序分配一块内存，这块内存是空的。每当使用malloc或new函数的时候，新声明的变量就都会被存入这片内存中。
使用完毕后，若不及时free或delete之前声明的变量，堆中刚占用的内存就不会释放，即内存泄露问题。总而言之，串的堆存储就是根据需要动态分配字符串的存储空间。
3.模式匹配：模式匹配是数据结构中字符串的一种基本运算。其是求第一个字符串(模式串)在第二个字符串(主串)中的位置。
4.KMP: Knuth-Morris-Pratt算法(简称KMP),是由D.E. Knuth、J.H. Morris和V.R. Pratt 共同提出的一个改进算法，消除了朴素的模式匹配算法中回溯问题，完成串的模式匹配。
5.BM: BM算法是一种精确字符串匹配算法(区别于模糊匹配)。采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。
第五章：树与二叉树
1.树的定义：包含n(n>0)个节点的有穷集合。
(1)集合中的每一个元素都称为一个节点(Node)
(2)有一个特殊的节点称为根节点(Boot)
(3)根节点之外的节点元素被分为m(m>=0)个互不相交的集合，其中每一个集合本身也是一颗树，称为根节点的子树。
2.树的存储结构：双亲表示法，孩子表示法，孩子兄弟表示法。
3.树的节点：包括一个数据元素以及若干指向其子树的分支。
- 节点拥有的子树称为节点的度。
- 度为0的节点称为叶子或终端节点。
- 树的度是树内个节点的度的最大值。
- 节点的子树的根称为该节点的孩子，相应的该节点为孩子的双亲。
- 同一个双亲的孩子之间互称兄弟。
- 节点的祖先是从根到该节点的所经分支上的所有节点。
- 反之，以某节点为根的子树中任一节点都称为该节点的子孙。
4.节点的层次：从树根开始定义，根节点为第1层，它的子节点为第2层，以此类推。
5.树的高度或深度：树中节点的最大层数。
6.有序树和无序树：树中节点的子树从左到右是有次序的，不能交换，叫做有序树。反之为无序树。
7.二叉树：是另一种树形结构，每个节点至多有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
性质1：二叉树第i层上的节点数目最多为
性质2：深度为k的二叉树至多有 2k-1 个节点(k≥1)。
性质3：包含n个节点的二叉树的高度至少为！ [log₂(N+ 1)]|或者[log2N]+1
性质4：在任意一棵二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1。
8.满二叉树：一棵高度为h，并且含有： 2h -1个节点的二叉树称为满二叉树。即每层都有最多的节点，叶子集中在二叉树的最下一层且除叶子之外的每个节点度为2.
9.完全二叉树：若设二叉树的深度为h，除第h层外，其它各层(1~h-1)的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。
11.森林:m(m>=0)棵互不相交的树的集合。
12.哈夫曼树：在含有N个带权叶子节点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树或最优二叉树。
13.哈夫曼编码：一种广泛应用而且非常有效的数据压缩编码。
14.路径和路径长度：树中两个节点之间的路径是由这两个节点之间所经过的节点序列构成的。路径长度是路径上经过的边的个数。
15.树的路径长度：树根到每一个节点的路径长度之和
16.树的带权路径长度(WPL)：树中所有叶子节点的带权路径长度之和。
17.二叉树的遍历：指按某条搜索路径访问树中的每个节点，使得每个节点均被访问一次且仅被访问一次。
18.树的先根遍历：若树非空，则先访问根节点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。
19.树的后根遍历：若树非空，则按从左到右的顺序遍历根节点的每一棵子树，之后再访问根节点。其访问顺序与其对应的二叉树的中序遍历相同。
20.先序遍历森林：若森林非空，则按如下规则遍历：
- 访问森林第一棵树的根节点
- 先序遍历第一棵树中根节点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
21.中序遍历森林：若森林非空，则按如下规则进行遍历：
- 中序遍历森林中第一棵树的根节点的子树森林
- 访问第一棵树的根节点
- 中序遍历除去第一棵树之后剩余的树构成的森林
22.线索二叉树：按照某种遍历与式对二叉树进行遍历，可以把二叉树中所有节点排序为一个线性序列。
在该序列中，除第一个节点外每个节点有且仅有一个直接前驱节点；除最后一个节点外每一个节点有且仅有一个直接后继节点。
这些指向直接前驱节点和指向直接后续节点的指针被称为线索(Thread)，加了线索的二叉树称为线索二叉树。
23.决策树：决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。
由于这种决策分支画成图形很像一棵树的枝干，故称决策树。
在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。
Entropy=系统的凌乱程度，使用算法ID3，C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
分类树(决策树)是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
24.随机森林：指的是利用多棵树对样本进行训练并预测的一种分类器。
第六章：图
1.图:由非空顶点集V和边集E组成,记作G=(V,E)。
2.图的存储结构：邻接矩阵、邻接表、十字链表、邻接多重表、边集数组。
3.有向图：E为有向边的有限集合时，图G为有向图
4.无向图：E为无向边的有限集合时，图G为无向图
5.简单图：不存在重复边，不存在顶点到自身的边称图G为简单图。与多重图相对
6.完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。具有n*(n-1)/2条边。有向图中，若任意两个顶点之间存在方向相反的两条弧，称为有向完全图，含有n(n-1)条有向边。
7.子图：如果一个图G2的所在顶点和边都是另一个图G1的子集，则称G2是G1的子图，只有顶点和边的集合都是子集，才称为子图，也就是说若顶点集合是子集，而边集合不是子集，不能称为子图。
8.连通：若从顶点v到顶点w存在路径，则v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则为非连通图。
9.连通分量：无向图中的极大连通子图称为连通分量。
10.强连通图：在有向图中，若从V到顶点W和从顶点W到顶点V都存在路径，则称两个顶点是强连通的，若图中任一对顶点都是强连通的，则称为强连通图。
11.强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。
12.生成树和生成森林：连通图的生成树是包含图中所有顶点的一个极小连通子图。若顶点为n则含有n-1条边。非连通图中，连通分量的生成树构成生成森林
13.最小生成树：一个带权连通无向图的生成树中边的权值之和最小的那个叫做此图的最小生成树。
14.路径、路径长度和回路：顶点V到顶点Q之间的一条路径是指之间的一个顶点序列。路径的长度是路径上边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。
15.简单路径：若一条路径上顶点不重复出现，则称这个路径为简单路径。
16.简单回路：若路径上第一个顶点和最后一个顶点相同，称为回路，或环，除了第一个顶点和最后一个顶点相同，其余各顶点都不重复出现的回路称为简单回路。
17.最短路径：带权图中，从一个顶点V0到另一个顶点V1的一条路径上所经过边的权值之和定义为该路径的带权路径长度，其中最短的那条称作最短路径。
此路径的长度称为从v 到u的距离。
18.图的遍历：从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中所有顶点访问一次且仅访问一次。
19.深度优先搜索：类似于树的先序遍历，假设从图中某顶点V出发，在访问了V之后一次从V的未被访问的邻接点出发做深度优先遍历，直到图中所有和V有路径相同的顶点都被访问到。
若图中还有顶点未访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。
20.广度优先搜索：类似于树的层次遍历，从顶点v出发，访问了V之后依次访问v的各个未被访问过的邻接顶点。再依次访问它们的邻接点，并使先被访问的顶点的的邻接点先于后访问的顶点的邻接点。
直到图中所有已被访问顶点的邻接点都被访问到。如果图中还有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问。
21.A0V网，用有向无环图表示一个工程，顶点表示活动，有向边<Vi， Vj>表示Vi必须先于Vj进行的关系。则称为AOV网。
22.AOE网，在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销(如时间)，则称这个网络为AOE网。
23.关键路径：在AOE网中，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是关键活动。
24.拓扑排序：将有向图中的顶点以线性方式进行排序，通过偏序得到图的全序。即对于任何连接自顶点u到顶点v的有向边<u，v>，在最后的排序结果中，顶点u总是在顶点v的前面。
第七章：排序
1.排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
2.算法的稳定性：假设Ri=Rj，且在排序之前Ri领先于Rj，若在排序后的序列中Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的。
3.内部排序：排序期间元素全部存放在内存中的排序；外部排序是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断的在内外存之间移动的排序。
4.监视哨：临时存储和判断数组边界。
5.插入排序：每次将一个待排序的记录，按关键字大小插入到前面已经排好序的子序列中，直至全部记录插入完成。
6.希尔排序：又称缩小增量排序，先将整个记录序列分割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体进行一次直接插入排序。
7.冒泡排序：从前往后(或从后往前)两两比较相邻元素的值，若为逆序则交换，知道序列比较完，既完成一趟冒泡排序。这一趟确定的最小元素不再参与比较，重复上述过程直到一趟排序没有记录交换。
8.快速排序：通过一趟排序将待排记录分配成独立两部分，其中一部分的关键字均比另一部分小，分别对两部分再进行快速排序直至整个序列有序
9.选择排序：每一趟在未排序的记录中选择最小的记录作为有序序列部分的下一个记录。
10.归并排序：将两个或两个以上的有序表组合成一个新的有序表。二路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
11.基数排序：采用多关键字排序思想，借助“分配/收集”两种操作对逻辑关键字进行排序。
12.堆排序：一种树形选择排序方法。在排序过程中把Z[1…N]堪称一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲和孩子之间的关系，在当前无序区选择最大或最小的元素。
13.堆：堆常用来实现优先队列，在这种队列中，待删除的元素为优先级最高(最低)的那个。在任何时候，任意优先元素都是可以插入到队列中去的，是计算机科学中一类特殊的数据结构的统称。【注意与栈的区别】
14.桶排序：工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间(0(n))。但桶排序并不是比较排序，他不受到0(nlog n)下限的影响。
第八章：查找
1.查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
2.查找表(查找结构)：用于查找的数据集合称为查找表。
3.静态查找表：如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中和检索满足条件的某个特定的数据元素的各种属性，则称为静态查找表。
4.动态查找表：需要动态的插入或删除的查找表称为动态查找表。
5.关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
6.平均查找长度(ASL)：在查找的过程中，一次查找的长度指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
7.折半查找：仅适用于有序的顺序表。将给定的值key与表中间位置元素的关键字比较，相等则查找成功返回位置。若不等则缩小查找范围，重复查找直到找到或者确定表中没有需查找的元素。
8.二叉排序树：一棵二叉排序树或是空二叉树或是具有以下性质的二叉树：左子树上所有关键字均小于根节点的关键字，右子树所有节点关键字大于根节点的关键字。左子树和右子树又各是一棵二叉排序树。
9.平衡二叉树：树上任一节点的左子树和右子树的深度之差不超过1.
10.平衡因子：该节点的左子树深度减去它的右子树深度。
11.判定树：树中每个节点表示表中的一个记录，节点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。
12.散列函数：一个把查找表中的关键字照射成该关键字对应的地址的函数，
13.冲突(同义词)：散列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突。
14.散列表：是根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址指间的一种直接映射关系。
15.开放定址法：指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
16.拉链法(链地址法)：把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。
17.装填因子：填入表中的元素个数/散列表的长度。
18.二次聚集：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。
19.再哈希法：这种方法是同时构造多个不同的哈希函数：H₁=RH₁(key) i=1,2,……,
k。当哈希地址H₃=RH₁(key)发生冲突时,再计算 ，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
20.红黑树：红黑树是一种特定类型的二叉树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由RudolfBayer发明的，他称之为"对称二叉B 树",它现代的名字是在LeoJ. Guibas和RobertSedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的，它可以在0(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
21.胜者树与败者树：胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。每个叶子节点相当于一个选手，每个中间节点相当于一场比赛，每一层相当于一轮比赛。
不同的是，胜者树的中间节点记录的是胜者的标号；而败者树的中间节点记录的败者的标号。
数据结构 - 简答题合集
第一章：绪论
1、数据结构是一门研究什么的学科?
数据结构是一门研究非数值计算的程序设计问题中，计算机操作对象及对象间的关系和施加于对象的操作等的学科。
2、数据存储结构有哪几种类型?
存储结构可分为顺序存储、链式存储、索引存储和散列存储。
3、数据逻辑结构包括哪几种类型?
逻辑结构包括线性结构和非线性结构。更细分的话可以说，逻辑结构包括集合、线性结构(线性表、栈、队列等)、树形结构和网状结构。
4、数据结构与数据类型有什么区别?
答：数据结构这一术语有两种含义，一是作为一门课的名称，二是作为一个科学的概念，目前尚无公认定义，一般认为，数据结构包括三个方面数据的逻辑结构，数据的存储结构，数据的运算。而数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构，后者是前者的一种简化情况。
5、数据类型和抽象数据类型是如何定义的?二者有何相同和不同之处?抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?数据类型和抽象数据类型是如何定义的?二者有何相同和不同之处?抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?
答：数据类型是程序设计语言中的一个概念，数据类型是值的集合和操作的集合，可以看做是已实现了的数据结构
抽象数据类型指一个数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示与实现无关。无论其内部如何变化。只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念，但是抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义，表示和实现三部分，封装在一起，对用户透明(提供接口)，而不必了解实现细节。
第二章：线性表
1、对顺序存储结构和链式存储结构，比较它们的优缺点。在什么情况下用顺序表比链表好?
1)顺序存储时，相邻数据元素的存放地址相邻(逻辑与物理统一)，内存中可用存储单元的地址也连续。
优点：存储密度大，存储空间利用率高。缺点：插入删除需要移动元素。
2)链式存储时，相邻元素随意存放，存储空间由结点值和指针两部分组成。
优点：插入删除方便。缺点：存储利用率低。
在线性表长度变化不大，主要操作是查找时，采用顺序表。
在线性表长度变化较大，插入删除操作时，采用链表。
2、试举一例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。
答：线性表的插入删除操作。在顺序存储方式下平均移动一半元素，时间复杂度为0(n)，在链式存储方式下，插入和删除的时间复杂度都是0(1)。
3、说明头指针、头节点、首元结点的概念
头指针是指向链表中第一个结点(或头节点或首元结点)的指针。
头节点是在链表的首元结点之前附加的一个结点，头结点是为了操作的统一方便而设立的。数据域一般无意义，只放空表标志和表长等信息。
首元素结点是指链表中存储线性表中第一个元素结点。
4、简述顺序存储队列假溢出的避免方法及队满和空的条件。
答：避免方法：一是将队列元素向前“平移”(占用0至rear-front 1)；二是将队列看成首尾相连，即看做循环队列(0…m-1)。
在循环队列下，定义front=rear时为队空，而判断队满则常用两种方法：一种是用 “牺牲一个单元” ,即rear+1=front(准确说是(rear+1) %m==front时,m是队列容量)时为队满:另一种方法是 “设标记”,如设标记tag, tag=0时为队空: tag=1时,若因插人导致front=rear 则为队满。
第三章：栈与队列
1、栈、队列的名词解释。栈、队列和线性表之间的联系与区别。
栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出表。
栈与队列都是操作受限的线性表，只允许在端点插入删除。都可通过顺序结构和链式结构实现。插入删除时间复杂度都为0(1)。
栈只允许在栈顶插入删除，队列在队头删除队尾插入。
相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储：栈和队列是两种特殊的线性表，即受限的线性表，只是对插人、删除运算加以限制
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插人删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插人，另一端进行删除运算，因而是先进先出表FIF0.②用途不同，堆栈用于子程调用和保护现场列用于多道作业处理、指令寄存及其他运算等等
2、栈和队列的应用有?
栈：表达式的转换和求值、函数调用和递归实现、深度优先搜索遍历
队列：计算机系统中各种资源的管理、消息缓冲器的管理、广度优先搜索遍历
2、什么是递归程序?
一个函数在结束本函数前，直接或间接调时函数自身，称为递归。
递归程序的优点是程序结构简单，清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。
递归程序执行中需要借助栈这种数据结构来实现。
递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序有基本项和归纳项组成。
第四章：串
1、什么是串?
串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。
2、描述一下概念的区别：空格串和空串
空格是一个字符，其ASCII码值是32。空格串是用空格组成的串，其长度等于空格的个数。
空串是不含任何字符的串，即空串的长度是零。
3、什么是广义表?广义表与线性表的区别
线性表中的元素可以是各种各样的，但必须具有相同的性质，属于同一数据对象。
广义表中的元素可以是元素也可以是子表。
4、试叙述一维数组和有序表的异同
一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排序(非递增或非递减)，而一维数组中元素没有按元素值排列顺序的要求。
第五章：树与二叉树
1、树与二叉树的区别和联系?
树与二叉树是两种不同的数据结构，在逻辑上都是树形结构，区别主要有：
一是二叉树的度至多为2，树无此限制；
二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还有右子树，树无此限制；
三是二叉树允许为空，树一般不允许为空。
2、什么叫完全二叉树
完全二叉树由满二叉树而引出来，对于深度为K的，有n结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
第六章：图
1、完全图
也叫简单完全图，假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。
2、连通、连通分量、强连通分量的概念，极大连通子图?极小连通子图?
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。图中任意两点是连通的，则称图G为连通图。无向图中的极大连通子图称为连通分量。
有向图中，若v到w和w到v都有路径存在，则称这两个点是强连通的。任一对顶点都是强连通的，则此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。
极大是要求该连通子图包含其所有的边(暗指无向图)，亦为连通分量。
极小是在保持连通的情况下使边数最少的子图(暗指无向图)，亦为最小生成树。
3、对一个图进行遍历可以获得不同的遍历序列，那么导致得到不同遍历序列不唯一的因素有哪些?
遍历不唯一的因素有：开始遍历的结点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
4、在什么情况下， Prim算法和Kruskual算法生成不同的最小生成树MST?
在有相同权值边时生成不同的MST，在这种情况下，用Prim算法或Kruskual算法会产生不同的MST。
5、Prim算法和Kruskual算法区别
Prim算法是加点法，适合边稠密图；Kruskual算法是一种按权值的递增次序选择合适边来构造生成树的加边法，适合边稀疏而顶点较多的图。
第七章：查找
1、散列表存储的基本思想是什么?
散列表的基本思想是用关键字的值决定数据元素的不储地址
2、散列表存储中解决碰撞的基本方法有哪些?
a、开放定址法根据di的取值又分为线性探测再散列、二次探测再散列、伪随机探测再散列
b、再散列法
c、链地址法
d、建立公共溢出区
3、如何衡量hash函数的优劣?
能否将关键字均匀映射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。
4、在查找算法中，设置监视哨的作用是什么?
监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。
5、对于一个有序顺序表来说，折半查找是否任何时候比顺序查找快?为什么?
答：并非在任何情况下折半查找都比顺序查找快。例如，若待查元素是该顺序表的第一个元素，则顺序查找顺序表会更快。对有序顺序表采用顺序查找，若元素存在表中，则在任一位置，查找都可能成功。同样，若元素不在表中，则在任一位置，查找都可能结束。折半查找必须经一-系列计算，方知查找成功还是失败。尽管如此，一般说来，在大多数情况下，折半查找还是比顺序查找快。
第八章：排序
1、排序稳定性的概念
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。
2、稳定排序有哪些?不稳定排序有哪些?
稳定排序：直接插入排序、冒泡排序、归并排序、基数排序
不稳定排序：选择排序、希尔排序、快速排序、堆排序
3、快速排序是在所有情况下，排序速度最快的吗?为什么?
不是，因为当序列已有序时，快速排序退化成了冒泡排序，时间复杂度为0(n2)。
当待排序列无序，使每次划分完成后，枢轴(pivot)两侧子文件长度相当，此时快速排序性能最好。
4、比较次数与序列初态无关的算法是：二路归并排序、简单选择排序、基数排序比较次数与序列初态有关的算法是：快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
5、简述堆的结构
堆是一种特殊的完全二叉树，所有父结点都比子结点要小的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。