数据结构与算法-考研试题(清华大学 1992年快速排序)

问答题（1992年清华大学）

回答问题并写出推导过程：

对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少？

答案解析

最大比较次数：在关键字有序的情况下，为

49+48+...+1=1225

最小比较次数：判定树如下图所示（树中结点，所示数字为此子序列所含关键字个数）

判定树 50 快速排序

最少比较次数：49+47+43+35+19=193.

讨论

数据结构与算法

在起泡（冒泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，请举例说明之。快速排序过程中有没有这种现象？

快速排序的最大递归深度是__________，最小递归深度是__________。

快速排序的速度在所有排序方法中为最快，而且所需附加的空间也最少。

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是【】。

下述排序算法中，所需辅助存储量最多的是__________，所需辅助存储量最少的是__________，平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序

在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么查找失败到达失败结点时所做的数据比较次数是多少？

最佳二叉树是AVL树（平衡二叉树）。

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。

若散列表的负载因子α<1，则可避免碰撞的产生。

快速排序

下列排序算法中，不稳定的是【】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢【】。

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列，用【】方法最快

根据枢轴元素(或基准元素)划分序列而进行排序的是【】。

写出和下列递归过程等价的非递归过程。void test(int sum){ int a; scanf("%d",&a); if(a==0) sum=1; else{ test(sum); sum=sum*a; } pritf("%d",sum); }

用单链表表示的链式队列的队头在链表的【】位置。

线性表是具有n个【】的有限序列。

设无向图的顶点个数为n，则该无向图最多有【】条边。

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

内部排序

下列排序算法中，哪些时间复杂度不会超过nlogn【】。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为【】。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

若有n个元素已构成一个小根堆，那么如果增加一个元素Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

堆排序是不是一种稳定的排序方法？为什么？

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

在待排序的一组关键码序列k1，k2，…，kn中，若ki和kj相同，且在排序前ki领先于kj，那么排序后，如果ki和kj的相对次序保持不变，ki仍领先于kj，则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形，则称此类排序为不稳定的。【】是稳定的排序方法。

对n个记录进行非递减排序，在第一趟排序之后，一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是【】。