首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
admin
2017-11-28
112
问题
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第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
程序员下午应用技术考试
软考初级
相关试题推荐
在大型分布式信息系统中,为提高信息处理效率,减少网络拥堵,信息存储的原则是:数据应尽量(66)________________。
操作系统的功能不包括______。
某信息处理技术员正在做大批数据处理的大项目时,领导又交宋了另一项临时性的紧迫工作,要求优先处理。该信息处理技术员需要转而做新的工作,他对原工作的处理方式应该是(69)。
在Word的编辑状态下,先后新建了两个文档,但并没有对这两个文档做“保存”或“另存为”操作,则______。
某企业的大数据工程项目包括如下四个阶段的工作:①数据获取,②数据清洗与整理,③数据分析,④数据展现。一般来说,工作量较大、花费时间较长的阶段是______(1),技术含量最高的阶段是______(2),准备向有关部门递交成果的阶段是______(3)。
对同一事物进行多次测量所得的结果可能不一致,这是幽测量误差所致。利用______可使误差基本抵消。
采购了多种品牌的部件进行计算机组装,每个部件都正常,连接、安装、配置操作也完全正确,但系统仍不能正常使用。很可能是____________问题。
现在,企业数字化转型已是大势所趋。以下关于企业数字化转型的叙述中,不正确的是_________。
此配置允许DHCP服务器分配给客户的地址范围是什么?#/sbin/chkconfig-level3dhcpdon命令的作用是什么?
随机试题
一项法律上有效的承诺必须具备的构成要件。
远期票据
在投资项目前期决策阶段中,项目可行性研究总结评价的内容分析应包括()。
某公司是一家生产电子产品的大型国有控股公司。2004年2月,由于产品销售不畅,公司面临亏损,公司董事长责成财会部经理胡某对会计报表做技术处理,实现当年盈利目标,并承诺如果做得好,将推荐他作为公司总会计师人选,胡某知道本年度公司亏损已成定局,如要落实董事长的
某投资者上一交易日结算准备金余额为157475元,上一交易日交易保证金为11605元,当日交易保证金为18390元,当日平仓盈亏为8500元,当日持仓盈亏为7500元,手续费等其他费用为600元,当日该投资者又在其保证金账户中存入资金50000元,该投资者
持仓量增加,价格下跌,表示新卖方在大量建仓空头,近期价格()。
青花瓷是先在瓷器上用钴料描绘纹饰,上透明釉经过()以上高温还原烧成。
根据艾里克森的心理社会发展理论,小学儿童的主要发展任务是()。
已知某信道的带宽为3kHz,而且其信噪比为1000(30dB),则信道极限数据传输率为【 】。
A、Shemissedthedeadlineforthecourseregistration.B、Shecouldn’tdecidewhichcoursetoregister.C、Shedidn’tgettheexte
最新回复
(
0
)