早教吧 育儿知识 作业答案 考试题库 百科 知识分享
早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->

●试题二 阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 下面

题目

●试题二

阅读下列说明、流程图和算法,将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

下面的流程图(如图3所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A[i],并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:

【流程图】

图3流程图

【算法说明】

将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int A[],int low,int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[],int L,int H)的功能是实现数组A中元素的递增排序。

【算法】

void sort (int A[], int 1,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。当ipivot,就继续向前扫描(j--);如果被扫描的元素A[i]pivot就停止扫描,并将此元素的值赋给目前空闲着的A[j]。3)这时又接第(1)步,直到i>j时退出循环。退出循环时,将pivot赋给当前的A[i](A[i]←pivot)。递归函数的目的是执行一系列调用,直到到达某一点时递归终止。为了保证递归函数正常执行,应该遵守下面的规则:1)每当一个递归函数被调用时,程序首先应该检查基本的条件是否满足,例如,某个参数的值等于0,如果是这种情形,函数应停止递归。2)每次当函数被递归调用时,传递给函数一个或多个参数,应该以某种方式变得"更简单",即这些参数应该逐渐靠近上述基本条件。例如,一个正整数在每次递归调用时会逐渐变小,以至最终其值到达0。本题中,递归函数sort(intA[],intL,intH)有3个参数,分别表示数组A及其下界和上界。根据流程图可知,这里的L相当于流程图中的i,这里的H相当于流程图中的j。因为P()返回基准数所在数组A中的下标,也就是流程图中最后的"A[i]←pivot"中的i。根据快速排序算法,在第一趟排序后找出了基准数所在数组A中的下标,然后以该基准数为界(基准数在数组中的下标为k),把数组A分成2组,分别是A[L,…,k-1]和A[k+l,…,H],最后对这2组中的元素再使用同样的方法进行快速排序。
看了●试题二 阅读下列说明、流程图...的网友还看了以下:

考正规试,我做题忘了填在横栏中了,选择题只写在括号里了,都是在同张试卷上,人工改卷, 数学 2020-03-31 …

算术题,妈妈不在家,谁来帮我答有一个长方形的栅栏,由一块块的栏板组成,已知每块栏板为3米长,栅栏的一 数学 2020-03-31 …

石油在地下的贮存量与岩质有关联吗还是与地形地貌有关联,有游漓岩隙的石油一说吗,刚才填写问题的时候没 其他 2020-04-06 …

在“马的世界”综合性学习中,老师布置每人出一期以“马”为主题的手抄报。(1)请你仿照栏目一、栏目二 语文 2020-05-14 …

在“马的世界”综合性学习中,老师布置每人出一期以“马”为主题的手抄报。(1)请你仿照栏目一、栏目二 语文 2020-05-14 …

5.学习《马说》一文后,老师布置出一期以“马”为主题的手抄报,请你完成下面的任务。(1)请你仿照栏 语文 2020-05-14 …

如果你主办校刊:经校刊编辑部研究决定,校刊第三期主题是“加强青少年思道德建设.”假如让你出这一期校 语文 2020-06-16 …

PowerPoint中,显示出当前被处理的演示文稿文件名的栏是。a、工具栏b、菜单栏c、标题栏d、 其他 2020-06-18 …

word具有分栏的功能,下列关于分栏的说法中正确的A最多可以设4栏B各栏的栏宽必须相等C各栏wor 其他 2020-06-18 …

配对阅读。左栏是对5个学生做演讲时存在问题的描述,请在右栏为每个学生选择一个合适的建议,并将答题卡 其他 2020-06-18 …