首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
19
问题
阅读下列说明和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代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
选项
答案
不稳定。修改第12行的for循环为for(i=n-1; i>=0; i--)即可。
解析
从图(k)可以看出,算法不稳定。算法不稳定的原因在于将数组a中元素放到数组b中时,是从数组a的第一个元素开始,依次取出元素放到数组b中。这样,相同的两个元素值,在数组a中的相对位置和在数组b中的相对位置正好相反。若从数组a的最后一个元素开始,依次向前取元素放到b数组中,可以保持相同元素的相对位置。因此将第12行的代码for(i=0; i<n; i++)改为for(i=n-1; i>0; i--),则排序算法是稳定的。
转载请注明原文地址:https://kaotiyun.com/show/OlDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在开发一个字处理软件时,首先快速发布了一个提供基本文件管理、编辑和文档生成功能的版本,接着发布提供更完善的编辑和文档生成功能的版本,最后发布提供拼写和语法检查功能的版本,这里采用了()过程模型。
为了能按时交付系统,开发小组在实现“确定最优任务分配方案”功能时采用了蛮力的方法。在系统交付后,对可能出现更多任务量的情况,采用更有效的方法来实现该功能,这属于()。
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现他们之间的同步过程如下图所示。其中,信号量S是一个互斥信号量,初值为(1);S1是一个(2);S2是一
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现他们之间的同步过程如下图所示。其中,信号量S是一个互斥信号量,初值为(1);S1是一个(2);S2是一
假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机,那么信号量S的取值范围为()。
甲、乙软件公司于2013年9月12日就其财务软件产品分别申请“大堂”和“大唐”商标注册。两财务软件相似,且经协商双方均不同意放弃使用其申请注册的商标标识。此情形下,()获准注册。
计算机采用分级存储体系的主要目的是为了解决()的问题。
下列协议中与Email应用无关的是()。
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
随机试题
汽车消费信贷考虑5C,即品质、能力、资本、抵押品、条件。()
"Happinessconsistsinthemultiplicityofagreeableconsciousness,"wroteSamuelJohnson,afamousBritishwriterandlexicogr
A.疝囊高位结扎术B.疝修补术C.两者均需D.两者均不需(2000年)一岁以内婴儿腹股沟斜疝的治疗
()是微生物广泛分布的第二个天然环境。
消防控制设备对消火栓应有哪些控制及显示功能?
下列属于具有法律效力的原始凭证是()。
为了留住人才,让员工有归属感,分享企业长期发展的成果,解决他们的后顾之忧,某大型企业的人力资源经理王总打算制订企业年金计划,就此事向理财规划师进行咨询。企业举办企业年金时,通常需要寻找企业年金受托人来管理企业年金基金,法人受托机构要满足一定的条件,其中
普通寿险是需要终身缴纳保费的终身寿险。下列关于普通寿险说法正确的是()。
古埃及的学校教育除了宫廷学校、僧侣学校和职官学校以外,还有
Nearlyallsurgicalstuntsstickthemselveswithneedlesand【C1】______instrumentswhileintraining.But【C2】______failtorepo
最新回复
(
0
)