首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
阅读下列说明和c代码,回答问题1至问题3,将解答写在对应栏内。 [说明] 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的
admin
2012-03-21
64
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
软件内部/外部质量模型中,以下(66)不是功能性包括的子特性。
设数组a[1..n,1..m](n>1,m>1)中的元素以行为主序存放,每个元素占用1个存储单元,则数组元素a[i,j](1≤i≤n,1≤j≤m)相对于数组空间首地址的偏移量为()。
测试成本控制的目标是使测试开发成本、测试实施成本和测试维护成本最小化,以下理解正确的是______。A.测试准备成本属于测试实施成本B.可以通过加强软件测试的配置管理来降低测试维护成本C.测试设计成本控制的目标是尽可能地减少测试总执行时间和所需的测试
某应用系统采用防火墙技术来实现安全防护,在进行安全防护测试时,设计的测试点不包括______。
软件可移植性应从如下(46)方面进行测试。
计算机系统中,虚拟存储体系由______两级存储器构成。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
正确的集成测试描述包括(43)。①集成测试也叫做组装测试,通常是在单元测试的基础上,将模块按照设计说明书要求进行组装和测试的过程②自顶向下的增殖方式是集成测试的一种组装方式,它能较早地验证主要的控制和判断点,对于输入输出模块、复杂算法模
静态图像压缩标准JPEG2000中使用的是(60)算法。
随机试题
A、Four.B、Five.C、Six.D、Seven.B
关于急性心包炎的临床表现,以下的哪一项不正确
腮腺最常见的恶性肿瘤是
慢性胃炎胃酸分泌过少时应建议选择哪类食物
某商业综合楼共21层,建筑高度84m,每层建筑面积1800m2,设置有两座防烟楼梯间,其中靠近东侧的防烟楼梯间设置了一部消防电梯,合用前室面积为8.4m2。建筑物采用机械加压送风系统,仅在楼梯间设置了机械加压送风口,楼梯间每隔三层至五层设有一个常闭式百叶送
关于ETF,以下表述错误的是()。[2016年9月真题]
××省人民政府通报因为在实践中遇到有关政府信息查询的困难,经过集体讨论,《××政府信息公开试行办法》于20××年×月×日第3次常务会议通过。现予公布。
我国在与世界各国和地区发展对外经济关系、扩大对外贸易、吸收和利用外资、发展对外技术交流时,必须坚持的一个共同原则是()。
Whenbirdscametothegarden,themonkeychasedthemaway.Theverb"chased"means__________.Themonkeypickedupalargesto
Bythe1820sintheUnitedStates,whensteamboatswerecommononwesternwaters,theseboatsweremostlypoweredbyenginesbui
最新回复
(
0
)