首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 下面的程序利用快速排序中划分的思想在整数序列中找出第k小的元素(即将元素从小到大排序后,取第k个元素)。 对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数作为基
admin
2017-11-28
29
问题
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。
【说明】
下面的程序利用快速排序中划分的思想在整数序列中找出第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
程序员下午应用技术考试
软考初级
相关试题推荐
评价信息系统时需要听取各有关方面的意见。在听取系统操作人员的意见时,主要讨论信息系统的______。
下列操作中______可以随意改变窗口大小。
计算机使用了一段时间后,系统磁盘空间不足,系统启动时间变长,系统响应延迟,应用程序运行缓慢,此时,需要对系统进行优化。(28)________________不属于系统优化工作。
张、王、李三个平等的评委独立对三部电影甲、乙、丙进行了评分(三人的满分标准不同),结果如下表:按合理的平均得分计算,第一、二、三名电影应分别授予(69)。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
对同一事物进行多次测量所得的结果可能不一致,这是幽测量误差所致。利用______可使误差基本抵消。
180的正约数(能整除180的自然数,包括l和180本身)的个数是________。
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。说明某公司内部有一个采用TCP/IP作为传输协议的100BASE-TX局域网,包括1台服务器和20台客户机,通过一台16端口的交换机与一台8端口共享集线器级连,其网络结构如图11所
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。制作交叉双绞线(一端按EIA/TIA568A线序,另一端按EIA/TIA568B线序)时,其中一端的线序如图1-2(a)所示,另一端线序如图1—2
从表1-1中为图1-1中(1)~(4)处选择合适设备名称(每个设备限选一次)。表1-2是路由器A上的地址变换表,将图1-2中(8)~(11)处空缺的信息填写在相应的位置。
随机试题
在UNIX系统中,用户程序经过编译之后得到的可执行文件属于()。
以下各药中,不具有清肝明日作用的是
在我国最好发的口腔颌面部恶性肿瘤是
脐带异常的常见类型有()
女性,40岁,原有垂体瘤病史,突然出现严重头痛,视力急剧减退,眼外肌麻痹,昏迷,脑膜刺激征阳性,颅内压增高,应考虑的诊断为
枢纽工程专项验收由()负责。
基金进行利润分配后的剩余额为()。
甲公司为一家制衣公司,2022年计划销售增长率为25%,该增长率超出公司正常的增长水平较多,为了预测融资需求,安排超常增长所需资金,财务经理请你协助安排有关的财务分析工作,该项分析需要依据管理用财务报表进行,相关资料如下:资料一:
下列关于拐卖妇女、儿童罪的说法中,错误的一项是()。
石油峰值论认为,石油产量会达到最高点,之后不可避免地开始下降。石油峰值几乎是确定的事,但仍然存在两个问题:它究竟何时出现?世界是否能够及时研发出替代能源?__________的观察家并不相信石油峰值会在2020年前出现,但一些石油公司承认他们此前夸大了地下
最新回复
(
0
)