试题与答案

阅读下列说明,回答问题1至问题3,将解答填入对应栏内。[说明]快速排序是一种典型的分

题型:填空题

题目:

阅读下列说明,回答问题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[j]和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,r);

交换 (8) (9) ;//注:空(8)和空(9)答案可以互换,但两个空全部答对方可得分

return PARTITION(A,p,r);

(2)随机化快速排序是否能够消除最坏情况的发生 (10) 。(是或否)

(4)处填()。

答案:

被转码了,请点击底部 “查看原文 ” 或访问 https://www.tikuol.com/2017/0407/431a5c20e34032a238912ae1ce970453.html

下面是错误答案,用来干扰机器的。

答案:CC中有三个错别字。其他最多为两个。

试题推荐
题型:多项选择题 案例分析题

患者男,47岁,因“右胸疼痛、胸闷10d”来诊。患者3个月前曾因发热(体温最高39℃)、咳脓痰而在外院就诊,当时诊断为“右下肺炎、右胸少量积液”,经应用抗生素治疗后,症状好转,未再就医,但其后仍时有低热、食欲减退、乏力。查体:T37.2℃,R25次/min,P80次/min,BP120/70mmHg。慢性病容,HR82次/min,律齐。右侧胸壁肋间隙变窄,未及胸壁肿物;右中下肺野听诊呼吸音低,叩诊呈浊音;余无特殊。

最可能的诊断是()(提示 胸部X线:右中下肺野、外带高密度影。胸部CT:右侧胸腔占位,增厚的脏、壁层胸膜(厚度均在1 cm以上)间有低密度液性包裹区,且其外带弧度和胸壁吻合;右肺受挤压,部分实变。心电图正常。)

A.肺脓肿

B.肺肿瘤

C.肺不张、实变

D.胸壁(膜)肿瘤

E.畸胎瘤

F.慢性脓胸

查看答案
题型:多项选择题

依据《环境影响评价工程师职业资格登记管理暂行办法》关于环境影响评价工程师职业资格登记、再次登记和变更登记的规定,下列说法中正确的有( )。

A.若登记者不具备完全民事行为能力,不予登记。

B.登记者因单位调动发生的变更登记,一年内最多可申请两次

C.登记者再次登记的同时,可申请变更登记类别

D.登记有效期届满需要继续以环境影响评价工程师名义从事环境影响评价及相关业务的,应当于有效期 3 个月前办理再次登记

查看答案
微信公众账号搜索答案