专业软件设计师网站|培训机构|服务商(加客服微信:cnitpm或QQ:800184589进软件设计师学霸群)

软题库 培训课程
当前位置:信管网 >> 软件设计师 >> 案例分析 >> 文章内容
软件设计师《案例分析》真题及答案22
来源:信管网 2021年09月23日 【所有评论 分享到微信

软件设计师下午考试科目为案例分析,考试题型为主观题,4道必答题,2道(5、6题)选答题,考试时长2个半小时,共75分。为帮助广大软考中级软件设计师考生更好备考,信管网特整理汇总了软件设计师部分真题、答案及解析供考生查阅,并提供免费在线模拟答题、历年真题免费下载等服务,了解软件设计师更多备考信息请关注信管网。

相关推荐:

点击查看/下载:软件设计师历年真题汇总

点击查看:软件设计师在线培训课程 丨 免费试听课程

免费练习:软件设计师考试题库(模拟试题、章节练习、每日一练)

阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。

【说明】

采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排好序的子数组得到排序结果。

下面的C代码是对上述归并算法的实现,其中的常量和变量说明如下:

arr:待排序数组

p,q,r:一个子数组的位置从p到q,另一个子数组的位置从q+1到r

begin,end:待排序数组的起止位置

left,right:临时存放待合并的两个子数组

n1,n2:两个子数组的长度

i,j,k:循环变量

mid:临时变量

【C代码】

#inciude

#inciude

#define MAX 65536

void merge(int arr[],int p,int q,int r) {

int *left, *right;

int n1,n2,i,j,k;

n1=q-p+1;

n2=r-q;

if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) {

perror("malloc error");

exit(1);

}

if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) {

perror("malloc error");

exit(1);

}

for(i=0;i left[i]=arr[p+i];

}

left[i]=MAX;

for(i=0; i right[i]=arr[q+i+1]

}

right[i]=MAX;

i=0; j=0;

for(k=p; (1) ; k++) {

if(left[i]> right[j]) {

(2) ;

j++;

}else {

arr[k]=left[i];

i++;

}

}

}

void mergeSort(int arr[],int begin,int end){

int mid;

if( (3) ){

mid=(begin+end)/2;

mergeSort(arr,begin,mid);

(4) ;

merge(arr,begin,mid,end);

}

}

【问题1】

根据以上说明和C代码,填充1-4。

【问题2】

根据题干说明和以上C代码,算法采用了(5)算法设计策略。

分析时间复杂度时,列出其递归式位(6),解出渐进时间复杂度为(7)(用O符号表示)。空间复杂度为(8)(用O符号表示)。

【问题3】

两个长度分别为n1和n2的已经排好序的子数组进行归并,根据上述C代码,则元素之间比较次数为(9)。

信管网参考答案:

【问题1】

(1)k<=r

(2)arr[k]=right[j]

(3)begin

(4)mergesort(arr,mid+1,end)

【问题2】

(5)分治

(6)T(n)=2T(n/2)+n

(7)O(nlgn)

(8)O(n)

【问题3】

(9)n1+n2

查看解析:www.cnitpm.com/st/3814226162.html

扫码关注公众号

温馨提示:因考试政策、内容不断变化与调整,信管网网站提供的以上信息仅供参考,如有异议,请以权威部门公布的内容为准!

信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务,解决其考试证书、技能提升和就业的需求。

信管网软考课程由信管网依托10年专业软考教研倾力打造,官方教材参编作者和资深讲师坐镇,通过深研历年考试出题规律与考试大纲,深挖核心知识与高频考点,为学员考试保驾护航。面授、直播&录播,多种班型灵活学习,满足不同学员考证需求,降低课程学习难度,使学习效果事半功倍。

相关内容

发表评论  查看完整评论  

推荐文章