全部科目 > 软件评测师 >
2019年下半年 上午试卷 综合知识
第 25 题
知识点 简单选择排序   排列   排序   选择排序  
章/节 程序设计语言知识  
 
 
对n个关键码构成的序列采用简单选择排序法进行排序的过程是:第一趟经过n-1次关键码之间的比较,确定出最小关键码在序列中的位置后,再将其与序列的第一个关键码进行交换,第二趟则在其余的n-1个关键码中进行n-2次比较,确定出最小关键码的位置后,再将其与序列的第二个关键码进行交换······以此类推,直到序列的关键码从小到大有序排列。在简单选择排序过程中,关键码之间的总比较次数为( ) 。
 
  A.  n (n-1)/2
 
  B.  n2/2
 
  C.  n (n+1)/2
 
  D.  nlogn
 
 




 
 
相关试题     程序设计语言的基本成分(数据、运算、控制和传输、过程/函数调用) 

  第7题    2011年下半年  
标识符在高级语言源程序中的作用不包括(7)。

  第40题    2015年下半年  
堆是一种数据结构,分为大顶堆和小顶堆两种类型,大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则(40)是一个大顶堆结构,该堆结构用二叉树表示,其高度(或层数)为(41)。

  第8题    2014年下半年  
已知函数f()、g()的定义如下所示,执行表达式”x=f(5)”的运算时,若函数调用g(a)是引用调用(call by reference)方式,则执行”x=f(5)”后x的值为 ( 7) ;若函数调用g(a)是值调..

 
知识点讲解
· 简单选择排序
· 排列
· 排序
· 选择排序
 
        简单选择排序
        n个记录进行简单选择排序的基本方法是:通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤in)个记录进行交换,当i等于n时所有记录有序排列。
        【算法】简单选择排序算法。
        
        简单选择排序法在最好情况下(待排序列已按关键码有序)不需要移动元素,因此n个元素排序时的总移动次数为0次。在最坏情况下(元素已经逆序排列),每趟排序移动记录的次数都为3次(两个数组元素交换值),共进行n-1趟排序,总移动次数为3(n-1)。无论在哪种情况下,元素的总比较次数为
        由此,简单选择排序是一种不稳定的排序方法,其时间复杂度为On2)。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换,空间复杂度为O(1)。
 
        排列
        设S为具有n个不同元素的n元集,从S中选取r个元素且考虑其顺序称为S的一个r排列,不同排列的总数记为,有时也用P(nr)表示。如果r=n,则称这个排列为S的全排列。从排列的定义可知,如果两个排列相同,不仅这两个排列的元素必须完全相同,而且排列的顺序也必须完全相同。
        
        例子1:用0~9这十个数字,可以组成多少个没有重复数字的三位数?
        解法1:由于百位数上的数字不能为0,因此可先考虑排百位上的数字,再排十位和个位上的数字。百位数上的数字只能从除0以外的1~9数字中任选一个,有种;十位和个位上的数字,可以从余下的9个数字中任选两个,有种。根据乘法原理,所求的三位数的个数是
        解法2:可先考虑从0~9这十个数字中任取三个数字的排列数(),再减去其中以0开头的排列数()。因此,所求的三位数的个数是
        解法3:符合条件的三位数可以分为三类:每一位数字都不是0的三位数有个;个位数是0的三位数有个;十位数是0的三位数有个。根据加法原理,符合条件的三位数个数是
 
        排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
        选择排序
        若设R[1...n]为待排序的n个记录,R[1...i-1]已按照主关键字由小到大排序,且任意x∈R[1...i-1],y∈R[i...n]满足x.key≤y.key,则选择排序的主要思路如下。
        (1)反复从R[i...n]中选出关键字最小的结点R[k]。
        (2)若i≠k,则将R[i]与R[k]交换,使得R[1...i]有序且保持原来的性质。
        (3)i增1,直到i为n。
        为方便描述,被查找的顺序表C类型定义如下:
        
        顺序存储线性表的选择排序算法如下:
        
        可见,选择排序不管原先序列是否有序,其排序需要比较的次数均为n(n-1)/2;同时,由于相等的两个元素,位置相对在前的可能被交换到后面,故该选择排序是不稳定的。



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2023 All Rights Reserved
软考在线版权所有