[话筒]22计算机考研数据结构各类排序算法…来自 教育…(话筒)

加入抓码公益社群，解锁更多计算机考研干货▼

抓码22计算机考研qq总群：625590924

22考研咨询 | 码哥（jnumagekaoyan）

或 码哥02（magevip2）

---

1

顺序查找

顺序表的的查找一般分为对有序表和无序表的查找。

对有序表和无序表的顺序查找成功的平均查找长度相同，都为：

而无序表的查找失败的平均查找长度为n+1（要查找到最后一个元素），有序表的查找失败的平均查找长度为：

2

折半查找

前提：有序的顺序表

查找成功：asl成功=o(log2(n+1))

查找失败：asl失败=［log2n］+1（折半查找判定树的树高）

3

分块查找

查找成功（索引表和块内采用顺序查找）：

（b为分块的数目，s为一块内元素的个数）

查找成功（索引表采用折半查找）：

（b为分块的数目，s为一块内元素的个数）

4

顺序表顺序查找、折半查找、分块查找的3种查找方法比较：

上述3种查找方法的比较如下:

?就平均查找长度而言，折半查找的平均查找长度取小，分块查找次之，顺序查找最大。

?就表的结构而言，顺序查找对有序表、无序表均适用，折半查找仅适用于有序表，而分块查找要求表中元素至少是分块有序的。

?就表的存储结构而言，顺序查找和分块查找可以适用于顺序表和链表两种存储结构,而折半查找只适用于以顺序表作为存储结构的表。

?分块查找综合了顺序查找和折半查找的优点，既能较快速地查找，又能适应动态变化的要求。

5

对长度为2^k-1的有序表进行折半查找，在成功查找时，最少需要多少次关键字比较?最多需要多少次关键字比较?查找失败时的平均比较次数是多少?

当查找的记录正好处于中间位置时，关键字比较次数最少，所以折半查找在成功查找时最少需要1次关键字比较。

折半查找在成功查找时最多关键字比较次数为判定树的高度，即?log2(2^k-1+1) = k。折半查找在不成功查找时比较过程都落在外部节点中，将判定树看成是一棵满二叉树，所有外部节点的高度为k+1，其关键字比较次数为k，所以查找失败时的平均比较次数是k 次。

6

散列表

查找成功：比较次数/表长

查找失败：查找失败时的比较次数/（mod后的数字）

决定散列表查找的asl的因素：

?选用的散列函数;

?选用的处理冲突的方法;?

?散列表饱和的程度，即装填因子的大小。（装填因子是指散列表中已存入的记录数ｎ与散列表长度ｍ的比值，单独凭n或m不构成影响asl的因素）

7

b树与b+树的不同点

?在b+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树;而在b树中，具有n个关键字的结点含有n+1棵子树。

?在b+树中，每个结点(非根内部结点)的关键字个数n的范围是［m/2］≤n≤m (根结点:1≤n≤m);在b树中，每个结点(非根内部结点)的关键字个数n的范围是［m/2］ -1≤n≤m-1 (根结点: l≤n≤m-1)。

?在b+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只

含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

?在b+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中;而在b树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

?b+树查找时是从上到下查找；b-树则是从下往上查找（中序遍历）。

8

简述平衡二叉树中插入新节点导致不平衡进行调整的4种形态。

在平衡二叉树中插入新节点可能导致不平衡，调整成平衡二叉树的4种形态如下。

ll型调整:在节点的左子树的左子树上插入新节点导致不平衡。

rr型调整:在节点的右子树的右子树上插入新节点导致不平衡。

lr型调整:在节点的左子树的右子树上插入新节点导致不平衡。

rl型调整:在节点的右子树的左子树上插入新节点导致不平衡。

9

排序算法时间性能对比

按平均的时间性能来分，有三类排序方法：?

时间复杂度为o(nlogn)的方法有：快速排序、堆排序和归并排序?

时间复杂度为o(n²)的有：直接插入排序、起泡排序和简单选择排序?

时间复杂度为o(d(n+r))的排序方法只有基数排序。

10

哪些排序算法会受初始关键字分布的影响？

当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到o(n)的时间杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为o(n²)，因此 是应该尽量避免的情况。?

另外，简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

11

哪些排序算法会受初始关键字分布的影响？

?所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为o(1)；

?快速排序为o(logn)，为栈所需的辅助空间;

?归并排序所需辅助空间最多，其空间复杂度为o(n);

?链式基数排序需要队列，则空间复杂度为o(r)。

12

排序算法的稳定性

?稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

?对于不稳定的排序方法，只要能举出一个实例说明即可。

?快速排序、简单选择排序、堆排序和希尔排序是不稳定的排序方法。

13

排序算法的比较

14

比较直接插入排序算法和希尔排序算法的不同点

直接插入排序算法是稳定的，更适合于原始元素基本有序的情况。若采用折半查找而不是顺序查找待插入元素的插入位置时，可减少元素比较的次数，但移动元素的次数没有减少;在采用顺序查找待插入元素的插入位置时也适用于链式存储结构。

希尔排序算法是不稳定的;元素的总比较次数和移动次数都比直接插入排序时要少，n越大时，效果越明显;增量序列d可以有不同的取法，但有两个共同的特征，即最后一个增量必须是1，增量序列中的值没有除1之外的公因子;希尔排序不适用于链式存储结构。

15

指出堆和二叉排序树的区别。

以小根堆为例，堆的特点是双亲节点的关键字必然小于等于孩子节点的关键字，而两个孩子节点的关键字没有次序规定。而二叉排序树中，每个双亲节点的关键字均大于左子树节点的关键字，每个双亲节点的关键字均小于右子树节点的关键字，也就是说，每个双亲节点的左、右孩子的关键字有次序关系。

16

堆排序是否是一种稳定的排序方法?为什么?

堆排序是一种不稳定的排序方法。因为在堆的调整过程中，关键字进行比较和交换所走的是该节点到叶子节点的一条路径，因此对相同的关键字而言，就可能出现排在后面的关键字被交换到前面来的情况。

17

将快速排序算法改为非递归算法时通常使用一个栈，若把栈换为队列会对最终排序结果有什么影响?

在执行快速排序算法时，用栈保存每趟快速排序划分后左、右子区段的首、尾地址，其目的是为了在处理子区段未排序子序列时能够知道其范围，这样才能对该子序列进行排序(排序过程中可能产生新的左、右区段)，但这与处理子序列的先后顺序没什么关系，而仅仅起存储作用。因此，用队列同样可以存储子区段的首、尾地址，即可以取代栈的作用。在执行快速排序算法时，把栈换为队列对最终排序结果不会产生任何影响。