在下列指定的排序算法中，()使用的附加空间与输人序列的长度及初始排列无关。

A.插入排序

B.冒泡排序

C.选择排序

D.堆排序

二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。

31为例检验算法的正确性。

构造轴点的另一更为快捷的策略，思路如图x12.1所示：

初始时取k-1=mi=lo，L和G均为空;此后随着k不断递增，逐一检查元素V[k]，并根据V[k]相对于候选轴点的大小，相应地扩展区间L(图(d))或区间G(图(c))，同时压缩区间U。最终当k-1=hi时，U不含任何元素，于是只需将候选轴点放至V[mi]，即成为真正的轴点。

a)试依此思路，实现对应的划分算法vector::partition()；

b)基于该算法的快速排序是否稳定？

c)基于该算法的快速排序，能否高效地处理大量元素重复之类的退化情况？

A.第一关键字

B.第二关键字

C.第三关键字

D.主要关键字

设使用Pratt序列：

对长度为n的任一向量S做希尔排序。

试证明：

a)若S已是(2，3)-有序，则只需o(n)时间即可使之完全有序;

b)对任何，若S已是(2h_k，3h_k)-有序，则只需o(n)时间即可使之h_k-有序;

c)针对序列中的前o(log^tn)项，希尔排序算法需要分别迭代一轮;

d)总体的时间复杂度为o(log²n)。

A.确定是否按该字段排序以及按什么方式排序

B.确定该字段是否在查询工作表中显示

C.指定该字段的查询条件

D.提供多个查询准则

试设计一个算法，在带附加头结点的单链表中查找倒数第k个结点（k≥1).若查找成功，算法通过参数表送出该结点的data域的值，并返回true，否则只返回false。