中级软件设计师问答集考试卷模拟考试_题_0

1、姓名：_ 班级：_ 学号：_-密-封 -线- 中级软件设计师问答集考试卷模拟考试_题考试时间：120分钟 考试总分：100分题号一二三四五总分分数遵守考场纪律，维护知识尊严，杜绝违纪行为，确保考试结果公正。1、说明冒泡排序算法的基本思想是：对于无序序列(假设扫描方向为从前向后，进行升序排列)，两两比较相邻数据，若反序则交换，直到没有反序为止。一般情况下，整个冒泡排序需要进行众(1kn)趟冒泡操作，冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时，只需1趟扫描，而数据初态为反序时，需进行n-1趟扫描。在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，

2、在传统的冒泡排序算法及近年的一些改进的算法中2，3，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序的基本思想是：对于n个待排序数据组成的序列，在一趟从前向后扫描待排数据序列时，两两比较相邻数据，若反序则对后一个数据作一趟前向的局部冒泡排序，即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第对数据对，若反序，对第2个数据向前冒泡，使前两个数据成为，有序序列；扫描第二对数据对，若反序，对第3个数据向前冒泡，使得前3个数据变成有序序列；扫描第i对数据

3、对时，其前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 sortdatan; /待排序的数据组node类型为待排序的记录(或称结点

4、)。数组sortdata为待排序记录的全体称为一个文件。key是作为排序依据的字段，称为排序码。datatype是与具体问题有关的数据类型。下面是用c语言实现的排序函数，参数r为待排序数组，n是待排序数组的维数，finish为完成标志。算法代码void part-bubblesort (node r, int n)int=0 ; /定义向前局部冒泡排序的循环变量/暂时结点，存放交换数据node tempnode；for (int i=0；in-1；i+) ;if (ri.keyri+1.key)(1)while (2)tempnode=rj ;(3)rj-1=tempnode ;finish=

5、false ;(4)/ end while/ end if/ end for/ end function1.问题1阅读下列函数说明和c代码，将应填入(n)处的字句写在的对应栏内。 （ ）2、说明冒泡排序算法的基本思想是：对于无序序列(假设扫描方向为从前向后，进行升序排列)，两两比较相邻数据，若反序则交换，直到没有反序为止。一般情况下，整个冒泡排序需要进行众(1kn)趟冒泡操作，冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时，只需1趟扫描，而数据初态为反序时，需进行n-1趟扫描。在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法

6、及近年的一些改进的算法中2，3，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序的基本思想是：对于n个待排序数据组成的序列，在一趟从前向后扫描待排数据序列时，两两比较相邻数据，若反序则对后一个数据作一趟前向的局部冒泡排序，即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第对数据对，若反序，对第2个数据向前冒泡，使前两个数据成为，有序序列；扫描第二对数据对，若反序，对第3个数据向前冒泡，使得前3个数据变成有序序列；扫描第i对数据对时，其前i个数据已

7、成有序序列，若第i对数据对反序，则对第i+1个数据向前冒泡，使前i+1个数据成有序序列；依次类推，直至处理完第n-1对数据对。当扫描完第n-1对数据对后，n个待排序数据已成了有序序列，此时排序算法结束。该算法只对待排序列作局部的冒泡处理，局部冒泡算法的名称由此得来。以下为c语言设计的实现局部冒泡排序策略的算法，根据说明及算法代码回答问题1和问题2。变量说明#define n=100 /排序的数据量typedef struct /排序结点int key；info datatype；.node;node sortdatan; /待排序的数据组node类型为待排序的记录(或称结点)。数组sortdata为待排序记录的全体称为一个文件。key是作为排序依据的字段，称为排序码。datatype是与具体问题有关的数据类型。下面是用c语言实现的排序函数，参数r为待排序数组，n是待排序数组的维数，finish为完成标志。算法代码void part-bubblesort (node r, int n)int=0 ; /定义向前局部冒泡排序的循环变量/暂时结点，存放交换数据node tempnode；for (int i=0；in-1；i+) ;if (ri.keyri+1.key)(1)while (2)tempnode=rj ;(3)rj-1=