问题 单项选择题

我国矿山行业的平均生产效率和安全状况与世界发达的采矿国家相比仍有着巨大的差距。2003年我国煤矿矿工有400余万人(含不完全统计的小煤矿矿工),我国煤矿百万吨死亡率为4.17人,与美国相比,是他们的140倍。其中国有重点煤矿1.08人,国有地方煤矿3.13人,乡镇小煤矿9.62人。2003年我国煤矿事故死亡人数近7000人,是美国煤矿死亡人数的 233倍。

2003年美国生产的原煤共计多少亿吨()

A.10.07

B.7.20

C.5.63

D.3.76

答案

参考答案:A

解析:

2003年美国煤矿死亡人数为7000÷233≈30(人),美国煤矿百万吨死亡率为0.02979。故美国原煤共计30÷0.02979≈1007(百万吨),即10.07亿吨。故选项A正确。

填空题

阅读下列说明,回答问题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) 。(是或否)

(3)处填()。

单项选择题