阅读下列说明和C代码,回答问题1至问题3【说明】??? 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-l、m-2、…个位置。例如,如果元素值小于等于4的元素个数有10个,其中元素值等于4的元素个数有3个,则4应该在输出元素序列的第10个位置、第9个位置和第8个位置上。算法具体的步骤为:步骤1:统计每个元素值的个数。步骤2:统计小于等于每个元素值的个数。步骤3:将输入元素序列中的每个元素放入有序的输出元素序列。【C代码】下面是该排序算法的C语言实现。(1)常量和变量说明R: 常量,定义元素取值范围中的取值个数,如上述应用中R值应取6i:循环变量n:待排序元素个数a:输入数组,长度为nb:输出数组,长度为nc:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数sort1??? void sort(int n,int a[],int b[]){2??? ???int c[R],i;3?? for (i=0;i4?? ??c[i]=0;5??? ???}6??? ???for(i=0;i7??? ?c[a[i]] = ??(2)? ;8??? ???}9 ??for(i=1;i10??? c[i]= ?(3)11??? ??}12 ?for(i=0;i13??? b[c[a[i]]-1]=? (4)?? ;14??? c[a[i]]=c[a[i]]-1;15??? ??}16??? }【问题1】? 根据说明和C代码,填充C代码中的空缺(1)~(4)。【问题2】根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用O符号表示)。【问题3】?? 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
阅读下列说明和C代码,回答问题1至问题3
【说明】
??? 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-l、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 7??? ?c[a[i]] = ??(2)? ;
8??? ???}
9 ??for(i=1;i 10??? c[i]= ?(3)
11??? ??}
12 ?for(i=0;i 13??? b[c[a[i]]-1]=? (4)?? ;
14??? c[a[i]]=c[a[i]]-1;
15??? ??}
16??? }
【问题1】
? 根据说明和C代码,填充C代码中的空缺(1)~(4)。
【问题2】
根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用O符号表示)。
【问题3】?
? 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
【说明】
??? 某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-l、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
8??? ???}
9 ??for(i=1;i
11??? ??}
12 ?for(i=0;i
14??? c[a[i]]=c[a[i]]-1;
15??? ??}
16??? }
【问题1】
? 根据说明和C代码,填充C代码中的空缺(1)~(4)。
【问题2】
根据C代码,函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用O符号表示)。
【问题3】?
? 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
参考解析
解析:试题答案 【问题1】
(1)R
(2)c[a[i]]+1
(3)c[i]+c[i -1]
(4)a[i]
【问题2】
(5)O(n+R)或者O(n)或n或线性
(6)O(n+R)或者O(n)或n或线性
【问题3】
不稳定。修改第12行的for循环为:for(i=n-1;i>=0;i--){ 即可。
(1)R
(2)c[a[i]]+1
(3)c[i]+c[i -1]
(4)a[i]
【问题2】
(5)O(n+R)或者O(n)或n或线性
(6)O(n+R)或者O(n)或n或线性
【问题3】
不稳定。修改第12行的for循环为:for(i=n-1;i>=0;i--){ 即可。
相关考题:
阅读下列说明,回答问题1至问题4,将解答填入对应栏内。【说明】提高操作系统的安全性是保障计算机和网络安全的重要内容之一,回答与Windows Server 2008安全管理相关的问题。刚刚安装完成的Windows Server 2008存在安全漏洞,应该如何解决?
阅读下列说明,回答问题1至问题2,将解答填入对应栏内。【说明】利用Windows Server 2008架设邮件服务器,回答相应问题。邮件服务器通常提供POP3和SMTP两种服务,它们各有什么作用?
阅读下列说明,回答问题1至问题5,将解答填入对应栏内。【说明】建立企业的Internet时,经常遇到的问题是:IP地址的申请、网络安全、网站的建立和维护,请就这些问题进行回答。当我们申请不到很多合法IP时,如何分配IP使得单位对外开放的服务器和内部的 PC终端能够上网?
先阅读以下说明,然后回答问题1至问题3。[说明]表12-1是IP地址与子网掩码关系对应表,子网掩码为255.255.240.0。表12-1 IP地址及其相应的子网掩码请把表12-1中和(1)~(5)填写完整。
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。【说明】在Windows的网络配置中,对网络协议进行IP地址配置,出现图5-1所示的对话框。什么场合下,可选择自动获取IP?什么场合下,选择人工配置IP?
阅读以下说明和Java代码,回答问题1和问题2,将解答填写在对应栏内。【Java代码】class usethread implements (1) {int numusethread(int n){num=n;}public void (2) {for(int i=0;i<3;i++)System.out.println("running:"+num);System.out.println("finished:"+num);}public class multhread{public static void main(String args[]) (3) InterruptedException{Thread m1=new Thread(new usethread(1));Thread m2=new Thread(new usethread(2));m1.start();m2.start();m1.join();m2.join();}}【问题1】补充完整上面Java代码中(n)处。【问题2】写出上面Java代码运行的结果。
阅读下列说明,回答问题1至问题3。【说明】文档测试应当贯穿于软件生命周期的全过程,其中用户文档是文档测试的重点。用户文档包括哪些?除了用户文档之外,文档测试还应当关注哪些文档?简述用户文档的测试要点。请帮忙给出每个问题的正确答案和分析,谢谢!
阅读以下关于软件测试的说明,回答司题l至问题3,将解答填入答题纸的对应栏内。【说明】使用在汽车、飞机中的嵌入式软件, 日于直接影响人的生命及财产安全,测试要求更为严格。语句覆盖、判定覆盖、条件覆盖和MC/DC覆盖是通常对这类软件的要求。以下是一段C语言代码,请仔细阅读并回答相关问题:【问题1】(6分)请根据测试要求,简要说明语句覆盖、判定覆盖、条件覆盖和MC/DC覆盖的含义。将答案填写在答题纸的对应栏中。【问题2】(5分)画出以上代码的流程图,将答案填写在答题纸的对应栏中。【问题3】(4分)请根据【说明】中的C语言代码,计算满足MC/DC覆盖要求的用例数量及条件取值范围,将答案填写在答题纸的对应栏中.
阅读下列说明,回答问题1 至问题3,将解答填入答题纸的对应栏内。【说明】某城市双创平台成立后,拟建设中小企业服务管理信息系统,主要工作计划如下。【问题1】(4分)结合案例,请问活动A和活动C的历时分别是多少。【问题2】(8分)请补充完整该管理信息系统的双代号网络图。【问题3】(4分)请给出关键路径和项目总工期
阅读以下说明,回答问题1至问题2,将解答填入答题纸对应的解答栏内。【说明】某留言系统采用ASP+Access开发,其后台管理登录页面如图4-1所示。【问题1】(9分)以下是该后台管理登录页面login.asp的部分代码,请仔细阅读该段代码,根据图4-1 将(1)~(9)的空缺代码补齐。【问题2】(6分)1.在登录页面 login.asp 中通过导入了bbb.asp的代码,以下是bbb.asp的部分代码,请仔细阅读该段代码,将空缺代码补齐。
阅读下面程序,回答问题1至问题3。【问题1】(3分)上述代码能否输出“This is a test”?上述代码存在什么类型的隐患?【问题2】(4分)造成上述隐患的原因是?【问题3】(3分)给出消除该安全隐患的思路。
阅读下列程序,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】逻辑覆盖法是设计白盒测试用例的主要方法之一,它是通过对程序逻辑结构的遍历实现程序的覆盖。针对以下由C 语言编写的程序,按要求回答问题。main( ){int i,n; //1for(i=1;i
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】????在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连,称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤iπ(j)。【问题1】(6分)根据以上说明和C代码,填充C代码中的空(1)~(3)。【问题2】(6分) ???????据题干说明和以上C代码,算法采用了??(4) ?算法设计策略。??????函数maxNum和constructSet的时间复杂度分别为??(5) ??和???(6) ?(用O表示)。?【问题3】(3分) ???????若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为???(7) ??,包含的连线为??(8) ??(用(i,π(i))的形式给出)。
问答题阅读下列说明,回答问题1至问题3【说明】某公司要开发一个多媒体辅导系统,该系统准备利用B/S架构,用户通过网上注册、登录,登录成功后,可进行在线学习辅导。目前常用的系统架构有B/S架构和C/S架构,请说明这两个架构的含义和原理。