首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m
admin
2014-11-13
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
voidsort(intn,inta[],intb[]){
intc[R],i;
for(i=0;i<(1);i++){
c
=0;
}
for(i=0;i
c[a
]=(2);
}
for(i=0;i
c
=(3);
}
for(i=0;i
b[c[a
]一1]=(4);
c[a
]=c[a
]一1;
}
}
根据C代码,函数的时间复杂度和空间复杂度分别为(5)和(6)(用O符号表示)。
选项
答案
(5)O(n+R)或者O(n)或n或线性(6)O(R)或者O(1)
解析
算法中只有单层循环,因此算法的时间复杂度为O(n+R)。算法中需要用到一个长度为R的辅助数组c,因此算法的空间复杂度为O(R)。
转载请注明原文地址:https://kaotiyun.com/show/OZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥以下关于摘要
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持根据上述inittab文件的内容,系统在引导过程结束前,至少还要执行______进程。A.rc.sy
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持root用户执行psaux|grepinit命令,得到init的PID是______。A.0
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持在系统控制台,______用Ctrl+Alt+Delete组合键来重新引导服务器。A.允许B
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持Linux系统运行级别3工作在______状态。A.单用户字符模式B.多用户字符模式
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
阅读以下说明,回答问题1至问题4。【说明】某学校计划建立校园网,拓扑结构如图12-1所示。该校园网分为核心、汇聚和接入三层,由交换模块、广域网接入模块、远程访问模块和服务器群四大部分构成。
请在(1)、(2)、(3)、(4)空白处填写恰当的内容。Web客户机与服务器共同遵守(1)协议,其工作过程是;Web客户端程序根据输入的(2)连接到相应的Web服务器上,并获得指定的Web文档。动态网页以(3)程序的形式在服务器端处理,并给客户端返
随机试题
对志愿者督导的工作态度的正确理解是()。
可引起全身感染的呼吸道病毒是
A.胸骨左缘第3~4肋间Ⅲ一Ⅳ级粗糙的收缩期杂音B.胸骨左缘第2~3肋间Ⅱ~Ⅲ级喷射性收缩期杂音C.胸骨左缘第2肋问粗糙响亮的连续性机器样杂音D.胸骨左缘第2—4肋间Ⅱ一Ⅲ级喷射性收缩期杂音E.胸骨左缘第2肋间Ⅱ~V级喷射性收缩期杂音房间隔缺损
库存控制落实到库存管理上就是()。
企业方针目标管理包括方针目标的_________四个环节。
王某在本市西区开了一家酒楼,2000年12月市工商局和公安局在联合执法中发现该酒楼正在加工数只国家二类保护动物,遂以该酒楼非法收购、加工国家级保护动物为由,以共同名义对其给予10000元的罚款,该酒楼不服。作为该酒楼法人代表的王某欲申请行政复议,可以依
解释性新闻的写作要求。(复旦大学,2009年)
设计一个通话计费程序,假设每分钟通话费用为0.20元,初始时,开始时间、结束时间、通话分钟和应付金额都为空。单击“开始”按钮,显示开始时间:单击“计费”按钮,显示结束时间、通话分钟和应付金额(每分钟0.20元,不满1分钟按1分钟计费)。表单样式如图3-7
Inmanycountries,authorityisseldomquestioned,eitherbecauseitishighlyrespected,orbecauseitis【B1】______.Sometimes,
A、Beforetheendofthemonth.B、Atthebeginningoftheyear.C、Nextmonth.D、Anytime.A
最新回复
(
0
)