阅读下列函数说明和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)处的字句写在的对应栏内。

阅读下列函数说明和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、冒泡排序

试题四(共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:输入数组,长度为nb:输出数组,长度为nc:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1 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;in;i++){7 c[a[i]] = (2) ;8 }9 for(i=1;iR;i++){10 c[i]= (3) ;11 }12 for(i=0;in;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 道解答。如果解答的试题数超过 道,则题号小的 道解答有效。

阅读下列说明和C代码,回答问题l至问题3.将解答写在答题纸的对应栏内。【说明】计算一个整数数组a的最长递增子序列长度的方法描述如下:假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤in)为结尾元素的最长递增子序列的长度,则数组a的最长递增子序列的长度为器;其中b[i]满足最优子结构,可递归定义为:【c代码】下面是算法的c语言实现。(1)常量和变量说明a:长度为n的整数数组,待求其最长递增子序列b:长度为n的数组,b[i]记录以a[i](0≤in)为结尾元素的最长递增子序列的长度,其中0≤inlen:最长递增子序列的长度i.j:循环变量temp,临时变量(2)C程序include stdio . hint maxL (int *b. int n) {int i. temp =0;For(i = 0; i n; i++){if (b[i] temp )Temp= b[i];}Return temp;【问题l】(8分)根据说明和C代码,填充C代码中的空(1)~(4)。【问题2】(4分)根据说明和C代码,算法采用了(5)设计策略,时间复杂度为(6)(用O符号表示)。【问题3】(3分)已知数组a={3,10,5,15,6,8},根据说明和C代码,给出数组b的元素值。

阅读下列说明和C代码,回答问题,将解答填入答题纸的对应栏内。【说明】计算一个整数数组a的最长递增子序列长度的方法描述如下:假设数组a的长度为n,用数组b的元素b[i]记录以a[i](0≤i<n)为结尾元素的最长递增子序列的长度为 ;其中b[i]满足最优子结构,可递归定义为:【C代码】下面是算法的C语言实现。(1)常量和变量说明a:长度为n的整数数组,待求其最长递增子序列b:长度为n的数组,b[i]记录以a[i](0≤ilen:最长递增子序列的长度i, j:循环变量temp:临时变量(2)C程序#include int maxL(int*b, int n) {int i, temp=0;for(i=0; itemp) temp=b[i]; } return temp;}int main() { int n,a[100], b[100], i, j, len; scanf("%d", for(i=0;i【问题1】(8分)根据说明和C代码,填充C代码中的空(1)~(4)。【问题2】(4分) 根据说明和C代码,算法采用了 (5) 设计策略,时间复杂度为 (6) (用O符号表示)。【问题3】(5分) 已知数组a={3,10,5,15,6,8},据说明和C代码,给出数组b的元素值。

阅读以下说明和C语言函数,将解答填入答题纸的对应栏内。【说明】函数sort (NODE *head)的功能是:用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻结点中的元素,若较小的元素在前面,则交换这两个结点中的元素值。其中,head指向链表的头结点。排序时,为了避免每趟都扫描到链表的尾结点,设置一个指针endptr,使其指向下趟扫描需要到达的最后一个结点。例如,对于图(a)的链表进行一趟冒泡排序后,得到图(b)所示的链表。

阅读下列说明和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:输入数组,长度为nb:输出数组,长度为nc:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1??? void sort(int n,int a[],int b[]){2??? ???int c[R],i;3?? for (i=0;i4?? ??c[i]=0;5??? ???}6??? ???for(i=0;i7??? ?c[a[i]] = ??(2)? ;8??? ???}9 ??for(i=1;i10??? c[i]= ?(3)11??? ??}12 ?for(i=0;i13??? b[c[a[i]]-1]=? (4)?? ;14??? c[a[i]]=c[a[i]]-1;15??? ??}16??? }【问题1】? 根据说明和C代码,填充C代码中的空缺(1)~(4)。【问题2】根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用O符号表示)。【问题3】?? 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。

排序时扫描待排序记录序列,依次比较相邻的两个元素的大小,逆序时就交换位置,这是()排序方法的基本思想。A.直接选择排序B.堆排序C.快速排序D.冒泡排序

2、关于排序算法说法不正确的是()。A.冒泡排序和选择排序都属于交换类的排序算法。B.冒泡排序是一种稳定的排序算法。C.对于同一个待排序列进行排序,使用选择排序比冒泡排序具有更少的元素交换次数。D.冒泡排序是一种通过多次选择最值并把它交换至数列一端,最终使数列达到有序的排序算法。

排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置。这是()排序方法的基本思想。A.堆排序B.直接插入排序C.快速排序D.冒泡排序