首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数
阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数
admin
2013-01-05
70
问题
阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
下面的流程图1—5用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A
,并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:
【算法说明】
将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数血p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],iht L;int H)的功能是实现数组A中元素的递增排序。
【算法】
void sort(int A[],int1,int H) {
if (L<H) {
k=p(A, L, R): //p()返回基准数在数组A中的下标
sort((4)); //小于基准数的元素排序
sort((5)); //大于基准数的元素排序
}
}
选项
答案
(1)j-- (2) i++ (3)A[i]←pivot或[j]←pivot (4)A,L,k-1或A,L,k (5)A,k+I,H或A,k,H
解析
题目考查快速排序算法。快速排序采用了一种分治的策略,通常称为分治法,其基本思想足:将原问题分解为若干个规模更小,但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程为:第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为基准,将所有记录分成2组,第一组各记录的排序码都小于等于该排序码,第二组各记录的排序码都大十该排序码,并把该记录排在这2组中间,这个过程称为一次划分。第二步,采用同样的方法,对划分出来的2组元素分别进行快速排序,直到所有记录都排到相应的位置为止。
在进行一次划分时,若选定以第一个元素为基准,就可将第一个元素备份在变量pivot
中,如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了,因此下一步就从后向前扫描。如图中的第②步所示,找到一个比基准元素小的元素时为止,将其前移,如图中的第③步所示。然后再从前向后扫描,如图中的第④步所示,找到一个比基准元素大的元素时为止,将其后移,如图中的第⑤步所示。这样,从后向前扫描和从前向后扫描交替进行,直到扫描到同一个位置为止,如图中的第⑥步所示。
由题目中给出的流程图可知,以第一个元素作为基准数,并将A[low]备份至pivot,i用于从前向后扫描的位置指示器,其初值为low,j用于从后往前扫描的位置指示器,其初值为high。当i<j时进行循环:
1.从后向前扫描数组A,在i<j的情况下,如果被扫描的元素A刚>pivot,就继续向前扫描(j--);如果被扫描的元素A[j]<pivot就停止扫描,并将此元素的值赋给目前空闲着的A
。
2.这时,再从前向后扫描,在i<j的情况下,如果被扫描的元素A刚<pivot,就继续向后扫描(i++);如果被扫描的元素A[j]>pivot就停止扫描,并将此元素的值赋给目前空闲着的A[j]。
3.这时又接第(1)步,直到i>j时退出循环。退出循环时,将pivot赋给当前的A
(A
←pivot)。
递归函数的目的是执行一系列调用,直到到达某一点时递归终止。为了保证递归函数正常执行,应该遵守下面的规则:
1.每当一个递归函数被调用时,程序首先应该检查基本的条件是否满足,例如,某个参数的值等于0,如果是这种情形,函数应停止递归。
2.每次当函数被递归调用时,传递给函数一个或多个参数,应该以某种方式变得“更简单”,即这些参数应该逐渐靠近上述基本条件。例如,一个正整数在每次递归调用时会逐渐变小,以至最终其值到达0。
本题中,递归函数sort(iht 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+l,…, H],最后对这2组中的元素再使用同样的方法进行快速排序。
转载请注明原文地址:https://kaotiyun.com/show/QYDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA等。其中,采用______方式时,不需要CPU控制数据的传输过程。
系统响应时间和作业吞吐量是衡量计算机系统性能的重要指标。对于一个持续处理业务的系统而言,其(4)。
以下说法中,错误的是________________。
(35)测试用例设计方法既可以用于黑盒测试,也可以用于白盒测试。
在进程状态转换过程中,可能会引起进程阻塞的原因是______。
缺陷探测率DDP是衡量一个公司测试工作效率的软件质量成本的指标。在某公司开发一个软件产品的过程中,开发人员自行发现并修正的缺陷数量为80个,测试人员A发现的缺陷数量为50个,测试人员B发现的缺陷数为50个,测试人员A和测试人员B发现的缺陷不重复,客户反馈缺
用户可以通过http://www.a.com和http://www.b.com访问在同一台服务器上(70)不同的两个Web站点。
某文件管理系统在磁盘上建立了位示图(bitmap),记录磁盘的使用情况。若系统中字长为32位,磁盘上的物理块依次编号为:0、1、2、…,那么8192号物理块的使用情况在位示图中的第(12)个字中有所描述。
针对程序段:IP(A||B||C)THENW=W/X,对于(A,B,C)的取值,(57)测试用例能够满足MCDC(修正条件逻辑判定)的要求。
以下关于边界值分析法的叙述中,不正确的是
随机试题
知识产权
如果货物在空运单上约定的到达时间届满后()天内仍没到达,收货人便可以向承运人主张权利。
纳税人将自产、委托加工或者外购的货物用于集体福利或个人消费的,均视同销售,征收增值税。()
企业发生的财务费用,在编制现金流量表时,均应作为筹资活动项目反映。()
实施“中小学教师继续教育工程”应放在突出地位的有()。
叶圣陶、郑振铎等都是江浙人,有着江浙知识分子特有的理性和宽容。他们像朱自清一样,都是新文学的热心鼓吹者,写得一手漂亮的白话散文。他们接受过五四新文化的洗礼,______,无论对中西之学,都采取平和的一视同仁态度。填入横线上最恰当的是()。
债务人甲怠于行使其对乙的到期债权,对债权人丙造成损害的,债权人丙可以向人民法院请求以自己的名义代为行使债务人的债权。但债权人丙提起代位权诉讼,应当符合的条件不包括()。
中国共产党在马克思主义指导下,立足中国国情,走出以农村包围城市、武装夺取政权的新民主主义道路。这给我们的哲学启示是()。
下列关于隋唐时期货币表述准确的是()。①隋朝使用五铢钱②开元年间开始统一使用开元通宝③开元通宝是唐朝的通用货币④开元通宝是唐代以后历代王朝货币的范式
共同要素说强调以下哪种因素在学习中的作用?
最新回复
(
0
)