下面算法是实现对n个整数的序列进行选择排序,其中序列的“长度”n为问题的规模。该算法的时间复杂度
A.O(n2)
B.O(n3)
C.O(n4)
D.O(n)
A.O(n2)
B.O(n3)
C.O(n4)
D.O(n)
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)
阅读下列函数说明和C代码,回答下面问题。
[说明]
冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时,只需1趟扫描,而数据初态为反序时,需进行n-1趟扫描。在冒泡排序中,一趟扫描有可能无数据交换,也有可能有一次或多次数据交换,在传统的冒泡排序算法及近年的一些改进的算法中[2,3],只记录一趟扫描有无数据交换的信息,对数据交换发生的位置信息则不予处理。为了充分利用这一信息,可以在一趟全局扫描中,对每一反序数据对进行局部冒泡排序处理,称之为局部冒泡排序。
局部冒泡排序的基本思想是:对于N个待排序数据组成的序列,在一趟从前向后扫描待排数据序列时,两两比较相邻数据,若反序则对后一个数据作一趟前向的局部冒泡排序,即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第—对数据对,若反序,对第2个数据向前冒泡,使前两个数据成为,有序序列;扫描第二对数据对,若反序,对第3个数据向前冒泡,使得前3个数据变成有序序列;……;扫描第i对数据对时,其前i个数据已成有序序列,若第i对数据对反序,则对第i+1个数据向前冒泡,使前i+1个数据成有序序列;……;依次类推,直至处理完第n-1对数据对。当扫描完第n-1对数据对后,N个待排序数据已成了有序序列,此时排序算法结束。该算法只对待排序列作局部的冒泡处理,局部冒泡算法的
名称由此得来。
以下为C语言设计的实现局部冒泡排序策略的算法,根据说明及算法代码回答问题1和问题2。
[变量说明]
define N=100 //排序的数据量
typedef struct{ //排序结点
int key;
info datatype;
......
}node;
node SortData[N]; //待排序的数据组
node类型为待排序的记录(或称结点)。数组SortData[]为待排序记录的全体称为一个文件。key是作为排序依据的字段,称为排序码。datatype是与具体问题有关的数据类型。下面是用C语言实现的排序函数,参数R[]为待排序数组,n是待排序数组的维数,Finish为完成标志。
[算法代码]
void Part-BubbleSort (node R[], int n)
{
int=0 ; //定义向前局部冒泡排序的循环变量
//暂时结点,存放交换数据
node tempnode;
for (int i=0;i<n-1;i++) ;
if (R[i].key>R[i+1].key)
{
(1)
while ((2) )
{
tempnode=R[j] ;
(3)
R[j-1]=tempnode ;
Finish=false ;
(4)
} // end while
} // end if
} // end for
} // end function
阅读下列函数说明和C代码,将应填入(n)处的字句写在的对应栏内。
从供选择的答案中选出应填入下列叙述中()内的正确答案:
堆是一种有用的数据结构。例如关键码序列(A) 是一个堆。
堆排序是一种(B) 排序,它的一个基本问题是如何建堆,常用的建堆算法是1964年 Floyd提出的(C) 。对含n个元素的序列进行排序时,堆排序的时间复杂性是(D) ,所需的附加存储结点是(E)。
供选择的答案
A:①16,72,31,23,94,53
②94,53,31,72,16,53
③16,53,23,94,31,?2
④16,31,23,94,53,72
⑤94,11,53,23,16,72
B:①插入 ②选择 ③交换 ④基数 ⑤归并
C:①淘汰法 ②筛选法 ③递推法 ④LRU算法
D、E:①O(nlog2n) ②O(n) ③O(log2n)
④O(n2) ⑤O(1)
试题四(共15 分)
阅读下列说明和C代码,回答问题 1 至问题3,将解答写在答题纸的对应栏内。
【说明】
某应用中需要对100000 个整数元素进行排序,每个元素的取值在 0~5 之间。排序算法的基本思想是:对每一个元素 x,确定小于等于 x的元素个数(记为m),将 x放在输出元素序列的第m 个位置。对于元素值重复的情况,依次放入第 m-l、m-2、…个位置。例如,如果元素值小于等于4 的元素个数有 10 个,其中元素值等于 4 的元素个数有3个,则 4 应该在输出元素序列的第10 个位置、第 9 个位置和第8 个位置上。
算法具体的步骤为:
步骤1:统计每个元素值的个数。
步骤2:统计小于等于每个元素值的个数。
步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。
【C代码】
下面是该排序算法的C语言实现。
(1)常量和变量说明
R:常量,定义元素取值范围中的取值个数,如上述应用中 R值应取6i:循环变量
n:待排序元素个数
a:输入数组,长度为n
b:输出数组,长度为n
c:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。
(2)函数sort
1 void sort(int n,int a[ ],intb[ ]){
2 int c[R],i;
3 for (i=0;i< (1) ;i++){
4 c[i]=0;
5 }
6 for(i=0;i<n;i++){
7 c[a[i]] = (2) ;
8 }
9 for(i=1;i<R;i++){
10 c[i]= (3) ;
11 }
12 for(i=0;i<n;i++){
13 b[c[a[i]]-1]= (4) ;
14 c[a[i]]=c[a[i] ]-1;
15 }
16 }
【问题1】(8 分)
根据说明和C代码,填充 C代码中的空缺(1)~(4)。
【问题2】(4 分)
根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用 O符号
表示)。
【问题3】(3 分)
根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过 100 字);
若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
从下列的2 道试题(试题五和试题六)中任选 1 道解答。
如果解答的试题数超过 道,则题号小的 道解答有效。
的最小值称为数据包序列的均衡负载量.
算法设计:对于给定的数据包序列,计算m个处理器的均衡负载量.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.n表示数据包个数,m表示处理器数.接下来的1行中有n个整数,表示n个数据包的大小.
结果输出:将计算的处理器均衡负载量输出到文件output,txt,且保留2位小数.
A.9
B.10
C.12
D.13
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i一1
个整数已经排好序,将第i个整数依次和第i.,i-2,…个整数进行比较,找到应该插入
的位置。现采用插入排序算法对6个整数{5 2,4,6,1,3}进行从小到大排序,则需要进行
(31)次整数之间的比较。对于该排序算法,输入数据具有(32)特点时,对整数进
行从小到大排序,所需的比较次数最多。
A.9
B.10
C.12
D.13
(32)A.从小到大
B.从大到小
C.所有元素相同
D.随机分布
请帮忙给出每个问题的正确答案和分析,谢谢!
算法设计:对于给定的I和k,计算I的最大k乘积.
数据输入:由文件input.txt提供输入数据.文件的第1行中有2个正整数n和k.正整数n是序列的长度,正整数k是分割的段数.接下来的一行中是一个n位十进制整数(n≤10).
结果输出:将计算结果输出到文件output.txt.文件第1行中的数是计算出的最大k乘积.