首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
71
问题
阅读下列说明和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代码,函数的时间复杂度和空间复杂度分别为(5)和(6)(用O符号表示)。
选项
答案
(5)[*]或者[*] (6)[*]或者[*]
解析
根据上述C代码,第3到第5行代码的for循环所花时间为
。第6到第8行的for循环所花时间为
。第9到第11行的for循环所花时间为
。第12到第15行for循环所花时间为
。因此整个算法的时间复杂度为
。若R远小于n或者
时,时间复杂度可以表示为
。
转载请注明原文地址:https://kaotiyun.com/show/KlDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在一个完整的功能测试过程中,______不属于应该编写的测试文档。A.测试需求文档B.测试用例文档C.测试标准D.问题报告单
程序质量评审通常是从开发者的角度进行评审,其内容不包括____________。
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现他们之间的同步过程如下图所示。其中,信号量S是一个互斥信号量,初值为(1);S1是一个(2);S2是一
(33)不属于功能测试用例构成元素。
测试成本控制的目标是使测试开发成本、测试实施成本和测试维护成本最小化,以下理解正确的是______。A.测试准备成本属于测试实施成本B.可以通过加强软件测试的配置管理来降低测试维护成本C.测试设计成本控制的目标是尽可能地减少测试总执行时间和所需的测试
某应用系统采用防火墙技术来实现安全防护,在进行安全防护测试时,设计的测试点不包括______。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
下列协议中与Email应用无关的是()。
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
用边界值分析法,假定X为整数,10≤X≤100,那么X在测试中应该取(40)边界值。
随机试题
Almosteveryonehasahobby.Ahobbycanbe【C1】______peopleliketodointheirsparetime.Ahobbycan【C2】______themwithinter
下列颈部血管损伤时,不可结扎的血管是
关于糖皮激素抗炎作用特点的描述,不正确的是()。
A.血管紧张素转化酶B.β肾上腺素受体C.羟甲戊二酰辅酶A还原酶D.钙离子通道E.钾离子通道氨氯地平的作用靶点是
现阶段在地籍测量中我国主要采用()土地分类系统。
[2014年,第68题]图5.7-4所示梁的横截面可选用空心矩形、矩形、正方形和圆形4种之一,假设四种截面的面积相等,载荷作用方向铅垂向下,承载能力最大的是()。
关于建设程序说法不正确的是()。
根据《刑法》的规定,下列关于徇私舞弊发售发票、抵扣税款、出口退税罪的说法中正确的是()。
某社区有12个积极分子A~L,他们之间的联系渠道见下图。居委会至少需要通知他们之中(67)________________个人,才能通过联系渠道通知到所有积极分子。
Manydaysseemtobring【B1】______tasksandresponsibilities,allofwhichapparentlymustbetackledrightaway.Youspendaday
最新回复
(
0
)