首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、流程图和算法,将应填(n)处的字句写在对应栏内。 [说明] 下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准
阅读下列说明、流程图和算法,将应填(n)处的字句写在对应栏内。 [说明] 下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准
admin
2009-02-15
78
问题
阅读下列说明、流程图和算法,将应填(n)处的字句写在对应栏内。
[说明]
下面的流程图(如图3所示)用N - S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A
,并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为 low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如下:
[流程图]
[算法说明]
将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int A[],int low,int hieh)实现了上述流程图的划分过程并返回基准数在数组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,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+1,H或A,k,H
解析
题目考查快速排序算法。快速排序采用了一种分治的策略,通常称为分治法。其基本思想是:将原问题分解为若干个规模更小,但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程为:第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为基准,将所有记录分成2组,第一组各记录的排序码都小于等于该排序码,第二组各记录的排序码都大于该排序码,并把该记录排在这2组中间,这个过程称为一次划分。第二步,采用同样的方法,对划分出来的2组元素分别进行快速排序,直到所有记录都排到相应的位置为止。
在进行一次划分时,若选定以第一个元素为基准,就可将第一个元素备份在变量pivot中,如图中的第①步所示。这样基准元素在数组中占据的位置就空闲出来了,因此下一步就从后向前扫描。如图中的第②步所示,找到一个比基准元素小的元素时为止,将其前移,如图中的第③步所示。然后再从前向后扫描,如图中的第④步所示,找到一个比基准元素大的元素时为止,将其后移,如图中的第⑤步所示。这样,从后向前扫描和从前向后扫描交替进行,直到扫描到同一个位置为止,如图中的第⑥步所示。
由题目中给出的流程图可知,以第一个元素作为基准数,并将A[low]备份至pivot,i用于从前向后扫描的位置指示器,其初值为low, j用于从后往前扫描的位置指示器,其初值为high。当i 1)从后向前扫描数组A,在ipivot,就继续向前扫描(j--);如果被扫描的元素A
2)这时,再从前向后扫描,在ipivot就停止扫描,并将此元素的值赋给目前空闲着的A[j]。
3)这时又接第(1)步,直到i>j时退出循环。退出循环时,将pivot赋给当前的A
(A
←pivot)。
递归函数的目的是执行一系列调用,直到到达某一点时递归终止。为了保证递归函数正常执行,应该遵守下面的规则:
1)每当一个递归函数被调用时,程序首先应该检查基本的条件是否满足,例如,某个参数的值等于0,如果是这种情形,函数应停止递归。
2)每次当函数被递归调用时,传递给函数一个或多个参数,应该以某种方式变得“更简单”,即这些参数应该逐渐靠近上述基本条件。例如,一个正整数在每次递归调用时会逐渐变小,以至最终其值到达0。
本题中,递归函数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/irDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
给定关系模式R(A,B,C,D)、S(C,D,E),与π1,3,5等价的SQL语句如下:SELECT(22)FROMR,sWHERE(23);下列查询B=“信息”且E=“北京”的A、B、E的关系代数表达式中,查询效率
包过滤防火墙是一种通过软件检查数据包以实现系统安全防护的基本手段,以下叙述中,不正确的是()。
在进行软件设计时,以下结构设计原则中,不正确的是()。
在如下所示的进程资源图中,()。
在支持多线程的操作系统中,假设进程P创建了若干个线程,那么__________是不能被这些线程共享的。
下面的协议中属于应用层协议的是(26),该协议的报文封装在(27)中传送。(26)
对于一般的树结构,可以采用孩子.兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子一兄弟表示如下图所示。以下关于结点D与E的关系的叙述中,正确的是_____。
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(26)
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
随机试题
小儿病危重,其食指可显现为
烧伤患者,高热灼手,汗多气粗,口渴头痛烦躁不安,舌红绛苔黄,脉洪数。其证型是
关于犯罪形态,下列哪种说法是正确的?
设函数f(x)在(-∞,+∞)上是偶函数,且在(0,+∞)内有f’(x)>0,f’’(x)>0,则在(-∞,0)内必有()。
如果当前的证券价格不仅反映了历史价格信息和所有公开的价格信息,该市场属于()。
对于长文档,使用键盘快速移动光标至文件首的操作是()。
Whatrhetoricdeviceisusedinthesentence"Manyhandsmakelightwork"?
材料 近日,特拉维夫大学宣布该学校实验室3D打印出了一颗“心脏”,该心脏不仅具有外形,还有细胞、血管和其他支撑结构,甚至可以像心脏一样收缩,但长度只有2.5厘米。该实验团队负责人说:“与过去相比,这项研究成果的突破点在于,这不仅是一个外观打印的心脏,而
某班级53名学生的物理成绩平均分为83分,标准差为7分,测验的信度为0.51。若小叶考试成绩为81分,那么在0.05的显著水平上,其真分数应该介于什么范围?()
RocketRenaissanceTheEarofPrivateSpaceflightIsAbouttoStartBackgroundTwoyearsago,peoplewitnessedthefirstspa
最新回复
(
0
)