工学
填空题对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为（）。
题目
相似问题和答案
第1题：
A、n-1
B、n
C、n+1
D、n(n-1)/2
第2题：
对有n个记录的表r[1…n]进行直接选择排序，所需要进行的关键字间的比较次数为______。
n(n-1)/2 解析：选择排序的思想为：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。第一个元素需要比较n-1次，第二次元素需要比较n-2次，依次类推，倒数第二个元素只须比较1次即可，所以总的比较次数为：(n-1)+(n-2)+…2+1=n(n-1)/2。
第3题：
A.n-1
B.n
C.n(n-1)/2
D.n(n+1)/2
第4题：
有n个记录的文件,如关键字位数为d,基数为r,则基数排序共要进行()遍分配与收集。
A：n
B：d
C：r
D：n-d
第5题：
Shell排序、快速排序、堆排序的稳定性如何?(23)。
若要尽可能的完成对实数数组的排序，且要求排序是稳定的，则应选(24)。
若用插入排序算法对n个记录进行排序，最佳情况下，对关键字进行的比较次数为(25)。
对于多关键字而言，(26)是一种方便而又高效的文件组织方式。
若用冒泡排序对关键字序列{19，16，11，8，5，3}从小到大进行排序，则需要次数为(27)。
A．Shell排序是稳定的
B．快速排序是稳定的
C．堆排序是稳定的
D．都不稳定
第6题：
A.n-1
B.n+1
C.n/2
D.n(n-1)/2
第7题：
以下关于排序算法的叙述中，正确的是( )。
A．冒泡排序法中，元素的交换次数与元素的比较次数一定相同
B．冒泡排序法中，元素的交换次数不少于元素的比较次数
C．简单选择排序中，关键字相同的两个记录在排序前后的相对位置一定不变
D．简单选择排序中，关键字相同的两个记录在排序前后的相对位置可能交换
解析：冒泡排序法的基本思路是：将相邻位置上的关键字进行比较，如果为逆序，则交换，否则继续往下比较，直到序列已经排好。所以，在这个过程中，元素问的比较次数应大于或等于交换次数。简单选择排序算法的思路是：第1趟在n个记录中选择最小的记录，将它与第1个元素交换，第2趟在n-1个基类中选取最小记录，将它与第2个元素交换，依此类推，直到序列的第n个元素为止。在这个过程中，关键字相同的两个记录在排序前后的相对位置可能发生变化。例如，序列为(80，80，40，30)时，选择排序法需要将第1个元素80和最后一个元素30交换，这样就使得两个80的相对位置改变了。
第8题：
有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
① 给出适用于计数排序的顺序表定义;
② 编写实现计数排序的算法;
③ 对于有n个记录的表，关键字比较次数是多少?
④ 与简单选择排序相比较，这种方法是否更好?为什么?
[算法描述]
① typedef struct
{int key;
datatype info
}RecType
② void CountSort(RecType a[],b[],int n)
//计数排序算法，将a中记录排序放入b中
{for(i=0;i
}
}//Count_Sort
③ 对于有n个记录的表，关键码比较n2次。
④ 简单选择排序算法比本算法好。简单选择排序比较次数是n(n-1)/2,且只用一个交换记录的空间;而这种方法比较次数是n2，且需要另一数组空间。
[算法讨论]因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：
for(i=0;i
第9题：
● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。
（39）
第10题：
对n个元素的序列进行冒泡排序时，最少的比较次数是_________。
n—1
【解析】 当初始元素正序时，第一趟比较n—1次，交换数为0，完成排序。