对n个元素进行直接选择排序，需要进行（）趟选择和交换。

B、n+1

C、n-1

D、n/2

(50)

A．插入排序

B．选择排序

C．交换排序

D．归并排序

【说明】

对20个数进行排序，可以利用选择法，即从后19个比较过程中，选择一个最小的与第一个元素交换，依次类推，即用第二个元素与后18个进行比较，并进行交换。

【函数】

define N 20

main()

{

int i,j,min,tem,a[N];

printf("please input twenty num:\n");

for(i=0;i＜N;i)

{

printf("a[%d]=",i);

scanf("%d",&a[i]);

}

printf("\n");

for(i=0;i＜N;i)

printf(",",a[i]);

printf("\n");

for(i=0;(1);i)

{

min=(2);

for(j=(3);j＜N;j++)

if((4))

min=j;

tem=a[i];

(5);

a[min]=tem;

}

printf("After sorted \n");

for(i=0;i＜N;i++)

printf(",",a[i]);

}

堆是一种有用的数据结构。例如关键码序列(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)

A、第3轮比较后，表中数据的顺序为：5,8,12,46,34,23

B、第1轮排序后，表中数据的顺序为：5,8,34,12,46,23

C、第2轮比较，表中没有数据交换

D、6个数经过5轮比较，就能排好序

[说明]

下面的程序演示了根据随机产生的奖牌数，生成金银奖牌榜的过程。程序使用的排序法是简单排序法。以金牌得数为例，其思想是选择最大的元素，将它交换到最前面；然后对剩下的部分采用同样的方法，直到全部排序完成。

程序界面中，左右两个文本框分别用于存放随机产生的奖牌数以及生成的奖牌榜，名为Text1和Text2，上下两个按钮分别名为Command1和Command2。代码中使用的量主要有：一维数组 cntries，用于存储10个国家的名称，二维数组medals，其元素medals(i,0)和medals(i,1)分别用于存放第i个(i从0开始)国家的金、银牌数目。

[Visual Basic代码]

Dim cntries(10) As String, medals(10,2) As Integer

’随机产生奖牌数

Sub newMedals()

…… ’为数组cntries和medals赋值

End Sub

’输出奖牌榜

Sub printOut(txt As (1) )

Dim strResuh As String, i As Integer

strResult=“国家”& Chr(9) &“金牌数”& Chr(9) &“银牌数”& vbCrLf

For i=0 To 9

strResult = strResult & cntries(i) & Chr(9) & medals(i,0) & Chr(9) & medals(i,1) & vbCrLf

Next

txt.Text = strResult

End Sub

’交换两变量的值

Sub exchange( (2) a As Variant, (2) b As Variant)

Dim temp As Variant

temp = a: a = b: b = temp

End Sub

’随机产生并输出奖牌数

Private Sub Command1_Click()

newMedals

printOut Text1

End Sub

’生成并输出奖牌榜

Private Sub Command2_Click()

Dim i,j, k As Integer, temp As String

For i = 0 To 9 ’按金牌数排序

j = i ’找到自第i个位置起全部数据中金牌得数最多者，记其下标为j

For k = i + 1 To 9

If (3) Then j=k

Next

If i ＜ ＞ j Then ’若i，j不等，则交换对应位置的国家名、金银牌数目

exchange cntnes(i), entries(j)

exchange medals(i, 0), medals(j, 0)

exchange medals(i, 1), medals(j, 1)

End If

Next

For i = 0 To 9 ’按银牌数进行二次排序

j = i

For k = i + 1 To 9

If medals(k,0) ＜＞ medals(j, 0) Then (4)

If (5) Then j = k

Next

If i ＜ ＞ j Then

exchange cntries(i), cntries(j)

exchange medals(i, 1), medals(j, 1)

End If

Next

printOut Text2

End Sub