02331数据结构
若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是（）的排序方法。
题目
若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是（）的排序方法。
参考答案和解析
相似问题和答案
第1题：
若待排序的记录数目较少且已按关键字基本有序，则宜采用______排序算法。
A．快速排序
B．插入排序
C．选择排序
D．冒泡排序
解析：不同的排序方法各有优缺点，可根据需要运用到不同的场合。在选取排序算法时需要考虑以下因素：待排序的记录个数n、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件及辅助空间的大小。依据这些因素可得以下结论：若待排序的记录数目n较小时，可采用插入排序和选择排序；若待排序记录按关键字基本有序，则宜采用直接插入排序或冒泡排序；当n很大且关键字的位数较少时，采用链式基数排序较好；若n较大，则应采用时间复杂度为O(nlogn)的排序方法——快速排序、堆排序、归并排序。
第2题：
在每一趟排序过程中，都将待排序序列中最大关键字选出来，并将它从待排序序列中剔除，继续对剩余元素进行同样操作的排序方法，这种排序方法称为( )。
A．基数排序
B．堆排序
C．起泡排序
D．选择排序
解析：若将堆看成一个完全二叉树对应的序列，则完全二叉树中所有非终端结点的值均不大于(不小于)其左右孩子结点的值。堆排序每次都选出最大或最小的结点。
第3题：
有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为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
第4题：
B.经过排序后，能使关键字相同的元素保持原顺序中的相对位置改变
C.排序算法的性能与被排序元素个数关系不大
D.排序算法的性能与被排序元素个数关系密切
第5题：
通过一趟排序将待排序的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，直至整个序列有序，该排序方法称为(40)。
A．插入排序
B．快速排序
C．希尔排序
D．归并排序
第6题：
若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。下列排序算法中，有(14)种排序算法是稳定的：归并排序、快速排序、希尔排序、堆排序、基数排序、直接插入排序、冒泡排序、直接选择排序。
A．3
B．4
C．5
D．6
解析：此题考察考生对稳定排序概念的理解。稳定排序算法是指在排序过程中两个排序关键字相同的元素，在排序的过程中位置不发生变化。例如对数列：62，42，12，36，4，12，67进行排序时，第一个12在排序完毕以后要排在第二个12的前面，这就是稳定的排序。有些人可能会发出疑问：既然都是12，为什么一定要保证它的顺序呢?举一个简单的例子：如果组织一次有奖答题活动，选手在电脑上答完题以后，就直接提交数据，最后按答题得分奖励前：100名参赛选手，这样会出现一个问题，即如果同时有10个人并列第100名，而我们只能给一个人发奖，到底给谁发呢?最合理的判断标准是给先提交答案的人发奖。这样稳定排序就可以用上了。以上的这些排序算法中，归并排序、基数排序、直接插入排序和冒泡排序是稳定的，其它的都不稳定。
第7题：
若待排序记录按关键字基本有序，则直采用的排序方法是（ ）。
A. 直接插入排序 B. 堆排序C. 快速排序 D. 简单选择排序
第8题：
A、该排序算法不允许有相同的关键字记录
B、该排序算法允许有相同的关键字记录
C、平均时间为0(nlogn)的排序方法
D、以上都不对
第9题：
第10题：
在Excel 2010中，数据清单包含有“姓名”、“工资”、“奖金”等多个字段，若“工资”作为主要关键字，“奖金”作为次要关键字进行排序，则有（）
- A、“工资”相同与否，不影响按“奖金”排序的结果
- B、按“工资”与“奖金”相加的结果进行排序
- C、分别按“工资”、“奖金”独立排序
- D、先按“工资”进行排序，“工资”相同时再按“奖金”排序
正确答案:D