计算机考研复试_数据结构_考试复试数据结构

名词解释

1. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式，它分为三个方面，即数据的逻辑结构，数据的物理结构，数据的操作。
2. 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，可分为原子类型和结构类型。
3. 抽象数据类型：是基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
4. 数据的逻辑结构：是数据元素之间逻辑关系的描述。
5. 数据的物理结构(数据的存储结构)：是指数据的逻辑结构在计算机中的映像，即数据结构在计算机中的存储方法。
6. 结构化算法：结构化算法是由一些基本结构顺序组成的，就是把一个大的功能的实现分隔为许多个小功能的实现。
7. 线性表：线性表是具有相同特性数据元素的一个有限序列。
8. 栈：是一种后进先出的线性表，它只允许在表尾进行插入和删除操作，表尾端称为栈顶，表头端称为栈底。
9. 队列：是一种先进先出的线性表，它只允许在表的一端进行插入，在表的另一端进行删除，允许插入的一端称为队尾，允许删除的一端称为队首。
10. 满二叉树：是一棵深度为k的，且有2k-1个结点的二又树。
11. 完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。
12. 二叉排序树(二叉查找树)：一棵二叉树或者是空二叉树，或者是具有以下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。
13. 平衡二叉树（AVL树）：是一种特殊的二叉排序树，以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
14. 连通图：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图。
15. 连通分量：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
16. 关键路径：在AOE网中, 从源点到汇点的所有路径中, 具有最大路径长度的路径称为关键路径。
17. 堆：堆是一类特殊的树，堆的通用特点是父节点会大于或小于所有子节点。

常用的数据结构

  数据结构可分为8类：数组、链表、栈、队列、树、散列表、堆、图。

算法的五大特性

（1）输入：算法具有0个或多个输入。
（2）输出：算法至少有1个输出。
（3）有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。
（4）确定性：算法中的每一步都有确定的含义，不会出现二义性。
（5）可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成。

数据结构和数据类型的区别

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

线性结构和非线性结构的区别

（1）线性结构：除第一个元素和最后一个元素外，每个数据元素都有唯一的前驱和唯一的后继，第一个元素没有前驱，最后一个元素没有后继，关系是一对一的。
（2）非线性结构：表示结点间关系的前驱后继不具有唯一性，结点间是一对多或多对多的关系。

比较顺序存储和链式存储的优缺点

（1）顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)，要求内存中可用存储单元的地址必须是连续的。
  优点：① 存储密度大(＝1)，存储空间利用率高；
     ② 可随机存取表中的任一元素，查找元素方便。
  缺点：① 插入或删除元素时不方便，须移动大量元素，效率较低；
     ② 存在预分配空间问题。
（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分为两个部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
  优点：① 插入或删除元素时很方便，使用灵活；
     ② 支持动态分配空间。
  缺点：① 存储密度小(<1)，存储空间利用率低；
     ② 查找元素不方便。

数组和链表的区别

（1）数组
  优点：① 随机访问性强
     ② 查找速度快
  缺点：① 插入和删除效率低
     ② 可能浪费内存
     ③ 大小固定，不能动态拓展
（2）链表
  优点：① 插入和删除效率高
     ② 内存利用率高，不会浪费内存
     ③ 大小没有固定，拓展很灵活
  缺点：不能随机查找，必须从第一个开始遍历，查找效率低

对比栈和队列数据结构的特点，并举例它们的典型应用

（1）相同点：栈和队列都是线性结构，是两种特殊的线性表即受限的线性表，都对插入和删除操作加以限制；栈和队列都可以通过顺序结构和链式结构实现。
（2）不同点：栈只允许在一端进行插入和删除，因而是后进先出表；队列只允许在一端进行插入，另一端进行删除，因而是先进先出表。
（3）典型应用：常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优先搜索遍历等。

什么是栈溢出，并举个导致栈溢出的简单例子

（1）栈溢出的概念：
  栈溢出指的是程序向栈中某个变量写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。
（2）栈溢出的原因：
  ① 递归调用的层次太多。递归函数在运行时会执行压栈操作，压栈次数太多也会导致栈溢出。
  ② 指针或数组越界。例如进行字符串拷贝，处理用户输入等。

堆和栈的区别，以及为什么栈要快

（1）堆和栈的区别
  ① 扩展方向不同：堆是由低地址向高地址扩展；栈是由高地址向低地址扩展。
  ② 申请方式不同：堆由程序员手动分配和管理；栈由系统自动分配和管理；
  ③ 效率不同：堆由程序员分配，分配效率较低，可能由于操作不当产生内存碎片；而栈由系统分配，分配效率较高，不会有内存碎片。
  ④ 程序局部变量使用的是栈空间，new和malloc函数动态申请的内存是堆空间。
（2）栈的效率高的原因
  栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的存储器存储栈的地址，压栈和入栈有专门的指令执行；
  而堆是由C和C++函数库提供的，机制复杂，需要一系列分配内存、合并内存和释放内存的算法，因此效率较低。

小根堆和大根堆的特点

（1）小根堆：根节点的值小于左右子树的值。
（2）大根堆：根节点的值大于左右子树的值。

AVL 树和红黑树的定义、特点以及二者的区别

（1）平衡二叉树（AVL）树：
  平衡二叉树又称AVL树，是一种特殊的二叉排序树，以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。
  将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，那么该二叉树就是不平衡的。
（2）红黑树：
  红黑树是一种二叉查找树，它在每个结点上增加一个存储位表示结点的颜色，可以是红或者黑。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索、插入、删除操作较多的情况，通常使用红黑树。
  红黑树的性质：
    ① 每个结点非红即黑
    ② 根结点是黑的
    ③ 每个叶结点都是黑的
    ④ 如果一个结点是红的，则它的子节点必须是黑的
    ⑤ 对于任意节点而言，其到叶结点的每条路径都包含相同数目的黑节点
（3）区别：
  AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；
  红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

B 树（B- 树）和 B+ 树

  B-树是一种平衡的多路查找树，主要应用在文件系统。
  B+树是主要为磁盘或其他直接存取辅助设备而设计的一种平衡的多路查找树。在B+树中，每个结点都可以有多个孩子，并且按照关键字大小有序排列。所有记录结点都是按照键值的大小顺序存放在同一层的叶节点中。

哈夫曼树

  结点的带权路径长度指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
  树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作“WPL”。
  哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。
  对于给定的有各自权值的n个结点，构建哈夫曼树的办法是：
  第一步，在n个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子的权值之和；
  第二步，在原有的n个权值中删除那两个最小的权值，同时将新的权值加入这n–2个权值的行列中；
  第三步，重复上述两步，直到所有的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

哈夫曼编码

  利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根结点到每个叶子结点都有一条路径，对路径上的各分支规定，指向左子树的分支表示“0”，指向右子树的分支表示“1”，取每条路径上“0”和“1”的序列作为各个叶子结点对应的字符编码，即哈夫曼编码。
  哈夫曼编码的作用是实现数据无损压缩。

请简要叙述对一个有向图进行拓扑排序的过程

（1）从有向图中选择一个没有前驱(入度为0)的顶点输出；
（2）删除（1）中所选择的顶点，并且删除从该顶点发出的全部边；
（3）重复上述两步，直到图中不存在没有前驱的顶点为止。

什么是排序的稳定性，稳定的排序方法有哪些

  排序的稳定性是指当待排序序列中有两个或两个以上相同的关键字时，排序前和排序后这些关键字的相对位置，如果没有发生变化就是稳定的，否则就是不稳定的。
  稳定的排序方法有：直接插入排序、冒泡排序、归并排序和基数排序。

冒泡排序

  冒泡排序是通过一系列的“交换”动作完成的，首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换…按这种方式一直进行下去，最终最大的那个关键字被交换到了最后，一趟冒泡排序完成。然后经过多趟这样的排序，最终使整个序列有序。

快速排序

  通过一趟排序将待排序的数据分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字要小，之后再按此方法分别对这两部分记录继续进行快速排序，整个排序过程可以递归进行，最终达到整个序列有序的目的。

简单选择排序

  从头到尾顺序扫描序列，找出最小的一个关键字，然后和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使整个序列有序。

折半查找

  折半查找又称二分查找，它仅适用于有序的顺序表。
  首先给定值key与表中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不相等，则所查找的元素只能在中间值以外的前半部分或后半部分（例如，在查找表升序排列时，给定值key大于中间元素的关键字，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所查找的元素，则查找不成功，返回查找失败的信息。
  若关键字不在表中时，停止查找的典型标志是：查找范围的上界<=查找范围的下界。

散列表的概念，散列函数的构造方法，处理冲突的办法

  散列表又称为哈希表，是根据关键字而进行直接访问的数据结构。也就是说，散列表建立了关键字和存储地址的一种直接映射关系。
  散列表是一种数据结构，它的优点是可以提供快速的查找操作和插入操作。缺点是删除操作慢，散列表是基于数组的，而数组创建后难于扩展，某些散列表被基本填满时，性能下降得非常严重。
  散列函数是一个把查找表中的关键字映射成该关键字所对应地址的函数。散列函数可能会把两个或两个以上的不同关键字映射到同一地址，这种情况称为冲突。
  散列函数的构造方法包括：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法。其中，最常用的是除留余数法。
（1）直接定址法：取关键字的某个线性函数值作为散列地址，即
      H(key) = a*key+b。
（2）除留余数法：取关键字对p取余的值作为散列地址，其中p通常是小于或等于散列表表长m的质数，即
      H(key) = key % p
  处理冲突的方法包括：开放定址法和拉链法。其中，开放定址法包括：线性探查法，二次探查法，双重散列法。
（1）线性探查法：将散列表T[0…m-1]看成是一个循环向量，若初始探查的地址为d（即h(key)=d），探查时从地址d开始，首先探查T[d]，再探查T[d+1]…直到探查到T[m-1]，此后循环到T[0]，T[1]…直到探查到T[d-1]为止，探查时，如果遇到有空的地址就插入。
（2）拉链法：若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组，凡是散列地址为i的结点均插入到头指针为i的单链表中。
  与开放定址法相比，链地址法的优点是：
  ① 链地址法处理冲突简单，且无堆积现象，因此平均查找长度较短；
  ② 在用链地址法构造的散列表中，删除结点的操作易于实现。
  而链地址法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。

普里姆算法

  从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相接的边中选取一条最短（权值最小）的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。

克鲁斯卡尔算法

  普里姆算法是从某一顶点为起点，逐步找各个顶点最小权值的边来构成最小生成树。那我们也可以直接从边出发，寻找权值最小的边来构建最小生成树。不过在构建的过程中要考虑是否会形成环的情况。

迪杰斯特拉算法

  迪杰斯特拉算法是典型最短路径算法，用于计算一个节点到其他结点的最短路径。