|
以关键字序列()为例分别写出执行以下排序算法的各趟排序结束时关键字序列的状态 () 直接插入排序 ()希尔排序 ()冒泡排序 ()快速排序 () 直接选择排序 () 堆排序 () 归并排序 ()基数排序 上述方法中哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例 上题的排序方法中哪些易于在链表(包括各种单双循环链表)上实现? 当R[lowhigh]中的关键字均相同时Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion使得划分结果是平衡的(即划分后左右区间的长度大致相等)? 若文件初态是反序的则直接插入直接选择和冒泡排序哪一个更好? 若文件初态是反序的且要求输入稳定则在直接插入直接选择冒泡和快速排序中就选选哪种方法为宜? 有序数组是堆吗? 高度为h的堆中最多有多少个元素?最少有多少个元素?在大根堆中关键字最小的元素可能存放在堆的哪些地方? 判别下列序列是否为堆(小根堆或大根堆)若不是则将其调整为堆 () (); () (); () (); () () 将两个长度为n的有序表归并为一个长度为n的有序表最小需要比较n次最多需要比较n次请说明这两种情况发生时两个被归并的表有何特征? 设关键字序列为()给出桶排序的结果 若关键字是非负整数快速排序归并堆和基数排序啊一个最快?若要求辅助空间为O()则应选择谁? 若要求排序是稳定的且关键字是实数则应选择谁? 对于节的表解释下述问题 ()当待排序的关键字序列的初始态分别为正序和反序时为什么直接选择排序的时间基本相同?若采用本书节的算法这两种情况下的排序时间是否基本相同? ()为什么数组的初态为正序时冒泡和直接插入排序的执行时间最少? ()若采用节的快速排序则数组初态为正序和反序时能得到与表类似的结果吗? |
