免费智能真题库 > 历年试卷 > 程序员 > 2017年下半年 程序员 上午试卷 综合知识
  第43题      
  知识点:   简单排序   直接插入排序   排序
  关键词:   插入排序   关键码   排序        章/节:   常用算法       

 
对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码Ki时,其前面的i-1个关键码已排好序,因此令Ki与Ki-1、Ki-2、...,依次比较,最多到K1为止,找到插入位置并移动相关元素后将Ki插入有序子序列的适当位置,完成本趟(即第i-1趟)排序。以下关于直接插入排序的叙述中,正确的是( )。
 
 
  A.  若原关键码序列已经升序排序,则排序过程中关键码间的比较次数最少
 
  B.  若原关键码序列已经降序排序,则排序过程中关键码间的比较次数最少
 
  C.  第1趟完成后即可确定整个序列的最小关键码
 
  D.  第1趟完成后即可确定整个序列的最大关键码
 
 
 

 
  第43题    2019年下半年  
   53%
对n个关键码构成的序列采用简单选择排序法进行排序的过程是:第一趟经过n-1次关键码之间的比较,确定出最小关键码在序列中的位置..
  第42题    2015年下半年  
   61%
若待排序记录按关键字基本有序, 则宜采用的排序方法是 (42)。
  第35题    2017年上半年  
   54%
采用()算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。
   知识点讲解    
   · 简单排序    · 直接插入排序    · 排序
 
       简单排序
        简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
        1)直接插入排序
        直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
        2)冒泡排序
        首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即 r[1].key>r[2].key),则交换两个记录,接着比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序,使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时,所有记录都已有序排列。
        3)简单选择排序
        简单选择排序的基本思想是:在进行每趟排序时,从无序的记录中选择出关键字最小(或最大)的记录,将其插入到有序序列(初始时为空)的尾部。
 
       直接插入排序
        若设R[1...n]为待排序的n个记录,R[1...i-1]已按照主关键字由小到大排序,则直接插入排序的主要思路如下。
        (1)寻找R[i]在R[1…i-1]中的插入位置,确保R[i]插入后保持有序。
        (2)i增1,若i小于等于m,则转到(1)执行,否则结束。
        顺序线性存储结构下的直接插入排序算法如下:
        
        【点评】
        (1)对n个结点的线性表采用直接插入排序,当线性表已是从小到大排序时,内循环每执行一次,只需要进行1次比较,整个排序过程只进行n-1次比较。当线性表已是从大到小排序时,对外循环执行i次,内循环要进行i次比较,整个排序过程需要进行n(n-1)/2次比较。可见,对n个结点的线性表采用直接插入排序,最少比较次数为n-1,最多比较次数为n(n-1)/2。
        (2)直接插入排序是在有序表的基础上进行的,所以排序效率较高且比较稳定。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
   题号导航      2017年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第43题    在手机中做本题