选择题:某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出

题目内容:

某应用中需要对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[i]=0;

5}

6?for(i=0;i<n;i++){

7 c[a[i]]=(2);

8}

9?for(i=1;i<R;i++){

10 c[i]=(3)

11}

12 for(i=0;i<n;i++){

13?b[c[a[i]]-1]=(4);

14?c[a[i]]=c[a[i]]-1;

15}

16}

【问题1】(8分)

根据说明和C代码,填充C代码中的空缺(1)~(4)。

【问题2】(4分)

根据C代码,函数的时间复杂度和空间复杂度分别为(5)和(6)(用O符号表示)。

【问题3】(3分)

根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。

答案解析:

在某市的政府采购中,系统集成公司甲中标了市政府部门乙的信息化项目。经过合同谈判,双方签订了建设合同,合同总金额为1150万元,建设内容包括:搭建政府办公网络平台

在某市的政府采购中,系统集成公司甲中标了市政府部门乙的信息化项目。经过合同谈判,双方签订了建设合同,合同总金额为1150万元,建设内容包括:搭建政府办公网络平台,-改造中心机房,并采购所需的软硬件设备

查看答案

某企业网络拓扑结构如图3-1所示。根据企业要求实现负载均衡和冗余备份,构建无阻塞高性能网络的建设原则。该企业网络采用两台S7606万兆骨干路由交换机作为双核心,

某企业网络拓扑结构如图3-1所示。根据企业要求实现负载均衡和冗余备份,构建无阻塞高性能网络的建设原则。该企业网络采用两台S7606万兆骨干路由交换机作为双核心,部门交换机S2924G通过光纤分别与两台

查看答案

应用MPLS VPN时,针对每个VPN地址规划应满足的条件是(  )。不同的VPN信息通过MPLS骨干网(或核心网)时通过(  )进行区分。问题1选项 A.每个

应用MPLS VPN时,针对每个VPN地址规划应满足的条件是(  )。不同的VPN信息通过MPLS骨干网(或核心网)时通过(  )进行区分。问题1选项 A.每个VPN都是独立的,可以使用任何地址,只要

查看答案

某地机场年度旅客吞吐量近800多万人,在航站楼进口处原设有20个值机柜台负责接待旅客,办理登机卡,托运行李。随着出港旅客流量的日益增长,为了提高服务质量,尽可能

某地机场年度旅客吞吐量近800多万人,在航站楼进口处原设有20个值机柜台负责接待旅客,办理登机卡,托运行李。随着出港旅客流量的日益增长,为了提高服务质量,尽可能地减少旅客的等待时间,机场旅客服务中心从

查看答案

试题二:论信息系统项目的合同管理项目合同管理是通过对项目合同的全生命周期进行管理,以回避和减轻可识别的项目风险。请以“论信息系统项目的合同管理”为题进行论述:1

试题二:论信息系统项目的合同管理项目合同管理是通过对项目合同的全生命周期进行管理,以回避和减轻可识别的项目风险。请以“论信息系统项目的合同管理”为题进行论述:1.概要叙述你参与管理过的信息系统项目(项

查看答案