更多"下面是快速排序的递归算法。试在算法后的空白中填上正确的内容,将该算法补"的相关试题:
[单项选择]将一个递归算法改为对应的非递归算法时,通常需要使用 (44) 。
A. 优先队列
B. 队列
C. 循环队列
D. 栈
[单项选择]将一个递归算法改为对应的非递归算法时,通常需要使用______。
A. 栈
B. 队列
C. 循环队列
D. 优先队列
[简答题]【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
{ int i=s,j=t+1,temp;
int x=A[s];
do{
do i ++ ;while (1) ;
do j -- ;while(A[j]>x);
if(i<j){temp=A[i]; (2) ; (3) ;}
}while(i<j);
A[a] =A[j];A[j] =x;
if(s<i-1) (4) ;
if(j+1<t) (5) ;
}
[简答题]【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
int i=s,j=t+1,temp;
int x=A[s];
do
do i ++ ;while (1) ;
do j -- ;while(A[j]>x);
if(i<j)temp=A[i]; (2) ; (3) ;
while(i<j);
A[a] =A[j];A[j] =x;
if(s<i-1) (4) ;
if(j+1<t) (5) ;
[单项选择]
计算N!的递归算法如下,求解该算法的时间复杂度时,只考虑相乘操作,则算法的计算时间T(n)的递推关系式为 (55) ;对应时间复杂度为 (56) 。
int Factorial (int n)
{//计算n!
if(n<=1)return 1;
else return n * Factorial(n-1);
}
(55)处填()。
A. T(=T(n-1)+1
B. T(=T(n-1)
C. T(=2T(n-1)+1
D. T(=2T(n-1)-1
[单项选择]在计算机内实现递归算法时所需的辅助数据结构是 ( )
A. 栈
B. 队列
C. 树
D. 图
[填空题]程序运行后,利用冒泡法对数组a中的数据按从小到大排序。请在空白处填上适当的内容,将程序补充完整。
Private Sub Form_load( )
Dim a(1 To 5)As Integer
a(1)=20:a(2)=25:a(3)=10:a(4)=40:a(5)=15
n=5
______
For z=1 To n-m
If a(z)>a(z+1)Then
t=a(z):a(z)=a(z+1):a(z+1)=t
End If
Next z
Next m
End Sub
[单项选择]
用递归算法求解F(5)时需要执行 (63) 次“+”运算,该方法采用的算法策略是 (64) 。
(63)处填()。
A. 5
B. 6
C. 7
D. 8
[单项选择]用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为()。
A. n
B. n/2
C. 10g2n
D. 10g2(n+1)
[多项选择]【说明】下面是一个用C编写的快速排序算法。为了避免最坏情况,取基准记录pivot时,采用从left、right和mid=[(left+right)/2]中取中间值,并交换到right位置的办法。数组a存放待排序的一组记录,数据类型为T,left和right是待排序子区间的最左端点和最右端点。
void quicksort (int a[], int left, int right)
int temp;
if (left<right)
hat pivot = median3 (a, left, right); //三者取中子程序
int i = left, j = right-1;
for(;;)
while (i <j && a[i] < pivot) i++;
while (i <j && pivot < a[j]) j--;
if(i<j)
temp = a[i]; a[j] = a[i]; a[i] = temp;
i++; j--;
else break;
if (a[i] > pivot)
temp = a[i]; a[i] = a[right]; a[right] = temp;
quicksort( (1) ); //递归排序左子区间
quieksort(a,i+1 ,right); //递归排序右子区间
void median3 (int a[], int left, int right)
int mid= (2) ;
int k = left;
if(a[mid] < a[k])k = mid;
if(a[high] < a[k]) k = high; //选最小记录
int temp = a[k]; a[k] = a[left]; a[left] = temp; //最小者交换到 left
if(a[mid] <
[单项选择]设有一个递归算法如下
im fact(int n)
if(n<=0)return 1;
else return n * fact(n-1);下面正确的叙述是()。
A. 计算fact(n)需要执行n次函数调用
B. 计算fact(n)需要执行n+1次函数调用
C. 计算fact(n)需要执行n+2次函数调用
D. 计算fact(n)需要执行n-1次函数调用