首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
58
问题
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。
[说明]
某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-1、m-2、…个位置。例如,如果元素值小于等于4的元素个数有10个,其中元素值等于4的元素个数有3个,则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。
算法具体的步骤为:
步骤1:统计每个元素值的个数。
步骤2:统计小于等于每个元素值的个数。
步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。
[C代码]
下面是该排序算法的C语言实现。
(1)常量和变量说明
R:常量,定义元素取值范围中的取值个数,如上述应用中R值应取6。
i:循环变量。
n:待排序元素个数。
a:输入数组,长度为n。
b:输出数组,长度为n。
c:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。
(2)函数sort
1 void sort(int n, int a[], int b[]) {
2 int c[R], i;
3 for(i=0; i< (1) ; i++) {
4 c
=0;
5 }
6 for(i=0; i<n; i++) {
7 c[a
]= (2) ;
8 }
9 for(i=1; i<R; i++) {
10 c
= (3) ;
11 }
12 for(i=0; i<n; i++) {
13 b[c[a
]-1]= (4) ;
14 c[a
]=c[a
]-1;
15 }
16 }
根据说明和C代码,填充C代码中的空缺(1)~(4)。
选项
答案
(1)R (2)c[a[i]]+1 (3)c[i]+c[i-1] (4)a[i]
解析
本题考查算法设计与分析技术以及算法的C语言实现,是比较传统的题目,要求考生细心分析题目中所描述的内容。
根据题中说明,第3到第5行代码进行c数组的初始化,c数组的长度为R,在C语言中,下标从0开始,因此空格(1)中填写R。第6到第8行检查a数组的每一个元素。如果元素的值为i,则增加c
的值。因此c[a
]=c[a
]+1,空格(2)填写c[a
]+1。完成第6行到第8行的代码后,c
中就存放了等于i的元素的个数。第9到第11行,通过在数组c中记录计数和,c
=c[i-1]+c
,可以确定对每一个i=0,1,…,R-1,有多少个元素是小于或等于i的。因此空格(3)填写c[i-1]+c
。第12行到第15行把数组a中每个元素a
放在输出数组b中与其相应的最终位置上,b[c[a
]-1]=a
,因此空格(4)填写a
。由于可能存在相同元素,因此每次将一个值a
放入数组b中时,都要减小c
的值。下面以一个例子来说明排序过程。
设a={4,1,3,4,3,4},R=5,即待排序的元素值在{0,1,2,3,4}中,其排序过程如下图所示。
图中(a)为输入数组a,(b)为初始化后的c数组,(c)为统计数组a中每个元素后的c数组,(d)为计数和,即统计小于等于i的元素个数后的c数组。(e)到(j)是将a数组中的元素依次放到b数组的过程,(k)是数组a和数组b的元素对应关系。
转载请注明原文地址:https://kaotiyun.com/show/7lDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的版本,接着发布提供更完善的编辑和文档生成功能的版本,最后发布提供拼写和语法检查功能的版本,这里采用了()过程模型。
软件内部/外部质量模型中,以下(66)不是功能性包括的子特性。
面向对象分析与设计是面向对象软件开发过程中的两个重要阶段,下列活动中,(25)不属于面向对象分析阶段。
程序质量评审通常是从开发者的角度进行评审,其内容不包括____________。
设数组a[1..n,1..m](n>1,m>1)中的元素以行为主序存放,每个元素占用1个存储单元,则数组元素a[i,j](1≤i≤n,1≤j≤m)相对于数组空间首地址的偏移量为()。
测试成本控制的目标是使测试开发成本、测试实施成本和测试维护成本最小化,以下理解正确的是______。A.测试准备成本属于测试实施成本B.可以通过加强软件测试的配置管理来降低测试维护成本C.测试设计成本控制的目标是尽可能地减少测试总执行时间和所需的测试
某应用系统采用防火墙技术来实现安全防护,在进行安全防护测试时,设计的测试点不包括______。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
正确的集成测试描述包括(43)。①集成测试也叫做组装测试,通常是在单元测试的基础上,将模块按照设计说明书要求进行组装和测试的过程②自顶向下的增殖方式是集成测试的一种组装方式,它能较早地验证主要的控制和判断点,对于输入输出模块、复杂算法模
随机试题
公务员离职学习超过一年的,立受到的人事处理是
在质量改进工作的诊断过程中,可以运用一些系统的方法提出推测,其中效果较好的方法是()
战略
A.极化B.去极化C.复极化D.超级化电位产生过程中,若只有K+外流则引起
男性,40岁,反复出现胸骨后烧灼样疼痛,多在餐后1小时出现,卧位时症状加重。其最可能的诊断是
损伤性血胸病人胸腔内积血不凝同的原因是
某施工项目业主在招标文件中规定承包商拖期违约赔偿按5000元/天计算,投标单位在投标文件中提出拖期违约赔偿按4000元/天计算。经过开标、评标、定标后,业主发出了中标通知书,双方在签订合同时日拖期违约赔偿应为()元/天。
在国民收入核算体系中,计入GDP的政府支出是指()。
小林私拿水果摊上的一只苹果,经同学揭发,被老师叫到了办公室。老师问道:“小林,你私拿别人的东西,这已经是第几次了?”小林低着头回答:“第五次了”。“你为什么不改呢?”“我……我也晓得不对,就是……就是有时忍不住。”这时,教师应从()入手对小
根据我国选举法规定,人民代表大会的选举经费来源于()。(2011法单11)
最新回复
(
0
)