第1题:
第2题:
●用插入排序和归并排序算法对数组<3,1,4,1,5,9,6,5>进行从小到大排序,则分别需要进行 (65) 次数组元素之间的比较。
(65)
A.12,14
B.10,14
C.12,16
D.10,16
第3题:
●下面算法是实现对n个整数的序列进行选择排序,其中序列的"长度"n为问题的规模。该算法的时间复杂度为 (23) 。
void select_sort(int a[],int n)
{
//将a中整数序列重新排列成从小到大有序的整数序列
for(i=0;i<n-1;++i){
j=i;
for(k=i+1;k<n;++k)
if(a[k]<a[j])j=k;
if(j!=i){w=a[j];a[j]=a[i];a[i]=w;}
}//select- sort
(23) A.O(n3)
B.O(n2)
C.O(n)
D.O(n4)
【解析】算法中的控制结构是两重循环,所以基本操作是在内层循环中的"比较",它的重复执行次数是:
对时间复杂度而言,只需要取最高项,并忽略常数系数。
第4题:
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数己经排好序,将第i个整数依次和第i-1, i-2, ...个整数进行比较,找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序,则需要进行(31)次整数之间的比较。对于该排序算法,输入数据具有(32)特点时,对整数进行从小到大排序,所需的比较次数最多。
A.9
B.10
C.12
D.13
第5题:
若对n个元素进行直接插入排序,则进行第i趟排序过程前,有序表中的元素个数为 ______。
A.1
B.i-1
C.i
D.i+1
第6题:
下面算法是实现对n个整数的序列进行选择排序,其中序列的“长度”n为问题的规模。该算法的时间复杂度为(11)。 void select_sort(int a[],int n){ //将a中整数序列重新排列成从小到大有序的整数序列 for(i=0;i<n-1;++i){ j=i; for(k=i+1;k<n;++k)if(a[k]<a[j])j=k; if(j!=i){w=a[j];a[j];a[i];a[i]=w} )//select_sort
A.O(n2)
B.O(n3)
C.O(n4)
D.O(n)
第7题:
对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码Ki时,其前面的i-1个关键码己排好序,因此令Ki与Ki-1、Ki-2、...,依次比较,多到K1为止,找到插入位置并移动相关元素后将Ki插入有序子序列的适当位置,完成本趟(即第i-1趟)排序。以下关于直接插入排序的叙述中,正确的是()。
A.若原关键码序列已经升序排序,则排序过程中关键码间的比较次数最少
B.若原关键码序列已经降序排序,则排序过程中关键码间的比较次数最少
C.第1趟完成后即可确定整个序列的最小关键码
D.第1趟完成后即可确定整个序列的最大关键码
第8题:
● 对于具有n 个元素的一个数据序列,若只得到其中第 k 个元素之前的部分排序, 最好采用(59) ,使用分治 (Divide and Conquer )策略的是(60) 算法。
(59)A. 希尔排序 B. 直接插入排序 C. 快速排序 D. 堆排序
(60)A. 冒泡排序 B. 插入排序 C. 快速排序 D. 堆排序
第9题:
对n个基本有序的整数进行排序,若采用插入排序算法,则时间和空间复杂度分别为(62);若采用快速排序算法,则时间和空间复杂度分别为(63)。
A.O(n2)和O(n)
B.O(n)和O(n)
C.O(n2)和O(1)
D.O(n)和O(1)
第10题:
已知一个单链表中有3000个结点,每个结点存放一个整数,( )可用于解决这3000个整数的排序问题且不需要对算法作大的变动。
A.直接插入排序方法
B.简单选择排序方法
C.快速排序方法
D.堆排序方法