首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
admin
2017-11-28
80
问题
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。
对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基准值,然后根据基准值进行划分,从而将待排序的序列划分为不大于基准值者(称为左子序列)和大于基准值者(称为右子序列);然后再对左子序列和右子序列分别进行快速排序,最终得到非递减的有序序列。
例如,整数序列“19,12,30,11,7,53,78,25”的第3小元素为12。整数序列“19,12,7,30,11,11,7,53,78,25,7”的第3小元素为7。
函数partition(int a[],int low,int high)以a[low]的值为基准,对a[low],a[low+1],…a[high]进行划分,最后将该基准值放入a
(low≤i≤high),并使得a[low],a[low+1],…a[i—1]都小于或等于a
,而a[i+1],a[i+2],…a[high]都大于a
。
函数findkthElem(int a[],int startldx,int endldx,int k)在a[startldx],a[startldx+1]…,a[endIdx]中找出第k小的元素。
【代码】
#include
#include
int partition(int a[],int low,int high)
{//对a[low..high]进行划分,使得a[low..i]中的元素都不大于a[i+1..high]中的元素。
int pivot=a[low]; //pivot表示基准元素
int i=low,j=high;
while( (1) ){
while(i
pivot)一一j;
a
=a[j];
while(i
<=pivot)++i;
a[j]=a
;
}
(2); //基准元素定位
return i;
}
int findkthElem(int a[],int startIdx,int endIdx,int k)
{//整数序列存储在a[startIdx..endIdx]中,查找并返回第k小的元素。
if(startIdx<0 ‖endIdx<0 ‖startIdx>endIdx ‖ k<1‖ k—l>endIdx ‖
k一1
return一1; //参数错误
if(startIdx
int loc=partition(a,startIdx,endIdx);
//进行划分,确定基准元素的位置
if(loc==k一1) //找到第k小的元素
return (3) ;
if(k一1
return findkthElem(a, (4),k);
else //继续在基准元素之后查找
return findkthElem(a,(5),k);
}
return a[startIdx],
}
int main()
{
int i,k;
int n;
int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 7 8, 25, 7};
n=sizeof(a)/sizeof(int); //计算序列中的元素个数
for(k=1; k
for(i=0; i
printf(“%d\t”,a
);
}
printf(“\n”);
printf(“elem%d=%d\n”, k, findkthElem(a,0,n一1,k));
//输出序列中第k小的元素
}
return 0;
}
选项
答案
(1)i
解析
本题考查C程序中数组、函数参数和排序算法的应用。
根据题目说明中提供的信息,利用快速排序查找给定序列中第k小的元素。
首先分析程序的逻辑结构、每个函数的作用和主要变量的含义及作用,然后再具体分析每个函数的运算逻辑。
函数partition(int a[],int low,int high)对保存在数组a中的元素序列进行划分,也就是指定第一个元素为基准,通过逐个扫描序列中的元素,将大于基准的其他元素移动到序列的后半区,将不大于基准的其他元素移动到序列的前半区,在这个过程中,对于本来就在后半区且大于基准的元素则保持不动,同理,对于本来就在前半区且小于或等于基准的元素保持其原来所在位置。
根据函数中已给出的语句,先从序列的后端开始向前扫描,遇到一个小于或等于基准的元素为止,语句如下:
while ( i
piVot ) 一一j;
然后通过“a
=a[j]”将不大于基准的元素a[j]往前移了。
之后从序列的前端开始向后扫描,遇到一个大于基准的元素为止,语句如下:
while ( i
<=pivot ) ++i;
然后通过“aD]:a
”将大于基准的元素a
往后移了。
显然易见,重复上面的过程直到基准元素的位置被确定下来,也就是“i=j”为止,因此空(1)处应填入“i
=pivot”或“a[j]=pivot”或其等效方式。
函数findkthElem(int a[],int startldx,int endldx,int k)的功能是在数组a[startldx..endldx]中查找并返回第k小的元素。该函数中,通过调用pattition不断地对序列进行划分,直到找到所需元素。调用语句如下:
loc=partition(a,startIdx,endIdx);//进行划分,确定基准元素的位置由于C语言中数组下标从0开始,即第一个元素的下标为0,元素在数组中的下标与元素的序号正好相差1。对于第一次调用,当得到基准元素的位置为loc,也就是说基准元素前面有loc个元素,而基准元素在序列中为第loc+1个元素,因此,此时若loc==k一1,则基准元素正好就是第k小的元素,即空(3)处填入“a[loc]”或其等效表示。若非如此,则k-1
由于是将所要找的元素的序号与其在数组中的下标直接绑定,也就是需要找出正好在下标为k一1位置上的元素,保证下标为0~k-2的元素都不大于a[k-1]即可。因此,若下一步需到前半区继续查找,则要找的元素仍然为第k个,因此空(4)处所在的完整语句为“return findkthElem(a,startldx,loc一1,k);”若下一步需到后半区继续查找,则要找的元素仍然为第k个,因此空(5)处所在的完整语句为“return findkthElem(a,loc+1,endldx,k);”程序中在递归调用的语句中保留了第1个参数和第4个参数,而将表示基准元素之前的前半区和之后的后半区参数留给考生解答,客观上降低了理解的难度,因此考生应重点把握程序的整体逻辑结构。
转载请注明原文地址:https://kaotiyun.com/show/49jZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在Word2010“查找和替换”文本框中,输入()符号可以搜索0到9的数字。
在用Word软件编辑文档时,若误删除了一个数据,随后可使用______命令进行恢复。
______不属于企业信息系统存在的问题。
某个字段的数据是原始数据计算的结果,该字段的宽度和小数位数对数据的精度有影响。一般来说,小数位数的确定需要考虑______。
在大型分布式信息系统中,为提高信息处理效率,减少网络拥堵,信息存储的原则是:数据应尽量(66)________________。
在Excel的A1单元格中输入函数“=IF(12,1,2)”,按回车键后,A1单元格中的值为()。
在域名地址www.rkb.gov.cn中,“cn”属于______。
自然数1,2,3,4,5中,任意两个数都可以算出平均值,其中有些平均值是相同的。那么,不同的平均值共有______个。
桌面上有各种图标,图标在桌面上的位置()。
由若干条直线段和圆弧等构成的图形,可以用一系列指令来描述。用这种方法描述的图形称为_________。
随机试题
药性寒凉而涩,能解毒敛疮的止血药为
根据上述表现,应辨证为:首选方剂是:
女性,55岁,2年前诊断系统性红斑狼疮,一直服用强的松治疗。近1个月来,高热,咳嗽、咳痰伴有呼吸困难,胸片示双肺粟粒性阴影,大小密度分布均匀
胎儿窘迫时,下列哪项措施恰当
[2004年第106题]在下述关于电缆敷设的叙述中,哪个是错误的?
【背景资料】承担某公路工程项目施工任务的某施工单位根据有关文件和资料对该公路工程质量控制设置了关键点,该工程技术总负责人负责对技术文件、报告、报表进行了审核和分析,在具体施工中遇到以下情况:(1)由于第三方的原因,该工程被迫停工,停工时项目经理组织有关
不同种类的灭火器,适用于不同物质的火灾,其结构和使用方法也各不相同。下列关于灭火器配置场所火灾种类和危险等级的说法中,正确的有()
甲公司希望新上马的某信息系统具有较强的容错能力和恢复能力,系统运行结果对管理活动能够起到较强的支持作用。根据以上信息可以判断,甲公司主要关注的是()。
受“重陆轻海”的传统观念影响,在较长时期内,我国国民的海洋国土意识淡薄。上世纪90年代末,共青团中央对上海大学生进行的抽样调查结果显示.90%以上的大学生竟然认为我国的版图只有陆域国土。2006年的一项报道披露.即使在经济和教育发达的北京和上海,一些大学生
某单位的办公室秘书小马接到领导的指示,要求其提供一份最新的中国互联网络发展状况统计情况。小马从网上下载了一份未经整理的原稿,按下列要求帮助他对该文档进行排版操作并按指定的文件名进行保存。按下列要求进行页面设置:纸张大小A4,对称页边距,上、下边距各2.
最新回复
(
0
)