免费智能真题库 > 历年试卷 > 软件设计师 > 2014年下半年 软件设计师 上午试卷 综合知识
  第63题      
  知识点:   简单排序   简单选择排序   排序   选择排序   直接插入排序
  关键词:   插入排序   排序        章/节:   计算机软件知识       

 
对一待排序序列分别进行直接插入排序简单选择排序,若待排序序列中有两个元素的值相同,则()保证这两个元素在排序前后的相对位置不变。
 
 
  A.  直接插入排序和简单选择排序都可以
 
  B.  直接插入排序和简单选择排序都不能
 
  C.  只有直接插入排序可以
 
  D.  只有简单选择排序可以
 
 
 

  相关试题:排序          更多>  
 
  第61题    2010年上半年  
   25%
对以下四个序列用直接插入排序方法由小到大进行排序时,元素比较数最少的是 (61).
  第65题    2015年下半年  
   42%
在某应用中,需要先排序一组大规模的记录,其关键字为整数。若这组记录的关键字基本上有序,则适宜采用(64)排序算法。若这组记..
  第65题    2009年下半年  
   63%
以下关于快速排序算法的描述中,错误的是(64)。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,..
   知识点讲解    
   · 简单排序    · 简单选择排序    · 排序    · 选择排序    · 直接插入排序
 
       简单排序
        下面介绍几种简单排序方法。
        (1)直接插入排序。在插入第i个记录时,R1,R2,…,Ri-1已经排好序,这时将关键字ki依次与关键字ki-1,ki-2,…,k1进行比较,从而找到应该插入的位置,然后将ki插入,插入位置及其后的记录依次向后移动。
        (2)冒泡排序。首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则交换两个记录的值,然后比较第二个记录和第三个记录的关键字,以此类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序,其结果是关键字最大的记录被安置到第n个记录的位置上,然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,其结果是关键字次大的记录被安置到第n-1个记录的位置上,当进行完第n-1趟时,所有记录有序排列。
        (3)简单选择排序。通过n-1次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换,当i等于n时所有记录有序排列。
 
       简单选择排序
        n个记录进行简单选择排序的基本方法是:通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1≤in)个记录进行交换,当i等于n时所有记录有序排列。
        【算法】简单选择排序算法。
        
        简单选择排序法在最好情况下(待排序列已按关键码有序)不需要移动元素,因此n个元素排序时的总移动次数为0次。在最坏情况下(元素已经逆序排列),每趟排序移动记录的次数都为3次(两个数组元素交换值),共进行n-1趟排序,总移动次数为3(n-1)。无论在哪种情况下,元素的总比较次数为
        由此,简单选择排序是一种不稳定的排序方法,其时间复杂度为On2)。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换,空间复杂度为O(1)。
 
       排序
        假设含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;同时,由于相等的两个元素,位置相对在前的可能被交换到后面,故该选择排序是不稳定的。
 
       直接插入排序
        直接插入排序是一种简单的排序方法,具体做法是:在插入第i个记录时,R1R2,…,Ri-1己经排好序,这时将记录Ri的关键字ki依次与关键字ki-1ki-2,…,k1进行比较,从而找到Ri应该插入的位置,插入位置及其后的记录依次向后移动。
        【算法】直接插入排序算法。
        
        直接插入排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较且不需要移动元素,因此n个元素排序时的总比较次数为n-1次,总移动次数为0次。在最坏情况下(元素已经逆序排列),进行第i趟排序时,待插入的记录需要同前面的i个记录都进行1次比较,因此,总比较次数为。排序过程中,第i趟排序时移动记录的次数为i+1(包括移进、移出temp),总移动次数为
        由此,直接插入排序是一种稳定的排序方法,其时间复杂度为On2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为O(1)。
   题号导航      2014年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第63题    在手机中做本题