免费智能真题库 > 历年试卷 > 软件设计师 > 2022年上半年 软件设计师 上午试卷 综合知识
  第29题      
  知识点:   排序   排序   排序算法   稳定性
  章/节:   计算机软件知识       

 
排序算法的稳定性是指将待排序排序后,能确保排序码中的相对位置保持不变。()是稳定的排序算法。
 
 
  A.  冒泡排序
 
  B.  快速排序
 
  C.  堆排序
 
  D.  简单选择排序
 
 
 

 
  第60题    2015年下半年  
   24%
在55个互异元素构成的有序表A[1..55]中进行折半查找(或二分查找,向下取整)。若需要找的元素等于A[19],则在查找过程中参与比较..
  第61题    2021年下半年  
   71%
归并排序算法在排序过程中,将待排序数组分为两个大小相同的子数组,分别对两个子数组采用归并排序算法进行排序,排好序的两个子数..
  第59题    2009年上半年  
   45%
下面关于二叉排序树的叙述,错误的是(59)。
   知识点讲解    
   · 排序    · 排序    · 排序算法    · 稳定性
 
       排序
               排序的基本概念及运算
               排序:假设含n个记录的文件内容为{R1,R2,…,Rn},其相应的关键字分别为{K1,K2,…,Kn}。经过排序确定一种排列:Ri1,Ri2,…,Rin,使得它们的关键字满足关系Ki1Ki2≤…≤Kin(或Ki1Ki2≥…≥Kin),这样的运算称为排序。
               内部排序:指待排序记录全部存放在内存中排序的过程。
               外部排序:指待排序记录的数量很大,以至内存不能容纳全部记录,在排序过程中尚需对外存进行访问的过程。
               简单排序
               下面介绍几种简单排序方法。
               (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的整数d1作为第一个增量,把文件的全部记录分成d1个组,将所有距离为d1倍数的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量d2<d1,重复上述分组和排序工作,以此类推,直至所取的增量di=1(di<di-1<…<d21),即所有记录放在同一组进行直接插入排序为止。
               快速排序
               快速排序的基本思想是:通过一趟排序将待排的记录分割为独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续进行排序,以达到整个序列有序。
               具体做法是:附设两个指针low和high,它们的初值分别指向文件的第一个记录和最后一个记录。设枢轴记录的关键字为Pivotkey,则首先从high所指位置起向前搜索,找到第一个关键字小于Pivotkey的记录并与枢轴记录互相交换,然后从low所指位置起向后搜索,找到第一个关键字大于Pivotkey的记录并与枢轴记录相互交换,重复这两步直至low=high为止。
               在所有同数量级(O(nlog2n))的排序方法中,快速排序被认为是平均性能最好的一种,但是,若初始记录序列按关键字有序或基本有序时,快速排序将退化为冒泡排序,此时算法的时间复杂度为O(n2)。
               堆排序
               对于n个元素的关键字序列K1,K2,…,Kn,当且仅当所有关键字都满足下列性质时称其为堆,即
               
               若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
               堆排序的基本思想是:对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字(对于小根堆而言),然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列为止。
               对于记录数较少的文件来说,堆排序的优越性并不明显,但对大量的记录来说堆排序是很有效的。堆排序的整个算法时间是由建立堆和不断调整堆这两部分时间代价构成的,堆排序算法的时间复杂度为O(nlog2n)。此外,堆排序只需要一个记录大小的辅助空间。但是堆排序是一种不稳定的排序方法。
               归并排序
               归并是将两个或两个以上的有序文件合并成为一个新的有序文件。
               归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件,然后进行两两归并,如此重复,直至最后形成一个包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
               基数排序
               基数排序的思想是:设立r个队列,队列的编号分别为0,1,2,…,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中关键字再依次收集起来;接着按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高有效位,这样得到了一个从小到大有序的关键字序列。为了减少记录移动的次数,队列可以采用链式存储分配,称为链队列。每个链队列设有两个指针,分别指向队头和队尾。
               对于n个记录,执行一次分配和收集的时间为O(n+r),如果关键字有d位,则要执行d遍,所以总的运算时间为O(d(n+r))。基数排序适用于链式分配的记录的排序,是一种稳定的排序方法。
               内部排序方法的比较和选择
                      内部排序方法的比较
                      内部排序方法的比较参见下表。
                      
                      内部排序方法的比较
                      
                      内部排序方法的选择
                      选择排序方法时需要考虑的因素有:①待排序的记录个数n;②记录本身的大小;③关键字的分布情况;④对排序稳定性的要求;⑤语言工具的条件、辅助空间的大小。依据这些因素,可以得到以下几点结论。
                      .若待排序的记录数目n较小时,可采用插入排序和选择排序。
                      .若待排序记录按关键字基本有序,则宜采用直接插入排序或冒泡排序。
                      .当n很大且关键字的位数较少时,采用链式基数排序较好。
                      .若n较大,则应采用时间复杂度为O(nlog2n)的排序方法,如快速排序、堆排序或归并排序。
               外部排序
               常用的外部排序法是归并排序。这种方法一般分为两个阶段:在第一阶段,把文件中的记录分段读入内存,利用某种内部排序方法对这段记录进行排序并输出到外存的另一个文件中,在新文件中形成许多有序的记录段,称为归并段;在第二阶段,对第一阶段形成的归并段用某种归并方法进行一趟趟的归并,使文件的有序段逐渐加长,直到将整个文件归并为一个有序段时为止。
 
       排序
        假设含n个记录的文件内容为{R1R2,…,Rn},其相应的关键字为{k1k2,…,kn}。经过排序确定一种排列{Rj1Rj2,…,Rjn},使得它们的关键字满足如下递增(或递减)关系:kj1≤kj2≤…≤kjn(或kj1kj2≥…≥kjn)。
 
       排序算法
               简单排序
               简单排序包括直接插入排序、冒泡排序、简单选择排序等方法。
               1)直接插入排序
               直接插入排序的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。
               2)冒泡排序
               首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序(即 r[1].key>r[2].key),则交换两个记录,接着比较第二个记录和第三个记录的关键字。依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止。这个过程称为第一趟冒泡排序,使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,结果是使关键字次大的记录被安置到第n-1个记录的位置上。当进行完第n-1趟冒泡排序时,所有记录都已有序排列。
               3)简单选择排序
               简单选择排序的基本思想是:在进行每趟排序时,从无序的记录中选择出关键字最小(或最大)的记录,将其插入到有序序列(初始时为空)的尾部。
               希尔排序
               希尔排序又称"缩小增量排序",是对直接插入排序方法的改进。希尔排序的基本思想是:先将整个待排记录序列分割成若干序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
               快速排序
               快速排序是对冒泡排序的一种改进。先通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,使得整个序列有序。
               堆排序
               1)堆的概念
               对于n个元素的关键字序列{k1,k2,…,kn},当且仅当所有关键字都满足下列关系时称其为堆:
               
               从序列元素间的关系来看,堆是一棵完全二叉树的层次序列。显然,堆顶元素为序列中n个元素的最小值(或最大值)。若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
               2)堆排序的基本思想(小根堆)
               对一组待排序记录的关键字,首先把它们按堆的定义排成一个堆序列,从而输出堆顶的最小关键字,然后将剩余的关键字再调整成新堆,便得到次小的关键字,如此反复进行,直到全部关键字排成有序序列。
               归并排序
               归并排序是不断将多个小而有序的序列合成一个大而有序的序列的过程。其中最常用的归并排序是二路归并排序,它是将整个序列中的元素进行分组,相邻的两个元素为一组,然后分别为每个小组进行排序,随后将两个相邻的小组合成一个组,继续进行组内排序;直到所有元素被合并成一个组内,并使组内元素有序,此时排序结束。
               基数排序
               基数排序的思想是按组成关键字的各个数位的值进行排序,它是分配排序的一种。基数排序把一个关键字Ki看成一个d元组,即
               
               其中称为最高有效位,@称为最低有效位。基数排序可以从最高有效位开始,也可以从最低有效位开始。
               基数排序的基本思想是:设立r个队列(r为基数),队列的编号为0, 1, 2, …,r-1。首先按最低有效位的值,把n个关键字分配到这r个队列中;然后从小到大将各队列中的关键字再依次收集起来;接着再按次低有效位的值把刚收集起来的关键字再分配到r个队列中。重复上述收集过程,直至最高位有效。这样得到了一个从小到大有序的关键字序列。
 
       稳定性
        运维要求系统不间断服务,即提供7×24不间断服务,专人值守,监控网站;意外情况下,及时通知信息中心相关负责人,并做好各项应急准备。定期向信息中心相关负责人汇报网站运营情况。另外,对于响应时间也有要求,所以要监控网站群访问速度,如访问响应时间过长,及时查找原因,并向信息中心相关负责人汇报;监控网站群动态应用,对影响应用性能方面因素及时预警,并提出相应解决方案,及时汇报给信息中心相关负责人。
               IT服务体系整体结构
               只有高效、稳定、个性化的本地化服务模式才能满足用户随时随地的服务需求;也只有迅速的维护响应才能真正保证用户的利益不受损害。因此在自身服务体系的基础上,针对政府门户网站内容管理平台运维项目,特定IT服务体系,由响应体系、维护体系和质量监督体系构成。
               (1)客户需求。在服务协议规定范围内的任何服务请求,包括咨询、问题申报、投诉等。
               (2)响应体系。第一时间受理客户的需求,以最快的速度解决问题,保障客户系统尽快恢复正常。
               (3)维护体系。对客户系统进行主动式服务,发现并解决系统隐患,优化系统性能,并提出合理的改进和升级建议。
               (4)质量监督体系。为保障服务的质量制定相关的服务协议,通过满意度调查等方式评估服务的提供是否正常。
               IT服务体系最终都可以通过本次项目建设的ITIL运维体系落实,响应体系对应ITIL运维体系的“事件管理”,维护体系对应ITIL运维体系的“问题管理”,质量监督体系则通过“运维管理”来实现。
               响应体系
               响应体系包含服务台和突发事件管理,主要任务是受理客户的服务需求,尽快恢复客户系统的正常运行。
               客户有问题可以通过热线电话、Email与服务台联系,服务台负责接听技术服务电话、受理客户问题,进行记录,分类并转给相应的工程师处理。二线工程师负责处理服务台分配的事件或问题,当二线工程师需要技术支持时,可以从公司总部或第三方获得到技术支持和实验室环境支持。
   题号导航      2022年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第29题    在手机中做本题