13年电大数据结构1到9章过程性测试习题答案

习题解答

Bub_Sort1(Ar, n) {

for (i=1; i

/* 这趟发生交换标志 */

for (j=1; j<=n-i; j++) if (Ar[j].key

temp = Ar[j+1]; Ar[j] = Ar[j+1]; Ar[j+1] = temp; flag = 1;

}

if (flag == 0) break; } }

/* 若没有发生交换,就结束算法 */ /* 这趟扫描的范围是从1到n-i */ /* 通过temp进行交换 */

/* 对无序记录序列进行n-1趟扫描 */

2.有待排关键字序列:68、70、67、73、23、67、28、92、18,以图示的方式对它进行快速排序,并说明快速排序是一种不稳定的排序算法。 答:图(a)是快速排序一次划分前的初始状态,图(b)是一次划分完成时的结果,这时关键字68已经到达它的最终位置,其他关键字被分为左、右两个子序列。

下面专门来看左边的待排子序列,它由A[1]=18、A[2]=28、A[3]=67、A[4]=67、A[5]=23组成,对其进行快速排序一次划分前的初始状态如图(c)所示,一次划分完成时的结果,关

- 41 -

习题解答

键字18已经到达它的最终位置,其他关键字只有右子序列,如图(d)所示。图(e)~图(h)表示对右字序列一次划分的过程。从最终结果可以看出,原来在左边的67现在被安排到了右边,如图(h)所示。这表明快速排序不具有稳定性。 3.把直接选择排序算法修改成各关键字最终由大到小排列。 答:修改的算法如下所示。

Sel_sort(Ar, n) {

for (i=1; i<=n-1; i++) {

large = i;

/* 用变量large记住当前最大关键字的位置 */

for (j = i+1; j<=n; j++) large = j; if (large != i) {

temp = Ar[i]; Ar[i] = Ar[large]; Ar[large] = temp;

} } }

/* 交换是利用临时变量temp进行的 */

/* large与比较范围首元素下标不同,则交换 */ /* j控制这趟扫描的比较范围 */

/* 如果发现更大者,随时修改large的值 */

/* i控制n-1趟扫描 */

if (Ar[j].key>Ar[large].key)

4.已知待排的关键字序列:70、83、99、65、10、32、7、9,请给出采用直接插入排序方法时每趟的图示过程。 答:采用直接插入排序方法时每趟的图示过程如下。

5.有待排序的关键字序列:18、02、22、15、56、18、88、27、68,请给出采用冒泡排序方法时每趟的图示过程(注意:这里有两个关键字都是18)。 答:采用冒泡排序方法时每趟的图示过程如下。

- 42 -

习题解答

过程性测试1到9

- 43 -

联系客服:779662525#qq.com(#替换为@)