试题内容
试题四
阅读下列说明,回答问题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 <r){
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) 。(是或否)
软题库参考答案:暂时没有答案(仅供参考)
软题库解析:正在加载....
你可能感兴趣的试题
试题四
阅读以下说明和C程序,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,
但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任务。
程序中,N个任务从0开始依次编号,N个工人也从0开始依次编号,主要的变量说明如下:
c[i][j]:将任务i分配给工人j的费用;
task[i]:值为0表示任务i未分配,值为j表示任务i分配给工人j;
worker[k]:值为0表示工人k未分配任务,值为1表示工人k已分配任务;
mincost:最小总费用。
【C程序】
#include<stdio.h>
#define N 8 /*N表示任务数和工人数*/
int c[N][N];
unsigned int mincost=65535; &n
试题六(共15分)
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某发票(lnvoice)由抬头(Head)部分、正文部分和脚注(Foot)部分构成。现采用装饰(Decorator)模式实现打印发票的功能,得到如图6-1所示的类图。
【java代码】
class invoice{
public void printInvoice(){:
System.out.println("This is the content of the invoice!");
}
}
class Decorator:extends Invoice{
protected Invoice ticket;
public Decorator(
试题三
阅读下列说明和图,回答问题1至问题4,将解答填入对应栏内。
【说明】
在线会议审稿系统(Online Reviewing System,ORS)主要处理会议前期的投稿和审稿事务,其功能描述如下:
1.用户在初始使用系统时,必须在系统中注册(register)成为作者或审稿人。
2.作者登录(login)后提交稿件和浏览稿件审阅结果。提交稿件必须在规定提交时间范围内,其过程为先输入标题和摘要、选择稿件所属主题类型、选择稿件所在位置 (存储位置)。上述几步若未完成,则重复;若完成,则上传稿件至数据库中,系统发送通知。
3.审稿人登录后可设置兴趣领域、审阅稿件给出意见以及罗列录用和(或)拒绝的稿件。
4.会议委员会主席是一个特殊审稿人,可以浏览提交的稿件、给审稿人分配稿件、罗列录用和(或)拒绝的稿件以及关闭审稿过程。其中,关闭审稿过程须包括罗列录用和(或)拒绝的稿件。
系统采用面向对象方法开发,使用UMi进行建模。在建模用例图时,常用的方式是先识别参与者,然后确定参与者如何使用系统来确定用例,每个