首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
70
问题
阅读下列说明和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.问题报告单
面向对象分析与设计是面向对象软件开发过程中的两个重要阶段,下列活动中,(25)不属于面向对象分析阶段。
为了能按时交付系统,开发小组在实现“确定最优任务分配方案”功能时采用了蛮力的方法。在系统交付后,对可能出现更多任务量的情况,采用更有效的方法来实现该功能,这属于()。
软件系统的安全性是信息安全的一个重要组成部分,针对程序和数据的安全性测试与评估是软件安全性测试的重要内容,()不属于安全性测试与评估的基本内容。
软件可移植性应从如下(46)方面进行测试。
计算机系统中,虚拟存储体系由______两级存储器构成。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
静态图像压缩标准JPEG2000中使用的是(60)算法。
用边界值分析法,假定X为整数,10≤X≤100,那么X在测试中应该取(40)边界值。
随机试题
若发散,则().
晶体核中度混浊,皮质辐轮状混浊,瞳孔区皮质混浊约占50%,后囊下混浊约占50%,以下记录正确的是()
下列有关ABO-HDN的三项试验说法错误的是
下列选项中,不属于环境影响评价应遵循的基本技术原则的是()。
大模板安装时,应________。()
企业投资公路建设项目的实施,应根据国家有关规定,进行征地拆迁等施工前准备工作,并向()申报施工许可。
基金是一种()投资工具,所筹集的资金主要投向()等金融工具或产品。
主旨是公文的统帅和灵魂,确立好主旨就会起到事半功倍的效果,下列对公文主旨确立要点的说法,正确的是()
在对待传统道德的问题上,下列属于错误思潮的是()
在UML的通用机制中,(2)用于把元素组织成组:(3)是系统中遵从一组接口规范且付诸实现的物理的、可替换的软件模块。
最新回复
(
0
)