考研数据结构复试题目整理_.多路归并排序主要包括两个相对独立的阶段,这两个相对独立的阶段分别为(),目置换-

数据结构复试题目自整理

说复试题目过于牵强，只是自己整理的一些知识点而已，为了便于理解和背诵，有些部分定义和说明尽量简明扼要，如有错误请多多指教！（不可转载）

只涉及简答形式，代码未总结（有用点点赞啊啊我升到3级就可以自定义标签了谢谢~）

1.大O什么意思？

在时间复杂度中，一个算法中所有语句被重复执行的次数记为T（n）,时间复杂度用来分析T（n）的数量级，也就是算法中基本语句被执行的次数，O的含义就是表示基本语句的数量级也就是算法的数量级。
在空间复杂度中，同样用O来表示基本运算所耗费的存储空间。

2.简述数据结构的三要素

逻辑结构：从逻辑上描述数据，即数据之间的逻辑关系。（线性结构和非线性结构）
物理结构：数据在计算机内的存储方式（顺序存储，链式存储，索引存储，散列存储）
数据的运算：数据的运算包括数据的定义与实现，运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

3.循环比递归效率高吗？

并不能绝对的说循环比递归效率高。
递归的优点是：代码简洁清晰，容易检查代码的正确性。缺点是：当递归调用的次数很多时，对执行效率会有一定的影响。
循环的优点是：结构简单，速度快；缺点是：并不能解决所有问题，有些问题适合用递归来解决而不适合用循环。

4.简述各存储结构

顺序存储：采用一组连续的存储空间存储数据。
优点：简单，可以实现随机存取，元素占用最少的存储空间。
缺点：只能使用连续的存储单元，会产生较多的外部碎片。
链式存储：数据的存储空间是离散的，借助元素中的指针来表示元素之间的逻辑关系。
优点：不会产生外部碎片，能充分利用所有存储单元。
缺点：只能顺序存取，每个元素因为存储指针而占用额外的存储空间。
索引存储：在存储元素数据的同时还建立附加的索引表。
优点：检索速度快。
缺点：索引表会占用额外的存储空间。
散列存储：根据元素的关键字直接得出元素的存储地址。
优点：检索，增加，删除元素的速度都很快。
缺点：散列函数选择不好可能会出现元素单元的冲突，而解决冲突需要额外的开销。

5.简述算法的特性？

（1）有穷性：一个算法必须在执行有穷步后结束。
（2）确定性：算法中的每条指令必须由确切的含义，不能有二义性。
（3）可行性：算法中描述的操作能够通过有限次的基本运算来实现。
（4）输入：一个算法必须有0个或者有限个输入。
（5）输出：一个算法必须有1个或者有限个输出。
一个好的算法应该保证：
正确性（算法能够正确的解决问题），可读性（易于人们理解），健壮性（输入非法数据时算法能够进行处理，不会出现莫名其妙的结果）。

6.顺序表与链表的比较

（1）存取方式：顺序表可以顺序存取，随机存取，链表是能顺序存取。
（2）逻辑结构和物理结构上：顺序存储是逻辑上相邻的元素物理上也相邻，链式存储是逻辑上相邻的元素物理上不一定相邻。
（3）插入删除操作:顺序表插入删除操作平均需要移动半个表长的元素，链表只需要修改相应的指针即可。
（4）空间分配：顺序存储在静态存储分配下需要预先分配足够大的空间，动态存储分配虽然可以扩充空间，但是需要移动大量的元素；链式存储空间在需要时申请即可。

7.头指针与头结点的区别

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

8.栈和队列的区别

队列和栈都是操作受限的线性表，队列是只允许在一段插入，在另一端删除的线性表，进入队列的元素按先入先出的原则进行处理；栈是指能在表尾进行插入和删操作的线性表，对于插入到栈的元素按先进后出的规则进行处理，插入和删除操作都在栈顶进行。

9.共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底设在共享空间的两端，两个栈顶向共享空间的中间延伸，这样能够更有效的利用存储空间。

10.队列在计算机系统中的应用

队列可以用于层次遍历和广度优先遍历
1.可以解决主机与外部设备之间速度不匹配的问题：以打印机为例，设置一个打印数据缓冲区数据按队列存储，主机先向缓冲区中写入数据，打印机按先进先出原则一次取出数据并打印。
2.解决多用户引起的资源竞争问题：以CPU资源的竞争为例，多个用户提出对CPU是使用请求,系统按照用户请求在时间上的先后顺序，排成队列将CPU依次分配。

11.串的存储结构

（1）定长顺序存储表示：采用一组连续的存储空间存储串的字符序列；
（2）堆分配存储表示：依然采用一组连续的存储空间存储串的字符序列，但是存储空间是在运行过程中动态分配的。

12.简述KMP算法

思想：如果已匹配相等的前缀序列中有某个后缀正好是子串的前缀，就可以将子串向后滑动到与这些后缀相匹配的位置。

13.名词解释，满二叉树，完全二叉树，二叉排序树，平衡二叉树。

满二叉树：高度为H，结点数为2^H-1的二叉树为满二叉树。
完全二叉树：除最后一层外，其余各层的节点数量达到最大值，并且最后一层只能在右侧缺少节点。
二叉排序树：左子树上所有的关键字均小于根结点，右子树上所有关键字均大于根结点。左子树和右子树又分别是一棵二叉排序树。
平衡二叉树：树中每一个结点的左子树，右子树高度之差的绝对值小于等于1

14.二叉树的存储结构

顺序存储：用一组连续的地址单元自上到下，自左到右的存储完全二叉树的结点元素。
链式存储：采用二叉链表来存储树的每个节点。

15.线索二叉树

将二叉链表中的空指针改成指向前驱节点或后继的线索。线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了 二叉链表找左、右孩子困难的问题。

16.树的存储结构

双亲表示法：采用一组连续的存储空间存储每个结点，同时在每个结点后面增设一个伪指针指向其双亲节点。
孩子表示法：将每个结点的孩子结点用单链表链接起来形成一个线性结构。
孩子兄弟表示法：以二叉链表作为树的存储结构，其左指针指向第一个孩子结点，右指针指向其相邻的兄弟结点。可以方便地实现树转换为二叉树的操作，易于查 找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。

17.哈夫曼树

权：树中的结点往往被赋予一个有意义的数值称为该结点的权。
结点的带权路径长度：从树的根到任意节点的路径长度与该结点的权值之积称为该结点的带权路径长度。
树的带权路径长度：树中所有叶结点的带权路径之和为该树的带权路径长度。
哈夫曼树：带权路径长度最小的树为哈夫曼树。

18.构造哈夫曼树的算法

将树中的每个结点都看成一个独立的二叉树构成森林F，从F中选择根结点最小的两棵树构成一棵新的二叉树，二叉树的根结点为两个结点之和，并将这两个树从F中删除，将新构成的树并入F中，重复上述过程，直到F中只剩下一个树。
特点：哈夫曼树中不存在度为1的结点，权值越小的结点距离根结点的路径长度越大。

19.图的名词解释

连通图：在无向图中如果两顶点之间有路径存在，就称这两个顶点是连通的。如果无向图中任意两个顶点是连通的，就称图为连通图。
极大连通子图（连通分量）：该连通子图包含所有的边。
极小连通子图：在保证连通的情况边最少的子图。
强连通图：在有向图中，如果顶点m到顶点n有路径存在且n到m也有路径存在，就称这两个顶点是强连通的。图中任何两个顶点都是强连通的，该图就是强连通图。
强连通分量：有向图中的极大强连通子图为强连通分量。
生成树：连通图中包含所有顶点的极小连通子图。
网：在图中每条边都可以标上具有某个意义的数值，称为该边的权值。边上带权值得图为网，

20.图的存储方式

邻接矩阵法：用一个一维数组存储图的顶点信息，用二维数组存储各顶点的邻接关系。存储顶点邻接关系的二维数组称为邻接矩阵。
邻接表法：图中每个顶点与其有邻接关系的顶点拉成一个单链表，每个顶点都有一个单链表。
十字链表法：十字链表法是有向图的一种链式存储结构。在十字链表中，有向图中的每一条弧都有一个对应的节点，每个顶点都有对应的一个节点。
邻接多重表法：

21.广度优先搜索

类似于层次遍历，先访问起始顶点，在访问与其相邻的所有顶点，再顺序访问与这些顶点相邻的顶点，重复上述过程，知道图中所有顶点都被访问过为止。

22.深度优先搜索

类似于先序遍历，从起始顶点出发，先访问与其相邻的顶点，再访问与该顶点相邻且未被访问过的顶点，重复上述步骤，当与其相邻的所有顶点都被访问过，依次回退曾经访问过的顶点，若某个顶点还有与其相邻且未被访问过的顶点，则从该点开始重复上述过程，直到所有顶点均被访问过。

23.最小生成树（普里姆算法，克鲁斯卡尔算法）

最小生成树：包含图中所有的顶点且含有最少的边且不构成回路。

24.普里姆算法

从图中任一顶点出发，构成一棵树，然后从与这棵树相邻的边中选择最小的边，并将这条边和所连接的顶点并入树中，在选择与该树相邻的最小边且不构成回路，将边和顶点并入，重复上述过程，直到所有顶点均已并入树中。

25.克鲁斯卡尔算法

假设图中每个顶点自成一个连通分量，按照图中边的权值由小到大的顺序，不断选取未被选取过且权值最小的边，若边的两个顶点在不同的连通分量上，就将该边及其顶点并入生成树中，如此重复，直到所有顶点均已并入。

26.最短路径

当图是带权图时，把从一个顶点到图中任意一个顶点的路径所经过的边的权值之和称为该路径的带权路径长度。把带权路径最短的那条路径称为最短路径。

27.迪杰斯特拉算法

设有两个顶点集S和T，S中存放当前已经找到最短路径的顶点，T中存放图中剩余顶点，开始时S中只有源点，然后不断地从集合T中选取到源点的路径长度最短的顶点并入集合S中，集合S每并入一个顶点就要修改源点到集合T中顶点的最短路径长度值，不断重复上述过程，直到集合T中顶点全部并入S。

28.弗洛伊德算法

总结的不标准先不放了

29.拓扑排序

AOV网：用顶点表示活动，有向边表示活动之间的关系的有向图记为AOV网。
在AOV网中选择一个没有前驱的顶点输出，并删除该顶点和以该顶点为起点的所有有向边，重复上述过程直到AOV网为空或者不存在无前驱的顶点为止。

30.关键路径

在带权有向图中，用顶点表示时间，以有向边表示活动，以边上的权值表示完成该活动所需要的时间，称为AOE网。

AOV网与AOE网的区别：

AOV网和AOE网都是有向无环图，区别在于它们的顶点和边所代表的含义是不同的，AOE网中的边有权值，AOV网的边无权值，仅代表活动之间的关系。
关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，在这条路径上活动称为关键活动，完成整个工程的最短时间就是关键路径的长度。

31.查找

静态查找：若一个查找表的操作无需动态的修改表，称为静态查找。
动态查找：需要动态的插入和删除的查找表称为动态查找表。
平均查找长度：所有查找过程中进行关键字比较次数的平均值。

32.顺序查找

从线性表的一端开始，逐个比较关键字的值是否满足查询条件。
优点：对数据元素的存储没有要求，顺序存储或链式存储均可。
缺点：平均查找长度大，效率低。

33.折半查找

若顺序表有序，先将关键字与表中间元素比较，若相等则查找成功，否则在除中间元素以外的前半部分或后半部分进行同样的查找，如此重复直到查找成功或者确定表中没有要查找的元素，查找失败。
优点：比顺序查找效率高
缺点：查找表必须有序且必须采用顺序存储结构。

34.分块查找

将查找表分为若干个子块，块内元素可以无序，各块之间必须有序，也就是说，第一个块内最大的关键字要小于第二个块内所有记录的关键字，第二个块内最大的关键字要小于第三个块内所有记录的关键字以此类推，再建立一张索引表，表项中存放每个块的最大关键字和第一个元素的地址。
查找步骤为：
（1）在索引表中确定待查记录所在的块，可以顺序查找也可以折半查找。
（2）在块内顺序查找。
吸取了顺序查找和折半查找各自的优点。

35.B树

B树中所有结点的孩子树的最大值为B树的阶，用m表示，一棵m阶B树的特点为：
（1）B树中每一个结点最多有m棵子树，即最多有m-1个关键字。
（2）B树除根结点外的所有非叶结点最少有m/2（向上取余）棵子树，即m/2（向上取余）-1个关键字。
（3）所有的叶节点都出现在同一层次且不带信息。
B树的查找：分两步（1）在B树中找结点（2）在节点内找关键字。由于B树常存放在磁盘上，所以第一次查找操作是在磁盘上进行的，而后一个查找操作是在内存上进行的，即在找到目标结点之后，先将结点读入内存，再对结点内采用顺序查找或折半查找。
B树的插入：（1）定位（2）插入（若被插入结点内关键字个数超出，就进行分裂）
B树的删除：（1）直接删除（2）兄弟够借（3）兄弟不够借（要进行合并）

36.m阶B树与B+树的比较

m 阶的B+树与m 阶的B 树的主要差异如下：

1. 在B+树中，具有n 个关键字的结点只含有n 棵子树，即每个关键字对应一棵子树；而在 B 树中，具有n 个关键字的结点含有n+1棵子树。
2. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只
   含有对应子树的最大关键字和指向该子树的指针。 在B树中页结点不携带任何信息。
3. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点
   中；而在B 树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

37.散列表

散列函数：一个把查找表中关键字映射成为该关键字对应地址的函数。
散列表：根据关键字直接进行访问的散列表，建立了关键字与存储地址的直接映射关系。
散列函数的构造方法：
（1）直接定址法：直接取关键字的某个线性函数值为其存储地址。
（2）除留余数法：假定散列表表长为m，取一个不大于m且最接近m的质数p，通过关键字取余p来得到关键字的存储地址。
（3）平方取中法：取关键字平方的中间几位作为该关键字的存储地址。
解决冲突的办法：
（1）开放地址法：
1.线性探测法：冲突发生时顺序查看表中下一个单元，直到找出一个空闲单元为止。（可能会造成大量元素在相邻的散列地址上堆积，降低查找效率）
2.平方探测法：令增量序列为0,1的平方，-1的平方……（能够避免出现堆积问题，但是不能够探测到散列表中的所有单元）
3.双散列法：使用两个散列函数，当第一个散列函数出现冲突时，就选用第二个散列函数。
（2）拉链法：把所有的同义词连接到一个线性链表中，这个线性链表由散列地址唯一标识。

38.排序

内部排序：排序期间元素全部存放在内存中。（插入，交换，选择，归并，基数）
外部排序：排序期间元素无法同时存放在内存中，必须在排序期间根据要求不停地在内，外存移动。（多路归并）

39.插入排序

直接插入排序：每次将一个待排序的记录按其关键字的大小插入到已排好序的子序列中。（1.从前面的有序子表中查出待插入元素应该插入的位置2.将已排序的记录逐步向后移动，给待插入元素腾出位置，并将待插入元素复制到插入位置。 适用顺序存储/链式存储）

折半插入排序：如果是顺序存储的线性表，可以通过折半查找的方式来查找待插入元素在有序子序列的位置。确定待插入位置之后，可以统一的向后移动位置。

希尔排序：将待排序列按相隔某个增量分割成若干个子序列，对各个子序列进行直接插入排序，逐渐缩小增量，重复上述步骤，直到序列基本有序，再对全体记录进行一次直接插入排序。

40.交换排序

冒泡排序：从前到后（从后往前）依次两两比较相邻元素的值，若为逆序，就交换元素，每一趟排序完成之后，就有一个元素被放在最终位置上，重复上述步骤，当一趟排序不发生任何元素的交换为止。
快速排序：每次从待排序列中选择一个元素作为枢轴（通常是序列的首元素），把比枢轴小的元素放前面，比枢轴大的元素放后面，最后确定枢轴元素的最终位置并将枢轴放入，再对枢轴前后得到的子序列再重复上述步骤，直到每部分只有一个元素或为空为止，则所有元素放在最终位置上。

41.选择排序

简单选择排序：每趟排序选择关键字最小的元素与序列前面的元素进行交换，每次排序均可确定一个元素的最终位置。
堆排序：先将待排元素建成初始堆，以大根堆为例，堆顶元素为最大值，将其输出后，把堆底元素送入堆顶，此时堆不满足大根堆的性质，将堆顶元素向下调整（从堆的最后一个非叶子节点开始，从左到右，从下到上的顺序进行调整），成为大根堆之后再输出堆顶元素，重复上述过程，直到输出所有元素。

42.归并排序

“归并”：就是将两个或两个以上的有序表组成一个新的有序表。
假定待排序表有n个记录，将其视为n个有序的子表，然后两两归并得到n/2个有序子表，再进行两两归并，直到合并成一个长度为n的有序表为止。

43.基数排序

创建0~9的十个数组，将待排序表的所有元素先按个位进行分类，将分类后的元素按索引大小取出形成新的队列，再对队列按十位，百位的顺序进行分类，重复上述过程，最后形成一个有序序列。

44.选取排序算法需要考虑的因素

（1）待排元素的数目；
（2）稳定性的要求；
（3）元素本身信息量的大小；
（4）关键字的结构及其分布情况；
若n较小，可直接采用直接插入排序或者简单选择排序。由于直接插入排序比简单选择排序移动的元素要多，所以当元素本身信息量比较大时可选用简单选择排序。
若待排序表已基本有序可以选用直接插入排序或者冒泡排序。
当n比较大时，可以选用快速排序、堆排序、归并排序。快速排序被认为是当前基于比较的内部排序中最好的排序方法，当待排序表记录随机分布时，使用快速排序速度最快。堆排序所用存储空间少于快速排序，且不会出现快速排序的最坏情况，这两种算法都是不稳定的，若要稳定排序则选用归并排序算法。

45.外部排序

采用多路归并法，包括两个相对独立的阶段：
（1）根据内部缓冲区的大小，将待排文件分成若干个大小合适的子文件，将子文件带入内存采用内部排序算法排序完成后再写回外存。
（2）对这些归并段进行逐趟归并，使归并段逐渐由小到大，直到得到整个有序文件为止。

46.提高外部排序算法的效率

由于待排文件无法全部放入内存，所以排序期间必须要频繁的进行内外存之间数据的交换，这会耗费大量的时间。所以可以通过增加归并路数来减少归并趟数，进而减少I/O次数。而增加归并路数又会增加内部排序的时间，所以引入了败者树。
增加初始归并段个数，并且不受内存空间的限制，引入了置换-选择算法。
文件经过置换-选择算法之后得到的是长度不同的初始归并段，如何组织长度不等的出使归并段的归并顺序，使得I/O次数最少，就引入了最佳归并树。

47.败者树（大的为失败者，小的为胜利者）

可视为一棵完全二叉树，每个叶结点存放各归并段在归并过程中参加比较的记录，非叶结点用来记录左右子树中的“失败者”，胜利者继续向上比较直到根节点。输出最后的胜利者。

48.置换选择算法

根据缓冲区的大小，由外存读入记录，当记录充满缓冲区时，选择最小的输出，其空缺位置由下一个记录来取代，输出记录称为当前初始归并段的一部分，如果新输出的记录比新建立归并段最大的记录小，就不能成为该归并段的一部分，只能成为下一个归并段的选择。重复上述步骤，直到缓冲区中所有记录都比当前归并段最大记录小时，就生成了一个初始归并段，用同样的方法继续生成下一个归并段，直到全部记录都处理完毕为止。

49.最佳归并树

对于K路归并算法，可用构造K叉哈夫曼树的方法来构造最佳归并树。

整理不易，请点点赞生生级好吧~