题目内容
(请给出正确答案)
[主观题]
在实现快速排序的非递归算法时,可根据基准元素.将待排序排序码序列划分为两个子序列。若下一趟
首先对较短的子序列进行排序,试编写相应的算法,并说明在此做法下,快速排序所需要的栈的深度为O(log2n),
查看答案
如果结果不匹配,请 联系老师 获取答案
已知Ackerman函数的定义如下:
(1)写出递归算法;
(2)写出非递归算法;
(3)根据非递归算法, 画出求akm(2,1)时栈的变化过程。
阅读下列对正整数关键字序列L操作的算法,并回答问题:
(1)设L=(28,19,27,49,56,12,10,25,20,50),写出f33(L,4)的返回值;
(2)简述函数f33的功能。
int Partition(SeqList*L,int low,int high);
//对L[low…high]做划分,返回基准记录的位置,并使左部的关键字
//都小于或等于基准记录的关键字,右部的关键字都大于基准记录的关键字
int f33(SeqList L,int k){
int low,high,pivotpos;
low=1;
high=L.length;
if(k<low||k>high)
return-1;
do {
pivotpos=Partition(&L,low,high);//调用快速排序的划分算法
if(pivotpos<k)
low=pivotpos+1;
else if(pivotpos>k)
high=pivotpos-1;
}while(pivotpos!=k);
return L.data[pivotpos];
}
A、锦标赛排序
B、快速排序
C、基数排序
D、归并排序
已知Ackerman函数定义如下:
(1)根据定义,写出它的递归求解算法;
(2)利用栈,写出它的非递归求解算法。
已知Ackermann函数定义如下:
①写出计算Ack(m,n)的递归算法,并根据此算法给出出Ack(2,1)的计算过程。
②写出计算Ack(m,n)的非递归算法。