第7章_排序_考点4_简单选择排序_2016年考研核心考点命题思路解密_数据结构.pdfVIP

2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 考点4 简单选择排序 一．选择题部分 1. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法， 称为 （ ）。 A. 归并排序 B. 冒泡排序 C. 插入排序 D. 选择排序 2. 采用简单选择排序，比较次数与移动次数分别为 （ ）。 A. O(n), O(logn) B. O(logn), O(n*n) C. O(n*n), O(n) D. 0(nlogn), O(n) 3. 下列排序算法中，第一趟排序完毕后，其最大或最小元一定在其最终位置上的算法是 （ ）。 A. 快速排序 B. 基数排序 C. 归并排序 D. 直接选择排序 二．综合应用题部分 1. 用单链表表示的数据的简单选择排序，结点的域为数据域data，指针域 next ，链表首指 针为head ，链表无头结点。 struct node { int data; struct node *next; }node; void selectsort(struct node *head) { p=head; while (p_______) { q=p; r=_______ while(______ ) { if (_______ ) q=r; r=_______ ; } tmp=q-data; 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 q-data=p-data; p-data=tmp; p= _______ ; } } 2. 以下简单选择排序算法，请将算法补充完整: void SelectSort(RecordType R[ ] , int length) { n=length; for ( i=1 ; i= n-1 ; i++) { ; for ( j=i+1; j=n ; j++ ) if ( ) k=j; if (k!=i) { x=R[i] ; R[i]=R[k] ; R[k]=x; } } } 参 考 答 案 一．选择题部分 1. D 【解析】排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始 时为空）的一端的方法，称为选择排序。 选择排序的基本思想是：将待排序的结点分为已排序(初始为空)和为未排序两组，依次 将未排序的结点中值最小的结点插入已排序的组中。 而从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 其放入已排序序列的正确位置上的方法，是插入排序，请同学们牢记这二者的区别。 常见的选