为帮助广大软考中级软件设计师考生更好备考,信管网特整理汇总了软件设计师部分下午真题、答案及解析供考生查阅,并提供免费在线模拟答题、历年真题免费下载等服务,了解软件设计师更多备考信息请关注信管网。
相关推荐:
免费练习:软件设计师考试题库(模拟试题、章节练习、每日一练)
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。
【说明】
快速排序是一种典型的分治算法。采用快速排序对数组a[p..r]排序的3个步骤如下。
1.分解:选择一个枢轴(pivot)元素划分数组。将数组a[p..r]划分为两个子数组 (可能为空)a[p..q-1]和a[q+1..r],使得a[q]大于等于a[p..q-1)中的每个元素,小于 a[q+1..r]中的每个元素。q的值在划分过程中计算。
2.递归求解:通过递归的调用快速排序,对子数组a[p..q-1]和a[q+1..r]分别排序。
3.合并:快速排序在原地排序,故不需合并操作。
【问题1】
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。
a:待排序数组
p,r: 数组元素下标,从p到r
q: 划分的位置
x:枢轴元素
i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值
j:循环控制变量,表示数组元素下标
quicksort (a,p,r){
if (p
q=partition(a,p,r) ;
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
partition(a,p,r){
x=a[r];i=p-1;
for(j=p;j≤r-1;j++){
if (a[j]≤x){
i=i+1;
交换a[i]和a[j]
}
}
交 (1) 和 (2) //注:空(1)和空(2)答案可互换,但两空全部答对方可得分 return (3)
}
【问题2】
(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用o记号。最佳情况为 (4) ,平均情况为 (5) ,最坏情况为 (6) 。
(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳,平均、最坏)
【问题3】
(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作,请填充其中的空缺处。其中,random(i,j)表示随机取i到j之间的一个数,包括i和j。
randomized- partition(a,p,r){
i=random(p,rl);
交换 (8) 和 (9) ;//注:空(8)和空(9)答案可互换,但两空全部答对方可得分
return partition (a,p,r);
}
(2)随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)
信管网参考答案:
(1)A[i+1]
(2)A[r]
注:空(1)和空(2)答案可以互换,但两空全部答对方可给分。
(3)i+1
(4)O(nlgn)或O(nlg2n)或O(nlbn)
(5)O(nlgn)或O(nlg2n)或O(nlbn)
(6)O(n2)
(7)最坏
(8)A[i]
(9)A[r]
注:空(8)和空(9)答案可以互换,但两空全部答对方可给分。
(10)否
温馨提示:因考试政策、内容不断变化与调整,信管网网站提供的以上信息仅供参考,如有异议,请以权威部门公布的内容为准!
信管网致力于为广大信管从业人员、爱好者、大学生提供专业、高质量的课程和服务,解决其考试证书、技能提升和就业的需求。
信管网软考课程由信管网依托10年专业软考教研倾力打造,官方教材参编作者和资深讲师坐镇,通过深研历年考试出题规律与考试大纲,深挖核心知识与高频考点,为学员考试保驾护航。面授、直播&录播,多种班型灵活学习,满足不同学员考证需求,降低课程学习难度,使学习效果事半功倍。
发表评论 查看完整评论 | |