首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
27
问题
阅读下列说明和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://jikaoti.com/ti/M3i7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的版本,接着发布提供更完善的编辑和文档生成功能的版本,最后发布提供拼写和语法检查功能的版本,这里采用了()过程模型。
一个Web信息系统所需要进行的测试包括____________。①功能测试②性能测试③可用性测试④客户端兼容性测试⑤安全性测试
程序质量评审通常是从开发者的角度进行评审,其内容不包括____________。
甲、乙软件公司于2013年9月12日就其财务软件产品分别申请“大堂”和“大唐”商标注册。两财务软件相似,且经协商双方均不同意放弃使用其申请注册的商标标识。此情形下,()获准注册。
软件可移植性应从如下(46)方面进行测试。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
“<titlestyle="italic">science</title>”是XML中一个元素的定义,其中元素的内容是(29)。
随机试题
Shoppingforclothesisnotthesameexperienceforamanasitisforawoman.Amangoesshopping(11)______heneedssometh
宫内生长迟缓儿易发生围生期窒息,且多留有神经系统后遗症。()
下列不属于必须经股份有限公司出席股东大会三分之二以上表决权股东通过的事项是()。
开发区区域环境影响评价重点包括()。
2011年9月10日,天明公司的财务科长持有关证件到A银行营业部办理基本存款账户开立手续,A银行工作人员审查了其开户的证明文件,并留存了相关证件的复印件,并为其办理了开户手续。同日该财务科长持以上证件和与B银行签订的贷款合同到B银行开立了一个一般存款账户。
城市用地布置,建筑物的结构、朝向、间距和排列方式,以及道路走向、市政工程设施状况等都与气候条件密切相关。其中与规划相关性大的气候要素有()等儿方面。
某公司注册资本100万元,有人要投资100万元人民币,占2%的股份,公司投后估值为()。
设A,B及A*都是n(n≥3)阶非零矩阵,且AB=O,则r(B)=().
A、VATistheacronymofValueAddedTax.B、VATisataxchargedonmostgoodsinBritain.C、VATisnotchargedondifferentserv
Duringaverageyear,about50peoplediefromcarbonmonoxidepoisoningin【M1】______theUK,causeddirectlybyfumesfromhome
最新回复
(
0
)