阅读下列函数说明和C代码,回答下面问题。[说明]冒泡排序算法的基本思想是:对于无序序列(假设扫描方向为从前向后,进行升序排列),两两比较相邻数据,若反序则交换,直到没有反序为止。一般情况下,整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作,冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时,只需1趟扫描,而数据初态为反序时,需进行n-1趟扫描。在冒泡排序中,一趟扫描有可能无数据交换,也有可能有一次或多次数据交换,在传统的冒泡排序算法及近年的一些改进的算法中[2,3],只记录一趟扫描有

题目

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


相似考题

4.试题四(共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;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 道解答。如果解答的试题数超过 道,则题号小的 道解答有效。

更多“阅读下列函数说明和C代码,回答下面问题。[说明] 冒泡排序算法的基本思想是:对于无序序列(假设扫描 ”相关问题
  • 第1题:

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




    答案:
    解析:
    (1) ptr->next(2) head->next(3) ptr!=endptr,或其等价形式⑷ptr(5) preptr

  • 第2题:

    排序时扫描待排序记录序列,依次比较相邻的两个元素的大小,逆序时就交换位置,这是()排序方法的基本思想。

    A.直接选择排序

    B.堆排序

    C.快速排序

    D.冒泡排序


    错误

  • 第3题:

    排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置。这是()排序方法的基本思想。

    A.堆排序

    B.直接插入排序

    C.快速排序

    D.冒泡排序


    C

  • 第4题:

    阅读下列说明和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值应取6
    i:循环变量
    n:待排序元素个数
    a:输入数组,长度为n
    b:输出数组,长度为n
    c:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。
    (2)函数sort
    1??? void sort(int n,int a[],int b[]){
    2??? ???int c[R],i;
    3?? for (i=0;i< ???(1)? :i++){
    4?? ??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字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。


    答案:
    解析:
    试题答案 【问题1】
    (1)R
    (2)c[a[i]]+1
    (3)c[i]+c[i -1]
    (4)a[i]
    【问题2】
    (5)O(n+R)或者O(n)或n或线性
    (6)O(n+R)或者O(n)或n或线性
    【问题3】
    不稳定。修改第12行的for循环为:for(i=n-1;i>=0;i--){ 即可。

  • 第5题:

    2、关于排序算法说法不正确的是()。

    A.冒泡排序和选择排序都属于交换类的排序算法。

    B.冒泡排序是一种稳定的排序算法。

    C.对于同一个待排序列进行排序,使用选择排序比冒泡排序具有更少的元素交换次数。

    D.冒泡排序是一种通过多次选择最值并把它交换至数列一端,最终使数列达到有序的排序算法。


    冒泡排序是一种通过多次选择最值并把它交换至数列一端,最终使数列达到有序的排序算法。