首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、流程图和算法,将应填入______处。 [流程图说明] 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,大于基准数的元素向高下标端移动。
阅读下列说明、流程图和算法,将应填入______处。 [流程图说明] 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,大于基准数的元素向高下标端移动。
admin
2007-03-10
72
问题
阅读下列说明、流程图和算法,将应填入______处。
[流程图说明]
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A
,并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:
[流程图]
[算法说明]
将上述划分的思想进一步用于被划分出的数组的2部分,就可以对整个数组实现递增排序。设函数int p(intA[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。
[算法]
void sort(int A[],int L,int H){
if(L<H){
k=p(A,L,H); /*p()返回基准数所在数组A中的下标 */
sort( (4) ); /*小于基准数的元素排序 */
sort( (5) ); /*大于基准数的元素排序 */
};
}
选项
答案
(1)j-- (2)i++ (3)A[i]←pivot或A[j]←pivot (4)A,L,k-1 (5)A,k+1,H
解析
题目考查快速排序算法。
快速排序采用了一种分治的策略,通常称为分治法。其基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程为:
第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为基准,将所有记录分成2组,第一组各记录的排序码都小于等于该排序码,第二组各记录的排序码都大于该排序码,并把该记录排在这2组中间,这个过程称为一次划分。
第二步,采用同样的方法,对划分出来的2组元素分别进行快速排序,直到所有记录都排到相应的位置为止。
在进行一次划分时,若选定以第一个元素为基准,就可将第一个元素备份在变量 pivot中,如图中的第①步所示。如此以来,基准元素在数组中占据的位置就空闲出来了,因此下一步就从后向前扫描,如图中的第②步所示,找到一个比基准元素小的元素时为止,将其前移,如图中的第③步所示。然后再从前向后扫描,如图中的第④步所示,找到一个比基准元素大的元素时为止,将其后移,如图中的第⑤步所示。这样,从后向前扫描和从前向后扫描交替进行,直到扫描到同一个位置为止,如图中的第⑥步所示。
由题目中给出的流程图可知,以第一个元素作为基准数,并将A[loW]备份至pivot,i用于从前向后扫描的位置指示器,其初值为low,j用于从后往前扫描的位置指示器,其初值为high。当i<j时进行循环:
(1)从后向前扫描数组A,在i<j的情况下,如果被扫描的元素A[j]>pivot,就继续向前扫描(j--),如果被扫描的元素A[j]<pivot就停止扫描,并将此元素的值赋给目前空闲着的A
;
(2)这时,再从前向后扫描,在i<j的情况下,如果被扫描的元素A[j]<pivot,就继续向后扫描(i++);如果被扫描的元素A[j]>pivot就停止扫描,并将此元素的值赋给目前空闲着的A[j];
(3)这时,又接第(1)步,直到i≥j时退出循环。退出循环时,将pivot赋给当前的A
(A
←pivot)。
递归函数的目的是执行一系列调用,直到到达某一点时递归终止。为了保证递归函数正常执行,应该遵守下面的规则:
(1)每当一个递归函数被调用时,程序首先应该检查一些基本的条件是否满足,例如,某个参数的值等于零,如果是这种情形,函数应停止递归。
(2)每次当函数被递归调用时,传递给函数一个或多个参数,应该以某种方式变得“更简单”,即这些参数应该逐渐靠近上述基本条件。例如,一个正整数在每次递归调用时会逐渐变小,以至最终其值到达零。
本题中,递归函数sort(int A[],int L,int H)有3个参数,分别表示数组A及其下界和上界。根据流程图可知,这里的L相当于流程图中的i,这里的H相当于流程图中的j。因为p()返回基准数所在数组A中的下标,也就是流程图中最后的“A
←pivot”中的i。
根据快速排序算法,在第一趟排序后找出了基准数所在数组A中的下标,然后以该基准数为界(基准数在数组中的下标为k),把数组A分成2组,分别是A[L,...,k-1)和 A[k+1,...,H],最后对这2组中的元素再使用同样的方法进行快速排序。
转载请注明原文地址:https://kaotiyun.com/show/czjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在Excel中,函数average(a,b,c)表示求a,b,c的______。
小张承担了某信息处理项目,在完成之日向领导做了汇报,将计划进度与实际进度画出了如下两条曲线:从该图可以看出,与计划进度相比,实际进度(69)。
某企业对多项已完成的数据处理任务进行了评估,按其满意度和重要性度量值为坐标,标在下图中,用小圆表示)。这些坐标点分别落入I、Ⅱ、Ⅲ、Ⅳ四个区中。领导认为,位于________区中的任务是需要优先改进的。
使用IE浏览器上网时,可以把喜欢的网页保存到_______中,以便于再次浏览。
计算机操作系统的功能不包括_______。
设有关系R、S、T如下所示,则________。
描述事物的数据有绝对数据和相对数据之分。大气中氧气的含量属于相对数据,常用______形式表示。
在Excel中,绝对地址在被复制或移动到其他单元格时,其单元格地址______。
________________是按照科学的城市发展理念,利用新一代信息技术,通过人、物、城市功能系统之间的无缝连接与协同联动,实现自感知、自适应、自优化,形成安全、便捷、高效、绿色的城市形态。
下列关于Windows7屏幕保护程序的叙述中,不正确的是__________。
随机试题
股票采用代销方式,代销期满后,向投资者出售的股票数量低于拟公开发行股票的数量的多少比例的,为发行失败?()
真空越高,其绝对压力越大。
人们常说“管理是一门艺术”强调的是()。
女,60岁,因慢性支气管炎继发感染住院月余,2天前突发高热,咳嗽加重,咳黄色脓痰,后为乳状脓血痰,伴气急、发绀,右肩胛下散在湿啰音。白细胞计数20×109/L,有中毒颗粒。胸部X线片示肺下野大片絮状浓淡不均阴影。最可能的诊断是
母乳喂养的足月婴儿,应于下列哪个时期服用维生素D
甲、乙二人为夫妻,甲赴外地打工五年未归。甲之合伙人丙与乙协商由乙请求法院宣告甲死亡,甲被宣告死亡后,乙依继承法取得甲的遗产,包括房屋一栋,存款10万元及在合伙企业中的股份若干,后甲返还,则甲有权:
某城市一公交站台前,一位独自坐轮椅的妇女要上车,车站工作人员考虑到她行动不便,轮椅在车上缺乏安全,司机又没法照顾她,只得婉拒这位妇女乘车。该妇女无奈之下,求助于警察。你认为这种情境说明了何种最重要的问题?()
杰克.伦敦规模最大的一部长篇小说是(),代表了他文学创作的最高成就。
EuphemismDefinition-lexicalmeaning:—speakingwithgoodwordsorin【T1】______【T1】______-apolite,roundabout
DeclineofColoradoRiverisSevere[A]TheColoradoRiver,whichflowedacrossthelandwithsuchgustothatitcarvedthemajes
最新回复
(
0
)