首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、流程图和算法进行填空。 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A[i],
阅读下列说明、流程图和算法进行填空。 下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A[i],
admin
2010-02-13
47
问题
阅读下列说明、流程图和算法进行填空。
下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是:以数组中的第一个元素作为基准数,将小于基准数的元素向低下标端移动,而大于基准数的元素向高下标端移动。当划分结束时,基准数定位于A
,并且数组中下标小于i的元素的值均小于基准数,下标大于i的元素的值均大于基准数。设数组A的下界为low,上界为high,数组中的元素互不相同。例如,对数组(4,2,8,3,6),以4为基准数的划分过程如图8-34所示。
算法说明:将上述划分的思想进一步用于被划分出的数组的两部分,就可以对整个数组实现递增排序。设函数int p(int A[],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
解析
本题的快速排序思想是:首先,以待排序序列的第1个元素为基准,将序列中所有小于基准元素的元素排到基准元素的一边,将序列中所有大于基准元素的元素排到基准的另一边。具体放在哪一边,要根据排序的升降而定。这样,就以基准元素为界,将原序列划分成了两个部分,然后再分别对这两个部分递归进行快速排序,直到无法再划分为止。这样,整个序列就被排序了。
题目中已经给出了快速排序的划分算法,我们要做的就是将划分算法的流程图和
快速排序的递归函数补充完整。
先看来流程图,pivot←A[low]就是将数组A的第1个元素赋给pivot,作为基准元素。然后,分别将数组的下界和上界赋给i和j(i←low;j←high),我们可以将 i和j理解为分别指向数组首和尾的两个指针。注意,其中的i指向的位置是基准元素所在位置。接下来是一个循环,循环条件为i<j。
在循环体中,首先从后往前寻找比基准元素小的元素,这是通过一个子循环来完成的。循环条件i<j&&A[j]>pivot的意思是,如果j所指的元素比基准元素大,并且j还在i的后面的话,我们应该把j往前移动1位,所以第1空应该填j--或其他等价形式。如果找到比基准元素小的元素或者j已经移动到i的位置了,则循环结束。下面的语句A
←A[j]刚就是将找到的元素移动到i所指位置。注意,现在可以将j所指位置看作是基准元素的位置,但是可以暂时不用把基准元素赋给A[j]。接下来的子循环跟前面的很类似,循环条件是i<j&&A
<pivot,如果i所指元素小于基准元素,且i并没有超过j,那么就应该将i往前移动1位,所以第2空应该填i++或其他等价的形式。直到i>=j(i和j已经重合,所有元素都遍历完了),或者A
>=pivot(在基准元素位置j的左边找到比基准元素大的元素了),则该子循环结束。然后执行A[j]←A
,将找到的元素跟基准元素交换位置,不过基准元素可以暂时不用赋给A
,因为它还要跟其他元素交换位置。
如果子循环不是因为i>=j结束的,那么外循环就会继续。直到所有大于基准元素的元素都被排到基准元素后面,小于基准元素的元素都被排到基准元素前面。外循环结束时,i和j一定是重合的,现在可以把基准元素写入它们所指的位置中去了。所以,第3空可以填A
←pivot或A[j]←pivot。
现在来看快速排序的递归函数sort(),在函数中首先判断下界L是否小于上界H,这一点很重要,因为它是递归函数回溯的条件。如果L<H,则表示需排序的元素个数不为0。在if子句中,首先调用前面分析过的划分算法p()函数,将数组A的 L~H范围进行一次划分,然后递归调用了两次sort()。很显然,这两次应该分别对划分出的前半部分和后半部分分别排序。所以,第(4)、(5)空应该分别填A,L, k-1和A,k+1,H,或者把它们的位置交换也可以。
转载请注明原文地址:https://kaotiyun.com/show/TpjZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
由EIA组织制订的RS—232—C标准,是常见的一种接口标准。该标准的设计数据速率为(22)b/s。
在计算机局域网协议集中,数据链路层又可分为介质访问控制子层和(43); LAN参考模型中服务访问点SAP的作用是(44);局域网中数据传输的误码率较低,一般约在(45);在LAN的介质访问方式中,争用属于(46);以太网的介质访问控制方式与CSMA相比较,
在关系数据库的关系模型中,采用(21)表达实体集以及实体集之间的联系。关系数据库的3种完整性约束中,(22)规定基本关系的主属性不能取空值。
现采用4级流水线结构分别完成一条指令的取指、指令译码和取数、运算以及送回运算结果4个基本操作,每步的操作时间依次为60ns、100ns、50ns和70ns。该流水线的操作周期应为(50)ns。若有一小段程序需要用20条基本指令完成(这些指令完全适合于在流水
软件工程标准的类型是多方面的。它可能包括(61)(如方法、技术和度量等)、(62)(如需求、设计、部件、描述、计划和报告等)、(63)(如职别、道德准则、认证、特许和课程等)以及(64)(如术语、表示法和语言等)。
软件工程标准的类型是多方面的。它可能包括(61)(如方法、技术和度量等)、(62)(如需求、设计、部件、描述、计划和报告等)、(63)(如职别、道德准则、认证、特许和课程等)以及(64)(如术语、表示法和语言等)。
电子邮件客户端应用程序向邮件服务器发送邮件时使用(40)协议。下面关于 FTP叙述错误的是(41)。因特网上最重要、最基本的服务是(42)。下面描述的不是Internet提供的服务的选项是(43)。
若进程P1正在运行,操作系统强行撤下P1进程所占用的CPU,让具有更高优先级的进程P2运行,这种调度方式称为(7),此时P1进程处于(8)状态。(9)将CPU的时间分成若干个时间片轮流地为各个用户服务。
计算机中声音、图形、图像信息都是以文件的形式存储的,它们的文件格式有许多种,可以通过扩展名来识别,常见的文件扩展名有:①BMP ②AIF ③JPG ④WAV ⑤GIF ⑥VOC其中,表示声音文件的有(9),表示图形、
若Web站点是基于IIS建设,而且Web站点内容位于NTFS分区时,有4种方法可以限制用户的访问权限。下列不是限制用户的访问权限的方法是(59)。
随机试题
恩格斯说:“对自然界的一切真实的认识,都是对永恒的东西、对无限的东西的认识,因而本质上是绝对的。”这表明()
局麻药物中作用时间最长的是
外科内治法的具体治法错误的是
含有木脂素的中药有
背景资料:某高速公路第五施工合同段地处城郊,主要工程为路基填筑施工。其中K48+010~K48+328段原为路基土方填筑,因当地经济发展和交通规划需要,经各方协商,决定将该段路基填筑变更为(5×20+3×36+5×20m)预应力钢筋混凝土箱梁桥,
资产按照现在购买相同或者相似资产所需支付的现金或者现金等价物的金额计量的会计计量属性是( )。
一容器内有浓度为30%的糖水,若再加入30千克水与6千克糖,则糖水的浓度变为25%。问原来糖水中含糖多少千克?
我们绝大多数人既不是有大笔财产可继承的“富二代”,也不是中得千万大奖的幸运儿,所以还是要咬紧牙关,去承担属于自己的那份责任,毕竟我们有父母需要赡养,有柴米油盐需要开支。但我们并非没有希望,我们希望通过今天的努力,能够得到职位的升迁,能够获得更丰厚的收入,然
Asinternationalcommercegrows,thereisanamazingdevelopmentwhichisexpandingatever-increasingrate—businessontheInte
情景:你是李明,你明天要外出度假,希望你的朋友Mike能够照看你的宠物猫,可是他不在家。任务:请用英语给Mike留一张50词左右的便条,告诉他:每天用鱼和牛奶喂猫3次;每隔一天给猫洗一次温水澡;外出时一定要关好门
最新回复
(
0
)